语法分析程序的设计与实现ppt课件
语法分析器的设计与实现自上而下的语法分析,阎 艳 2010.11,编译原理实验2,语法分析器的实质（ch4.1）,功能：验证源程序是否符合语法规则。 输入：词法分析器生成的单词符号序列-种别 输出：语法分析树；如有错，则指明错误的性质和位置。,词法分析器,语法分析器,编译程序后续部分,符号表,语法分析器的分类,按照语法树的建立方法，分为 自上而下分析法 递归下降 预测分析 自下而上分析法 算符优先,自上而下语法分析器的实现,1 从语言定义中整理出语法规则,语法的定义,语法规则 通常用上下文无关文法描述（ch2.5）,micro语言定义,仅有的数据类型是整型INT。 所有的标识符采用显式声明，且长度不超过32个字符。标识符必须以字母开头并由字母、数字和下划线组成。 整型常量由一串数字组成。 注释由“-”开始，并在当前行尾结束。 语句类型为： 赋值语句：ID := Expression；Expression是由标识符、文字常量、+ - * / 运算符组成的中缀表达式结构，其中允许含有括号。 输入输出语句：read( List of IDs);write(List of Expressions); begin、end、read、write、INT都是保留字。 每条语句以分号（;）结束。程序体由begin和end界定。 词法记号不能跨行。,1 从语言定义中整理出语法规则,/程序体由begin和end界定 $begin $end /每条语句以分号（;）结束 $semicolon | | | | | .,例1 $begin $end bool program() symbol=scanner()； if ( symbol = $begin) then /调用词法分析器获取下一个单词 symbol=scanner()； if ( statements() ) then if ( symbol = $end) return true; return false; ,例2 $add | $sub | bool expression() ,expression() $add term(),expression() $sub term(),term(),问题：左递归 回溯 解决：对语法规则加以限制 自上而下的语法要求：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； j< i-1；j+) 将Pj代入Pi的产生式（若可代入的话）； 消除关于Pi的直接左递归； 化简上述所得文法,将间接左递归转化为直接左递归,例3 消除表达式语法规则的左递归 $add | $sub | $mul | $div | $id | $num | $lpar $rpar,排序： E E $add E | $sub E | T T $mul T | $div T | $id | $num | $lpar $rpar,LL(1)文法消除回溯,提左公因子（ch4.3.2） 假定 A 1| 2| |n| 1| 2| |m 则，改写成 A A| 1| 2| |m A 1 | 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 按此式扩充语法树； 指针移过已匹配子串； return true； else return false。,可能存在的缺陷？ 效率，错误处理 解决：非递归化预测分析,预测分析程序,数据结构 栈 预测分析表M,预测分析表的构造： （1）对文法G的每个产生式A执行第二步和第三步； （2）对于每个终结符aFIRST()，把A加到MA,a中； （3）若FIRST() ，则对任何的b FOLLOW(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),目的 遇到错误时，使语法分析程序可以继续下去。 思想 栈顶为非终结符：跳过输入符号至同步符号/ 栈顶为终结符号：弹出该终结符 / 跳过输入串/ 同步符号 FOLLOW集 ,语法规则,micro语言定义,LL(1)文法,整理 （手动）,自上而下语法分析器的实现,语法分析 （错误处理机制）,4 用正例和反例对语法分析程序进行测试,单词序列,词法分析器,输入字符,源程序,编程实现 -自动语法分析器,文档存储,语法分析结果,
