实验二 编写语法分析程序

1、实验二 编写语法分析程序2.1 实验类型设计型实验，6学时(2学时完成文法改造； 2学时完成程序编码；2学时完成程序测试)2.2 实验目的通过设计、编写、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握递归下降语法分析方法。2.3 背景知识2.3.1 递归下降分析自顶向下语法分析过程中，如果产生回溯，则分析过程需要穷举所有可能的推导，看是否能推导出待检查的单词序列，导致分析程序时间和空间开销增大，降低分析效率。而无回溯的自顶向下分析技术可根据输入串的当前单词，选择唯一的产生式构造推导过程，从而提高分析效率。无回溯的自顶向下分析要求文法是LL(1)文法

2、。递归下降分析程序的实现思想是：(1) 分析程序由一组子程序组成，每个子程序对应于一个非终结符号。(2) 每一个子程序的功能：选择正确的产生式右部，扫描相应的单词；产生式右部有非终结符号时，调用该非终结符号对应的子程序来完成。2.3.2 LL(1)文法LL(1)文法满足以下三个条件：（1）文法不含左递归 （2）文法的任何一个非终结符A的各个产生式的右部符号串的FIRST集两两不相交，即： 若有A1|2|n ，则 FIRST (ai) FIRST (aj) = (i j，1i,jn) （3）文法的任何一个非终结符A,若有A1|2|n且存在ai ，有 FIRST (i)，则 FIRST (j) F

3、OLLOW (A) = （ i j， j=1,2,. . .,n ）2.3.3 文法改造1、消除直接左递归（将左递归改为右递归）：直接左递归形式：UUx|y；其中：x，y(VNVT)* ，y不以U打头。直接左递归的消除：UyU UxU|直接左递归的一般形式：UUx1|Ux2|Uxm|y1|y2|yn；其中：xi ,yi都不以U打头。一般形式直接左递归的消除:Uy1U| y2U | ynU Ux1U| x2U| | xmU|2、消除间接左递归：要求无环路（形如A+ A的推导）和无-产生式。 （1）把非终结符按某一顺序排序为A1,A2An 。 （2）for(i=1;i=n;i+) for(j=1;

4、j=i-l;j+) if(Aj1|2|k ,AiAj) 把AiAj改写成 Ai1|2|k; 消除关于Ai产生式的直接左递归; （3）化简由（2）所得到的文法。（4）化简改写之后的文法，删除多余产生式。 3、提取左公因子 Aab1|ab2 |abn |1 |m改写成:AaA|1 |m Ab1|b2 |bn2.3.4递归下降分析程序的基本架构定义：变量：ch，为当前符号；函数：READ(ch)：读输入串下一符号；对于每个非终结符号U 1| 2| n处理的方法如下：U（）if chFIRST(1 ) then P(1) /处理1的程序部分。 else if chFIRST(2 ) then P(2)

5、 /处理2的程序部分。 else if chFIRST(n ) then P(n) else if chFOLLOW(U) then return /处理产生式情况。 else error 对于每个右部 =x1x2xn的处理架构如下：P( )P(x1 ); /处理x1的程序。P(x2 ); /处理x2的程序。 P(xn ); /处理xn的程序。对于右部中的每个符号xi；如果xi为终结符号：if(ch= a) READ (ch)else error如果xi为非终结符号，直接调用相应的过程：P (xi)。2.3.5编写递归下降分析程序一般步骤1) 改写文法，消除二义性；2) 消除左递归、提取左因子

6、；3) 求FIRST集、FOLLOW集；4) 检查是不是 LL(1) 文法， 若不是 LL(1)，说明文法的复杂性超过自顶向下方法的分析能力（对文法的改造会影响文法的可读性，可以采用超前读一个单词的来处理）。5) 直接根据产生式设计相应的程序2.4 实验内容1、语法规则TEST语言的语法规则如下：1) 2) | 3) int ID;4) | 5) | | |6) if () | if () else 7) while () 8) for (;)9) write ;10) read ID;11)12);|;13) ID=|14) |(|=|=|=|!=) 15)+|-| 16)*|/|17)()

7、|ID|NUM2、要求：根据递归下降分析方法，完成TEST语言的递归下降语法分析程序的构造，主要完成：(1) 改造文法，使之满足无回溯的递归下降分析条件，给出改写后的文法（写入实验报告）；说明：A、规则6能否提取左公因子？如果提取后会有什么后果？分析原因后给出你的处理方案。B、规则13可以采用采用超前读一个单词来解决，避免对该规则进行改写，保持文法的可读性。C、红色标注的文法均需要进行改写。D、对改写后的文法，计算所有右部符号串的FIRST集合；如有产生式，计算该产生式左部非终结符的FOLLOW集。(2) 编写递归下降分析程序；（将，的程序流程图写入实验报告）(3) 使用下述的TEST语言代码测试编写的递归下降分析程序（先使用实验一的词法分析程序进行词法分析，要求标识符类别记为ID，整数记为NUM，其它单词采用单词本身，比如int的类别就是int，=的类别就是+）。int a;int i;int b,c;for (i=1; i b) write a;else write b;w