自动机与形式语言_第六章讲述.pptx

2017-4-7 1 第6章 上下文无关语言 Gbra：S?S(S)|ε L(Gbra)不是RL,是CFL 高级程序设计语言的绝大多数语法结构都可以用上下文无关文法(CFG)描述。。 BNF(巴科斯范式：Backus normal form，又叫Backus-naur form)。 2017-4-7 2 第6章 上下文无关语言 主要内容 关于CFL的分析 派生和归约、派生树 CFG的化简 无用符、单一产生式、空产生式 CFG的范式 CNF GNF CFG的自嵌套特性 2017-4-7 3 第6章 上下文无关语言 重点 CFG的化简。 CFG到GNF的转换。 难点 CFG到GNF的转换，特别是其中的用右递归替换左递归的问题。 2017-4-7 4 6.1 上下文无关语言 文法G=(V，T，P，S)被称为是上下文无关的。 如果除了形如A?ε的产生式之外，对于?α?β∈P，均有|β|≥|α|，并且α∈V成立。 关键：对于?A∈V，如果A?β∈P，则无论A出现在句型的任何位置，我们都可以将A替换成β，而不考虑A的上下文。 2017-4-7 5 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 2017-4-7 6 6.1.1 上下文无关文法的派生树 算术表达式x+x/y↑2的不同派生 E?E+T?T+T?F+T?P+T?x+T?x+T/F?x+F/F ?x+P/F?x+x/F?x+x/F↑P?x+x/P↑P?x+x/y↑P ?x+x/y↑2 E?E+T?E+T/F?E+T/F↑P?E+T/F↑2?E+T/P↑2 ?E+T/y↑2? E+F/y↑2? E+P/y↑2? E+x/y↑2 ? T+x/y↑2? F+x/y↑2? P+x/y↑2?x+x/y↑2 E?E+T?T+T?T+T/F?F+T/F?F+T/F↑P ?P+T/F↑P?x+T/F↑P?x+F/F↑P?x+F/F↑2 ?x+F/P↑2?x+P/P↑2?x+P/y↑2?x+x/y↑2 2017-4-7 7 6.1.1 上下文无关文法的派生树 文法Gexp1句子x+x/y↑2的结构。 8 6.1.1 上下文无关文法的派生树 S - SS | (S) | () (())() 9 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是其父顶点的惟一儿子。 2017-4-7 10 6.1.1 上下文无关文法的派生树 别称 生成树 分析树(parse tree) 语法树(syntax tree) 顺序 v1，v2是派生树T的两个不同顶点，如果存在顶点v，v至少有两个儿子，使得v1是v的较左儿子的后代，v2是v的较右儿子的后代，则称顶点v1在顶点v2的左边，顶点v2在顶点v1的右边。 2017-4-7 11 6.1.1 上下文无关文法的派生树 结果(yield) 派生树T的所有叶子顶点从左到右依次标记为X1，X2，…，Xn，则称符号串X1X2…Xn是T的结果。 一个文法可以有多棵派生树，它们可以有不同的结果。 句型α的派生树：“G的结果为α的派生树”。 2017-4-7 12 6.1.1 上下文无关文法的派生树 派生子树(subtree) 满足派生树定义中除了对根结点的标记的要求以外各条的树叫派生子树(subtree)。 如果这个子树的根标记为A，则称之为A子树。 惟一差别是根结点可以标记非开始符号。 2017-4-7 13 6.1.1 上下文无关文法的派生树 定理6-1 设CFG G=(V，T，P，S)，S?*α的充分必要条件为G有一棵结果为α的派生树。 证明： 证一个更为一般的结论：对于任意A∈V，A?*α的充分必要条件为G有一棵结果为α的A-子树。 充分性：设G有一棵结果为α的A-子树，非叶子顶点的个数n施归纳，证明A?*α成立。 2017-4-7 14 6.1.1 上下文无关文法的派生树 设A-子树有k+1个非叶子顶点，根顶点A的儿子从左到右依次为v1，v2，…，vm，并且它们分别标记为X1，X2，…，Xm 。 A?X1X2…Xm∈P 。 以X1，X