当前位置：文档之家› 编译原理语法分析实验报告

编译原理语法分析实验报告

编译原理实验报告

二、语法分析

(一) 实验题目

编写程序，实现对词法分析程序所提供的单词序列进行语法检查和

结构分析。

(二) 实验内容和要求

1. 要求程序至少能分析的语言的内容有:

1) 变量说明语句

2) 赋值语句

3) 条件转移语句

4) 表达式(算术表达式和逻辑表达式)

5) 循环语句

6) 过程调用语句

2. 此外要处理:包括依据文法对句子进行分析;出错处理;输出结果的构造。

3. 输入输出的格式:

输入:单词文件(词法分析的结果)

输出:语法成分列表或语法树(都用文件表示)，错误文件(对

于不合文法的句子)。

4. 实现方法:可以采用递归下降分析法，LL(1)分析法，算符优先法或LR分析法的任何一种，也可以针对不同的句子采用不同的分析方法。

(三) 实验分析与设计过程

1. 待分析的C语言子集的语法:

该语法为一个缩减了的C语言文法，估计是整个C语言所有文

法的60%(各种关键字的定义都和词法分析中的一样)，具体的

文法如下:

语法:

100: program -> declaration_list

101: declaration_list -> declaration_list declaration | declaration 102: declaration -> var_declaration|fun_declaration

105: fun_declaration -> type_specifier ID (params)|compound_stmt 106: params -> params_list|void

107: param_list ->param_list,param|param

108: param -> type-spectifier ID|type_specifier ID[]

109: compound_stmt -> {local_declarations statement_list}

110: local_declarations -> local_declarations var_declaration|empty 111: statement_list -> statement_list statement|empty

编译原理实验报告

112: statement -> epresion_stmt|compound_stmt

|selection_stmt|iteration_stmt|return_stmt

113: expression_stmt -> expression;|;

114: selection_stmt -> if{expression)statement

|if(expression)statement else statement

115: iteration_stmt -> while{expression)statement

116: return_stmt -> return;|return expression;

117: expression -> var = expression|simple-expression

118: var -> ID |ID[expression]

119: simple_expression ->

additive_expression relop additive_expression|additive_expression 120: relop -> <=|<|>|>=|= =|!=

121: additive_expression -> additive_expression addop term | term 122: addop -> + | -

123: term -> term mulop factor | factor

124: mulop -> *|/

125: factor -> (expression)|var|call|NUM

126: call -> ID(args)

127: args -> arg_list|empty

128: arg_list -> arg_list,expression|expression

该文法满足了实验的要求，而且多了很多的内容，相当于一

个小型的文法

说明:把文法标号从100到128是为了程序中便于找到原来的文法。

2. 实现方法的选择:

因为时间的问题，我选择了递归下降的方法进行开发。

3. 消除左递归

因为递归下降要求文法中不能出现有左递归的产生式，因

此必须把待分析的C语言子集的语法中带有左递归的都消除左

递归。其中产生式101、110、111、121、123、128均为左递归

文法。

这些产生式消除左递归后的文法如下:

1)101消除左递归后的产生式分别为:

101: declaration_list -> declaration declaration_list_zdg

135: declaration_list_zdg-> declaration declaration_list_zdg

|empty

2)110消除左递归后的产生式分别为:

110: local_declarations -> empty local_declarations_zdg

133: local_declarations_zdg->

var_declarationlocal_declarations_zdg

|empty

3)111消除左递归后的产生式分别为:

111: statement_list-> empty statement_list_zdg

编译原理实验报告

134: statement_list_zdg->statement statement_list_zdg|empty

4)121消除左递归后的产生式分别为:

121: additive_expression -> term additive_expression_zdg

131: additive_expression_zdg-> addop term additive_expression_zdg |empty

5)123消除左递归后的产生式分别为:

123: term -> factor term_zdg

132: term_zdg-> mulop factor term_zdg|empy

6)128消除左递归后的产生式分别为:

128:arg_list->expression arg_list_zdg

129:arg_list_zdg->,expression arg_list_zdg|empty

说明:empty代表可以为空。

4. 词法分析和语法分析的关系

由于语法分析要用到词法分析的结果，在词法分析中，我逐个得到单词，而语法分析的整个过程中都必须利用从词法分析中得到的每一个单词，因此从语法分析的入口点开始就必须利用token读取源C程序的第一个词，然后再语法分析的过程中，采取相关的措施，在匹配当前单词后继续利用token读取下一个单词。

5. 递归下降的思想

递归下降的思想在于“递归”二字，对于每一个消除了左递归的产生式，通过为每一个产生式建立一个函数，函数名为相应的产生式的左部，然后对产生式的每一项进行展开，如果产生式的右部碰到一个非终结符，则调用这个非终结符的函数(该非终结符肯定是一个产生式的左部，为之建立一个函数)，如果遇到的是一个非终结符，则调用match()方法(见下文)，match方法除了匹配当前的非终结符之外，还调用了词法分析的token方法，读取下一个单词。

这里举一个例子来说明:下面的产生式是一个关于变量定义的产生式:

var_declaration -> type_specifier ID; 来说，编写的函数名为

var_declaration的方法:简单的表达如下:

public void var_declaration(){

type_specifier();

ID();

match(SEMICOLON);// SEMICOLON表示分号

}

其他的产生式的函数编写都跟这个var_declaration函数类似。只是，但是还有的产生式有比这复杂的地方，在后面继续说明。

6. 结果输出形式和错误处理

1)结果的输出形式

当碰到一个单词，我首先输出这个单词的类型，因为用

编译原理实验报告

到的是递归函数，对于每个产生式，当展开到产生式的末尾

的时候，我就把反映该产生式的源代码(规约)都输出，当

最后到达产生是式program(即分析出了是一个程序)，便输出

整个程序，因此这种方法是一个反映了我语法分析过程的结

果输出。当遇到一个单词或者遇到了一个产生式的规约，便

输出结果，方法为:

public void syntaxPrint(String message, String blk, int n)

其中参数 message为:当当前的输出为当前单词时，message

为当前的词类型，当当前的输出为一个产生式的规约时，

message为当前用于规约的产生式。参数 blk是为了方便结果

输出的时候，在程序中间加上必要的空格。参数n表示当前

用于规约的产生式的项的个数，当知道个数后，便与把保存

在栈顶的n个元素连接起来并且输出。

2)错误处理

因为语法分析的时候，源程序有很多的不符合语法的地

方，因此就需要处理，更重要的是需要进行错误恢复，以便

语法分析输出当前的错误后继续正确地进行分析。这里我采

用了栈的形式来进行错误恢复(见数据结构设计与建立)

7. 数据结构(栈)

这里用到了栈，栈的运用在这里主要就是用于结果的输出和错误处理。

当分析一个产生式的时候，如果发现当前的字符匹配，则把当前的字符压入栈中，或者当前的不是一个字符，而是一个非终结符(一个函数)，则因为该函数也进行了相应的处理，当函数结束的时候把一个字符串压在栈中，因此直接调用这个函数的时候已经实现了压栈的动作，然后在输出该非终结符所表示的源程序的时候，把在该非终结符的函数中压入栈中的内容合并成一个字符串输出后再压回栈顶。实现了递归调用。

如果在该非终结符的函数展开过程中，出现的错误，也即当前的字符并不是产生式所需要的，那么便往栈中压入一个空字符，即做了错误恢复，从而继续进行分析。

个人感觉利用栈让我很好地解决了分析结果的输出和错误处理恢复。

8. 产生式函数的流程图

这个问题是我在语法分析中遇到的比较棘手的几个问题之一，主要分成以下的几种情况。

1)产生式的右部只有一种情况，如产生式102、126等

以126: call -> ID(args)

为例，说明我处理这种情况的处理方法:因为产生式有右

部的First集为ID(即标识符)，的程序流程图，见下面的

流程图(3)

编译原理实验报告

函数call ()

当前单词的类N错误处理型是否为ID

调用函数ID()往栈中压入空字符

当前单词类型YN是否为LB错误处理

(LB表示’(’)

match(LB)往栈中压入空字符

调用函数args()

当前单词类型N是否为RB错误处理

(RB表示’)’)

match(RB)往栈中压入空字符

函数call结束

流程图(3)

2) 产生式的右部有两个或者两个以上的规约产生式，但是右部的这两个或者两个以上的产生式的First集并不相同，如产生式112、113等，其中还有复杂一点的情况，因为有的产生式的右部的First有很多，或者是First集的寻找比较困难，需要找到很多的产生式，这个属于First集的寻找，在这里就不详细描述了。

我以产生式112

statement ->expression_stmt|compound_stmt|selection_stmt

|iteration_stmt|return_stmt

编译原理实验报告

为例来说明处理这种情况的产生式的方法，其中

iteration_stmt的First集为WHILE，selection_stmt的First集为if，return_stmt的First集为RETURN，compound_stmt 的First集为LH，expression_stmt|的First集为LB、SEMICOLON和ID，详细的流程图见下图流程图(4)

函数statement()

当前单词的类

N型是否为LH或 IF或 WHILE 错误处理或 RETURN或ID或LB或

SEMICOLON

往栈中压入空字符

当前单词的类NNN当前单词的类当前单词的类当前单词的类型是否为ID、LB 型是否为RETURN型是否为IF型是否为LH或SEMICOLON

调用函数调用函数调用函数调用函数

return_stmt()selection_stmt()compound_stmt()compound_stmt()

函数statement结束

流程图(4)

3)产生式的右部有两个或者两个以上的规约产生式，但

是右部的这两个或者两个以上的产生式的First集的第

一个或者前几个都相同，如产生式103、108、116等，

则在这种情况下，就不像前两种情况那么简单了，因

为知道了当前的单词并不能知道到底使用哪个产生式

来进行规约，因此当当前字符相同的时候，需要读下

一个字符，如果下一个字符仍然相等，则继续往下读

取，一直到遇到的字符可以区分是使用哪个产生式为

止。

在这种情况下，就需要在第一个字符的时候，记

住当前的字符的位置，以便在判断知道是使用哪个产

生式的时候可以回退到函数刚开始的字符的位置，进

而用正确的产生式进行展开。

编译原理实验报告

下面以产生式116

116: return_stmt -> return;|return expression;

为例来说明这种情况的产生式的处理方法，因为产生式右部的两个产生式的First集都为return，因此先记录当前的状态，判断下一个词，如果为分号，则用左边的产生式，如果为ID、NUMBER 或LB(expression的First集为ID、NUMBER 或LB)则回退到当前字符为return的状态，用产生式:return_stmt ->return expression;详细的分析见流程图(5)

函数return_stmt()

N当前单词的类错误处理型是否为RETURN

Y记录当前状态往栈中压入一

个空字符

当前单词的类当前单词的类NN错误处理型是否为ID、NUMBER型是否为

SEMICOLON 或LB

回退状态，用往栈中压入一return 回退状态(或直接规

个空字符约)用 return;规约expression;规约

函数return_stmt结束

流程图(5)

4)关于产生式中的empty的处理

消除了左递归之后的那些产生式中都有empty的

现，empty代表可以为空。因此在这种情况下，就往

栈中压入一个空字符:

this.mystack.push(""); 5)其他的各种情况都在上述的几种情况之中，大同小异

因此这里不再赘述。

9. 语法分析的流程图

编译原理实验报告

在把所有的产生式的函数都写好后，语法分析的过程就变得很

简单了，因为程序的入口点就是函数program(),只要用token为

其读取第一个单词即可进行以后的分析，以后的分析中在其他

的各个函数中实现了单词的读取和结果的输出以及错误的恢

复处理等。流程图见流程图(6)。

语法分析

调用token()读

取第一个字符

调用program()

函数进行递归

分析

End

流程图(6)

(四) 实验编写代码和测试

1. 代码的编写，由于递归的实现就是为每个函数建立一个函数，对不同的产生式类型用不同的方法进行编写，但由于逻辑的判断和转换比较多，因此很容易出错和导致思维的混乱。

由于用到的栈处理比较多，因此对栈的使用前先做了不少的测试。

2. 程序的测试用例和结果输出，以及相应的错误恢复与错误显示。 1) 正确的测试用例以及结果

测试用例:

void main(void)/*主函数*/

{

int ss[32];

if(a == b)

return a;

else return b;

while (a >= b)

a=b+a;

}

结果显示:

编译原理实验报告

分析结果显示>>>

type_specifier void void

params->void void

type_specifier int int

var_declaration ->type_specifier ID[NUM]; int ss [ 32 ] ;

local_declarations_zdg-> var_declaration local_declarations_zdg|empty int

ss [ 32 ] ;

factor->var a

term -> factor term_zdg a

additive_expression -> term additive_expression_zdg a factor->var b term -> factor term_zdg b

additive_expression -> term additive_expression_zdg b

simple_expression -> additive_expression relop additive_expression a == b

expression ->simple_expression a == b factor->var a

term -> factor term_zdg a

additive_expression -> term additive_expression_zdg a

simple_expression -> additive_expression a expression -

>simple_expression a

return_stmt -> return expression; return a ; statement ->

return_stmt return a ;

selection_stmt -> if(expression)statement if(a == b )return a; statement -> selection_stmt if(a== b)return a ; factor->var a term -> factor term_zdg a

additive_expression -> term additive_expression_zdg a factor->var b term -> factor term_zdg b

additive_expression -> term additive_expression_zdg b

simple_expression -> additive_expression relop additive_expression a >= b

expression ->simple_expression a >= b factor->var b

term -> factor term_zdg b

addop->+ +

factor->var a

term -> factor term_zdg a

additive_expression_zdg-> addop term additive_expression_zdg|empty

additive_expression -> term additive_expression_zdg b + a

simple_expression -> additive_expression b + a expression -

>simple_expression b + a expression -> var = expression a=b + a expression_stmt -> expression; a=b + a ;

11 statement -> epresion_stmt a=b + a ;

iteration_stmt -> while(expression)statement while ( a >= b ) a=b + a ;

编译原理实验报告

expression_stmt -> expression; a=b + a ; statement -> epresion_stmt a=b + a ; iteration_stmt -> while(expression)statement while (a>= b) a=b + a ; statement -> iteration_stmt while ( a>= b) a=b + a;

statement_list_zdg->statement statement_list_zdg|empty while(a >= b )

a=b + a ; statement_list_zdg->statement statement_list_zdg|empty

if(a==b)return a; while ( a>= b) a=b+ a ; statement_list->

statement_list_zdg if(a==b)return a; while(a>= b) a=b+ a; compound_stmt -> {local_declarations statement_list} { int ss [ 32 ] ; if(a== b)return a ; while ( a>= b) a=b+ a ; } declaration -> fun_declaration void main (void) {int ss [ 32 ]; if(a == b)return a; while ( a>= b) a=b+ a; } declaration_list ->declarations declaration_list_zdg void main ( ) ) { int ss [ 32 ] ; if(a== b)return a; while ( a>= b) a=b + a; } program -> declaration_list void main ( void ) { int ss [ 32 ] ; if(a == b)return a; while ( a>= b) a=b+ a; }

2) 测试用例中含有错误，错误显示

含错误的测试用例:

int function( param,int s[])/*参数没有定义*/

{

param=param*param/*缺失分号*/} int functionB(float param,int s[dd ss] )/*数组参数中含有非法字符*/

{

param=param*param;} float functionC(float param,int s[ )/*数组参数s

中缺少']'*/

{

param=param*param;} void main(void) {

int aa;

if(aa>=bb)

{

dd=aa-bb;/*if语句缺少'}'*/

else

return /*return语句缺少';'*/

while(aa

{

aa=aa+bb;

function(a);

} 11 }

编译原理实验报告

错误显示 :(输入语法分析阶段的错误不在这里显示)

第1行有语法错误!>> 参数param没有定义类型或者缺失类型声明～第3行有语法错误!>> ';'丢失～第4行有语法错误!>> 数组参数s中'[]'中含有非法字符～第4行有语法错误!>> 数组参数s中'[]'中含有太多的非法字符～第7行有语法错误!>> 数组参数s中'[]'中含有非法字符～第7行有语法错误!>> 数组参数s中缺失']'～第16行有语法错误!>> 语句缺少'}'～第18行有语法错误!>> return语句缺少';'～第19行有语法错误!>> while语句缺少) 说明:如果有的错误是出现在词法分析中的，就会导致语法分析的错误不会太全面，或者会造成语法分析中的一些程序上的多次循环，但是不管怎么样，被分析的程序只要出现错误范围是违背了我的产生式的情况的，编译器都应该可以找出来的。