三型文法的终结符可以有多个吗

Question

如题所述

Answer 1

终结符可以有多个
四种文法：
0型文法：α→β，其中α至少包含一个非终结符。
1型文法（上下文有关文法）：α→β，其中|β|≥|α|，S→ε除外。
2型文法（上下文无关文法）：a→β，其中a是一个非终结符。
3型文法（规范文法）：A→a或A→aB.
4种文法是逐渐增加限制的，所以规范文法一定是0型文法、1型文法、2型文法，上下文无关文法也一定是0型文法、1型文法
文法的二义性：
一个句型可能对应多个语法树，一个句型可能对应多个最左/最右推导。
如果一个文法中的某个句子可以对应两个不同的语法树，则称这个文法是二义的。
两个不同的文法可能是一样的语言。
如果一种语言的所有文法都是二义的，则称此语言先天二义。
判定一个文法是否是二义的是递归不可解的。