在文法的乔姆斯基体系中,文法被分为4类,分别是0型文法、1型文法、2型文法、3型文法。具体释义和特点如下:
一、0型文法:也叫短语结构文法或无限制文法,其描述能力相当于图灵机,可使用任何的语法描述形式;
二、1型文法:也叫上下文有关文法,其描述能力相当于线性有界自动机,语法形式如下:
xSy -> xAy。也就是说,S推导出A是和上下文x, y相关的,即S只有在上下文x, y的环境中才能推导出A;
三、2型文法:也叫上下文无关文法,其描述能力相当于下推自动机,语法形式如下:
S -> A。S可以无条件的推导出A,和上下文无关,上下文无关文法因此得名;
四、3型文法:也叫正则文法,等价于正则表达式,其描述能力相当于有穷自动机,语法形式如下:S -> Aa。其中最后一个a必须为非终结符。
通俗地说,在0型文法基础上加以条件的约束,α—>β 后者长度要大于前者。于是1型文法即上下文有关文法诞生了。再在此基础上加上条件限制,让α只能为变量串,不允许有终极符就有了上下文无关文法;再添加限制条件,也就是产生式的右端必须得有终极符。这就是正则文法。
四种文法的判断非常简单,其实四种文法就是规定产生式的左和右边的字符的组成规则不同而已,其它的不能理解就不要去想了,你只要知道判断的时候就是以产生式的左边和右边符合的规则进行判断。下面解释一下如何根据产生式左边和右边的特征来进行判断。
首先,应该明确,四种文法,从0型到3型,其规则和约定越来越多,限制条件也越来越多,所以,我们判断时可以从最复杂的3型进行判断,依次向下判断,如果不符合3型的,那再看是不是2型的,不是2型的,再看是不是1型的。当你熟能生巧了之后,就可以一眼直接看出来了。
3型文法遵循什么规范呢?
第一点:
左边必须只有一个字符,且必须是非终结符
;
第二点:其右边最多只能有两个字符,且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时,此字符必须为终结符。
第三点:对于3型文法中的所有产生式,其右边有两个字符的产生式,这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定,也就是说如果一个产生式右边的两个字符的排列是:终结符+非终结符,那么所有产生式右边只要有两个字符的,都必须前面是终结符而后面是非终结符。反之亦然,要么,就全是:非终结符+终结符。 例如这样:
A->wB或A->w,(右线性文法)
A->Bw或A->w,(左线性文法)
再看2型文法如何判断:
第一点:与3型文法的第一点相同,即:
左边必须有且仅有一个非终结符
。
第二点:2型文法所有产生式的右边可以含有若干个终结符和非终结符(只要是有限的就行,没有个数限制)。 例如这样:
S -> aSb
S -> ab
这个文法有两个产生式,每个产生式左边只有一个非终结符S,这就是上下文无关文法,因为你只要找到符合产生式右边的串,就可以把它归约为对应的非终结符。
再看1型文法如何判断:
第一点:1型文法所有产生式
左边可以含有一个、两个或两个以上的字符
,但其中必须至少有一个非终结符。
第二点:与2型文法第二点相同。
例如这样:
aSb -> aaSbb
S -> ab
这就是上下文相关文法,因为它的第一个产生式左边有不止一个符号,所以你在匹配这个产生式中的S的时候必需确保这个S有正确的“上下文”,也就是左边的a和右边的b,所以叫上下文相关文法。
最后是0型文法,这个就不用看了,只要你能描述出来,都属于这个类型,即0型。
输出:相应的chomsky(
文法
类型和推导)
要求:1.
文法
的输入应简便(不代表产生式少)
2.指明是那一类chomsky
文法
,给出相应的
四
元祖形式,不考虑0
型文法
3.给出清晰的推导序列,并判断符号串是否是该
文法
的句型实验原理
1,
文法
定义:
文法
G定义为
四
元组(Vn,Vt,P,S)。
其中Vn为非终结符集,Vt
本程序的基本数据结构是一个字符型的二维数组。
先将文本文件一行一行的读入二维字符数组中,每一行只有一个产生式;
然后将二维数组中的每一行进行判断处理,先通过扫描找到每一行的推导符号“->”;
对“->”前面以及后面的字符分开进行处理,分别对其进行终结字符与非终结字符数量的统计;
比较产生式左部与右部所有的终结字符与非终结字符的数量,分别对不同的情况进行判断,将判断的结果保存在一个一位数组中(所有情况都不符合用-1标记);
对一维数组按从小到大的顺序进行冒泡排序,所以一位数组的第一个元素的大小即为此
文法
的类型,进行输出(-1则为不符合所有
文法
类型)。
输入文件格式样例:
S->aA
A->aB
A->dB
B->aB
B->dB
一、正则
文法
(3型)
定义:如果
文法
G=(N, Σ, P, S) 的 P 中的规则满足如下形式:A → B x(这里注意B只是一个形式,代表非终结符),或 A → x,其中 A, B ∈ N,x ∈ Σ, 则称该
文法
为正则
文法
(简写为 FSG)或称3型文 法。(左线性正则
文法
)(如果 A → x B,则该
文法
称为右线性正则
文法
。)
例如有如下规则:A→ Ax,A → x。那么可以推出AA...
3
型文法
遵循什么规范呢?
第一点:左边必须只有一个字符,且必须是非终结符
第二点:其右边最多只能有两个字符,且当有两个字符时必须有一个为终结符而另一个为非终结符。当右边只有一个字符时,此字符必须为终结符。
第三点:对于3
型文法
中的所有产生式,其右边有两个字符的产生式,这些产生式右边两个字符中终结符和非终结符的相对位置一定要固定,也就是说如果一个产生式右边的两个字符的排列是:终结符+非终结符,那么所有产生式右边只要有两个字符的,都必须前面是终结符而后面是非终结符。反之亦然,要么,就全是:非终