编译原理:已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法
时间: 2023-06-20 08:04:47 浏览: 98
要判断该文法是否是SLR(1)文法,需要进行以下步骤:
1. 构造该文法的LR(0)自动机,并求出LR(0)项集族和对应的转移表。
2. 对每个LR(0)项集,求出它的闭包和GOTO集合。
3. 对于每个非终结符A和每个终结符a,求出它们的FOLLOW集。
4. 对于每个LR(0)项集I和每个终结符a,求出ACTION[I, a]和GOTO[I, A]的值。
5. 判断文法是否是SLR(1)文法。对于每个LR(0)项集I和每个终结符a,如果ACTION[I, a]和GOTO[I, A]同时存在冲突,且冲突中至少有一项是移进-归约冲突,那么该文法就不是SLR(1)文法。
下面是具体的步骤:
1. 构造LR(0)自动机:
起始状态:[S' -> .A] (S'是起始符号)
状态1:[A -> .fAa, A -> .fAg]
状态2:[A -> f.Aa, A -> f.Ag]
状态3:[A -> fA.a, A -> fAg.]
状态4:[A -> fAg.]
状态5:[A -> fA.a]
状态6:[A -> f.Ag]
状态7:[A -> b.]
2. 对每个LR(0)项集,求出它的闭包和GOTO集合:
闭包({[S' -> .A]}) = {[S' -> .A], [A -> .fAa, A -> .fAg]}
GOTO({[S' -> .A]}, f) = {[A -> f.Aa, A -> f.Ag]}
GOTO({[S' -> .A], [A -> .fAa, A -> .fAg]}, a) = {[A -> fA.a]}
GOTO({[S' -> .A], [A -> .fAa, A -> .fAg]}, g) = {[A -> fAg.]}
GOTO({[A -> f.Aa, A -> f.Ag]}, a) = {[A -> fA.a]}
GOTO({[A -> f.Aa, A -> f.Ag]}, g) = {[A -> fAg.]}
GOTO({[A -> fA.a]}, a) = {}
GOTO({[A -> fAg.]}, a) = {}
GOTO({[A -> fA.a]}, g) = {[A -> f.Ag]}
GOTO({[A -> f.Ag]}, a) = {}
GOTO({[A -> f.Ag]}, g) = {[A -> fAg.]}
3. 对于每个非终结符A和每个终结符a,求出它们的FOLLOW集:
FOLLOW(A) = {a, g}
FOLLOW(f) = {a, g}
FOLLOW(g) = {a, b}
4. 对于每个LR(0)项集I和每个终结符a,求出ACTION[I, a]和GOTO[I, A]的值:
ACTION[{[S' -> .A]}, f] = {[A -> f.Aa, A -> f.Ag]}
ACTION[{[S' -> .A], [A -> .fAa, A -> .fAg]}, a] = {[A -> fA.a]}
ACTION[{[S' -> .A], [A -> .fAa, A -> .fAg]}, g] = {[A -> fAg.]}
ACTION[{[A -> f.Aa, A -> f.Ag]}, a] = {[A -> fA.a]}
ACTION[{[A -> f.Aa, A -> f.Ag]}, g] = {[A -> fAg.]}
ACTION[{[A -> fA.a]}, a] = {[A -> fAa]}
ACTION[{[A -> fA.a]}, g] = {[A -> f.Ag]}
ACTION[{[A -> f.Ag]}, a] = {}
ACTION[{[A -> f.Ag]}, g] = {[A -> fAg.]}
GOTO集合已经在步骤2中求出。
5. 判断文法是否是SLR(1)文法:
根据步骤4中求出的ACTION和GOTO,可以看出该文法没有移进-归约冲突,但存在归约-归约冲突(ACTION[{[A -> fA.a]}, a]和ACTION[{[A -> fAg.]}, a]同时存在)。因此,该文法不是SLR(1)文法。
阅读全文