General Parsing (GLL/GLR) at a Glance

参考：Practical GeneralTop-down Parsers, by Ali Afroozeh and Anastasia Izmaylova

---

所谓 General Parsing，就是指能 parse general CFLs，意味着：

• 我不需要像 $LL(k)$ 或者 $LR(k)$ 那样先针对 grammar 做一些预处理 (see Appetizers Before Parsing: Serving Order)
• 我不怕 $LL(k)$ 或者 $LR(k)$ parsing 中可能出现的 conflicts
• 我对 grammar 的要求极低

GP 处理 conflicts 以及 ambiguity 用的都是同一个招数：spawns parallel parsing processes on conflicts/ambiguous parse trees. 这样会导致 $O(n^3)$ 的复杂度，为了提升性能，GP 会使用 Graph-Structured Stack (GSS).