C词法扫描器及语法分析器实现

《C词法扫描器及语法分析器实现》由会员分享，可在线阅读，更多相关《C词法扫描器及语法分析器实现（106页珍藏版）》请在装配图网上搜索。

1、编译原理及实践课程报告课题名称:c词法扫描器及语法分析器实现课题负责人名（学号）：指导教师:金军 老师评阅成绩:评阅意见:提交报告时间:2013年6月13日目录!课程设计目标22分析与设计22.1程序结构22 .L1语法分析采用递归下降方法的程序结构23 .1.2语法分析采用LL(1)方法的程序结构22.2程序流程32.2.1 递归下降方法的程序流程图32.2.2 LL(1)方法程序流程图43词法分析53.1 递归下降方法的词法分析53.1.1 代码结构分析53.1.2 Token 定义63.1.3 DNF 分析74语法分析94.1 递归下降94.1.1 代码结构分析94.1.2 节点定义10

2、4.1.3 递归下降语法分析114.2.1 代码结构分析174.2.2 节点定义184.2.3 LL(1)语法分析185测试结果205.1 递归下降方法的测试结果205.1.1 流程205.1.2 出错的情况275.2 LL(1)方法测试结果305.2.1 流程305.2.2 出错的情况336总结356.1 收获356.2 特色356.3 不足357附录357.1 递归下降方法源代码357.2 LL(1)源文件707.3 C一文法110!课程设计目标学生在学习编译原理课程过程中,结合各章节的构造编译程序的基本理论, 要求用C或C+语言描述及上机调试,实现个C-Minus小编译程序（包括 词法分

3、析,语法分析等重要子程序）,使学生将理论与实际应用结合起来,受到 软件设计等开发过程的全面训练,从而提髙学生软件开发的能力。要求:实现scanner和parser功能2分析与设计2.1 程序结构2.1.1 语法分析采用递归下降方法的程序结构本程序采用面向对象的思想编写，使用C+语言实现，程序分为两部分: 词法分析（Scanner）和语法分析（Parser）,分别将两个处理阶段封装成Scanner 类和Parser类,两个类分别完成词法分析和语法分析的任务。Scanner类主要的工作是删除注释、词法分析获取Token。Parser类的主要 工作是根据Scanner类词法分析之后的Token进行语

4、法分析,生成语法树,最 后并输出语法树。四个文件分别为scanner.h和scanner.cpp以及parser.h和 parser.cpp,他们分别是Scanner类声明文件、Scanner类实现文件、Parser类声 明文件、Parser类实现文件。B Source Files 团 parser.cpp 团 scanner.cppE 6 Header Files 司 parser.h 国 scanner.h LJ Resource Files2.1.2 语法分析采用LL（1）方法的程序结构B Source Files国 grammarlnit.cpp国 main.cpp国 parse.cp

5、p国 parseTablelnit.cpp 国 scan.cpp 鹵 util.cppF Header Files 圓 globals.h Bl parse.h i scan.h 團 util.h Resource Files本程序采用C+语言实现,程序分为两大 部分:词法分析（Scanner）和语法分析（Parser）, 这两个部分分别完成词法分析和语法分析的任 务。其中,grammarlnit.cpp 中定义了 C-Minus 的文法规则,parseTablelnit.cpp 中实现了 First 集和Follow集的构建以及分析表构建的方法。 uitl.cpp实现了语法分析输出相关的函数

6、2.2 程序流程2.2.1 递归下降方法的程序流程图2.2.2 LL(1)方法程序流程图3词法分析3.1 递归下降方法的词法分析3.1.1 代码结构分析词法分析阶段的代码被封装成一个类Scanner, scanner.h中主要是Scanner类的声明代码,scanner.cpp中主要是Scanner类的实现代码。Scanner 类对外提供的函数主要有:getSourseStringFromFile（string s）（从文件中获取待 分析的源代码）、deleleCommenls。（过滤注释）、scan。（词法分析主程序）。词 法分析的过程主要是: Scanner调用getSourseStrin

7、gFromFile（string s）从文件中获取待分析的源代 码 Scanner调用deleteComments。,将注释过滤掉,如果注释出错,则不进行 词法分析 Scanner调用scan。,进行词法分析,将分析得到的所有Token保存在Scanner 类的成员变量tokenList中,以备语法阶段调用,并将!oken输出到文件 Token.txt 中 以上三个函数构成了词法分析的骨架,在Scanner类中还有其他成员变量 和函数,主要作为这三个函数处理过程的中间步骤,为这三个函数服务。Scanner 类的代码结构和主要的成员变量和函数如下图所示:B Scanner# backToLast

8、CharQ charType(char) deleteCommentsOA getNextCharQ getSourseStringFromFilefstring s) getTokenAt(int)立 printTokenO立 retu rnTo ke nTyp e (stri n g s) scanQ ScannerQ茅 charindex齢 commentFlag士 lineCountQ scanSuccess sourseStringa str齢 tokenList其他函数和成员变量的作用和含义: void backToLastChar():在词法分析过程中,回退个字符 DFAStat

9、e charType(char):返回字符的类型(按状态分),如white space返 回 START, 0-9 返回 NUM char getNextChar():获取到下个字符 Token getTokenAt(int):根据下标从tokenList数组中获取词法分析后所保存 的Token (供语法分析阶段调用) void printToken():将词法分析好的Token输出到文件Token.txt中 TokenType returnTokenType(string s):根据字符串返回对应的 31 种 Token 类 型,如字符串”in将返回INT, “var”将返回ID int c

10、harindex:配合 getNextChar()和 backToLastChar()使用(分别自增和自减 1),用以指示当前待分析的char在源代码中的位置 bool commentFlag:标注注释开始的标志,为true时表示正在注释体内, 即源代码进入”之后且“*/”之前的状态 int lineCount：对行号计数,表示当前词法分析在源代码的行位置(每次获 取到的char为就自增1) bool scanSuccess:词法分析是否成功的标志 string sourseString:获取源代码的字符串 string str:在分析过程中保存Token对应的串 vector tokenLi

11、st:保存 Token 序列3.1.2 Token 定义3.1.2.1 Token的定义和类型Token定义:/定义的Token结构体,包括类型、对应的串、所在代码的行号 struct Token(TokenType tokenType;string tokenstring;int lineNo;);Token 类型(TokenType):程序中,将Token的类型分为31种,分别对应于else、if、int、return void while +、 、= = !=、=、;、(、)、 、 /、/、num、id、错误、文件结束,TokenType的定义和种别码分别如下所示:/定义的Token的类

12、型(31种)，分别对应于else、if int、eturn、void、while +、/、=、=、!=、=、;、,、(、)、/、/、num、 id、错误、结束 typedef enumELSE1,IF,NT,RETURN,VOID, WHILE,PLUS,MINUS,TIMES,OVER,LT,LEQ,GT,GEQ,EQ,NEQ,ASSIGN,SEMI,COMMA,L PAREN,RPAREN,LMBRACKET, RMBRACKET,LBBRACKET,RBBRACKET,LCOMMENT,RCOMMENT,NUM,ID,ERROR,ENDFILE TokenType;3.1.2.2 Tok

13、en的种别码TokenType的种别码如F表所小,共31种单词符 号种别码Value单词 符号种别码ValueelseELSE1=ASSIGN17ifIF2rSEMI18intINT3COMMA19returnRETURN4(LPAREN20voidVOID5)RPAREN21whileWHILE6LMBRACKET22+PLUS7RMBRACKET23一MINUS8(LBBRACKET24*TIMES9RBBRACKET25/OVER10/*LCOMMENT26LT11*/RCOMMENT27GT13idID29=geq14错误ERROR30=EQ15结束ENDFILE311 =NEQ163

14、.1.2 DNF 分析3.1.2.1 删除注释DNF删除注释的DFA描述:删除注释的DFA如下所示,共分为5个状态,在开始状态1时,如果输入的 字符为/,则进入状态2,此时有可能进入注释状态，如果在状态2时，输入的 字符为,则进入注释状态,状态将转到3,如果在状态3时，输入的字符为, 则有可能结束注释状态,此时状态将转到状态4,如果在状态4时输入的字符 为/,则注释状态结束，状态转移到结束状态。“3.1.2.2 词法分析DNF词法分析的DFA描述:词法分析的DFA如下所示,共分为5个状态:START、INNUM、INID, INDBSYM, DONE。状态START表示开始状态,状态!NNUM

15、表示数字类型（NUM） Token的状态,状态!NID表示字符串类型Token的状态（如关键字和一般 的标示符）,状态NDBSYM表示双目运算符型Token的状态（如 =、=、!=、 =）,状态DONE表示接收状态。other3.2 LL(1)方法的词法分析这里,在词法分析方面,我所用的方法同样是手动分析的方法,与递归下 降方法的词法分析唯一不同的一点是这里的词法分析方法没有用到删除注释的 方法,而是在出现注释并且分析出是正确的注释的时候,跳过该注释，不作处 理，其余在词法分析的Token集的定义等方面,以及词法分析的DNF与递归下 降方法的词法分析的方法类似,这里就不再赘述。4语法分析4.1

16、 递归下降4.1.1 代码结构分析语法分析阶段的代码中 9 parser.h 中主要是Parser类的声明代码, parser.cpp 中主要是Parser类的实现代码。语法分析的过程主要是:在语法分析之前进行词法分析,然后通过递归向下分 析法根据C语言的文法进行语法分析,并生成语法树,最后打印语法树,输出 到文件 tokenTree . txt 中。Parser类的代码结构和主要的成员变量和函数如下图所示: Parser齢 additive_expressionTreeNode *k) & argsfl立 callfTreeNode *k) compound stmtQ 立 declarat

17、ionQ “ declarationJistQ expressionQ* expression_stmtQ 2 factorfTreeNode *k) getTokenfl& iteration stmtQ ocal_declaration() % match(TokenType ex) & newNode(Nodekind k) 融 paramfTreeNode *k) 齢 param_listTreeNode *k) paramsQ立 printSpace(int n“ printTree(TreeNode *t)& return_stmtQ& selection_stmtQ“ simpl

18、e_expression(TreeNode *k)立 state mentQ& statementJistQ“ syntaxError(string s立 termfTreeNode *k)事 varQ currentToken由 ErrorM lastToken齢 scannera stepQ syntaxTree和 tokenindex parseQ .ParserQ4.1.2 节点定义4.1.2.1 节点定义和类型节点定义:/reeNode定义包括子节点、兄弟节点、所处行号、节点类型、属性、表达式返回类型 typedef struct treeNode struct treeNode *

19、 childMAXCHILDREN;struct treeNode * sibling; int lineno; Nodekind nodekind; union TokenType op; int val; const char * name; attr; ExpType type;)TreeNode;节点类型:/19种节点类型,分别表示int、id、void、数值、变量声明、数组声明、函数声明、函 数声明参数列表、函数声明参数、复合语句体、if、while、return、赋值、运算、数组 元素、函数调用、函数调用参数列表、未知节点typedef enum ntK,dK, VoidK, Co

20、nstK, Var_DeclK, Arry_DeclK, FunK, ParamsK, ParamK, CompK, Selection_StmtKr Iteration_StmtK, Return_StmtK, AssignK, OpK, Arry_ElemK, CallK, ArgsK, UnkownK! Nodekind;4.1.2.2 各类型节点的描述节点类型描述子节点组成IntK变量或返回值类型 (int)无VoidK变量或返回值类型 (void)无IdK标示符(id)无ConstK数值无Var_DeclK变量声明变量类型+变量名Var_DeclK数组声明数组名+数组大小FunK函数

21、声明返回类型+函数名+参数列表+函数体ParamsKFunK的参数列表参数(如果有多个参数,则之间为兄 弟节点)ParamKFunK的参数参数类型+参数名CompK复合语句体变量声明列表+语句列表Selection_StmtKif条件表达式+ IF体+ ELSE体Iteration_StmtKwhile条件表达式+循环体Return_StmtKreturn表达式AssignK赋值被赋值变量+赋值变量OpK运算运算符左值+运算符右值Arry_ElemK数组元素数组名+下标CallK函数调用函数名+参数列表ArgsKCallK的参数列表表达式（如果有多个表达式,则之 间为兄弟节点）UnkownK未

22、知节点无4.1.3 递归下降语法分析4.1.3.1 C语法(已消除左递归,附录有BNF语法)program-declaration-list declaration list - declaration declaration declarationvar-declaration|fun-declaration var_declaration type-specifier ID; | type-specifier ID NUM; type - specifier - int | void fun-declatationtype-specifier ID (params) | compound-

23、stmt paramsparam_list | void param_listparam, param) param type-specifier ID compound-stmt local-declaration statement-list) local-deci ar at ions -* empty var- declaration statement-liststatement statementexpression-stmt | compound-stmt I selection-stmt | iteration-stmt | return-stmt expression-stm

24、t expression;selection-stmtif (expression) statement else statement iteration-stmtwhile (expression)statement return-stmtreturn expression; expression var = expression | simple-expression relop -=|=|=| != varID I ID expression simple-expressionadditive-expression relop additive-expression additive-e

25、xpressiontermaddop term addop -* + I - termfactormulop factor mulop -* I /f actor- (expression) | var | call | NUMcall-ID( args )argsarg-list I emptyarg-list expression, expression4.1.3.2 递归下降分析过程以下表格列出了根据上文中的c一文法使用递归向下分析方法分析程序的过程,在代吗部分只列出了函数名,具体函数见附件。待分析文 法programdeclaration-list分析函数TreeNode * pars

26、e(void)分析说明C-语言编写的程序由一组声名序列组成。parse(void)函数使用递归向下 分析方法直接调用declaration_list()函数,并返冋树节点代码TreeNode * Parser : parse(void)待分析文 法declaration_list f declaration declaration 分析函数TreeNode * declaration_list(void)分析说明C语言编写的程序由一组声名序列组成。declaration_list (void)函数 使用递归向下分析方法直接调用declaration。函数,并返回树节点代码TreeNode *

27、Parser : declaration list ()待分析文法declaration_*var-declaration|fun-declaration var_declaration -* type-specifier ID; | type-specifier ID NUM;fun-declatation_*type-specifier ID (params) | compound-stmt type - specifier -* int | void分析函数TreeNode * declaration(void)分析说明C-语言的声明分为变量声明和函数声明。declaration (vo

28、id)函数并不 是直接调用var-dec larat ion或fun-dec la rat ion文法所对应的函数, 令其返回节点，实际上程序并没有为var-dec larat ion和 fun-declaration文法定义函数,而是在declaration (void)函数中,通 过求First集合的方式先确定是变量定义还是函数定义,然后分别根据探测的 结果生成变量声明节点(Var_DeclK)或函数声明节点(FunK ) 所以 var-declaration 和 fun-declaration 文法在 declaration -* var-dec la rat ion | fun-dec

29、laration 文法中就都已经分析了代码TreeNode * Parser : declaration(void)待分析文法params*param_list | void分析函数TreeNode * params(void)分析说明函数参数列表要么是void,要么是多个参数组成。params (void)函数先 判断第一个是void还是int,如果是int说明是由param_list组成,则调 用param_list (TreeNode * k)函数递归向下分析;如果是void说明可能是 void型的参数,也可能参数就是void,所以再求其Follow集合,如果集合求 出来是右括号,则说明

30、参数就是void,于是新建一个VoidK节点就行:如果集 合求出来不是右括号则说明是void型的参数,然后再调用 param_list (TreeNode * k)函数递归向下分析,并将已经取出VoidK节点 传递给 param list (TreeNode * k)函数代码TreeNode * Parser : params(void)待分析文 法param_1ist-*param, param分析函数TreeNode * param_list(TreeNode * k)分析说明参数列表由param序歹组成,并由逗号隔开。param_list (TreeNode * k) 函数使用递归向下分

31、析方法直接调用param (TreeNode * k)函数,并返回树节 点代码TreeNode * Parser : param_list(TreeNode * k)待分析文法param_* type-specifier ID 分析函数TreeNode * param(TreeNode * k)分析说明参数由int或void、标示符组成,最后可能有中括号表示数组。 param (TreeNode * k)函数根据探测先行Token是int还是void而新建ntK 或VoidK节点作为其第一个子节点,然后新建!dK节点作为其第二个子节点, 最后探测Follow集合,是否是中括号,而确定是否再新建

32、第三个子节点表示数 组类型代码TreeNode * Parser : param(TreeNode * k)待分析文法compound-stmt_* local-deciaration statement-list分析函数TreeNode * compound_stmt(void)分析说明复合语句由用花括号围起来的组声明和语句组成。 compound_stmt (void)函数使用递归向下分析方法直接调用 local_declaration ()函数和statement_list ()函数,并根据返回的树节 点作为其第一个子节点和第二个子节点代码TreeNode * Parser : comp

33、ound_stmt(void)待分析文local-declarations empty var- declaration法分析函数TreeNode * local_declaration(void)分析说明局部变量声明要么是空,要么由许多变量声明序列组成。10cal_declaration (void)函数通过判断先彳亍的Token是否是int或 void 便可知道局部变量声明是否为空,如果不为空,则新建一个变量定义节点(Var DeclK)代码TreeNode * Parser : local_declaration(void)待分析文 法statement-list*statement分析

34、函数TreeNode * statement_list(void)分析说明由语句列表由0至多个statement组成。statement_list (void)函数通 过判断先行Token类型是否为statement的First集合确定后面是否是个 statement,如果是，则使用递归向下分析方法直接调用statement ()函数代码TreeNode * Parser : statement list(void)待分析文statement-*expression-stmt I compound-stmt | selection-stmt |法iteration-stmt | return-

35、stmt分析函数TreeNode * statement(void)说明statement由表达式或复合语句或if语句或while语句或return语句构 成。statement (void)函数通过判断先行Token类型确定到底是哪种类型。如分析果是F则是if语句类型,如果是WHILE,则是while语句类型,如果是RETURN, 则是return语句类型,如果是左大括号,则是复合语句类型,如果是D、SEMI. LPAREN、NUM则是表达式语句类型代码TreeNode * Parser : statement(void)待分析文 法expression-stmt_* expression;

36、分析函数TreeNode * expression_stmt(void)分析说明表达式语句有一个可选的且后面跟着分号的表达式。 expression_stmt (void)函数通过判断先行Token类型是否为分号，如果不是 则直接调用函数expression ()代码TreeNode * Parser : expression_stmt(void)待分析文 法selection-stmt-*if (expression) statement else statement分析函数TreeNode * selection stmt(void)分析selection_stmt (void)函数直接调

37、用 expression ()函数和 statement () 数分别得到其第一个和第二个子节点,然后通过判断先行Token类型是否为ELSE, 如果是则直接调用statement。函数得到其第三个子节点代码TreeNode * Parser : selection stmt(void)待分析文 法iteration-stmt-*while (expression)statement分析函数TreeNode * iteration_stmt(void)分析iteration_stmt (void)函数直接调用 expression。函数和 statement ()函 数分别得到其第一个和第二个

38、子节点代码TreeNode * Parser : iteration_stmt(void)待分析文 法return-stmt_* return expression;分析函数TreeNode * return_stmt(void)分析return_stmt(void)函数通过判断先行Token类型是否为分号,如果不是则直 接调用函数expression得到其子节点代码TreeNode * Parser : return_stmt(void)待分析文 法expression-* var = expression | simple-expression分析函数TreeNode * expressi

39、on(void)分析expression (void)函数通过判断先行Token类型是否为D,如果不是说明只能 是 simple_expression 情况,则调用 simp1e_expression (TreeNode * k) 函数递归向下分析;如果是ID说明可能是赋值语句，或simple_expression中 的var和call类型的情况,所以再求其Follow集合,如果集合求出来是赋值类 型的Token,则说明是赋值语句,于是新建一个AssignK节点就行;如果集合求 出来不是赋值类型的Token则说明是simple_expression中的var和cal!类 型的情况，然后再调用s

40、imple_expression (TreeNode * k)函数递归向下分析, 并将已经取出dK节点传递给simple_expression (TreeNode * k)函数代码TreeNode * Parser : expression(void)待分析文 法var-*ID | ID expression分析函数TreeNode * var(void)分析var (void)函数先新建一个dK节点,再通过判断先行Token类型是否为左中括 号,如果是则新建一个数组节点Arry_ElemK,将dK作为Arry_ElemK节点的 第一个子节点,再直接调用函数expression。得到Arry_

41、ElemK的第二个子节 点，最后返回的节点时Arry_EemK;如果先行Token类型不是左中括号，则将之 前的IdK返回代码TreeNode * Parser : var(void)待分析文simple-expressionadditive-expressionrelop冲additive-expression )relop -*=|=|=| !=分析函数TreeNode * simple_expression(TreeNode * k)分析simple_expression (TreeNode*k)函 数 先 调 用additive_expression (TreeNode * k)函数返

42、回一个节点,然后再一直判断后 面的Token是否为=、=、=、!=,如果是则新建OpK节点,然后令之前 的节点为其第一个子节点，然后继续调用additive_expression (TreeNode * k)函数返回一个节点,作为OpK节点的第二个节点代码TreeNode * Parser : simple_expression(TreeNode * k)待分析文 法additive-expression_termaddop term addop f + 1 -分析函数TreeNode * additive_expression(TreeNode * k)分析additive_expressi

43、on (TreeNode * k)函数先调用 term (TreeNode * k)函 数返回一个节点,然后再一直判断后面的Token是否为+或-,如果是则新建OpK 节点,然后令之前的节点为其第一个子节点，然后继续调用term (TreeNode * k) 函数返回一个节点，作为OpK节点的第二个节点代码TreeNode * Parser : additive_expression(TreeNode * k)待分析文 法term-*factormulop factor mulop / I /分析函数TreeNode * term(TreeNode * k)分析term (TreeNode *

44、 k)函数先调用factor (TreeNode * k)函数返回一个节点， 然后再一直判断后面的Token是否为或/,如果是则新建OpK节点,然后令之前的 节点为其第一个子节点,然后继续调用actor (TreeNode * k)函数返回一个节点, 作为OpK节点的第二个节点代码TreeNode * Parser : term(TreeNode * k)待分析文 法factor-(expression) | var | call | NUM分析函数TreeNode * factor(TreeNode * k)分析factor (TreeNode * k)函数首先判断k是否为空,如果不为空,则

45、k为上面传 下来的已经解析出来的以ID开头的var,此时可能为call或var的情况,然后判 断后面的Token是否为左括号,如果是则说明是call的情形，如果不是则为var 的情形。如果k为空,再根据先行的Token类型判断是4中推导中的哪种,然后 直接调用相关的函数返回个节点代码TreeNode * Parser : factor(TreeNode * k)待分析文 法call-* ID ( args )分析函数TreeNode * call(TreeNodek)call (TreeNode * k)函数新建一个call语句的节点CallK,如果k不为空,则分析将k设为CallK的第一个子

46、节点,然后通过调用args (void)函数获得其第二个节点,最后返回CallK节点代码TreeNode * Parser : call(TreeNode * k)待分析文 法args_*arg-list | emptyarg-list_* expression, expression分析函数TreeNode * args(void)分析factor (TreeNode * k)函数首先判断后面的Token是否为右括号,如果是则说 明是empty的情形,如果不是则为至少有一个expression的情形,然后调用 expression ()函数返回节点,然后一直判断后面的Token是否为逗号,如

47、果是则 说明后面还有一个expression,则再调用expression ()函数,使各expression 返回的节点为兄弟节点,然后再将第一个expression返回的节点作为函数调用语 句参数节点ArgsK的子节点代码TreeNode * Parser : args(void)4.2 LL(1)语法分析4.2.1 代码结构分析利用LL(1)分析,输入C-Minus文法,构造文法每个非终结符的FIRST和 FOLLOW集合，然后根据FIRST和FOLLOW集合构造SELECT集合用来构造 LL ( 1)分析表,最后利用分析表，根据LL(I)语法分析构造个分析器。；基 #indude pa

48、rse.h*三 俗 setElementNode token; next;1 今 SetElementNode;日今 firstSet head;二 withEmpty;今 FirstSet;白今 followSet head; . withEmpty; withDollor;今 FollowSet;S File scope variables init(int parseTable35)三 firstGen(GrammarStmt grammar) followGen(GrammarStmt *grammar) LLtable(GrammarStmt *grammar,int parseTa

49、bleO35)E) S *includesH File scope variables二 parse(void)Parse.cpp 结构E *include *parse.h grammars(Grammar$tmt grammar)grammerinit.cpp 结构ParserTablelnit.cpp 结构4.2.2 节点定义节点定义:typedef struct treeNodestruct treeNode * childMAXCHILDREN;NodeKind nodeKind; int lineno;unionNonTerminalsType nonTerm; TokenType

50、 token;kind; char *tokenStr;TreeNode;节点类型:/非终结字符类型 typedef enum (Program,DeclarationList,DeclarationListApp,Declaration,Declara tionApp,VarDeclaration,FunDeclaration,Params,ParamList,ParamListApp,Pa ram,ParamApp,Compoundstmt,LocalDeciarations,StatementList,Statement,Express ionStmt,TypeSpecifier,Sel

51、ectionStmt,ElsePart,IterationStmt,ReturnStmt, ReturnStmtApp,Expression,ExpressionApp,VarApp,SimpleExpressionApp,Relop,Addi tiveExpression,AdditiveExpressionApp,Addop,Term,TermApp,Mulop,Factor,FactorAp p,Call,Args,ArgList,ArgListApp,FactorElse,App,ExpressionAppApp NonTerminalsType;/节点种类:非终结符,token, $

52、typedef enumNonTerminalsK,TokenKNodeKind;4.2.3 LL语法分析函数void grammars(GrammarStmt *grammar)分析将C-的文法消除左递归以及提取公因子后的文法,用代码的形式记录到数组 中,方便以后调用函数void init(int parseTable35)分析初始化函数,对分析表所有元素置零,默认的错误格式,对非终结字符的First, Follow集初始化,对语法规则的First集初始化,对开始符号的Follow集 中，添加$函数void firstGen(GrammarStmt *grammar)分析First集生成函数

53、:看是否有集合发生改变,当集合都不变化时,集合生成完成。 对于推导A-a,对A赋值,对每个推导项遍历集合的指针,如果是token, 直接把它加入First集中，如果表示A的First集中，没有该token,把它 加入集合。如果是非终结字符,添加它的first给A,遍历First (x),添加 First(x)进入A,査找是否A的First集中,是否存在该token,若表示A 的First集中，没有该token,把它加入集合。对推导式求First集,对每 则语法对每个推导项遍历，如果是token,直接把它加入First集中,如果 First集中,没有该token,把它加入集合。如果是非终结字符,

54、添加它的first 给该grammar。遍历First (x),添加First (x)进入该grammar,然后査找 是否该grammar的First集中,是否存在该token,若没有该token,把它 加入集合。函数void followGen(GrammarStmt *grammar)分析follow集生成函数:对每则推导、对每个非终结符Xi遍历,对于Xi + 1Xn,如果是token,直接把它加入Follow集中，同时査找是否该非终结符的 Follow集中,是否存在该token若Follow集中，没有该token把它加 入集合。如果是非终结字符,添加它的First给该非终结字符,遍历Fi

55、rst (Xj), 添加First (Xj)进入该非终结字符,同时查找是否该非终结字符的Follow集 中，是否存在该token,若Follow集中，没有该token,把它加入集合。函数void LLtable(GrammarStmt *grammar,int parseTable35)分析分析表生成函数:首先对分析表,First, Follow集初始化,然后调用函数生 成first集和follow集。对First集来进行构造,如果FRST集有空,则加入A的Follow集，若不为空,则为出错情况，POPo函数TreeNode * parse(void)分析利用分析表构造分析栈来分析源文件:首先

56、初始化语法、分析栈、分析表,开始 非终结符压栈,取出第一个token,分析结束标志相当于,分析栈输入栈都为$, 如果匹配则继续,如果出错，进行scan操作，取出下个token,或pop操作, 弹出当前分析栈的非终结字符，如果分析栈为空，强行终止分析。如果没有错误, 则进行压栈操作,同时建立非终结符节点以及终结符节点,然后压入分析栈,建 立分析树。5测试结果5.1 递归下降方法的测试结果5.1.1 流程文件分析成功结果如下图: D:my own space、贾思宇的文档大三下、编译原理隔浮原理课程设计、compDebugcomp.exeDelete connents. Delete connen

57、t success? Scanner starting. Scanner success? Parser starting. Parser success? 请按任意键继续. . . 源文件:testtxt 记事本.0 I 回文件(F)编辑(E)改()直看(V)幫助(H)*A program to perform Euclids Algorithm to compute gcd. * int a;int b10;int gcd(int u, int v)1 if (v0)return u;else return gcd (v, u-u v*v);)int ac;int be;int i;/*u

58、-u/v*v=u mod v*/|void main(void) f (int x;int y;gcd(x, x+y);x= input ();y=input ();gcd(x, y);output (gcd(x, y)；删除注释后的文件生成的Token集0:1: int a;1:keyword：intINT1:ID：aID1:2: intb10symbols：SEMI2:keyWord：intINT2:ID：bID2: symbols： 10LMBRACKET NUM2: NUM：2: symbols：1RMBRACKET2: symbols：3: int gcd(int u,int v)S

59、EMI3: keyword：intINT3:ID：gcdID3: symbols：(LPAREN3: keyWord；intINT3:ID：uID3: symbols：COMMA3: keyWord：intINT3:ID：VHD4： (3: symbols：)RPAREN5:4: symbols： if (v0)(LBBRACKET5: keyWord：ifIF5: symbols：(LPAREN5:ID：VID5: symbols：LT5: NUM：0NUM6:5: symbols： return u;)RPAREN6: keyWord：returnRETURN6:ID：uID7:6: symbols： else5