递归下降分析.docx

编译原理实验递归下降分析实验1.2 递归下降分析1. 实验目的加深递归下降的理解2. 实验平台VC+6.0 +Flex3. 实验内容选择一个文法或自己设计一个文法 写出文法接受的语言。针对文法手工构造递归下降分析程序实现下列功能：输入一个符号串，输出文法分析的结果，接受或拒绝。从文件中读入若干符号串，依次分析文法的结果。4. 实验步骤1.选择语言: T0语言Program BEGIN Stmt-List ENDStmt-List Stmt-List Stmt /左递归| StmtStmt Assign-stmtAssign-stmt ID = Expr;Expr Expr Add-Op Term /左递归| TermTerm Term Multiple-Op Factor /左递归| FactorFactor (Expr)| ID| NUMAdd_Op + | -Multiple_Op * | /文法含有左递归，手工消除左递归。2.消除左递归后的文法：Program BEGIN Stmt-List ENDStmt-List Stmt Stmt-ListStmt-List Stmt Stmt-List | Stmt Assign-stmtAssign-stmt ID = Expr ;Expr Term ExprExpr Add-Op Term Expr| Term Factor TermTerm Multiple-Op Factor Term| Factor ( Expr )| ID| NUMAdd_Op + | -Multiple_Op * | /3求出文法各个非终极符的FIRST集和FOLLOW集非终极符是否可推导为空FIRST集FOLLOW集ProgramBEGIN $Stmt-ListIDEND Stmt-ListID END StmtID END Assign-stmtIDEND Expr( ,ID ,NUM,; )Expr+ - , ; )Term( ,ID ,NUM,+ - ; ) Term* / + - ; )Factor( ,ID ,NUM,* /Add_Op+ -( ,ID ,NUM,Multiple_Op* /( ,ID ,NUM根据FIRST和FOLLOW集可以判读消除左递归后的文法为LL（1）文法，可以进行自上而下的文法分析根据个各非终极符产生式和FIRST和FOllOW集构造递归下降分析：利用lex自动工具生成词法分析部分。然后根据lex识别的串进行文法的分析，输出结果：失败匹配或成功匹配。5. 实验源码本代码利用FLEX编译后用VC+编译生成的lex.yy.c文件；FILE：t8.lex%#include#includechar ch; /全局变量盛放识别的串的标识/函数声明P(); / Program产生式L(); / Stmt-List 产生式L1(); / Stmt-ListS(); / StmtA(); / Assign-stmtE(); / ExprE1(); / ExprT(); / TermT1(); / TermF(); / FactorO(); / Add_OpM(); / Multiple_Op%BEGIN ch=b; return ;END ch=e; return ;nt r* ch=k; return;a-zA-Za-zA-Z0-9* ch=i; return ;0-90-9* ch=n; return; + ch=+; return;- ch=-; return;* ch=*; return;/ ch=/; return;= ch=; return; ch=; return;( ch=(; return;) ch=); return;. ch=X;return;% int yywrap(void) return 1;main() void next1(); yyin=fopen(hh.c,r); /lex读取文件 next1(); /是指针移到开始符号 printf(匹配中); P(); /匹配函数调用void next1() /去下个被识别串的标识 yylex();if(ch=k) next1();/int P()if (b=ch)next1();L(); printf(.);if (e=ch) printf(n-n); printf(-成功-n);printf(-n);next1();return 0;elseprintf(n-失败-n);exit(0);return -1;elseprintf(n-失败-n); exit(0); return -1;/int L()if (e=ch)return 0;elseS();printf(.);L1(); printf(.);return 0;/int L1()if (e=ch)return 0;elseS();printf(.);L1();printf(.);return 0;/int S()A();printf(.);return 0;/int A()if (i=ch)next1();if (=ch)next1();E();printf(.);if(;=ch) next1(); return 0;elseprintf(n-失败-n);return -1;else printf(n-失败-n);exit(0);return -1;else printf(n-失败-n);exit(0); return -1;/int E()T();printf(.);E1();printf(.);return 0;/int E1()if (;=ch|)=ch)return 0;elseO();printf(.);T();printf(.); E1();printf(.);return 0;/int T()F();printf(.);T1();printf(.);return 0;/int T1()if (+=ch| -=ch |;=ch|)=ch)return 0;elseM(); printf(.);F();printf(.);T1();printf(.);return 0;/int F()if (=ch)next1();E();printf(.);if ()=ch)next1();return 0;else printf(n-失败-n);exit(0); return -1;else if (i=ch)next1();return 0;else if (n=ch)next1();return 0;else printf(n-失败-n);exit(0); return -1;/int O()if (+=ch)next1();return 0;else if(-=ch)next1();re