[其它]形式语言与自动机理论电子教案-06.ppt

第6章 上下文无关语言 Gbra：S?S(S)|ε L(Gbra)不是RL,是CFL 第6章 上下文无关语言 主要内容 关于CFL的分析 派生和归约、派生树 CFG的化简 无用符、单一产生式、空产生式 CFG的范式 CNF GNF CFG的自嵌套特性 第6章 上下文无关语言 重点 CFG的化简。 CFG到GNF的转换。 难点 CFG到GNF的转换，特别是其中的用右递归替换左递归的问题。 6.1 上下文无关语言 文法G=(V，T，P，S)被称为是上下文无关的。 如果除了形如A?ε的产生式之外，对于?α?β∈P，均有|β|≥|α|，并且α∈V成立。 关键：对于?A∈V，如果A?β∈P，则无论A出现在句型的任何位置，我们都可以将A替换成β，而不考虑A的上下文。 6.1.1 上下文无关文法的派生树 算术表达式的文法 Gexp1：E?E+T|E-T|T T?T*F|T/F|F F?F↑P|P P?(E)|N(L)|id N?sin|cos|exp|abs|log|int L?L,E|E 6.1.1 上下文无关文法的派生树 算术表达式x+x/y↑2的不同派生 6.1.1 上下文无关文法的派生树 文法Gexp1句子x+x/y↑2的结构。 6.1.1 上下文无关文法的派生树 派生树(derivation tree) 一棵(有序)树(ordered tree) 树的每个顶点有一个标记X，且X∈V∪T∪{ε} 树根的标记为S； 如果非叶子顶点v标记为A，v的儿子从左到右依次为v1，v2，…，vn，并且它们分别标记为X1，X2，…，Xn，则A?X1X2…Xn∈P； 如果X是一个非叶子顶点的标记，则X∈V； 如果顶点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，则称符号串X1X2…Xn是T的结果。 一个文法可以有多棵派生树，它们可以有不同的结果。 句型α的派生树：“G的结果为α的派生树”。 6.1.1 上下文无关文法的派生树 派生子树(subtree) 满足派生树定义中除了对跟结点的标记的要求以外各条的树叫派生子树(subtree)。 如果这个子树的根标记为A，则称之为A子树。 惟一差别是根结点可以标记非开始符号。 6.1.1 上下文无关文法的派生树 定理6-1 设CFG G=(V，T，P，S)，S?*α的充分必要条件为G有一棵结果为α的派生树。 证明： 证一个更为一般的结论：对于任意A∈V，A?*α的充分必要条件为G有一棵结果为α的A-子树。 充分性：设G有一棵结果为α的A-子树，非叶子顶点的个数n施归纳，证明A?*α成立。 6.1.1 上下文无关文法的派生树 设A-子树有k+1个非叶子顶点，根顶点A的儿子从左到右依次为v1，v2，…，vm，并且它们分别标记为X1，X2，…，Xm 。 A?X1X2…Xm∈P 。 以X1，X2，…，Xm为根的子树的结果依次为α1，α2，…，αm 。 X1，X2，…，Xm为根的子树的非叶子顶点的个数均不大于k。 6.1.1 上下文无关文法的派生树 X1?*α1 X2?*α2 … Xm?*αm 而且 α=α1α2…αm 6.1.1 上下文无关文法的派生树 A?X1X2…Xm ?*α1X2…Xm ?*α1α2…Xm … ?*α1α2…αm 6.1.1 上下文无关文法的派生树 6.1.1 上下文无关文法的派生树 必要性 设A?nα，现施归纳于派生步数n，证明存在结果为α的A-子树。 设n≤k(k≥1)时结论成立，往证当n=k+1时结论也成立：令A?k+1α，则有： A?X1X2…Xm ?*α1X2…Xm ?*α1α2…Xm … ?*α1α2…αm 6.1.1 上下文无关文法的派生树 6.1.1 上下文无关文法的派生树 例6-1设Gbra：S?S(S)|ε，(()(()))和(S)((S))的派生树。 6.1.1 上下文无关文法的派生树 关于标记ε的结点 6.1.1 上下文无关文法的派生树 最左派生(leftmost derivation) α的派生过程中，每一步都是对当前句型的最左变量进行替换。 左句型(left sentencial form) 最左派生得到