设有下列文法: (1)S→cA|ccB B→ccB|b A→cA|a (2)S→AaAb|BbBa B→ε A→ε 判断上述文法是否为LR(0)文法。若是,构造LR(0)分析表。若不是,说明理由。
时间: 2023-06-13 09:08:45 浏览: 311
首先说明一下LR(0)文法的定义:若对于文法G的任何产生式A→α,对于任何一个串x和任何一个非终结符B,都有α⋅x⋅B不能推导出一个以B开头的字符串,则称文法G是LR(0)文法。
对于第一道文法:
首先,我们需要求出该文法的所有LR(0)项集,然后根据项集构造LR(0)分析表。
求解过程如下:
1. 求出初始项集{S'→·S}。
2. 对于任何一个项集I,对于I中的每一个项A→α·Bβ,将B→γ加入I'中,并将I'作为I的后继项集。
3. 重复2步骤,直到没有新的项集可以被加入。
求解出来的所有项集为:
I0:
S'→·S
I1:
S'→S·
S→·cA
S→·ccB
I2:
S'→S·
S→c·A
A→·cA
A→·a
I3:
S'→S·
S→cc·B
B→·ccB
B→·b
I4:
S'→S·
S→cA·
A→·cA
A→·a
I5:
S→ccB·
B→·ccB
B→·b
I6:
A→c·A
A→·cA
A→·a
I7:
B→cc·B
B→·ccB
B→·b
I8:
B→b·
根据项集构造LR(0)分析表:
c a b $ S A B
0 s2 s4 s1
1 accept
2 s2 s4 s3
3 r2 r2
4 s2 s4 s5
5 r3 r3
6 s7 s4 s8
7 r1 r1
8 r4 r4
其中,si表示移入状态i,ri表示规约到产生式i的状态。
由于该文法的LR(0)分析表中没有冲突,因此它是LR(0)文法。
对于第二道文法:
初始项集为{S'→·S}。
对于S→AaAb和S→BbBa,它们的右部都有两个非终结符,因此无法直接进行规约,也就是说这个文法不是LR(0)文法。
阅读全文