Abstract

背景：目前的语法分析技术会遇到以下困难1. 难以嵌入带有副作用的actions 2. 速度慢 3. 有二义性 4. 匹配策略违反直觉
本文：介绍ALL(*)分析技术，对应ANTLR v4
特点：

1. 简单，高效，有常规topdown LL(k)parsers的预测能力，也有GLR类型文法的决策能力
2. 虽然理论上是O(n4)的，但是实践时常是线性复杂度
3. 在解析的时候就做语法分析
   效果：
   比GLL和GLR有量级提升

Intro

LL(*)缺点：1. 无法静态确定语法条件 2. 有时无法找到能区分语法规则选项肢的DFA

Proj THUDBFuzz Paper Reading: Adaptive LL(*) Parsing: The Power of Dynamic Analysis