1. 基本概念
1.1 状态 state
- 上下文无关文法规则
- 圆点 · （左边是已分析的，右边是未分析的；点在最右端表示完成状态，否则为未完成状态）
- 状态的起止位置
1.2 基本操作/算子 operator
- 预测 Predicator：若圆点右方是一个非终结符，那么以该终结符为左部的规则都有匹配的希望。
- 扫描 Scanner：若圆点右方是一个终结符，那么圆点向右扫描一个字符。
- 归约 Completer：若圆点右方没有符号，则表示当前状态所作的预测已经实现，因为可以将当前状态与已有包含当前状态的状态进行归约。
1.3 算子的形式定义
*α，β，γ是终结符或非终结符串 是终结符或非终结符串，其中α，β均 为空字符 可 i <= j <= k
- Predicator：对于状态 Z -> α·Xβ[j,k]（X 是非终结符），对于语法中每条形如 X -> γ 的规则，都可以形成一个新状态：X -> ·γ[k,k]
- Scanner：对于状态 Z -> α·Xβ[j,k]（X 是终结符），如果 X 与输入字符串中的第 k 个字符匹配，就形成一个新状态 Z -> αX·β[j,k+1]
- Completer：对于一个已经完成的状态 Z -> γ·[j,k]，如果已后状态集合中有形如 X -> α·Zβ[i,j]这样的状态，就形成一个新状态：X -> αZ·β[i,k]
2. 算法描述
设输入字符串长度为n, 字符间隔可记做0,1,2,…,n
（1）将文法规则中形如 S -> α 的规则形成状态： <S -> ·α[0,0]> 加入到状态集合中（种子状态/seed state）
（2）对当前分析句子的每个词，依次进行循环：
i）如果当前状态是[未完成状态]，且点后不是终结符，则 执行Predicator；
ii）如果当前状态是[未完成状态]，且点后是终结符，则 执行Scanner；
iii）如果当前状态是 如果当前状态是[完成状态]，则 执行Completer；
（3）如果最后得到形如<S -> α·[0,n]>这样的状态，那么输入字符串被接受为合法的句子，否则分析失败
3. 示例
使用以下文法分析字符串 "I-I-|"：
p : e '-|'
e : t
| e '-' t
t : f
| t '/' f
f : I
| '(' e ')'
（0）字符串长度为 4，因此分析表共有 4+1=5 个状态集，将所有种子状态加入状态集 0
（1）此时需要匹配的字符为 'I',首先对状态 e 执行 Scanner 操作后，产生状态 f
由于状态 f 处于完成状态，触发 Completer 操作。由于状态 f 的左部为非终结符 f ，因此对于状态集 0 中所有圆点右方第一个字母为 f 的状态，都可以产生一个新状态。继而由状态 d 得到了状态 g
此时状态 g 也处于完成状态，因为执行 Completer 操作，得到状态 h 和未编号状态 t : t·'/'f,0
状态 h 也处于完成状态，执行 Completer 得到状态 i 和未编号状态 p : e·'-|',0
（2）（3）（4）以此类推，填充每个状态集，最后得到的状态 p : e'-|'·,0 为完成状态，表示分析成功
此时回顾整张分析表，对所有在这次成功分析中有所贡献的状态进行编号。
注：
1. “基本概念”与“算法描述”两个部分参考了 http://ccl.pku.edu.cn/doubtfire/Course/Computational%20Linguistics/contents/Earley_Parsing.pdf
2. 例题取自 http://inst.eecs.berkeley.edu/~cs164/sp19/