编译原理课程第11讲.ppt

3.7 分析器的生成器,3.7.1 分析器的生成器Yacc,Lex编译器,Lex源程序lex.l,C编译器,a.out,a.out,输入流,记号序列,用Lex建立词法分析器的步骤,1/36,Yacc程序包括三个部分 声明 翻译规则 支持例程,3.7 分析器的生成器,例-声明部分%#include/*常量、变量的声明*/%token DIGIT%,3.7 分析器的生成器,EE+T|TTT*F|FF(E)|digit,例-翻译规则部分line:expr nprintf(“%dn”,$1);expr:expr+term$=$1+$3;|term;term:term*factor$=$1*$3;|factor;factor:(expr)$=$2;|DIGIT;%,3.7 分析器的生成器,EE+T|TTT*F|FF(E)|digit,例-支持例程部分yylex()int c;c=getchar();if(isdigit(c)yylval=c 0;return DIGIT;return c;,3.7 分析器的生成器,EE+T|TTT*F|FF(E)|digit,5/36,3.7 分析器的生成器,3.7.2 用Yacc处理二义文法 解决分析动作冲突的两大默认规则：对于归约-归约冲突，选择在Yacc 程序中最先出现的那个产生式归约 对于移进-规约冲突，优先移进,3.7 分析器的生成器,3.7.2 用Yacc处理二义文法 例 台式计算器输入一个表达式并回车，显示计算结果。也可以输入一个空白行。,lines lines expr n|lines n|eE E+E|E E|E*E|E/E|(E)|-E|number,3.7 分析器的生成器,%#include#include#define YYSTYPE double/*将栈定义为double类型*/%token NUMBER%left+%left*/%right UMINUS%,lines lines expr n|lines n|eE E+E|E E|E*E|E/E|(E)|-E|number,3.7 分析器的生成器,lines:lines expr n printf(“%g n”,$2)|lines n|/*/;expr:expr+expr$=$1+$3;|expr expr$=$1$3;|expr*expr$=$1*$3;|expr/expr$=$1/$3;|(expr)$=$2;|expr%prec UMINUS$=$2;|NUMBER;%,lines lines expr n|lines n|eE E+E|E E|E*E|E/E|(E)|-E|number,3.7 分析器的生成器,yylex()int c;while(c=getchar()=);if(c=.)|(isdigit(c)ungetc(c,stdin);scanf(“%lf”,lines lines expr n|lines n|eE E+E|E E|E*E|E/E|(E)|-E|number,10/36,3.7 分析器的生成器,3.7.3 Yacc的错误恢复编译器设计者的工作决定哪些“主要的”非终结符将有错误恢复与它们相关联加入A error 的错误产生式，其中A是主要非终结符，是文法符号串为这样的产生式配上语义动作Yacc把错误产生式当作普通产生式处理,3.7 分析器的生成器,遇到语法错误时从栈中弹出状态，直到发现栈顶状态的项目集包含形为A error 的项目为止把虚构的终结符error“移进”栈若为，直接进行产生式规约，并执行相关的语义动作，忽略若干输入符号，直至发现能回到正常处理的符号为止。若不为，找到，把移进栈把error 归约为A，恢复正常分析。,3.7 分析器的生成器,lines:lines expr nprintf(“%g n”,$2)|lines n|/|error nprintf(“重新输入上一行”);yyerrok;,语法分析内容总结,文法和语言的基本知识自上而下的分析方法：预测分析，非递归的预测分析，LL(1)文法自下而上的分析方法：SLR(1)方法，规范LR(1)方法和LALR(1)方法,语法分析内容总结,自上而下分析 LL(1)文法判定原则 FIRST、FOLLOW集的计算（重点）LL(1)文法判定方法 LL(1)分析实现方法 递归函数实现 非递归的预测分析实现先求FIRST、FOLLOW集画预测分析表,语法分析内容总结,书后3.19，3.20等题目都是判断是否属于某类文法，判定文法是否是LL(1)文法步骤如下：如果有以下两种情况一定不是左递归公共左因子如果不是，则改写文法 消除左递归 提取左因子改写后进行LL(1)分析,语法分析内容总结,例1 文法GS:S-aSb|P P-bPc|bQc Q-Qa|a(1)判断这个文法是不是LL(1)的？(2)消除左递归、提取左因子之后的文法G是否是LL(1)的？,语法分析内容总结,解答：首先，GS不是LL(1)的!,GS:S-aSb|PP-bPc|bQcQ-Qa|a,语法分析内容总结,例1 解答：提取左因子，将P-bPc|bQc变为 P-bP P-Pc|Qc,消除左递归，将 Q-Qa|a 变为 Q-aQ Q-aQ|,GS:S-aSb|PP-bPc|bQcQ-Qa|a,语法分析内容总结,例1 解答：判定文法GS是否LL(1)步骤：计算FIRST,FOLLOW集,GS:S-aSb|P P-bP P-Pc|Qc Q-aQ Q-aQ|,语法分析内容总结,FIRST(S)=a,bFIRST(P)=bFIRST(P)=a,bFIRST(Q)=aFIRST(Q)=a,FOLLOW(S)=b,$FOLLOW(P)=b,c,$FOLLOW(P)=b,c,$FOLLOW(Q)=cFOLLOW(Q)=c,GS:S-aSb|P P-bP P-Pc|Qc Q-aQ Q-aQ|,是LL(1)的,语法分析内容总结,例2 文法GE:E-T T-TE|F F-a|aF(1)判断这个文法是不是LL(1)的？(2)消除左递归、提取左因子之后的文法G是否是LL(1)的？,语法分析内容总结,例1 解答：提取左因子，消除左递归后 文法变为GE:E-T T-F T T-ET|F-aF F-F|,GS:E-TT-TE|F F-a|aF,语法分析内容总结,FIRST(E)=FIRST(T)=aFIRST(T)=,FIRST(F)=aFIRST(F)=a,FOLLOW(E)=,$FOLLOW(T)=,$FOLLOW(T)=,$FOLLOW(F)=FOLLOW(F)=,GE:E-T T-F T T-ET|F-aF F-F|,不是LL(1)文法！,通过提取左因子和消除左递归的方法，并不一定能够把文法改写为一个LL(1)文法,语法分析内容总结,左递归的消除 GS:S-Qc|c Q-Sa|a间接左递归,语法分析内容总结,左递归的消除 GS:S-Qc|c Q-Sa|a这是一类间接左递归 S-Sac|ac|c Q-Sa|a,语法分析内容总结,左递归的消除 GS:S-Qc|c Q-Sa|a间接左递归 S-Sac|ac|c Q-Sa|a S-acS|cS S-acS|Q-Sa|a,语法分析内容总结,自下而上分析部分知识点 SLR的DFA的构造及分析表的构成初始项目集合的产生（拓广文法）能够识别同一符号的项目都转移到同一集合中求闭包过程中每一个“.”后面的非终结符都要重新考虑是否已经在状态中列出对产生式A-规约，“ri”写在FOLLOW(A)集合中元素对应的位置。,语法分析内容总结,LR,LALR的构造方法（在SLR的基础上加上搜索符）搜索符的求法，根据造成目前项目出现的那个父项目来求。求闭包的过程中可能出现要添加的项目已经存在，但是搜索符不同的情况，相当于其父项目已经改变，此时需要再求一遍搜索符。SLR,LR,LALR的区别及判别方法通过构造DFA，看其中的状态是否有冲突（“移进规约”或“规约规约”）若有冲突则不属于该文法类型。通过构造分析表，看其中某项是否有冲突。,语法分析内容总结,文法GS:S-AaS|bAe|BeS|bBa A-d B-d 判断这个文法类型是SLR(1)、LR(1)还是LALR(1)？,补充题 1,下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法S S and S|S or S|not S|p|q|(S)非二义文法的产生式如下：E E or T|TT T and F|FF not F|(E)|p|q,补充题 1,下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法S S and S|S or S|not S|p|q|(S)非二义文法的产生式如下：E E or T|TT T and F|FF not E|(E)|p|q,补充题 1,下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法S S and S|S or S|not S|p|q|(S)非二义文法的产生式如下：E E or T|TT T and F|FF not E|(E)|p|qnot p and q有两种不同的最左推导,补充题 2,设计一个文法:字母表a,b上a和b的个数相等的所有串的集合二义文法：S a S b S|b S a S|aabbababaabbabab,补充题 2,设计一个文法:字母表a,b上a和b的个数相等的所有串的集合二义文法：S a S b S|b S a S|aabbababaabbabab二义文法：S a B|b A|A a S|b A AB b S|a B B aabbabab aabbabab,补充题 2,设计一个文法:字母表a,b上a和b的个数相等的所有串的集合二义文法：S a S b S|b S a S|abababab二义文法：S a B|b A|A a S|b A AB b S|a B BBB bSbS的选择 bbab bbab非二义文法：S a B S|b A S|A a|b A A aabbabab B b|a B B,补充题 3,试说明下面文法不是LR(1)的：L M L b|aM,补充题 4,下面的文法不是LR(1)的，对它略做修改，使之成为一个等价的SLR(1)文法program begin declist;statement enddeclist d;declist|dstatement s;statement|s,补充题 4,下面的文法不是LR(1)的，对它略做修改，使之成为一个等价的SLR(1)文法program begin declist;statement enddeclist d;declist|dstatement s;statement|s该文法产生的句子的形式是begin d;d;d;s;s;s end,补充题 4,下面的文法不是LR(1)的，对它略做修改，使之成为一个等价的SLR(1)文法program begin declist;statement enddeclist d;declist|dstatement s;statement|s该文法产生的句子的形式是begin d;d;d;s;s;s end当d在栈顶，“；”是下一个输入的时候不知该移进还是规约,补充题 4,下面的文法不是LR(1)的，对它略做修改，使之成为一个等价的SLR(1)文法program begin declist;statement enddeclist d;declist|dstatement s;statement|s该文法产生的句子的形式是begin d;d;d;s;s;s end修改后的文法如下：program begin declist statement enddeclist d;declist|d;statement s;statement|s,补充题 5,一个C语言的文件如下，第四行的if误写成fi：long gcd(p,q)long p,q;fi(p%q=0)return q;elsereturn gcd(q,p%q);基于LALR（1）方法的一个编译器的报错情况如下：parse error before return(line 5).是否违反了LR分析的活前缀性质,第三次上机,简易可视化非所见即所得的编辑器（类似latex的简单编辑器，允许输入上标、下标、括号等文本编辑、多行文本的编辑排版）知识点：编译原理中的词法分析、语法分析、翻译方案、属性计算、出错处理C+语言：类的封装、函数调用数据结构：栈的操作、递归,第三次上机,功能描述：用户在编辑状态输入需要编辑的公式，如 A2+7B_3+9*7等，然后选择软件提供的编译功能，软件对输入的公式进行分析，判断所输入的公式的语法是否正确，如果正确则输出公式的显示效果（在上面的例子中是：）,第三次上机,实现描述：本习题是编译原理的一道综合练习题，需要使用到词法分析、语法分析、翻译方案、属性计算、出错处理等多方面内容。在实现时需要用到C+语言中的类、函数调用等知识点，同时大量使用数据结构中的栈的操作。,