V T V_T VT?:终结符是文法所定义的语言嘚基本符号有时也称为token。(对应词义分析)
V N V_N VN?:非终结符是用来表示语法成分的符号有时也称为"语法变量",可以推出其它的语法成分(对应语法分析)
S∈VN? 开始符号表示的是该文法中最大的语法成分
- 又称为无限制文法或短语结构文法(PSG)
G=(VN?,VT?P,S)其中
- 又称为仩下文有关文法(CSG)
- CSG中不包含ε产生式
G=(VN?,VT?P,S)其中
- 又称为上下文无关文法(CFG)
- 上下文无关文法可用于描述语法构造
G=(VN?,VT?P,S)其中
- 又称为正则文法,包括左线性文法和右线性文法
- 正则文法可用来描述大多数单词但是,它的生成能力有限几乎描述不了语法构造
- 正则文法一般用于词法分析,通过NFA、DFA就可以识别
- 两套规则不能同时出现在一个语法中只有完全满足其中的一个才能算 3型文法。
- 文法中不能含有形如 A → A A→A A→A 的规则这种规则称为有害规则。这样的规则对描言显然是没有必要的并且它还会引起文法的二义性。所以在設计文法时应该避免定义里的规则。
- 文法中不能有多余规则所谓多余规则是指文法中出现以下两种规则的情况,一是某条规则 A → α A→α A→α 的左部符号 A A A 不在所属文法的任何其他规则右部出现即在推导文法的所有句子中始终都不可能用到的规则;二是对文法中的某个非終结符A,无法从它推导出任何终结符号串来