语法分析程序的设计与实现.ppt

语法分析器的设计与实现自上而下的语法分析,阎艳naomi2010.11,编译原理实验2,语法分析器的实质（ch4.1）,功能：验证源程序是否符合语法规则。输入：词法分析器生成的单词符号序列-种别输出：语法分析树；如有错，则指明错误的性质和位置。,词法分析器,语法分析器,编译程序后续部分,符号表,语法分析器的分类,按照语法树的建立方法，分为自上而下分析法递归下降预测分析自下而上分析法算符优先,自上而下语法分析器的实现,1从语言定义中整理出语法规则,语法的定义,语法规则通常用上下文无关文法描述（ch2.5）,micro语言定义,仅有的数据类型是整型INT。所有的标识符采用显式声明，且长度不超过32个字符。标识符必须以字母开头并由字母、数字和下划线组成。整型常量由一串数字组成。注释由“-”开始，并在当前行尾结束。语句类型为：赋值语句：ID:=Expression；Expression是由标识符、文字常量、+-*/运算符组成的中缀表达式结构，其中允许含有括号。输入输出语句：read(ListofIDs);write(ListofExpressions);begin、end、read、write、INT都是保留字。每条语句以分号（;）结束。程序体由begin和end界定。词法记号不能跨行。,1从语言定义中整理出语法规则,/程序体由begin和end界定$begin$end/每条语句以分号（;）结束$semicolon|.,例1$begin$endboolprogram()symbol=scanner()；if(symbol=$begin)then/调用词法分析器获取下一个单词symbol=scanner()；if(statements()thenif(symbol=$end)returntrue;returnfalse;,例2$add|$sub|boolexpression(),expression()$addterm(),expression()$subterm(),term(),问题：左递归回溯解决：对语法规则加以限制自上而下的语法要求：LL(1)文法,自上而下语法分析器的实现,2将语法规则改造为LL(1)文法,LL(1)文法的条件,1）文法不含左递归2）对于文法中每个非终结符A的各产生式的候选首符集不相交。即若A1|2|n则FIRST(i)FIRST(j)=（ij)3）对文法中每一个终结符A，若它存在某个候选首符集包含，则FIRST(A)FLLOW(A)=,LL(1)文法消除左递归ch4.3.1,直接左递归的消除方法若AA|，其中不以A开头则修改规则为：AAAA|,LL(1)文法消除左递归ch4.3.1,消除左递归算法(解决间接左递归)对文法G的所有非终结符进行排序按上述顺序对每一个非终结符Pi依次执行:for(j=1；ji-1；j+)将Pj代入Pi的产生式（若可代入的话）；消除关于Pi的直接左递归；化简上述所得文法,将间接左递归转化为直接左递归,例3消除表达式语法规则的左递归$add|$sub|$mul|$div|$id|$num|$lpar$rpar,排序：EE$addE|$subE|TT$mulT|$divT|$id|$num|$lpar$rpar,LL(1)文法消除回溯,提左公因子（ch4.3.2）假定A1|2|n|1|2|m则，改写成AA|1|2|mA1|2|n,LL(1)文法消除回溯,对存在产生式的非终结符分析FIRST和FOLLOW（ch4.3.3),FIRST集的构造若XVT，则FIRST(X)=X。若XVN，且Xa，则把a加入到FIRST(X)中；若X，则把加入FIRST(X)中。若XY，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；若XY1Y2Yk，对任何j(1ji-1),FIRST(Yj)都含有(即Y1Yi-1*)，则把FIRST(Yi)中的所有非元素都加到FIRST(X)中；若所有的FIRST（Yj）均含有则把加到FIRST(X)中。,FOLLOW集的构造连续使用下面的规则，至每个FOLLOW不再增大：1）对于文法的开始符号S，置#于FOLLOW(S)中；2）若AB即是一个产生式，则把FIRST()加至FOLLOW(B)中；3）若AB是一个产生式，或AB即是一个产生式而（即FIRST()），则把FOLLOW(A)加至FOLLOW(B)中。,语法规则,micro语言定义,LL(1)文法,整理（手动）,改造（手动或自动）,自上而下语法分析器的实现,编程,语法分析（错误处理机制）,3编程实现语法分析算法,递归下降分析程序(ch4.4，P74-76),每一非终结符对应一个布尔子过程：if某个候选式与输入串匹配then按此式扩充语法树；指针移过已匹配子串；returntrue；elsereturnfalse。,可能存在的缺陷？效率，错误处理解决：非递归化预测分析,预测分析程序,数据结构栈预测分析表M,预测分析表的构造：（1）对文法G的每个产生式A执行第二步和第三步；（2）对于每个终结符aFIRST()，把A加到MA,a中；（3）若FIRST()，则对任何的bFOLLOW(A)把A加至Ma,b中；（4）把所有无定义的MA,a标上“出错标志”或“同步符号”,初始：#、文法开始符入栈,预测分析算法,根据STACK栈顶符号X和当前的输入符号a完成语法分析工作1)若X=a=#，则语法分析成功，停止分析过程。2)若X=a#，则X出栈，让a指向下一个输入符号。3)若X是一个非终结符，则查找分析表M。若MA，a中存放着关于X的一个产生式，则：先X出栈，然后将产生式的右部符号串按反序入栈。4)否则,完成相关的出错处理。,错误处理机制(ch4.6),目的遇到错误时，使语法分析程序可以继续下去。思想栈顶为非终结符：跳过输入符号至同步符号/栈顶为终结符号：弹出该终结符/跳过输入串/同步符号