发布时间 : 星期三 文章编译原理 - 复习重难点更新完毕开始阅读487eb1c128ea81c759f5780b
from成都信息工程大学软件工程学院
消除空产生式 定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式。 证明：根据G1，构造G2的方法如下： (1) ={A | A} (2) ={A | A +, +}。 (3) 从G1中删除所有空产生式。 (4) 从G1中删除只能导出空串的非终极符。 (5) 对于文法中任意产生式AX1X2…Xi-1XiXi+1…Xn a.若XiVT，不做动作； b.若XiVN- c.若XiA X1X2…Xi-1Xi+1…Xn； 例： AaBcD Bb | DBB | d 详见Page18 消除不可达产生式 定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2中的每个非终极符必出现在它的某个句型中。 证明：根据G1，构造文法G2的方法如下： (1) ={Z | Z是文法的开始符}。 (2) ={B | AxByG1, BVN, A} (3) 若一个产生式左部非终极符AA为左部的所有产生式。 消除特型产生式 注：形如A->B(B为非终极符)的产生式为特型产生式，特型产生式在语法分析中会降低分析速度，因此应该消除。 定理：对任一文法G1，可以构造文法G2，使得L(G1)=L(G2)，且在G2中没有特型产生式。 证明：构造无特型产生式的文法G2的方法如下： (1) 对文法G1中任意非终极符A，求集合 A={B | A+B, BVN}。 (2) 若BA，且BG中的一个非特型产生式，则补充如下规则A (3) 去掉文法G1中的所有的特型产生式。 (4) 去掉新的文法中的无用产生式。 例： AB | D | aB BC | b Cc DB | d 消除左递归 一个文法含有下列形式的产生式时 （1） AAa |b AVN, a , (VNVT)* （2） A B | B A | b A,B VN, a ,, (VNVT)* 其中（1）为直接左递归，（2）为间接左递归，因此文法中只要有A+A…，则称from成都信息工程大学软件工程学院
文法为左递归的。 文法的化简： 文法应没有多余的或有害的规则。 化简：(1) 删除形如A→A的产生式。 (2) 删除不可到达的文法符号及其相应的产生式。 (3) 删除不可终止的非终结符及其相应的产生式。 【例2-21】 文法G： S → aS | W | U U → a V → bV | ac W → aW 化简后的文法G： S → aS | U U → a W 是不可终止的、V 是不可到达的。 文法的二义性 可见：（1）一棵语法树表示了一个句型的多种可能的不同推导过程， 但未必是所有的。 （2）一个句型未必只有一棵语法树。 最左推导：在推导的任何一步α?β（α、β是句型）都是对α中的最左非终结符进行替换。 from成都信息工程大学软件工程学院
最右推导：在推导的任何一步α?β（α、β是句型）都是对α中的最右非终结符进行替换。也称规范推 导，推出的句型称规范句型。 例如 最左推导： E ? E*E ? i*E ? i*E+E ? i*i+E ? i*i+i 最右推导： E ? E*E? E*E+E ? E*E+i ? E*i+i ? i*i+I 显然，一棵语法树表示的最左（右）推导是唯一的！ 定义：若一个文法存在某个句子，它对应两棵（或以上）不同的语法树，或 它有两个不同的最左（右）推导，则该文法是二义的（具有二义性）。 二义性文法：如果一个文法的某个句型有两棵不同的语法分析树，则称该文法二义性为二义性文法。 文法G=( {+,*,I,(,)}, {E}, E, P),其中P为： E i E E + E E E * E E ( E )
from成都信息工程大学软件工程学院
1. 正规式和正规集的定义 定义 ：设有字母表Σ，则 （1）ε和 ?都是Σ上的正规式，所表示的正规集是{ε}和?； （2）若a∈Σ，则a是Σ上的正规式，所表示的正规集是{a}； （3）若U、V都是Σ上的正规式，它们所表示的正规集分别记为L(U) 和L(V)，则U|V（或）、U·V（连接，也可写UV）和U*（闭包）也 都是正规式，它们所表示的正规集分别为L(U)∪L(V) 、L(U) L(V) （乘积）和(L(U))*； （4）仅由有限次使用上述三步骤得到的表达式才是Σ上的正规式， 仅由这些正规式所表示的集合才是Σ上的正规集。 优先级从高到低为“*”（闭包）、“·”（连接）、“|”（或），括号优先。