能否提供Earley解析器优于LL(k)解析器的简易示例？

下面几个极简例子能直观体现Earley解析器相对于LL(k)的核心优势：

1. 直接处理左递归语法 #

LL(k)解析器天生无法处理左递归语法，比如最常见的表达式语法：

Expr → Expr + Num | Num
Num → 0 | 1 | 2 | ... | 9

LL解析器是自顶向下工作的，遇到Expr会优先尝试匹配Expr + Num，导致无限递归调用Expr，必须先手动改写语法消除左递归（比如改成右递归或引入辅助非终结符）才能处理。

而Earley解析器完全不需要改写，直接就能解析这种符合直觉的左递归语法，省去了语法改写的额外工作量。

2. 处理需要无限向前看的语法 #

假设有这样的无歧义语法：

S → A | B
A → a^n b^n （n ≥ 1，即任意数量的a后跟相同数量的b）
B → a^n c^n （n ≥ 1，即任意数量的a后跟相同数量的c）

当解析一串连续的a时，LL(k)不管你把k设多大，都无法提前判断后面跟着的是b还是c——如果a的数量超过k，LL(k)就会因为无法预知足够多的后续符号而失败。

Earley解析器则可以逐步处理每一个a，直到遇到b或c时再完成对应的推导，完美适配这种需要"无限向前看"的场景。

3. 自然处理歧义语法 #

比如经典的歧义表达式语法：

Expr → Expr + Expr | Expr * Expr | Num
Num → 0 | 1 | ... | 9

LL(k)解析器处理歧义语法要么需要手动添加优先级/结合性规则消除歧义，要么会陷入回溯的低效困境。而Earley解析器可以在解析过程中保留所有可能的推导路径，自然生成所有可能的语法树，不需要额外规则干预就能处理歧义场景。

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