2014小型编译程序的构造讲解.ppt

* * * * * * * * 最终改造后的文法为： P →{DS} D →int ID ;{int ID;} S→if (B) then S [else S ] | while (B) do S | { L } | ID=E L→SL’ L’ →; L | ? B→T’ {∨T’} T’ →F’ {∧ F’ } F’ →ID relop ID | ID E→T{+T| -T} T→F{* F | /F } F→ (E) | NUM | ID 注意：红颜色的｛｝是终极符． 　　　黑颜色的｛｝和［］不是终极符． 　　　 * 自顶向下语法分析 5. 递归子程序语法分析方法 递归子程序法，又称递归下降分析法。思想是：非终极 符的文法规则可看成是识别该非终极符的过程定义，针对文 法的每一非终极符，根据相应产生式各候选式的结构，为其 编写一个递归函数，用来识别该非终极符所表示的语法范畴。 递归下降分析法是一种确定的自顶向下的语法分析方法，其分析过程是从文法开始符号出发，执行一组递归过程，不断向下推导，直到推出句子。 * 自顶向下语法分析 为了构造递归子程序，有如下的约定和要注意的问题： (1)文法必须是LL（1）文法。 (2)待匹配符号串是要被分析的源程序，是用助记符或整数码表示的单词类别串。 例如待匹配符号串“ ID:=ID+NUM# ”，按从左向右扫描输入串的顺序，开始的时候，当前匹配指针指向的输入符号是“ID”。 (3)设辅助函数getsym()的作用是读取当前指针指向的待匹配符，并使待匹配指针向前移，指向下一个待匹配符。变量sym用来存储当前匹配指针指向的输入符号。 (4)进入子程序时已经取到了当前的输入符号；从子程序返回时，也已经取到了下一次准备匹配的输入符号。 * 自顶向下语法分析 为了构造递归子程序，有如下的约定和要注意的问题： (5) 如果遇到非终极符，则直接调用该非终极符对应的子程序。如果非终极符A的右部只有一个候选式，则按从左向右的顺序依次构造A的识别过程。 如果遇到终极符，判断是否与输入的符号匹配。若匹配，则读取下一个待匹配符号；如果匹配失败，则意味着有语法错误。 (6)如果非终极符A的右部有多个候选式，则根据每个候选式的第一个符号确定识别非终极符A的流程控制转向。 * 例：文法Z→(U)| aUb ，U → dZ|e，为其构造递归下降分析子程序。并对输入串aeb进行语法分析 。 自顶向下语法分析 解： 文法中有两个非终结符号Z和U，需要分别编两个函数来完成Z和U规则的识别。 对于规则Z→(U)|aUb，右部有两个候选式，因此，U的识别过程有两个分支，分别根据符号( 和 a 来判别。 同理对规则U→dZ|e 设计的过程也分为两个分支。见图(a)和(b)所示。 * Z →(U)|aUb 图(a) 非终结符号Z的分析程序 过程Z sym= getsym() U 出口 语法错误： 输入串少‘)’ sym =‘a’ Y N N N N Y Y 语法错误： 输入串少‘(’、‘a’ 语法错误： 输入串少‘b’ sym =‘(’ sym =‘)’ sym =‘b’ sym= getsym() sym= getsym() U Y 对输入串aeb进行语法分析 * U → dZ|e 过程U sym= getsym() Z 出口 sym =‘e’ Y N N Y 语法错误： 输入串少‘d’、‘e’ sym= getsym() Y 图(b) 非终结符号U的分析程序 sym =‘d’ 对输入串aeb进行语法分析 * U → dZ|e 每个非终结符对应的函数设计好后，就可以对输入串进行语法分析。 假设输入串为aeb, 从Z函数开始识别，由于sym不等于(，等于a，所以选择Z函数的右边分支，表示选择了Z→aUb规则。读下一个符号，使sym=e; 调U函数，因sym=e，表示使用U→e 规则, 读下一个符号，使sym=b，并返回调用程序Z函数右边分支U的下方，接着判断sym=b，读下一个符号，并退出Z. 在主函数中判断:若sym=#,则分析过程结束，从而判定输入串aeb语法分析成功。 这个过程相当于构造了如下推导过程：Z=aUb=aeb Z →(U)|aUb 对输入串aeb#进行语法分析 * 递归子程序语法分析方法 再如:　　L’ →; L | ? 　　L’()　　 { if(sym==‘;’) { 读下一个待匹配符=sym; L();