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

语法分析器的设计与实现自上而下的语法分析阎艳[e-mail]2010.11编译原理实验2——语法分析器的实质（ch4.1）•功能：验证源程序是否符合语法规则。•输入：词法分析器生成的单词符号序列---种别•输出：语法分析树；如有错，则指明错误的性质和位置。词法分析器语法分析器编译程序后续部分符号表源程序单词符号取下一个单词符号语法分析语法分析器的分类按照语法树的建立方法，分为•自上而下分析法递归下降预测分析……•自下而上分析法算符优先……语法规则micro语言定义整理自上而下语法分析器的实现1从语言定义中整理出语法规则语法的定义•语法规则–通常用上下文无关文法描述（ch2.5）micro语言定义•仅有的数据类型是整型INT。•所有的标识符采用显式声明，且长度不超过32个字符。标识符必须以字母开头并由字母、数字和下划线组成。•整型常量由一串数字组成。•注释由“--”开始，并在当前行尾结束。•语句类型为：1.赋值语句：ID:=Expression；Expression是由标识符、文字常量、+-*/运算符组成的中缀表达式结构，其中允许含有括号。2.输入输出语句：read(ListofIDs);write(ListofExpressions);•begin、end、read、write、INT都是保留字。•每条语句以分号（;）结束。程序体由begin和end界定。•词法记号不能跨行。1从语言定义中整理出语法规则//程序体由begin和end界定•program→$beginstatements$end//每条语句以分号（;）结束•statements→stmt$semicolonstatements|ε•stmt→declare_smt|assign_smt|read_smt|write_smt|ε•…..例1program→$beginstatements$endboolprogram(){symbol=scanner()；if(symbol==$begin)then{//调用词法分析器获取下一个单词symbol=scanner()；if(statements())then{if(symbol==$end){returntrue;}}returnfalse;}例2expression→expression$addterm|expression$subterm|termboolexpression(){}expression()$addterm()expression()$subterm()term()问题：左递归回溯解决：对语法规则加以限制自上而下的语法要求：LL(1)文法语法规则micro语言定义LL(1)文法整理（手动）改造（手动或程序实现）自上而下语法分析器的实现2将语法规则改造为LL(1)文法LL(1)文法的条件1）文法不含左递归2）对于文法中每个非终结符A的各产生式的候选首符集不相交。即若A1|2|…|n则FIRST(i)FIRST(j)=（ij)3）对文法中每一个终结符A，若它存在某个候选首符集包含，则FIRST(A)FLLOW(A)=LL(1)文法——消除左递归ch4.3.1•直接左递归的消除方法若A—＞Aα|β，其中β不以A开头则修改规则为：A—＞βA′A′—＞αA′|εLL(1)文法——消除左递归ch4.3.1消除左递归算法(解决间接左递归)•对文法G的所有非终结符进行排序•按上述顺序对每一个非终结符Pi依次执行:–for(j=1；ji-1；j++)»将Pj代入Pi的产生式（若可代入的话）；–消除关于Pi的直接左递归；•化简上述所得文法将间接左递归转化为直接左递归例3消除表达式语法规则的左递归expression→expression$addterm|expression$subterm|termterm→term$mulfactor|term$divfactor|factorfactor→$id|$num|$lparexpression$rpar排序：expressiontermfactorexpression→termE’E’→$addtermE’|$subtermE’|εterm→factorT’T’→$mulfactorT’|$divfactorT’|εfactor→$id|$num|$lparexpression$rparLL(1)文法——消除回溯•提左公因子（ch4.3.2）假定A1|2|…|n|1|2|…|m则，改写成AA’|1|2|…|mA’1|2|…|nLL(1)文法——消除回溯•对存在产生式的非终结符分析FIRST和FOLLOW（ch4.3.3)FIRST集的构造•若X∈VT，则FIRST(X)={X}。•若X∈VN，且Xa…，则把a加入到FIRST(X)中；若Xε，则把ε加入FIRST(X)中。•若XY…，则把FIRST(Y)中的所有非ε-元素都加到FIRST(X)中；•若XY1Y2…Yk，对任何j(1≤j≤i-1),FIRST(Yj)都含有ε(即Y1…Yi-1*ε)，则把FIRST(Yi)中的所有非ε元素都加到FIRST(X)中；若所有的FIRST（Yj）均含有ε则把ε加到FIRST(X)中。FOLLOW集的构造连续使用下面的规则，至每个FOLLOW不再增大：1）对于文法的开始符号S，置#于FOLLOW(S)中；2）若A→αBβ即是一个产生式，则把FIRST(β)＼{ε}加至FOLLOW(B)中；3）若A→αB是一个产生式，或A→αBβ即是一个产生式而β→ε（即ε∈FIRST(β)），则把FOLLOW(A)加至FOLLOW(B)中。语法规则micro语言定义LL(1)文法整理（手动）改造（手动或自动）自上而下语法分析器的实现编程语法分析（错误处理机制）3编程实现语法分析算法递归下降分析程序(ch4.4，P74-76)每一非终结符对应一个布尔子过程：if某个候选式与输入串匹配then按此式扩充语法树；指针移过已匹配子串；returntrue；elsereturnfalse。可能存在的缺陷？效率，错误处理…解决：非递归化——预测分析预测分析程序数据结构•栈•预测分析表M预测分析表的构造：（1）对文法G的每个产生式A执行第二步和第三步；（2）对于每个终结符aFIRST()，把A加到M[A,a]中；（3）若FIRST()，则对任何的bFOLLOW(A)把A加至M[a,b]中；（4）把所有无定义的M[A,a]标上“出错标志”或“同步符号”初始：‘#’、文法开始符入栈预测分析算法根据STACK栈顶符号X和当前的输入符号a完成语法分析工作1)若X=a=‘#’，则语法分析成功，停止分析过程。2)若X=a≠‘#’，则X出栈，让a指向下一个输入符号。3)若X是一个非终结符，则查找分析表M。若M[A，a]中存放着关于X的一个产生式，则：先X出栈，然后将产生式的右部符号串按反序入栈。4)否则,完成相关的出错处理。错误处理机制(ch4.6)•目的遇到错误时，使语法分析程序可以继续下去。•思想栈顶为非终结符：跳过输入符号至同步符号/…栈顶为终结符号：弹出该终结符/跳过输入串/…•同步符号FOLLOW集…语法规则micro语言定义LL(1)文法整理（手动）自上而下语法分析器的实现语法分析（错误处理机制）4用正例和反例对语法分析程序进行测试单词序列词法分析器输入字符源程序编程实现----自动语法分析器文档存储语法分析结果