精品文档

I1: S′?S· SaAbI2: S?a· S?a·Ab A?·1A0 ? A?·I4: S?aA·b AI8: S?aAb· I9: A?1A·0 01I5: A?1·A0 A?·1A0 ? A?·1I12: A?1A0· I0: S′?·S S?·a S?·aAb S?·b S?·bBa BbI3: S?b· S?b·Ba B?·1B0 ? B?·I6: S?bB·a aBI10: S?bBa· I11: B?1B·0 011I7: B?1·B0 B?·1B0 ? B?·I13: B?1B0· 项目集族和DFA

1、w a b + c d e 10 - / + 8 + * +

2、abcd-*e/+

3、abc+e*bc+f/+:= 4、4231

5、句子b(aa)b的规范归约过程： 步骤 0 1 2 3 4 5 6 7 8 9 10 6、消除左递归

S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF | +a

# #b #b( #b(a #b(A #b(Ma #b(Ma) #b(B #bA #bAb #S 符号栈 输入串 b(aa)b# (aa)b# aa)b# a)b# a)b# )b# b# b# b# # # 预备 移进 移进 移进 归约 移进 移进 归约 归约 移进 接受 动作 精品文档