形式语言与自动机理论第六章(蒋宗礼)ppt课件.ppt

形式语言与自动机理论Formal Languages and Automata Theory,蒋宗礼,课程目的和基本要求,课程性质技术基础 基础知识要求 数学分析（或者高等数学），离散数学 主要特点 抽象和形式化 理论证明和构造性 基本模型的建立与性质,课程目的和基本要求,本专业人员4种基本的专业能力计算思维能力算法的设计与分析能力程序设计和实现能力计算机软硬件系统的认知、分析、设计与应用能力计算思维能力逻辑思维能力和抽象思维能力构造模型对问题进行形式化描述理解和处理形式模型,课程目的和基本要求,知识掌握正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。能力培养学生的形式化描述和抽象思维能力。使学生了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。,主要内容,语言的文法描述。RLRG、 FA、RE、RL的性质 。CFLCFG(CNF、GNF)、PDA、CFL的性质。 TM基本TM、构造技术、TM的修改。CSLCSG、LBA。,教材及主要参考书目,蒋宗礼，姜守旭. 形式语言与自动机理论. 北京：清华大学出版社，2003年 John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation (2nd Edition). Addison-Wesley Publishing Company, 2001 John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979,第6章 上下文无关语言,Gbra：SS(S)| L(Gbra)不是RL,是CFL,高级程序设计语言的绝大多数语法结构都可以用上下文无关文法(CFG)描述。BNF(巴科斯范式：Backus normal form，又叫Backus-naur form)。,第6章 上下文无关语言,主要内容关于CFL的分析派生和归约、派生树CFG的化简 无用符、单一产生式、空产生式CFG的范式 CNFGNFCFG的自嵌套特性,第6章 上下文无关语言,重点CFG的化简。CFG到GNF的转换。 难点CFG到GNF的转换，特别是其中的用右递归替换左递归的问题。,6.1 上下文无关语言,文法G=(V，T，P，S)被称为是上下文无关的。 如果除了形如A的产生式之外，对于P，均有|，并且V成立。关键：对于AV，如果AP，则无论A出现在句型的任何位置，我们都可以将A替换成，而不考虑A的上下文。,6.1.1 上下文无关文法的派生树,算术表达式的文法 Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E,6.1.1 上下文无关文法的派生树,算术表达式x+x/y2的不同派生,EE+TT+TF+TP+Tx+Tx+T/Fx+F/Fx+P/Fx+x/Fx+x/FPx+x/PPx+x/yPx+x/y2,EE+TE+T/FE+T/FPE+T/F2E+T/P2E+T/y2 E+F/y2 E+P/y2 E+x/y2 T+x/y2 F+x/y2 P+x/y2x+x/y2,EE+TT+TT+T/FF+T/FF+T/FPP+T/FPx+T/FPx+F/FPx+F/F2x+F/P2x+P/P2x+P/y2x+x/y2,6.1.1 上下文无关文法的派生树,文法Gexp1句子x+x/y2的结构。,6.1.1 上下文无关文法的派生树,派生树(derivation tree) 一棵(有序)树(ordered tree) 树的每个顶点有一个标记X，且XVT 树根的标记为S； 如果非叶子顶点v标记为A，v的儿子从左到右依次为v1，v2，vn，并且它们分别标记为X1，X2，Xn，则AX1X2XnP；如果X是一个非叶子顶点的标记，则XV；如果顶点v标记为，则v是该树的叶子，并且v是其父顶点的惟一儿子。,6.1.1 上下文无关文法的派生树,别称生成树分析树(parse tree)语法树(syntax tree) 顺序v1，v2是派生树T的两个不同顶点，如果存在顶点v，v至少有两个儿子，使得v1是v的较左儿子的后代，v2是v的较右儿子的后代，则称顶点v1在顶点v2的左边，顶点v2在顶点v1的右边。,6.1.1 上下文无关文法的派生树,结果(yield) 派生树T的所有叶子顶点从左到右依次标记为X1，X2，Xn，则称符号串X1X2Xn是T的结果。 一个文法可以有多棵派生树，它们可以有不同的结果。句型的派生树：“G的结果为的派生树”。,6.1.1 上下文无关文法的派生树,派生子树(subtree) 满足派生树定义中除了对跟结点的标记的要求以外各条的树叫派生子树(subtree)。如果这个子树的根标记为A，则称之为A子树。 惟一差别是根结点可以标记非开始符号。,6.1.1 上下文无关文法的派生树,定理6-1 设CFG G=(V，T，P，S)，S*的充分必要条件为G有一棵结果为的派生树。证明：证一个更为一般的结论：对于任意AV，A*的充分必要条件为G有一棵结果为的A-子树。 充分性：设G有一棵结果为的A-子树，非叶子顶点的个数n施归纳，证明A*成立。,6.1.1 上下文无关文法的派生树,设A-子树有k+1个非叶子顶点，根顶点A的儿子从左到右依次为v1，v2，vm，并且它们分别标记为X1，X2，Xm 。 AX1X2XmP 。 以X1，X2，Xm为根的子树的结果依次为1，2，m 。 X1，X2，Xm为根的子树的非叶子顶点的个数均不大于k。,6.1.1 上下文无关文法的派生树,X1*1X2*2Xm*m而且=12m,6.1.1 上下文无关文法的派生树,AX1X2Xm *1X2Xm *12Xm *12m,6.1.1 上下文无关文法的派生树,6.1.1 上下文无关文法的派生树,必要性设An，现施归纳于派生步数n，证明存在结果为的A-子树。设nk(k1)时结论成立，往证当n=k+1时结论也成立：令Ak+1，则有：AX1X2Xm *1X2Xm *12Xm *12m,6.1.1 上下文无关文法的派生树,6.1.1 上下文无关文法的派生树,例6-1设Gbra：SS(S)|，()()和(S)(S)的派生树。,6.1.1 上下文无关文法的派生树,关于标记的结点,6.1.1 上下文无关文法的派生树,最左派生(leftmost derivation) 的派生过程中，每一步都是对当前句型的最左变量进行替换。左句型(left sentencial form)最左派生得到的句型可叫做左句型。最右归约(rightmost reduction)与最左派生对相的归约叫做最有归约。,6.1.1 上下文无关文法的派生树,最右派生(rightmost derivation) 的派生过程中，每一步都是对当前句型的最右变量进行替换。右句型(right sentencial form)最右派生得到的句型可叫做右句型。最左归约(leftmost reduction)与最左派生对相的归约叫做最右归约。,6.1.1 上下文无关文法的派生树,规范派生(normal derivation)最右派生。规范句型(normal sentencial form)规范派生产生的句型。规范归约(normal reduction)最左归约。,6.1.1 上下文无关文法的派生树,定理6-2 如果是CFG G的一个句型，则G中存在的最左派生和最右派生。证明：基本思路：对派生的步数n施归纳，证明对于任意AV，如果An，在G中，存在对应的从A到的最左派生：An左。,6.1.1 上下文无关文法的派生树,AX1X2Xm *1X2Xm *12Xm *12m,A左X1X2Xm *左1X2Xm *左12Xm *左12m,同理可证，句型有最右派生。,6.1.1 上下文无关文法的派生树,定理6-3 如果是CFG G的一个句型，的派生树与最左派生和最右派生是一一对应的，但是，这棵派生树可以对应多个不同的派生。,6.1.2 二义性,简单算术表达式的二义性文法Gexp2：EE+E|E-E|E/E|E*EE EE|(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E,6.1.2 二义性,E E+E x+E x+E/E x+x/E x+x/EEx+x/yEx+x/y2,句子x+x/y2在文法中的三个不同的最左派生,E E/E E+E/E x+E/E x+x/E x+x/EE x+x/yE x+x/y2,E EE E/EE E+E/EE x+E/EE x+x/EE x+x/yE x+x/y2,6.1.2 二义性,对应3个不同的语法树,6.1.2 二义性,二义性(ambiguity) CFG G=(V，T，P，S)，如果存在wL(G)，w至少有两棵不同的派生树，则称G是二义性的。否则，G为非二义性的。二义性的问题是不可解的(unsolvable)问题。,6.1.2 二义性,例6-2 用其他方法消除二义性。Gifa：Sif E then S else S | if E then SGifm：SU|MUif E then SUif E then M else UMif E then M else M|SGifh：STS|CSCif E thenT CS else,6.1.2 二义性,例 6-3 设Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1可以用如下文法产生语言Lambiguity：G：SAB|0C3A01|0A1B23|2B3C0C3|12|1D2D12|1D2 语言Lambiguity不存在非二义性的文法。,6.1.2 二义性,固有二义性的(inherent ambiguity) 如果语言L不存在非二义性文法，则称L是固有二义性的，又称L是先天二义性的。文法可以是二义性的。语言可以是固有二义性的。,6.1.3 自顶向下的分析和自底向上的分析,自顶向下的分析方法通过考察是否可以从给定文法的开始符号派生出一个符号串，可以判定一个符号串是否为该文法的句子。例SaAb|bBaAaAb|bBaBd,aabdabb的派生树的自顶向下的“生长”过程,6.1.3 自顶向下的分析和自底向上的分析,自底向上的分析方法通过考察是否可以将一个符号串归约为给定文法的开始符号，完成判定一个符号串是否为该文法的句子的任务。和归约与派生是互逆过程相对应，自顶向下的分析与自底向上的分析互逆的分析过程。,aabdabb的派生树的自底向上的“生长”过程,6.2 上下文无关文法的化简,如下文法含有无用的“东西”G1：S0|0A|EA|0A|1A|BB_CC0|1|0C|1CD1|1D|2DE0E2|E02,去掉无用“东西”后的文法G2：S0|0AA|0A|1A|BB_CC0|1|0C|1C,6.2 上下文无关文法的化简,去掉产生式A后的文法G3：S0|0AA0|1|0A|1A|BB_CC0|1|0C|1C,去掉产生式AB后的文法G4：S0|0AA0|1|0A|1A| _CC0|1|0C|1C,可以去掉文法中的无用符号、 产生式和单一产生式。,6.2.1 去无用符号,无用符号(useless symbol) 对于任意XVT，如果存在wL(G)，X出现在w的派生过程中，即存在，(VT)*，使得S*X*w，则称X是有用的，否则，称X是无用符号。对CFG G=(V，T，P，S) G中的符号X既可能是有用的，也可能是无用的。当X是无用的时候，它既可能是终极符号，也可能是语法变量。,6.2.1 去无用符号, 对于任意XVT，如果X是有用的，它必须同时满足如下两个条件： 存在wT*，使得X*w； ，(VT)*，使得S*X。 注意到文法是语言的有穷描述，所以，集合V，T，P都是有穷的。从而我们有可能构造出有效的算法，来完成消除文法的无用符号的工作。,6.2.1 去无用符号,算法 6-1 删除派生不出终极符号行的变量。输入：CFG G=(V，T，P，S)。输出：CFG G=(V，T，P，S)，V中不含派生不出终极符号行的变量，并且L(G)=L(G)。 主要步骤：,6.2.1 去无用符号,(1) OLDV=;(2) NEWV=A|AwP且wT*；(3) while OLDVNEWV dobegin(4) OLDV=NEWV；(5) NEWV=OLDVA|AP且(TOLDV) *end(6) V=NEWV；(7) P= A| AP且 AV且(TV)*,6.2.1 去无用符号,第(3)条语句控制对NEWV进行迭代更新。第一次循环将那些恰经过两步可以派生出终极符号行的变量放入NEWV；第二次循环将那些恰经过三步和某些至少经过三步可以派生出终极符号行的变量放入NEWV；，第n次循环将那些恰经过n步和某些至少经过n+1步可以派生出终极符号行的变量放入NEWV。这个循环一直进行下去，直到所给文法G中的所有可以派生出终极符号行的变量都被放入NEWV中。,6.2.1去无用符号,定理 6-4 算法6-1是正确的。 证明要点：首先证明对于任意AV，A被放入V中的充要条件是存在wT，An w。再证所构造出的文法是等价的。(1)对A被放入NEWV的循环次数n施归纳，证明必存在wT，满足A w。,6.2.1去无用符号,(2)施归纳于派生步数n，证明如果An w，则A被算法放入到NEWV中。实际上，对原教材所给的证明进行分析，同时考虑算法6-1的实际运行，可以证明，A是在第n次循环前被放入到NEWV中的。(3)证明L(G)=L(G) 。显然有L(G) L(G)，所以只需证明L(G)。,6.2.1 去无用符号,算法 6-2 删除不出现在任何句型中的语法符号。输入：CFG G=(V，T，P，S)。输出：CFG G=(V，T，P，S)，VT中的符号必在G的某个句型中出现，并且有L(G)=L(G)。主要步骤：,6.2.1 去无用符号,主要步骤：(1) OLDV=;(2) OLDT=;(3) NEWV=SA|SAP;(4) NEWT=a|SaP;,6.2.1去无用符号,(5) while OLDVNEWV 或者OLDTNEWT do begin(6) OLDV=NEWV;(7) OLDT=NEWT;(8) NEWV=OLDVB| AOLDV且 ABP 且BV;(9) NEWT=OLDTa| AOLDV且 AaP 且aT; end,6.2.1去无用符号,(10) V=NEWV;(11) T=NEWT;(12) P= A| AP且 AV且(TV)*。,6.2.1去无用符号,定理 6-5 算法6-2是正确的。证明要点：(1)施归纳于派生步数n，证明如果Sn X，则当XV时，X在算法中被语句(3)或者语句(8)放入NEWV；当XT时，它在算法中被语句(4)或者语句(9)放入NEWT。(2)对循环次数n施归纳，证明如果X被放入NEWT或者NEWV中，则必定存在，(NEWVNEWT)*，使得Sn X。(3) 证明L(G)=L(G) 。,6.2.1去无用符号,定理6-6 对于任意CFL L，L，则存在不含无用符号的CFG G，使得L(G)=L。证明要点：依次用算法6-1和算法6-2对文法进行处理，可以得到等价的不含无用符号的文法。 不可先用算法6-2后用算法6-1。,6.2.1去无用符号,例 6-2-1 设有如下文法 SAB|a|BB，Aa，Cb|ABa先用算法6-2，文法被化简成： SAB|a|BB，Aa再用算法6-1，可得到文法： S a，Aa显然，该文法中的变量A是新的无用变量。,6.2.2 去-产生式,-产生式（-production） 形如A的产生式叫做-产生式。 -产生式又称为空产生式（null production。 可空(nullable)变量对于文法G=(V，T，P，S)中的任意变量A，如果A+，则称A为可空变量。,6.2.2 去-产生式,对形如AX1X2Xm的产生式进行考察，找出文法的可空变量集U，然后对于HU，从产生式AX1X2Xm中删除H中的变量。对于不同的H，得到不同的A产生式，用这组A产生式替代产生式AX1X2Xm。必须避免在这个过程中产生新的-产生式：当 X1，X2，XmU时，不可将X1，X2，Xm同时从产生式AX1X2Xm中删除。,6.2.2 去-产生式,算法6-3 求CFG G的可空变量集U。输入：CFG G=(V，T，P，S)。输出：G的可空变量集U。主要步骤：(1)OLDU=;(2) NEWU=A| AP;,6.2.2 去-产生式,(3)while NEWUOLDU do begin(4)OLDU = NEWU;(5) NEWU= OLDU A|AP并且OLDU* end(6)U=NEWU,6.2.2 去-产生式,定理 6-7 对于任意CFG G，存在不含-产生式的CFG G使得L(G)=L(G)-。证明： (1) 构造设CFG G=(V，T，P，S) ，用算法6-3求出G的可空变量集U，构造P。,6.2.2 去-产生式,对于 AX1X2XmP 将A12m放入P，其中if XiU then i=Xi或者i=；if XiU then i=Xi要求：在同一产生式中，1，2，m不能同时为。,6.2.2 去-产生式,证明对于任意wT+，AnG w的充分必要条件是A。必要性：设AnG w，施归纳于n，证明AmG w成立。 当n=1时，由AG w知，AwP，按照定理所给的构造G的方法，必定有AwP。所以，AG w成立。,6.2.2 去-产生式,设nk时结论成立(k1)，当n=k+1时AX1X2Xm *G w1X2Xm *G w1w2Xm *G w1w2wm其中w1w2wm=w，且w1，w2，wmT*。,6.2.2 去-产生式,注意到w，必存在1im，wi，设i，j，k是w1，w2，wm中所有非空串的下标，并且1ijkm，即： w= wiwjwk按照G的构造方法，A XiXjXkP 再由归纳假设，Xi*G wi，Xj*G wj，Xk*G wk。,6.2.2 去-产生式,A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk所以，结论对n=k+1成立。由归纳法原理，结论对所有的n成立。,6.2.2 去-产生式,充分性：设AmG w，施归纳于m，证明AnG w成立。当m=1时，由AG w知，AwP，按照定理所给的构造G的方法，必定有AP。Aw是通过删除产生式A右部中的可空变量而构造出来的，所以，AG *G w 成立。,6.2.2 去-产生式,设nk时结论成立(k1)，当m=k+1时A*G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w其中Xi*G wi，Xj*G wj，Xk*G wk 。,6.2.2 去-产生式,表明A XiXjXkP。按照G的构造方法，必定存在A X1X2XmP，而且Xi，Xj，XkX1，X2，XmX1，X2，Xm-Xi，Xj，XkU从而，AG X1X2Xm *G XiXjXk,6.2.2 去-产生式,再根据Xi*G wi，Xj*G wj，Xk*G wk和归纳假设，有Xi*G wi，Xj*G wj，Xk*G wk。这表明，如下派生成立： AG X1X2Xm *G XiXjXk *G wiXjXk *G wiwjXk *G wiwjwk=w,6.2.2 去-产生式,表明结论对m=k+1成立。由归纳法原理，结论对任意m成立。注意到A 的任意性，当S=A时结论成立。即：S*G w 的充分必要条件是S*G w亦即：L(G)=L(G)-。定理得证。,6.2.3 去单一产生式,文法Gexp1：EE+T|E-T|TTT*F|T/F|FFFP|PP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E存在派生：ETFPid,6.2.3 去单一产生式,Gexp3：EE+T|E-T|T*F|T/F|FP|(E)|N(L)|idTT*F|T/F| FP| (E)|N(L)|idFFP| (E)|N(L)|idP(E)|N(L)|idNsin|cos|exp|abs|log|intLL,E|E该文法中不存在类似的派生。,6.2.3 去单一产生式,单一产生式(unit production) 形如AB的产生式称为单一产生式。 定理 6-8对于任意CFG G，L(G)，存在等价的CFG G1，G1不含无用符号、-产生式和单一产生式。 满足本定理的CFG为化简过的文法。已有去无用符号和去-产生式的结论，所以只讨论去单一产生式的问题。,6.2.3 去单一产生式,证明要点： （1）构造G2，满足L(G2)=L(G)，并且G2中不含单一产生式。用非单一产生式A1取代A1*G An用到的产生式系列 A1A2，A2A3，An-1An，An。其中，A1A2，A2A3，An-1An都是单一产生式。（n1）,6.2.3 去单一产生式,（2） 证明L(G2)=L(G)。 用A1所完成的派生A1与产生式系列A1A2，A2A3，An-1An，An所完成的派生A1*G An相对应。在原文法中可能会出现一个变量在派生过程中循环出现的情况，在wL(G) 证明w L(G2)的过程中，要取w在G中的一个最短的最左派生。S=0G1G2GGn=w,6.2.3 去单一产生式,（3）删除G2中的无用符号。由于在删除单一产生式后，文法中可能出现新的无用符号，因此，我们还需要再次删除新出现的无用符号。 此外，在去-产生式后可能会产生新的单一产生式，也可能会引进新的无用符号。这是值得注意的。,6.3 乔姆斯基范式,乔姆斯基范式文法(Chomsky normal form ，CNF)简称为Chomsky文法，或Chomsky范式。CFG G=(V，T，P，S)中的产生式形式：ABC，Aa其中，A、B、CV，aT。CNF中，不允许有-产生式、单一产生式。,6.3 乔姆斯基范式,例 6-3-1 试将文法Gexp4转换成等价的 GNF。Gexp4：EE+T| T*F|FP| (E)| idTT*F| FP| (E) |idFFP| (E) |idP(E) |id 可以分两步走变成A a和A A1A2An的形式。变成CNF。,第一步,EEA+T| T A*F|F AP| A(EA5| idTTA*F| FAP| A(EA) |idFFAP| A(EA)|idPA(EA) |idA+A*AA(A),第二步,GexpCNF：EEA1| TA2E FA3| A(A4| idTTA2| FA3| A(A4 |idFFA3| A(A4|idPA(A4 |idA+A*,AA(A)A1A+T A2A*FA3APA4EA),6.3 乔姆斯基范式,定理6-9 对于任意CFG G，L(G)，存在等价的 CNF G2 。 证明要点：1. 构造CNF按照上述例子所描述的转换方法，在构造给定CFG的CNF时，可以分两步走。假设G为化简过的文法构造G1=(V1，T，P1，S) G1中的产生式都是形如AB1B2Bm和Aa的产生式，其中，A，B1，B2，BmV1，aT，m2,6.3 乔姆斯基范式,构造CNF G2=(V2，T，P2，S)。 m3时，引入新变量：B1、B2、Bm-2，将G1的形如AA1A2Am的产生式替换成AA1B1B1A2B2Bm-2Am-1Am,6.3 乔姆斯基范式,2. 构造的正确性证明。按照上述构造，证明被替换的产生式是等价的。例如：在第二步中A A1B1， B1A2B2 ， ， Bm-2Am-1Am与AA1A2Am等价。,6.3 乔姆斯基范式,例 6-6 试将下列文法转换成等价的 CNF。 SbA | aB AbAA | aS | a BaBB | bS | b,6.3 乔姆斯基范式,先引入变量Ba，Bb和产生式Baa，Bbb ，完成第一步变换。 SBbA | BaB ABbAA | BaS | a BBaBB | BbS | b Baa Bbb,6.3 乔姆斯基范式,引入新变量B1、B2 SBbA | BaBABbB1 | BaS | aBBaB2 | BbS | b Baa Bbb B1AA B2BB,6.3 乔姆斯基范式,不能因为原来有产生式A a和B b而放弃引进变量Ba 、Bb和产生式Baa 、Bbb。L(A)=x | xa，b+ & x中a的个数比b的个数恰多1个。L(B)=x | xa，b+ & x中b的个数比a的个数恰多1个。L(Ba)= a 。L(Bb)= b 。,6.4 格雷巴赫范式,格雷巴赫范式文法(Greibach normal form ,GNF)简称为Greibach文法，或Greibach范式。Aa 其中，AV，aT，V* 。在GNF中，有如下两种形式的产生式AaAaA1A2Am(m1),6.4 格雷巴赫范式,右线性文法是一种特殊的GNF。 由于GNF中不存-产生式，所以对任意的GNF G，L(G)。当L(G)时，能够找到一个GNF G，使得 L(G)=L(G) 。经过化简的CFG，都有一个等价的GNF。,6.4 格雷巴赫范式,引理 6-1 对于任意的CFG G=(V，T，P，S)，ABP，且G中所有的B产生式为 B1 |2 |n 取G1=( V，T，P1，S)P1=(P-AB)A1，A2，An则，L(G1)=L(G)。,6.4 格雷巴赫范式,证明 以下两组产生式等价AB ；B1 |2 |n A1，A2，An,6.4 格雷巴赫范式,递归(recursive) 如果G中存在形如AnA的派生，则称该派生是关于变量A递归的，简称为递归派生。当n=1时，称该派生关于变量A直接递归(directly recursive)，简称为直接递归派生。形如AA的产生式是变量A的直接递归的(directly recursive)产生式。,6.4 格雷巴赫范式,当n2时，称该派生是关于变量A的间接递归(indirectly recursive)派生。简称为间接递归派生。当=时，称相应的(直接/间接)递归为(直接/间接)左递归(left-recursive)；当=时，称相应的(直接/间接)递归为(直接/间接)右递归(right-recursive)。,6.4 格雷巴赫范式,引理 6-2 对于任意的CFG G=(V，T，P，S)，G中所有A的产生式,可以被等价地替换为产生式组,6.4 格雷巴赫范式,证明要点： 用直接右递归取代原来的直接左递归。 两组产生式产生的符号串都是,前者是先产生,然后产生k 。,6.4 格雷巴赫范式,后者先产生k 。然后产生,6.4 格雷巴赫范式,6.4 格雷巴赫范式,定理6-10 对于任意CFG G，L(G)，存在等价的GNF G1。 证明要点： (1)使用引理6-1将产生式都化成如下形式的产生式 AA1A2Am AaA1A2Am-1 Aa其中，A，A1，A2，AmV1，aT，m2。,6.4 格雷巴赫范式,(2)根据引理6-1和6-2，将产生式变成如下形式的产生式AiAjij+1AiaBi其中，V2=V1 B1，B2，Bn， V1 B1，B2，Bn=。 “B类变量”： B1，B2，Bn是在文法的改造过程中引入的新变量。 V1中的变量称为“A类变量”。,6.4 格雷巴赫范式,（3）根据引理6-1，从编号较大的变量开始，逐步替换，使所有产生式满足GNF的要求： 1) for k=m-1 to 1 do 2) if AkAk+1P2 then 3) for 所有的Ak+1产生式Ak+1 do 将产生式Ak放入P3； 4) for k= 1 to n do 5)根据引理6-1，用P3中的产生式将所有的Bk产生式替换成满足GNF要求的形式。,6.5 自嵌套文法,自嵌套文法(self-embedding grammar) CFG G=(V，T，P，S)是化简后的文法，如果G中存在有形如A+A的派生，则称G为自嵌套文法，其中、(VT)+。 自嵌套的文法描述的语言可以是正则语言 例如： S0S0|1S1|0S1|1S0|0S|1S|0|1,6.5 自嵌套文法,定理 6-11 非自嵌套的文法产生的语言是正则语言。 证明要点：（1）将G化成GNF（2）取RG G=(V,T,P,S)，其中V=| V+并且|m(n-2)+1P=A a|AaP并且V*当=时，=。,6.6 小结,本章讨论了CFG的派生树，A子树，最左派生与最右派生，派生与派生树的关系，二义性文法与固有二义性语言，句子的自顶向下分析和自底向上分析；无用符号的消去算法，空产生式的消除，单一产生式的消除。CFG的CNF和GNF；CFG的自嵌套特性。 (1)S*的充分必要条件为G有一棵结果为的派生树。 (2)如果是CFG G的一个句型，则G中存在的最左派生和最右派生。,6.6 小结,(3)文法可能是二义性的，但语言只可能是固有二义性的，且这种语言是存在的。 (4)对于任意CFG G，L(G)，存在等价的CFG G1，G1不含无用符号、-产生式和单一产生式。 (5)对于任意CFG G，L(G)，存在等价的 CNF G2。 (6)对于任意CFG G，L(G)，存在等价的GNF G3。 (7)非自嵌套的文法产生的语言是正则语言。,