 |
例4.16 |
|
文法G[S]:
(1)S→Be
(2)B→Ce
(3)B→Af
(4)A→Ae
(5)A→e
(6)C→Cf
(7)D→f
对文法G=(VN,VT,P,S)来说,为了保证其任一非终结符A在句子推导中出现,必须满足如下两个条件:
① A必须在某句型中出现。即有S αAβ,其中α,β属于(VT∪VN)*
。
② 必须能够从A推出终结符号串t来。即A t,其中t∈VT
若程序设计语言的文法包含有多余规则时,其中必定有错误存在,因此检查文法是否包含多余规则是很有必要的。 |
有关文法的实用限制
文法中不得含有有害规则和多余规则
有害规则:形如U→U的产生式。会引起文法的二义性
多余规则:指文法中任何句子的推导都不会用到的规则
① 文法中某些非终结符不在任何规则的右部出现,该非终结符称为不可到达。
② 文法中某些非终结符,由它不能推出终结符号串,该非终结符称为不可终止。 |