PCFG相关笔记

终结符与非终结符

终结符是一个形式语言的基本符号。就是说，它们能在一个形式语法的推导规则的输入或输出字符串存在，而且它们不能被分解成更小的单位。确切地说，一个语法的规则不能改变终结符。例如说，下面的语法有两个规则：

1. x -> xa

2. x -> ax

在这种语法之中，a是一个终结符，因为没有规则可以把a变成别的符号。不过，有两个规则可以把x变成别的符号，所以x是非终结符。一个形式语法所推导的形式语言必须完全由终结符构成。

Context-Free Grammars

上下文无关文法包含下列四个集合

• N: a set of non-terminal symbols (非终端符号)

• ΣΣ: a set of terminal symbols (终端符号)

• R: a set of production rules of the form X → Y1Y2YnX → Y1Y2Yn for n>=0, X∈NX∈N, Yi∈(N∪Σ)Yi∈(N∪Σ) (语法规则)

• S∈NS∈N: a distinguished/special start symbol (起始符号)

CYK算法

CYK处理的CFG必须是CNF形式的, CNF只有以下两种表示:

• A→B C

• A→a