C语言编译器设计与实现毕业论文设计(7)

&& x!=dollar) { item_node* p_item = new item_node; p_item->possible_prefix = prefix; p_item->cfg_no = cfg_no; p_item->dot_pos = dot_pos+1; //加点位置后移1位 j.push_back(*p_item); delete p_item; } }

return get_closure(j); //求得新项目集并返回 }

4) 求整个文法的项目集簇。项目集的个数即为有穷状态自动机的状态个数，根据以上

57个产生式，本编译器产生的状态为171个。 项目集族具体的生成：

size_t Grammar::make_items() {

init_item();

vector item_tmp; item_node* tmp = new item_node; const int dollar = get_int(\ tmp->possible_prefix = dollar; tmp->cfg_no = 0; tmp->dot_pos = 0;

item_tmp.push_back(*tmp);

time_t time_s = time(NULL); //cerr << \

closure_item.push_back(get_closure(item_tmp)); //计算初始项目集I0 static size_t count = 0;

for (size_t i=0; i set_temp; for (size_t j=0; j goto_tmp; int prefix = closure_item[i][j].possible_prefix; size_t cfg_no = closure_item[i][j].cfg_no; size_t dot_pos = closure_item[i][j].dot_pos; int str_nxdot = cfg[cfg_no].right_int[dot_pos]; if (str_nxdot!=dollar && set_temp.find(str_nxdot)==set_temp.end())

24

{ //1.移进 set_temp.insert(str_nxdot); goto_tmp = get_goto(i, str_nxdot); } else { //2. 规约R(j) begin- if (cfg_no!=0 && dot_pos==cfg[cfg_no].right.size()-1) { if (action_goto[i][prefix]==ERROR) { action_goto[i][prefix] = -(int)cfg_no; //填规约时分析表 } else { cout << \ } } //3. 接受Accept--- if (cfg_no==0 && prefix==dollar && dot_pos==cfg[cfg_no].right.size()-1) { if (action_goto[i][dollar]==Token::ERROR) action_goto[i][dollar] = Token::ACC; else { cerr << \ } } //end--- continue; } if (goto_tmp.size()>0) //移进动作，填分析表 { ... } //end if } //end for } //end for delete tmp;

return closure_item.size(); }

25

5) 生成LR(1)分析表，由于分析表的庞大，故将之生成后存于文件中。即

action_goto_table.txt

6) 完成LR分析器，读入第5步的分析表即可进行语法分析。

LR（1）分析器分析方法：

LR（1）分析方法的基本思想是从左至右扫描程序，进行自底向上的语法分析， 且在分析的每一步既要记住当前移进和规约的全部文法符号，又要向前看1个输入符号，由此确定栈顶的符号串是否构成相对某一产生式的句柄，从而确定当前缩影采取的分析动作（移进或规约）。

一个自底向上的分析器也是一台下推自动机，该下推自动机具有一个给定的输入符号串、一个下推分析栈和一个有穷的控制结构。其逻辑结构如下图所示：

# … ai ai+1 … #

总控程序

Sn … S1 S0 xn X1 X0 图4-2 LR（1）分析具体步骤

一个LR（1）分析器由三部分组成：

1． 一个有待分析的输入符号串（c源程序）。

2． 一个控制结构，其中包括一个总控程序和一张分析表。对于不同的文法，分析表各不相同，而总控程序都是一样的（保存在action_goto_table.txt中）。 3． 一个先进后出的下推分析栈，其中包括文法符号栈和相应状态栈。（Lr:: analyse()函数中定义stackstk;）。 4． LR（1）分析器的工作过程就是在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的文法符号和状态及当前的输入符号，按分析表的指示完成相应的分析动作。（Lr:: analyse()函数的功能）。

以上的每一个步骤都用程序完整实现。

4.3 语义分析阶段

4.3.1 概述

简单地说，语义分析就是分析语法结构含义，表示成中间语言或生成目标指令。语

26

义分析部分以语法分析部分的输出作为输入，输出则是中间代码甚至目标代码。

语义分析是一个用于计算编译过程中所需的附加语义信息的阶段。由于它包括了计算上下文无关文法和标准语法分析算法以外的信息（即语义信息），因此，它不能被视为语法。语义信息的计算与被翻译程序的最终含义或语义密切相关，因为编译器完成的语义分析是静态定义（在程序执行之前予以明确的），所以语义分析也可称作静态语义分析。在一个典型的静态类型的语言（如C语言）中，语义分析的工作通常包括构造符号表、记录声明中建立的名字的含义、在表达式和语句中进行类型推断和类型检查、在程序的不同作用域范围内判断变量的合法性。

语义分析可以分为两类[12]： （1） 第一类分析是正确性分析，要求根据编程语言的语义规则判定程序的正确性，并保证它能正确执行。对于不同的语言来说，语义分析的差异很大。比如在LISP和Smalltalk这类动态制导的语言中，可能完全没有静态语义分析；而在Ada或C这类语言中就有很强的静态语义分析需求，程序必须提交执行。其他的语言介于这两种极端情况之间（例如Pascal语言，不像Ada和C对静态语义分析的要求那样严格，也不像LISP那样完全没有要求）。

（2） 第二类分析是优化性分析，是由编译程序执行的用于提高翻译程序执行效率的分析。这一类分析通常包括对“最优化”或代码改进技术的实现。 4.3.2 C语言的语义

C语言在静态语义方面的要求比较简单，分析是由程序Lr类负责的。

在C中的类型检查也比较简单。它只有两种类型：整型和布尔型。仅有的布尔型值是两个整数值进行比较的结果。因为没有布尔型运算符或变量，所以布尔值只出现在if或while语句的条件测试表达式中，不作为运算符的操作数或赋值给变量的值。 4.3.3 C的符号表

在C语义分析程序的符号表的设计中，首先要确定哪些信息需要在符号表中保存。一般情况下，符号表需要包括数据类型和作用域信息，但考虑到本实验C语言本身没有作用域信息，因此C符号表也就不需要保存这些信息了。

需要保存一个记录表来记录每一个变量的在内存中的位置（符号表），每一个符号的结点定义如下：

struct idenfierNode { int type; int addr; }; //类型 //地址 图4-3 符号表表示形式

map idTable; //存放符号表 利用map中key的唯一性，存放符号表。

符号表的处理也伴随着语法分析来同时生成维护。

27

4.3.4 C语义分析程序的实现

将语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号，而属性的计算以语义规则(semantic rules)的形式赋予由文法符号组成的产生式；在语法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理。

语法制导定义中，需要对文法进行处理，加上一个只能产生终结符空(e)的非中介符号M,这一步已经在第3部分的文法给出来，以下是每一个产生式的语法指导定义。其中直接向上传递的信息直接封装在节点U_node中，包括存储四元式的code域等，在语法指导定义中则只给出向上传递的即为U_node域。

1 S0 -> translation_unit

{S0.nodeInfo = translation_unit.nodeInfo } 2 translation_unit -> external_declaration

{ translation_unit .nodeInfo=external_declaration.nodeInfo, //直接向上传递 translation_unit.nodeInfo.code = external_declation.nodeInfo.code || gen(“halt”)}

3 external_declaration -> function_definition

{external_declaration.nodeInfo = function_definition.nodeInfo}

4 external_declaration -> declaration

{external_declaration.nodeInfo=declaration.nodeInfo} 5 declaration -> type_specifier id ;

{declaration.nodeInfo.code= type_specifier.nodeInfo.code ; id.nodeInfo.addr=new Temp()}

6 type_specifier-> void

{type_specifier.nodeInfo.type=IS_VOID, type_specifier.nodeInfo.addr=void.nodeInfo.addr}

7 type_specifier -> int

{ type_specifier.nodeInfo.type=IS_INT, type_specifier.nodeInfo.addr=int.nodeInfo.addr}

8 type_specifier -> double

{type_specifier.nodeInfo.type=IS_DOUBLE,type_specifier .nodeInfo.addr= double.nodeInfo.addr}

9 function_definition -> type_specifier function_name parameter compound_statement

{function_defination.nodeInfo.code =type_specifier.nodeInfo.code ||function_name.nodeInfo.code||parameter.nodeInfo.code ||compound_statement.nodeInfo.code}

10 function_name -> id

{function_name.nodeInfo = id.nodeInfo, function_name.nodeInfo.addr=new Temp()}

11 parameter -> ( )

{parameter.nodeInfo.code=null}

12 compound_statement -> “{” decalration_list “ }”

{compound_statement .nodeInfo=declaration_list.nodeInfo}

13 compound_statement -> “{” statement_list “}”

{ compound_statement .nodeInfo=statement_list.nodeInfo}

14 compound_statement -> “{” decalration_list statement_list “}”

{compound_statement .nodeInfo.code=declration_list.nodeInfo.code||statement_list.nodeInfo.code}

15 decalration_list -> declaration

28

//直接向上传递