如何对指定含左递归的文法进行完全左因子化适配自上而下编译器？

首先先明确你给出的原始文法：

S → ABAC | ACAB
A → Ax | Ay
B → Bxx | Byy
C → xy | yx

第一步：先修正文法的合法性问题 #

得提个醒：你给出的A和B的产生式只有左递归推导，没有基础产生式（也就是能直接推导出终结符或空串的产生式）。这样的话，A和B永远无法推导出有限长度的终结符串，文法是不合法的。我先假设你是笔误，比如A应该是A → Ax | Ay | ε（允许空串）或者A → x | y | Ax | Ay（基础是单个终结符），下面的操作我会基于A → x | y | Ax | Ay和B → xx | yy | Bxx | Byy来演示，这样文法才有实际意义。

第二步：消除直接左递归 #

直接左递归的消除逻辑是：对于形如 X → Xα | β（β不以X开头）的产生式，替换为：

X → β X'
X' → α X' | ε

处理非终结符A

原始修正后的A产生式：A → x | y | Ax | Ay
这里β是x和y，α是x和y，拆分后得到：

A → x A' | y A'
A' → x A' | y A' | ε

处理非终结符B

原始修正后的B产生式：B → xx | yy | Bxx | Byy
这里β是xx和yy，α是xx和yy，拆分后得到：

B → xx B' | yy B'
B' → xx B' | yy B' | ε

第三步：对S进行左因子化 #

自上而下分析要求文法没有左递归，同时也不能有左因子（也就是同一个非终结符的多个产生式不能有相同的前缀）。看S的产生式：S → ABAC | ACAB，两个产生式的前缀都是A，所以需要提取公共前缀：

1. 提取公共前缀A，将S改写为：

S → A S'

2. 把两个产生式剩下的差异部分作为新非终结符S'的产生式：

S' → BAC | CAB

第四步：最终适配自上而下分析的文法 #

把所有修改整合起来，最终的文法是：

S → A S'
S' → BAC | CAB
A → x A' | y A'
A' → x A' | y A' | ε
B → xx B' | yy B'
B' → xx B' | yy B' | ε
C → xy | yx

额外补充 #

• 如果你的原始文法中A和B的基础产生式是ε（空串），处理后的A和B会是：

  A → ε A'
  A' → x A' | y A' | ε
  

  这种情况A可以推导出任意数量的x/y组合，和修正后的版本逻辑一致，只是写法不同。
• 左因子化的核心就是提取公共前缀，把不同的后缀交给新的非终结符处理，这样自上而下分析时遇到公共前缀不会出现回溯。

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