编译原理----0型，1型，2型，3型文法

2023-12-25 14:32:15

0型文法：

解释：\alpha（左部）可以包含非终结符和终结符，\beta(右部)可以包含非终结符和终结符，但是\alpha（左部）中至少包含1个非终结符

符合：Ab-->b,B-->Bb

不符合：a-->b,ab-->BA,a-->bA

1型文法（上下文有关文法）：

在0型文法的基础上，还需符号
?

解释：左部符号串长度必须小于右部符号串长度

符合：A--->bB? ? ? ? Aa--->abc????????\alpha--->\varepsilon(特例)? ? ? ? aB--->\varepsilon

不符合：Ab-->c? ? ? ? Ba--->c????????

2型文法（上下型无关文法）：

在1型文法的基础上

符合：A--->aB? ? ? ? B--->BB? ? ? ? B-->ab

不符合：Ab--->aB? ? ? ? AA--->Ba? ? ? ? bb--->AB

?

3型文法（正规文法）：

在2型文法的基础上

解释：产生式规则的右侧只能包含一个终结符后跟一个非终结符，或者只包含一个终结符，或者是空串。

右线性文法就是后半部分中非终结符在右侧，例如：A--->bA

左线性文法就是后半部分中非终结符在左侧，例如：B--->Ab

符合：A--->bA? ? ? ? B---->Ba? ? ? ? B---->BBa? ? ? ?A-->b

不符合：A--->AbB?

从0型到3型文法的限制是越来越大的：

?

文章来源:https://blog.csdn.net/weixin_69884785/article/details/135197194
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。