乔姆斯基把方法分成四种类型,即0型、1型、2型和3型。这几种文法类型的概念一定要掌握,是一个非常重要的考点。对于这几种文法,一般书上都只有简单的概念介绍,比较抽象,所以很多学员都没有真正理解。下面我将把概念结合例题进行讲解。
0型文法
设G=(VN,VT,P,S),如果它的每个产生式α→β是这样一种结构:α∈(VN∪VT)*且至少含有一个非终结符,而β∈(VN∪VT)*,则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是:0型文法的能力相当于图灵机(Turing)。或者说,任何0型文语言都是递归可枚举的,反之,递归可枚举集必定是一个0型语言。0型文法是这几类文法中,限制最少的一个,所以我们在试题中见到的,至少是0型文法。
1型文法
1型文法也叫上下文有关文法,此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
注意:虽然要求|β|>=|α|,但有一特例:α→ε也满足1型文法。
如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a,则不符合1型文法。
2型文法
2型文法也叫上下文无关文法,它对应于下推自动机。2型文法是在1型文法的基础上,再满足:每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。
如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求,因为其α=Ab,而Ab不是一个非终结符。
3型文法
3型文法也叫正规文法,它对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB(右线性)或A→α|Bα(左线性)。
如有:A->a,A->aB,B->a,B->cB,则符合3型文法的要求。但如果推导为:A->ab,A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说,例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结符+一个终结符”的形式(即为aB)就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc的形式就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。
注意:上面例子中的大写字母表示的是非终结符,而小写字母表示的是终结符。
引用
Ps:
看了上面的文法的解释,终于有点明白了什么是文法.在这里记下了.但我想不出这个文法有啥用啊,不知道大家有没有懂的指点一二.
虽然问题有点BT,但本小姐打算今年过软设没着得搞会它啊, .
分享到:
相关推荐
证明了乔姆斯基谱系中1型文法(上下文相关文法)两种定义形式的等价性。
1.什么是S-属性文法?什么是L-属性文法?它们之间有什么关系? 解答: S-属性文法是只含有综合属性的属性文法。 (2分) L-属性文法要求对于每个产生式AX1X2…Xn,其每个语义规则中的每个属性或者是综合属性,...
LL(1)型文法分析编译原理老师布置的作业 对大家做实验有用
3) 整理文法的结构,判断该文法的文法类型,是否为0型,1型,2型或3型文法,并输出判断结果; 4) 在计算机屏幕或者文本框中输出文法,文法输出按照一个非终结符号一行,开始符号引出的产生式写在第一行,同一个非...
1. 实验内容 1、 让计算机接受一个文法,示例如(仅供参考): G[S] 为: ...2、 编程实现对上述文法是否是LL(1)文法的判断,是则给出肯定回答,否则给出否定回答。 3、判别是否是LL(1)文法 。。。。。。
本程序的所用的存储结构都是string...最终有三种结果,一种是是LL(1)文法,一种是不是LL(1),但是经过转换变成了LL(1),还有一种是经过转换也无法变成LL(1)。 输入文本格式样例: A A->ad A->Bc B->aA B->bB
(1)对输入文法,它能判断是否为LL(1)文法,若是,则转(2);否则报错并终止; (2)输入已知文法,由程序自动生成它的LL(1)分析表; (3)对于给定的输入串,应能判断识别该串是否为给定文法的句型。 2.分析 ...
根据判断一个文法是LL(1)文法的三个条件,逐一实现其判别条件的算法实现。 满足是LL(1)文法的三个条件: (1)文法不含有左递归 (2)对于文法中每一个非终结符A,若它存在某个候选首符 集两两不相交,即,若A→α1|α2|...
(p[i].right.length()==1||p[i].right.length()==2)||(p[i].right[0]>='A'&&p[i].right[0])) //右部字符个数不是1或2,或首字符是非终结符 { flag++; break; } else if((p[i].right.length()==2)&&!(p[i]....
给定一个上下文无关文法,判断其是否为 LL(1)型文法。如果不是,尝试是否 可以改写为 LL(1)文法。 覆盖知识点:FIRST 集、FOLLOW 集、SELECT 集、预测分析表的构建、消除左递归、 消除左公共因子。 求first集、...
LR(0)文法分析器(LR (0) grammar parser)对于实现整个编译器而言,语法分析器是整个过程的核心部分,同时对构造整个编译器起到了关键作用,对程序的进一步扩展,以后有机会涉及对编译器的编写而言,将会是很容易便...
1.文法G属于chomsky哪一型文法? 2.给定符号串,判定该符号串是不是该文法的一个句子,请证实。 3.若是句子,写出该句型的所有短语、简单短语,以及句柄。 4.构造识别该文法的活前缀的DFA。 5.判断该文法是LR(0)...
该文件可运行LL(1)文法的判断过程,并可直接运行给出详细的过程
这是一个c0文法的编译器示例
用C语言编写实现编译原理实验判断文法是不是LL1文法的程序。程序简单易懂,且基本功能都实现了。
是编译原理的实习,关于LL(1)的文法分析程序,鄙人的拙手作品,多多谅解!
编译原理实验八:非LL(1)文法到LL(1)文法的转换,zip文件里包含实验报告和源代码两部分。
通过构造文法的有限自动机(DFA),得出LR(0)分析表和分析程序,并且能够判别字符串是否属于当前文法,内含C++源代码和实验报告说明
讲述关于编译原理里的3型文法,里面也有相关例子。