*1第6章 上下文无关语言 主要内容 关于CFL的分析 派生和归约、派生树 CFG的化简 无用符、单一产生式、空产生式 CFG的范式 CNF GNF CFG的自嵌套特性 *2第6章 上下文无关语言 重点 CFG的化简。 CFG到GNF的转换。 难点 CFG到GNF的转换，特别是其中的用右递归替 换左递归的问题。*36.1 上下文无关语言 文法G=(V，T，P，S)被称为是上下文无关 的。 如果除了形如A的产生式之外， 对于P，均有|，并且 V成立。 关键：对于AV，如果AP，则无 论A出现在句型的任何位置，我们都可以将 A替换成，而不考虑A的上下文。 *46.1.1 上下文无关文法的派生树 算术表达式的文法 Gexp1：EE+T|E-T|T TT*F|T/F|F FFP|P P(E)|N(L)|id Nsin|cos|exp|abs|log|int LL,E|E *56.1.1 上下文无关文法的派生树 算术表达式x+x/y2的不同派生 EE+TT+TF+TP+Tx+Tx+T/Fx+F/F x+P/Fx+x/Fx+x/FPx+x/PPx+x/yP x+x/y2 EE+TE+T/FE+T/FPE+T/F2E+T/P2 E+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/FP P+T/FPx+T/FPx+F/FPx+F/F2 x+F/P2x+P/P2x+P/y2x+x/y2 *66.1.1 上下文无关文法的派生树 文法Gexp1句子x+x/y2的结构。 *76.1.1 上下文无关文法的派生树 派生树(derivation tree) 一棵(有序)树(ordered tree) 树的每个顶点有一个标记X，且 XVT 树根的标记为S； 如果非叶子顶点v标记为A，v的儿子从左到右 依次为v1，v2，vn，并且它们分别标记为 X1，X2，Xn，则AX1X2XnP； 如果X是一个非叶子顶点的标记，则XV； 如果顶点v标记为，则v是该树的叶子，并且v 是其父顶点的惟一儿子。 *86.1.1 上下文无关文法的派生树 别称 生成树 分析树(parse tree) 语法树(syntax tree) 顺序 v1，v2是派生树T的两个不同顶点，如果存在顶 点v，v至少有两个儿子，使得v1是v的较左儿子 的后代，v2是v的较右儿子的后代，则称顶点v1 在顶点v2的左边，顶点v2在顶点v1的右边。 *96.1.1 上下文无关文法的派生树 结果(yield) 派生树T的所有叶子顶点从左到右依次标记 为X1，X2，Xn，则称符号串X1X2Xn 是T的结果。 一个文法可以有多棵派生树，它们可以有 不同的结果。 句型的派生树：“G的结果为的派生树” 。*106.1.1 上下文无关文法的派生树 派生子树(subtree) 满足派生树定义中除了对跟结点的标记的 要求以外各条的树叫派生子树(subtree)。 如果这个子树的根标记为A，则称之为A子 树。 惟一差别是根结点可以标记非开始符号。*116.1.1 上下文无关文法的派生树定理6-1 设CFG G=(V，T，P，S)，S*的 充分必要条件为G有一棵结果为的派生 树。 证明： 证一个更为一般的结论：对于任意AV， A*的充分必要条件为G有一棵结果为的A- 子树。 充分性：设G有一棵结果为的A-子树，非叶子 顶点的个数n施归纳，证明A*成立。 *126.1.1 上下文无关文法的派生树 设A-子树有k+1个非叶子顶点，根顶点A的 儿子从左到右依次为v1，v2，vm，并且 它们分别标记为X1，X2，Xm 。 AX1X2XmP 。 以X1，X2，Xm为根的子树的结果依次 为1，2，m 。 X1，X2，Xm为根的子树的非叶子顶点 的个数均不大于k。 *136.1.1 上下文无关文法的派生树 X1*1 X2*2 Xm*m 而且 =12m*146.1.1 上下文无关文法的派生树AX1X2Xm*1X2Xm*12Xm*12m*156.1.1 上下文无关文法的派生树*166.1.1 上下文无关文法的派生树 必要性 设An，现施归纳于派生步数n，证明存在结果为 的A-子树。 设nk(k1)时结论成立，往证当n=k+1时结论也成立：令 Ak+1，则有： AX1X2Xm*1X2Xm*12Xm *12m *176.1.1 上下文无关文法的派生树*186.1.1 上下文无关文法的派生树 例6-1设Gbra：SS(S)|，()()和(S)(S) 的派生树。*196.1.1 上下文无关文法的派生树 关于标记的结点*206.1.1 上下文无关文法的派生树 最左派生(leftmost derivation) 的派生过程中，每一步都是对当前句型的最 左变量进行替换。 左句型(left sentencial form) 最左派生得到的句型可叫做左句型。 最右归约(rightmost reduction) 与最左派生对相的归约叫做最有归约。*216.1.1 上下文无关文法的派生树 最右派生(rightmost derivation) 的派生过程中，每一步都是对当前句型的最 右变量进行替换。 右句型(right sentencial form) 最右派生得到的句型可叫做右句型。 最左归约(leftmost reduction) 与最左派生对相的归约叫做最右归约。*226.1.1 上下文无关文法的派生树 规范派生(normal derivation) 最右派生。 规范句型(normal sentencial form) 规范派生产生的句型。 规范归约(normal reduction) 最左归约。*236.1.1 上下文无关文法的派生树定理6-2 如果是CFG G的一个句型，则G中 存在的最左派生和最右派生。 证明： 基本思路：对派生的步数n施归纳，证明对于 任意AV，如果An，在G中，存在对 应的从A到的最左派生：An左。 *246.1.1 上下文无关文法的派生树AX1X2Xm*1X2Xm*12Xm*12mA左X1X2Xm*左1X2Xm*左12Xm*左12m 同理可证，句型有最右派生。 *256.1.1 上下文无关文法的派生树定理6-3 如果是CFG G的一个句型，的派 生树与最左派生和最右派生是一一对应的 ，但是，这棵派生树可以对应多个不同的 派生。*266.1.2 二义性 简单算术表达式的二义性文法 Gexp2：EE+E|E-E|E/E|E*E E EE|(E)|N(L)|id Nsin|cos|exp|abs|log|int LL,E|E *276.1.2 二义性 E E+E x+E x+E/E x+x/E x+x/EE x+x/yE x+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 *286.1.2 二义性 对应3 个不同 的语法 树*296.1.2 二义性 二义性(ambiguity) CFG G=(V，T，P，S)，如果存在wL(G) ，w至少有两棵不同的派生树，则称G是二 义性的。否则，G为非二义性的。 二义性的问题是不可解的(unsolvable)问 题。 *306.1.2 二义性 例6-2 用其他方法消除二义性。 Gifa：Sif E then S else S | if E then S Gifm：SU|M Uif E then S Uif E then M else U Mif E then M else M|S Gifh：STS|CS Cif E then T CS else *316.1.2 二义性 例 6-3 设 Lambiguity=0n1n2m3m|n,m10n1m2m3n|n,m1 可以用如下文法产生语言Lambiguity： G：SAB|0C3 A01|0A1 B23|2B3 C0C3|12|1D2 D12|1D2 语言Lambiguity不存在非二义性的文法。 *326.1.2 二义性 固有二义性的(inherent ambiguity) 如果语言L不存在非二义性文法，则称L是 固有二义性的，又称L是先天二义性的。 文法可以是二义性的。 语言可以是固有二义性的。 *336.1.3 自顶向下的分析和自底向上 的分析 自顶向下的分析方法 通过考察是否可以从给定文法的开始符号派生 出一个符号串，可以判定一个符号串是否为该 文法的句子。 例 SaAb|bBa AaAb|bBa Bd *34aabdabb的派生树的自顶向下的“生长”过程 *356.1.3 自顶向下的分析和自底向上 的分析 自底向上的分析方法 通过考察是否可以将一个符号串归约为 给定文法的开始符号，完成判定一个符 号串是否为该文法的句子的任务。 和归约与派生是互逆过程相对应，自顶向 下的分析与自底向上的分析互逆的分析过 程。*36aabdabb的派生树的自底向上的“生长”过程 *376.2 上下文无关文法的化简 如下文法含有无 用的“东西”G1：S0|0A|E A|0A|1A|B B_C C0|1|0C|1C D1|1D|2D E0E2|E02 去掉无用“东西”后 的文法 G2：S0|0A A|0A|1A|B B_C C0|1|0C|1C *386.2 上下文无关文法的化简 去掉产生式A后 的文法 G3：S0|0A A0|1|0A|1A|B B_C C0|1|0C|1C 去掉产生式AB后的 文法 G4：S0|0A A0|1|0A|1A| _C C0|1|0C|1C 可以去掉文法中的无用符号、 产生式和 单一产生式。*396.2.1 去无用符号 无用符号(useless symbol) 对于任意XVT，如果存在wL(G)， X出现在w的派生过程中，即存在， (VT)*，使得S*X*w，则称X 是有用的，否则，称X是无用符号。 对CFG G=(V，T，P，S) G中的符号X既可能是有用的，也可能是 无用的。当X是无用的时候，它既可能是 终极符号，也可能是语法变量。*406.2.1 去无用符号 对于任意XVT，如果X是有用的， 它必须同时满足如下两个条件： 存在wT*，使得X*w； ，(VT)*，使得S*X。 注意到文法是语言的有穷描述，所以， 集合V，T，P都是有穷的。从而我们有 可能构造出有效的算法，来完成消除文 法的无用符号的工作。 *416.2.1 去无用符号 算法 6-1 删除派生不出终极符号行的变量。 输入：CFG G=(V，T