正则表达式a*a转LL(1)解析器匹配输入aaa失败问题咨询

问题根源 #

你构造的文法本身不符合LL(1)文法的要求，存在预测分析表冲突：

• 非终结符A的两个候选式：A→aA的FIRST集为{a}，A→ε的FOLLOW集为{a, $}
• 两者存在公共元素a，意味着当输入字符为a时，A有两个合法的产生式可选：要么继续匹配a*，要么退出a*匹配，把当前a留给产生式S→Aa末尾的a
  你之前构建预测分析表时，直接给[A,a]填了A→aA，默认走贪心匹配a*的逻辑，才会把输入里的3个a全部匹配完，最后末尾的模式a没有剩余输入可匹配，触发错误。

解决方案 #

方案1：改写文法消除LL(1)冲突 #

你的正则模式a*a本身和aa*是完全等价的，两者都匹配「至少1个a」的规则，你可以把产生式改写为：

S → aA  # 先匹配必须存在的1个a
A → aA | ε # 再匹配剩下0个或多个a

对应的预测分析表不存在任何冲突：

匹配aaa的执行步骤如下：

0: S$    aaa$  # 用[S,a]规则S→aA
1: aA$   aaa$  # 匹配'a'，指针后移
2: A$    aa$   # 用[A,a]规则A→aA
3: aA$   aa$   # 匹配'a'，指针后移
4: A$    a$    # 用[A,a]规则A→aA
5: aA$   a$    # 匹配'a'，指针后移
6: A$    $     # 用[A,$]规则A→ε
7: $     $     # 匹配成功

方案2：保留原文法，处理预测表冲突 #

如果你要保留原有的S→Aa结构，就需要在构建预测分析表遇到[A,a]的冲突时，补充判断逻辑：如果当前A的后继字符和输入字符一致，优先选择A→ε退出a*匹配，把字符留给后续规则。但这种方式本质是破坏了标准LL(1)的匹配逻辑，仅适合单一场景，通用性差。

内容的提问来源于stack exchange，提问作者hackape