编译原理实验报告实验名称：编写语法分析程序实验类型：设计性实验指导教师：蒋*专业班级：软件工程1401姓名：****学号：**********实验地点：东六E座301实验成绩：_________________日期：2016年5月17日实验一编写词法分析程序一、实验目的：1.设计、编写、调试一个递归下降分析程序，实现对词法分析程序提供的单词序列进行语法检查和结构分析。

2.掌握递归下降语法分析方法。

3.巩固理论知识。

二、实验设计：1.设计原理：1)对于文法的每一个非终结符U的文法规则是一个识别U的过程定义，为每一个非终结符构造子程序。

2)如果U的右部符号串只有一个候选式则从左到右依次构造U的识别代码。

3)如果U的右部符号串有终结符号，则判断输入的符号是否匹配终结符号，如果相等，则读入下一个符号；如果不相等，则有语法错误，应当报错。

4)如果是非终结符号，则调用非终结符号的子程序即可。

5)如果U的右部有多个候选式，应该根据每个候选式的第一个符号来确定该分支。

6)对于含有ε表达式的文法规则需要判断输入的符号是否在U的FOLLOW集里面。

2.设计方法：(1)文法改造，消除二义性；(2)对含有左递归或者左公因子的文法消除左递归，提取左公因子；(3)求每一个右部符号串的FIRST集合，如果右部含有ε，则需要求出其产生式左部非终结符的FOLLOW集。

判断文法是否是LL（1）文法，若不是LL(1)文法，说明文法的复杂性超过自顶向下方法的分析能力。

(4)根据改写后的文法设计程序，依据设计原理构造每一个非终结符的子程序。

3.设计过程：(1)改写文法、消除左递归（将左递归改为右递归）、提取左公因子；(2)求出相应的First集和Follow集；(3)设计程序流程图，设计程序；(4)编写程序；4.框架思路，错误信息输出：对每一个非终结符构造其子程序，设定一个返回值。

如果语法分析有错则返回1，没有错误就返回0；对于错误，在程序的相应行数报错。

各个非终结符之间依据文法规则调用。

每次遇到终结符函数都判断是否匹配当前终结符号，如果不匹配则报错，返回1。

如果匹配，则读入下一个符号。

三、实验过程(一)本次实验的TEST语言语法规则：1) <program>→{<declaration_list><statement_list>}2) <declaration_list>→<declaration_list><declaration_stat> | ε3) <declaration_stat>→int ID;4) <statement_list>→<statement_list><statement>| ε5) <statement>→<if_stat>|<while_stat>|<for_stat>|<read_stat>|<write_stat>|< compound_stat > |<expression_stat>6) <if_stat>→if (<expr>) <statement >| if (<expr>) <statement >else < statement >7) <while_stat>→while (<expression>) < statement >8) <for_stat>→for (<expression>;<expression>;<expression>)<statement>9) <write_stat>→write <expression>;10) <read_stat>→read ID;11)<compound_stat>→{<statement_list>}12)<expression_stat>→< expression >;|;13)< expression >→ID=<bool_expr>|<bool_expr>14)<bool_expr>→<additive_expr> |< additive_expr >(>|<|>=|<=|==|!=)<additive_expr >15)< additive_expr>→< additive_expr>+<term>|< additive_expr>-<term>|< term >16)< term >→< term >*<factor>|< term >/<factor>|< factor >17)< factor >→(< expression >)|ID|NUM1.将左递归改为右递归：2) <declaration_list>→<declaration_list><declaration_stat> | ε改写后：<declaration_list>::=<declaration_list1><declaration_list1>:=<declaration_stat><declaration_list1>|ε4) <statement_list>→<statement_list><statement>| ε改写后：<statement_list>::=<statement_list1><statement_list1>::=<statement><statement_list1>|ε15)< additive_expr>→< additive_expr>+<term>|< additive_expr>-<term>|< term >改写后：<additive_expr>::=<term><additive_expr1><additive_expr>::=+<term><additive_expr1>|-<term><additive_expr1>|ε16)< term >→< term >*<factor>|< term >/<factor>|< factor >改写后：<term>::=<factor><term1><term1>::=*<factor><term1>|/<factor><term1>|ε2.提取公因式：14)<bool_expr>→<additive_expr> |<additive_expr>(>|<|>=|<=|==|!=)< additive_expr >改写后：<bool_expr> ::= <additive_expr><bool_expr1><bool_expr1> ::=ε|(>|<|>=|<=|==|!=)<additive_expr>3.是否可以提取公因式6) <if_stat>→if (<expr>) <statement >| if (<expr>) <statement >else < statement >不可以提取公因式，if语句和if…else语句是相互独立的,并没有必然的联系。

4．规则13超前读入符号解决方案：如果识别出标识符的符号ID后，在读入一个符号，如果这个符号时=，说明选择的是赋值表达式，如果不是=，则说明选择是布尔表达式。

(二)、求出右部符号串的FIRST集和含有ε产生式的左部非终结符的FOLLOW集1)<program>→{<declaration_list><statement_list>}FIRST({<declaration_list><statement_list>}) = { { };2) <declaration_list>::=<declaration_list1><declaration_list1>:=<declaration_stat><declaration_list1>|εFIRST(<declaration_list1>) = { int,ε};FIRST(<declaration_stat><declaration_list1>) = { int };FOLLOW(<declaration_list1>) = {if,while,for,read,write,{,},;,ID,(,NUM};3) <declaration_stat>→int ID;FIRST(int ID;) = { int };4)<statement_list>::=<statement_list1><statement_list1>::=<statement><statement_list1>|εFIRST(<statement_list1>) = {if,while,for,read,write,{,;,ID,NUM,(};FIRST(<statement><statement_list1>) = {if,while,for,read,write,{,;,ID,NUM,(};FOLLOW(<statement_list1>) = {}};5) <statement>→<if_stat>|<while_stat>|<for_stat>|<read_stat>|<write_stat>|<compound_stat > |<expression_stat>FIRST(<if_stat>) = {if};FIRST(<while_stat>)= {while}FIRST(<for_stat>) = {for}FIRST(<read_stat>) = {read};FIRST(<write_stat>) = {write}FIRST(<compound_stat>)={{}FIRST(<expression_stat>)={ID,NUM,;,(}6) <if_stat>→if (<expr>) <statement >| if (<expr>) <statement >else < statement >FIRST(if (<expr>) <statement >) = {if}FIRST(if (<expr>) <statement >else < statement >)={if}7) <while_stat>→while (<expression>) < statement >FIRST(while (<expression>) < statement >) = {while}8) <for_stat>→for (<expression>;<expression>;<expression>)<statement>FIRST(for (<expression>;<expression>;<expression>)<statement> = {for}9) <write_stat>→write <expression>;FIRST(write <expression>;) = {write}10) <read_stat>→read ID;FIRST(read ID;) = {read}11)<compound_stat>→{<statement_list>}FIRST({<statement_list>}) = {{}12)<expression_stat>→< expression >;|;FIRST(< expression >;) = {(,ID,NUM};FIRST(;) = {;};13)< expression >→ID=<bool_expr>|<bool_expr>FIRST(ID=<bool_expr>) = {ID};FIRST(<bool_expr>) = {ID,NUM,(};14)<bool_expr>→<additive_expr> |<additive_expr>(>|<|>=|<=|==|!=)< additive_expr > <bool_expr> ::= <additive_expr><bool_expr1><bool_expr1> ::=ε|(>|<|>=|<=|==|!=)<additive_expr>FIRST(<additive_expr><bool_expr1>)={（，ID，NUM}FIRST((>|<|>=|<=|==|!=)< additive_expr >)={>,<,>=,<=,==,!=}FOLLOW(<bool_expr1>)={),;}15)< additive_expr>→< additive_expr>+<term>|< additive_expr>-<term>|< term ><additive_expr>::=<term><additive_expr1><additive_expr1>::=+<term><additive_expr1>|-<term><additive_expr1>|εFIRST(< term ><additive_expr1>)={ (,ID,NUM }FIRST(+<term><additive_expr1>)={+}FIRST(-<term><additive_expr1>)={-}FOLLOW(<additive_expr1>)={>,<,>=,<=,==,!=,;,)}16)< term >→< term >*<factor>|< term >/<factor>|< factor ><term>::=<factor><term1><term1>::=*<factor><term1>|/<factor><term1>|εFIRST(<factor>) = {(,ID,NUM};FIRST(*<factor><term1>)={*};FIRST(/<factor><term1>)={/};FOLLOW(<term1>) = {+,-,;,},>,<,>=,<=,==,!=}17)< factor >→(< expression >)|ID|NUMFIRST((<expression>))= {(}:FIRST(ID) ={ID};FIRST(NUM) = {NUM};(三)、<statement>程序流程图(四)、<expression>程序流程图四、试验调试记录：1、问题表现：当语法分析到最后一行时进入死循环。