编译原理compiler4.pptVIP

本章目的 描述程序语言的语法结构，需借助于上下文无关文法。文法是描述程序语言的依据，也是编译的依据。识别上下文无关文法所生成的语言的方法是语法分析的关键。本章的目的是研究这些方法。 三、消除左递归 产生式 其中b不以A为前缀。这是直接左递归形式，它产生的符号串为ba*结构。引进非终结符A’，令 它同样产生ba*形符号串，所以与(4.3)等价，但是它不是左递归的。 更一般些对 的等价文法为 消除左递归后，为 消除间接左递归的算法 (1) 将文法G的所有非终结符按一给定的顺序排序； (2) for(i＝1；i=n；i++) for(j＝1；j=i-1；j++) { 4.1消除下列文法 S-(L)|a L-L,S|S 中左递归，构造递归下降分析器；写出句子(a,(a,a))的分析过程;它是不是LL(1)文法？请构造预测分析表。 (1).消除左递归后产生式为: S-(L)|a L-SL’ L’-,SL’|ε (2).构造递归下降分析器如下: void match(token t) { if (lookahead == t ) { lookahead = nexttoken; } else { error(); } } 2．void L’() { if ( lookahead == ‘,’ ) { match(‘,’); S(); L’(); } } 3. void S() { if ( lookahead == ‘(‘ ) { match(‘(‘); L(); If (lookahead == ‘)’ ) {match( ‘)‘};} else{error();} } elseif ( lookahead == ‘a‘ ) {match(‘a’);} else { error(); }; } 4. void L() { S(); L’(); } (3).句子(a,(a,a))的分析过程如下: S( )中匹配字符 ‘(‘ 成功。 调用L( ) L( )中调用S( ) S( )中匹配a成功，然后读入下一个字符’,’。 这一步我不知道如何描述了，因为我用C语言写的递归下降分析器根本不可能调用L’()函数，却只是在S()与L()之间来回调用。请老师告诉我如何修改递归下降分析器，使它可以分析句子(a,(a,a))，谢谢。 (4).它是LL(1)文法。 (5).构造预测分析表 a(),$SS-aS-(L)LL-SL’L-SL’L’L’-εL’-,SL’ [例4.7] 如果输入串为i+i*i，按图4.4的分析表，分析过程如图4.7所列。 注意到有限集可用成员表来表示的事实，如全集E={a,b,c,d}，集合A={a,c,d}，集合B={b,c}，则可用下表来表示集合A,B： 如果例4.8的FIRST集和FOLLOW集也用成员表来表示（当然，FIRST集的全集为VT∪{ε}，FOLLOW集的全集为VT∪{$}，其中VT为终结符集），则按算法求取相应集合的过程，可分别用图4.8之(a)、(b)表来表示： 其中，数字x分别表示引用相应求取FIRST集、FOLLOW集算法的第x规则。鉴于求FOLLOW集的规则2依赖于FIRST集，因此将二张表用一张表表示，可能会更方便些。这时，表中用√表示FIRST集的成员，○表示FOLLOW集的成员，于是有图4.9，当然它忽略了过程，只表示了结果。 三、LL(1)文法 上下文无关文法G，任一非终结符A的产生式设为 (1) ，当 时，i,j=1,2,…,n； (2) 若 ，则 ，j=1,…n， 且 。 则称G是LL(1)文法。 四、预测分析表的构造 对文法的每个产生式 (1) 对每个 ，将 记入M[A, a]中； (2) 若 ，则对任何 ，把 记入M[A, b] (3) 凡无定义的M[A,