编译原理作业7答案
发布时间:2012-12-02 14:48:27
发布时间:2012-12-02 14:48:27
软件学院 2012秋季学期
《编译原理》第七次作业参考答案
一、 证明下列文法
S Aa | bAc | dc | bda
A d
是LALR(1)文法但不是SLR(1)文法.
构造LR(1)自动机(没有需要合并的状态):
没有状态存在冲突,因而是LALR(1)文法.
构造LR(0)自动机:
在状态I6,由于’a’∈FOLLOW(A),因而对于SLR(1)分析而言,存在移进-归约,所以这一文法不是SLR(1)文法.
二、 证明下列文法
S Aa | bAc | Bc | bBa
A d
B d
是LR(1)文法但不是LALR(1)文法.
略.
三、 (附加题,选做)类似LL(1)文法,我们很容易给出LL(k)文法的定义. 对于一个上下文无关文法,如果递归下降分析器(recursive-descent parser)每次都可以通过向前看k个符号来确定选用哪一个产生式而不需要回溯,这一文法便称为LL(k)文法. 试构造一个无左递归且无二义的文法,使得对任意固定的k,这一文法都不是LL(k)文法.
S A | B
A aA | a
B aB | b