首页 > 试题广场 >

以下文法 G2 是否为 LL(1) 的？如不是，适当修改该文

[问答题]
以下文法 G2 是否为 LL(1) 的？如不是，适当修改该文法，使之成为 LL(1) 的。
A 是开始符号。
A → B a
B → d a b B → C b
C → c B C → A c
添加回答
阿奻_头像 阿奻_
显然该文法含有左递归：A=>B a=>C b a=>A c b a 。因此该文法不是 LL(1) 的。
文法修改过程如下：
A 带入 C ，得到 C → c B C → B a c
C 带入 B ，得到 B → d a b | c B b | B a c b
除 消除 B 的直接左递归：
B → d a b E | c B b E
E → a c b E
E → 注：此为空产生式
知 可知 B 产 生串：(dab|cBb)(acb)*
而 而 A 产生的串：(dab|cBb)(acb)*a = (dab|cBb)a(cba)*
的 因此，可重新给出的 A 的产生式如下：写 （重写 A 的串组成方式，主要消除来 原来 Follow(B)
含 中含 a 的情况，否则在 E 的 两个 产生式 均在 出现在 a 的名下，而 那样合 不符合 LL(1)） 文法要求！）
A → d a b a D | c B b a D
D → c b a D
D → 注：此为空产生式
足 最终修改后的文法如下，满足 LL(1) 文法特征：
A → d a b a D | c B b a D
D → c b a D
D → 注：此为空产生式
B → d a b E | c B b E
E → a c b E
E → 注：此为空产生式
发表于 2017-05-01 17:52:23 回复(0)
提交观点

问题信息

编译和体系结构
上传者：阿奻_
难度：
1条回答 2978浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号