终结符与非终结符
终结符是一个形式语言的基本符号。就是说,它们能在一个形式语法的推导规则的输入或输出字符串存在,而且它们不能被分解成更小的单位。确切地说,一个语法的规则不能改变终结符。例如说,下面的语法有两个规则:
-
x -> xa
-
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
网友评论