编译原理第03章 文法和语言课件

编译原理

文法和语言Tel:7046821E-mail:1编译原理第03章文法和语言第三章 文法和语言本章目的为语言的语法描述寻求工具工具要对程序设计语言给出精确无二义的语法描述。（严谨、简洁、易读）形式工具--形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。2编译原理第03章文法和语言3.1文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型分析3.7实用说明第三章文法和语言3编译原理第03章文法和语言文法的直观概念一个程序设计语言是一个记号系统，如同自然语言一样，它的完整的定义应包括语法和语义两个方面。所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序。目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具。语法只是定义什么样的符号序列是合法的，与这些符号的含义毫无关系阐明语法的一个工具是文法，这是形式语言理论的基本概念之一。示例：汉语句子的描述语言概述4编译原理第03章文法和语言汉语句子的描述语法规则定义字符串的判断5编译原理第03章文法和语言语法规则定义〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉6编译原理第03章文法和语言字符串的判断有了一组规则以后，按照如下方式用它们导出句子：开始去找∷=左端的带有〈句子〉的规则并把它由∷=右端的符号串代替，这个动作表示成：〈句子〉

〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应规则的∷=右端代替之。比如，选取了〈主语〉，并采用规则〈主语〉∷=〈代词〉，那么得到：〈主语〉〈谓语〉

〈代词〉〈谓语〉，重复做下去。句子：“我是大学生”的全部动作过程是：〈句子〉

〈主语〉〈谓语〉

〈代词〉〈谓语〉

我〈谓语〉

我〈动词〉〈直接宾语〉

我是〈直接宾语〉

我是〈名词〉

我是大学生7编译原理第03章文法和语言字符串的判断“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。8编译原理第03章文法和语言符号和符号串定义：符号：可以相互区别的记号（元素）。字母表（）：符号（元素）的非空有穷集合。符号串：由字母表

中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε(没有符号的符号串)是

上的符号串2.若x是

上的符号串,a是

的元素,则xa是

上的符号串3.

y是

上的符号串,当且仅当它可以由1和2导出。例如：Σ={a,b}ε,a,b,aa,ab,aabba…都是

上的符号串符号串的运算9编译原理第03章文法和语言符号串的运算既然将语言定义为一个集合，那么有关集合的运算也适合语言。即：设L是（∑上的）一个语言,M是（∑上的）一个语言，则语言L和M的并，交，差，补是一个语言。符号串的头、尾、子串符号串的长度符号串的连接符号串的方幂符号串的集合10编译原理第03章文法和语言符号串的头、尾、子串符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀.符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana的一个后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如:ana是符号串banana的一个子串.对于每个符号串s，s和ε两者都是符号串s的前缀，后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串x,相应地，是s的前缀，后缀或子串，并且s

x。11编译原理第03章文法和语言符号串中符号的个数。符号串s的长度记为|s|。ε的长度为0符号串的长度12编译原理第03章文法和语言符号串的连接设x、y是符号串，则x、y的连接是把y的符号写在x的符号之后得到的符号串xy如x=ab,y=cd则xy=abcd有εa=aε13编译原理第03章文法和语言符号串的方幂方幂：设x是符号串，把x自身连接n次得到的符号串z，即z=aa…aa称为符号串x的方幂。写作z=an示例：a1=a,a2=aaa0=ε14编译原理第03章文法和语言符号串集合若集合A中所有元素都是某字母表

上的符号串，则称A为字母表

上的符号串集合。两个符号串集合A和B的乘积定义为：AB=xy|xA且yB若集合A=ab,cdeB=0,1，则AB=ab1,ab0,cde0,cde1使用*表示上的所有有穷长符号串（包括ε）组成的集合。Σ*称为Σ的闭包。

上的除ε外的所有符号串组成的集合记为

+。

Σ+称为Σ的正闭包。Σ*=Σ0∪Σ1∪Σ2∪⋯∪Σn⋯Σ+=Σ1∪Σ2∪⋯∪Σn⋯Σ*={ε}∪Σ+Σ+=ΣΣ*=Σ*Σ15编译原理第03章文法和语言文法和语言的形式定义文法和语言的形式定义文法的定义推导的定义句型（子）的定义语言的定义文法等价的定义16编译原理第03章文法和语言语言概述语言是由句子组成的集合，是由一组符号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体每个句子构成的规律语言研究每个句子的含义每个句子和使用者的关系每个程序构成的规律研究程序设计语言每个程序的含义每个程序和使用者的关系语法Syntax

语言研究的三个方面语义Semantics

语用Pragmatics17编译原理第03章文法和语言程序设计语言研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax

语义Semantics

语用Pragmatics18编译原理第03章文法和语言

语言研究的三个方面语法--表示构成语言句子的各个记号之间的组合规律语义--表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用--表示在各个记号所出现的行为中，它们的来源、使用和影响。每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。19编译原理第03章文法和语言文法的定义文法G定义为四元组(VN，VT，P，S)其中VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。

VN和VT不含公共的元素，即VN∩

VT=φ

通常用V表示VN∪

VT

，称为文法G的字母表或字汇表。规则，也称重写规则、产生式或生成式，是形如α→β或α∷=β的(α，β)有序对，其中α是字母表V的正闭包V+中的一个符号，β是V*中的一个符号。α称为规则的左部，β称作规则的右部。示例：例3.1例3.220编译原理第03章文法和语言例3.1文法G=（VN，VT，P，S），VN={S},VT={0,1}，P={S→0S1,S→01}。这里，非终结符集中只含一个元素S；终结符集由两个元素0和1组成；有两条产生式；开始符号是S。21编译原理第03章文法和语言例3.2文法G=(VN，VT，P，S)其中VN={标识符，字母，数字}VT={a,b,c,…，x,y,z,0,1,…，9}P={〈标识符〉→〈字母〉

〈标识符〉→〈标识符〉〈字母〉

〈标识符〉→〈标识符〉〈数字〉

〈字母〉→a

〈字母〉→b

…

〈字母〉→z

〈数字〉→0

〈数字〉→1

…

〈数字〉→9}

S=〈标识符〉

这里，使用尖括号"〈"和"〉"括起非终结符。22编译原理第03章文法和语言推导的定义直接推导“”：如α→β是文法G=(Vn，VT，P，S)的规则(或说是P中的一产生式)，γ和δ是V*中的任意符号，若有符号串v，w满足：v=γαδ，w=γβδ

则说v(应用规则α→β)直接产生w，或者说，w是v的直接推导，也可以说，w直接归约到v，记作vw。如果存在直接推导的序列：示例：直接推导多步推导23编译原理第03章文法和语言直接推导的示例对于例3.1的文法G，可以给出直接推导的一些例子如下：v=0S1,w=0011，直接推导：0S1

0011，使用的规则：S→01，这里γ=0，δ=1。v=S,w=0S1，直接推导：S

0S1使用的规则：S→0S1，这里γ=ε，δ=εv=0S1,w=00S11，直接推导：0S1

00S11，使用的规则：S→0S1，这里γ=0，δ=1。对于例3.2的文法G，直接推导的例子有：v=〈标识符〉，w=〈标识符〉〈字母〉，直接推导：〈标识符〉〈标识符〉〈字母〉，使用的规则：〈标识符〉→〈标识符〉〈字母〉，这里γ=δ=εv=〈标识符〉〈字母〉〈数字〉，w=〈字母〉〈字母〉〈数字〉，直接推导：〈标识符〉〈字母〉〈数字〉〈字母〉〈字母〉〈数字〉，使用的规则：〈标识符〉→〈字母〉。这里γ=ε，δ〈字母〉〈数字〉。v=abc〈数字〉，w=abc5，直接推导：abc〈数字〉abc5,使用的规则：〈数字〉→5，这里γ=abc,δ=ε。24编译原理第03章文法和语言多步推导的示例对例3.1的文法，存在直接推导序列v=0S1

00S11

000S111

00001111=w，即0S100001111，也可记作0S100001111对例3.2的文法，存在直接推导序列v=〈标识符〉

〈标识符〉〈数字〉

〈字母〉〈数字〉

x〈数字〉

x1=w，即<标识符>x1，也可记作<标识符>x1。25编译原理第03章文法和语言句型(子)的定义设G[S]是一文法，如果符号串x是从识别符号推导出来的，即有Sx，则称x是文法G[S]的句型。若x仅由终结符号组成，即Sx，x∈VT*，则称x为G[S]的句子。例：S，0S1，000111都是例3.1的文法G的句型，其中000111是G的句子。〈标识符〉〈字母〉，〈字母〉〈数字〉，a1等都是例3.2文法G的句型，其中a1是G的句子。26编译原理第03章文法和语言语言的定义文法G所产生的语言定义为集合{x|Sx，其中S为文法识别符号，且x∈VT*}。可用L(G)表示该集合。从定义可以看出两点：第一，符号串x可从识别符号推出，也即x是句型。第二，x仅由终结符号组成，即x是文法G的句子。也就是说，文法描述的语言是该文法一切句子的集合。例：例3.1G：S→0S1，S→01L(G)={0n1n|n≥1}例3.327编译原理第03章文法和语言例3.3设G=(VN，VT，P，S)，VN={S,B,E}，VT={a,b,e}，P由下列产生式组成：(1)S→aSBE(2)S→aBE(3)EB→BE(4)aB→ab(5)bB→bb(6)bE→be(7)eE→ee则L（G）={anbnen|n≥1}

28编译原理第03章文法和语言文法的等价若L（G1）=L（G2），则称文法G1和G2是等价的。示例：文法G1[A]：A→0RA→01R→A1与G2[S]：S→0S1S→01等价。29编译原理第03章文法和语言文法的类型乔姆斯基分类示例：例3.4例3.5乔姆斯基分类文法之间关系对应于乔姆斯基分类文法的语言文法和语言之间的关系30编译原理第03章文法和语言乔姆斯基对文法的分类通过对产生式施加不同的限制，Chomsky（乔姆斯基）将文法分为四种类型：0型文法：对文法G=(VN，VT，P，S)的任一产生式α→β，都有α∈(VN∪VT)*且至少含有一个非终结符，β∈(VN∪VT)*。1型文法（上下文有关文法）：对文法G=(VN，VT，P，S)的任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外。2型文法（上下文无关文法）：对文法G=(VN，VT，P，S)的任一产生式α→β，都有α∈VN

，β∈(VN∪VT)*。3型文法（正规文法）：设G=(VN，VT，P，S)，若P中的每一个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，a是终结符。3型文法G=(VN，VT，P，S)的P中的规则有两种形式：一种是前面定义的形式，即：A→aB或A→a其中A，B∈VN

，a∈VT*，另一种形式是：A→Ba或A→a，前者称为右线性文法，后者称为左线性文法。正规文法所描述的是VT*上的正规集。31编译原理第03章文法和语言例3.4G=({S,A,B},{a,b},P,S)，其中P由下列产生式组成：S→aBA→bAAS→bAB→bA→aB→bSA→aSB→aBB或将P改写为：S→aB|bAA→bA|aA→a|A→aSB→bS|B→aB|b则G是正规文法或3型文法。32编译原理第03章文法和语言例3.5文法G=({S,A,B},{0,1},P,S)，其中P由下列产生式组成：S→0AA→1BS→1BB→1BS→0B→1A→0AB→0A→0S或将P改写为：S→0A|1B|0A→0S|1B|0AB→1B|1|0则G是正规文法或3型文法。33编译原理第03章文法和语言乔姆斯基分类文法之间关系2型文法1型文法0型文法四种文法之间的逐级“包含”关系3型文法34编译原理第03章文法和语言对应乔姆斯基分类文法的语言0型文法产生的语言称为0型语言。1型文法或上下文有关文法（CSG

）产生的语言称为1型语言或上下文有关语言（CSL）。2型文法或上下文无关文法（CFG

）产生的语言称为2型语言或上下文无关语言（CFL）。

3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）。

35编译原理第03章文法和语言文法和语言之间的关系四种文法之间的关系是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。 36编译原理第03章文法和语言上下文无关文法及其语法树语法树句型能够构造关联语法树的条件示例：例3.7最左（右）推导二义性文法判断依据示例：例3.8二义性文法与二义性语言的区别37编译原理第03章文法和语言句型能够构造关联语法树的条件给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树(推导树)。这棵树满足下列4个条件：①每个结点都有一个标记，此标记是V的一个符号。②根的标记是S。③若一结点n至少有一个它自己除外的子孙（子结点），并且有标记A，则A肯定在VN中。④如果结点n的直接子孙，从左到右的次序是结点n1，n2，…，nk，其标记分别为A1，A2，…，Ak，那么A→A1A2…Ak一定是P中的一个产生式。38编译原理第03章文法和语言例3.7G=(｛S,A｝,｛a,b｝,P,S)，其中P为：

①S→aAS

②A→SbA

③A→SS

④S→a

⑤A→ba右图是G（aabbaa）的一棵推导树。39编译原理第03章文法和语言最左（右）推导如果在推导的任何一步α

β，其中α，β是句型，都是对α中的最左(最右)非终结符进行替换，则称这种推导为最左(最右)推导。在形式语言中，最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。最左推导示例S

aAS

aSbAS

aabAS

aabbaS

aabbaa最右推导示例S

aAS

aAa

aSbAa

aSbbaa

aabbaa40编译原理第03章文法和语言二义文法的判断依据若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。

或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，即，不存在一个算法，它能在有限步骤内，确切判定任给的一个文法是否为二义的。我们所能做的事是为无二义性寻找一组充分条件(当然它们未必都是必要的)。41编译原理第03章文法和语言例3.8文法G=(｛E｝,｛+,*,i,(,)｝,P,E)其中P={

E→i

E→E+E

E→E*E

E→(E)}是二义性的，假若规定了运算符“+”与“*”的优先顺序和结合规则，即按惯例，让“*”的优先性高于“+”，且它们都服从左结合，那么就可以构造出一个无二义文法。定义表达式的无二义文法G[E]：

E→T|E+T

T→F|T*F

F→(E)|i

它和上述文法产生的语言是相同的。即它们是等价的。42编译原理第03章文法和语言二义性文法与二义性语言的区别文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。43编译原理第03章文法和语言句型的分析句型分析是识别一个输入符号串是否为语法上正确的程序的过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。句型的分析算法分类句型的分析算法反映语法树的构造过程句型分析的有关定义句型分析的有关问题44编译原理第03章文法和语言句型的分析算法分类自上而下分析法：是从文法的开始符号出发，反复使用各种产生式，寻找“匹配”于输入符号串的推导。示例：例3.9自下而上分析法：从输入符号串开始，逐步进行“归约”，直至归约到文法的开始符号。示例45编译原理第03章文法和语言两种方法反映语法树的构造过程自上而下方法：自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。自下而上方法：自下而上方法是从输入符号串开始，以它做为语法树的末端结点符号串，自底向上地构造语法树。46编译原理第03章文法和语言例3.9：自上而下分析例：考虑文法G[S]；

①S→cAd

②A→ab

③A→a

识别输入串w=cabd是否该文法的句子。推导过程：S

cAd

cabd47编译原理第03章文法和语言示例：自下而上分析例：考虑文法G[S]；

①S→cAd

②A→ab

③A→a

识别输入串w=cabd是否该文法的句子。 S

A

A

cabd

ca

bd

ca

b

d

规约过程构造的推导：cAd

cabdS

cAd48编译原理第03章文法和语言句型分析的有关定义令G是一文法，S是文法的开始符号，αβδ是文法G的一个句型。如果有：SαAδ且Aβ则称β是句型αβδ相对于非终结符A的短语。特别，如有A

β则称β是句型αβδ相对于规则A→β的直接短语(也称简单短语)。一个句型的最左直接短语称为该句型的句柄。示例从句型的推导树中查找方法49编译原理第03章文法和语言示例文法G[E]的一个句型i*i+i。为了叙述方便，将句型改写为i1*i2+i3。因为有：EF*i2+i3

且F

i1则称i1是句型i1*i2+i3的相对于非终结符F的短语，也是相对于规则F→i的直接短语。又有：Ei1*F+i3

且F

i2则i2是句型i1*i2+i3的相对于F的短语，也是相对于规则F→i的直接短语，还有：Ei1*i2+F且F

i3则i3也是句型i1*i2+i3的相对于F的短语，也是相对于规则F→i的直接短语。ET*i2+i3，且Ti1则i1是句型i*i2+i3的相对于T的短语。Ei1*i2+T且Ti3则i3是句型i1*i2+i3的相对于T的短语。EE+i3

且Ei1*i2则i1*i2是句型i1*i2+i3的相对于E的短语。EE且E

i1*i2+i3则i1*i2+i3是句型i1*i2+i3相对于E的短语。即i1，i2，i3，i1*i2和i1*i2+i3都是句型i1*i2+i3的短语，而且i1，i2，i3均为直接短语，其中i1是最左直接短语，即句柄。虽然i2+i3是句型i1*i2+i3的一部分，并不是它的短语，因为尽管有Ei2+i3，但不存在从文法开始符号E到i1*E的推导。50编译原理第03章文法和语言从句型的推导树中查找方法从句型的推导树上很容易找出句型的短语和直接短语。设A是句型αβδ的某一子树的根，其中β是形成此子树的末端结点的符号串，则其中β是句型αβδ的相对于A的短语。若这个子树只有一层分支，则β是句型αβδ的直接短语。示例51编译原理第03章文法和语言示例：推导树中找短语52编译原理第03章文法和语言句型分析的有关问题在自上而下的分析方法中如何选择使用哪个产生式进行推导？假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？在自下而上的分析方法中如何识别可归约的串？在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”。存在确定和不确定分析。53编译原理第03章文法和语言实用说明

有关文法的实用限制上下文无关文法中的ε规则无用符号和无用产生式的消除ε-产生式的消除单产生式的消除54编译原理第03章文法和语言有关文法的实用限制在实用中，我们将限制文法中不得含有有害规则和多余规则：有害规则，是指形为U→U的产生式。它对描述语言显然是没有必要的。说它有害，是说它只会引起文法的二义性。多余规则，是指文法中那些连一个句子的推导都用不到的规则，这类规则在文法中以两种形式出现。一种是文法中某些非终结符不在任何规则的右部出现，所以任何句子的推导中不可能用到它。对文法G=(VN，VT，P，S)来说，为了保证其任一非终结符A在句子推导中出现，必须满足如下两个条件：①A必须在某句型中出现。即有SαAβ，其中α，β属于(VT∪VN)*

。②必须能够从A推出终结符号串t来。即At，其中t∈VT。若程序设计语言的文法包含有多余规则时，其中必定有错误存在，因此检查文法是否包含多余规则是很有必要的。55编译原理第03章文法和语言上下文无关文法中的ε规则上下文无关文法中某些规则可具有形式A→ε，称这种规则为ε规则。ε规则会使得有关文法的一些讨论和证明变得复杂,有时会限制这种规则的出现。上下文无关文法的相关定理定理3.1定理3.256编译原理第03章文法和语言定理3.1若L是由文法G=(VN，VT，P，S)产生的语言，P中的每一个产生式的形式均为A→α，其中A∈VN，α∈(VN∪VT)*(即α可能为ε)，则L能由这样一种文法产生：每一个产生式或者为A→β形式，其中A∈VN，β

∈(VN∪VT)+(即β≠ε)，或者S→ε且S不出现在任何产生式右边。57编译原理第03章文法和语言定理3.2如果G=(VN，VT，P，S)是一个上下文有关文法，则存在另一个上下文有关文法G1，它所产生的语言与G产生的相同，即L(G)=L(G1)，其中G1的开始符号不出现在G1的任何产生式的右边。若G为上下文无关文法或正规文法，类似结论成立。58编译原理第03章文法和语言无用符号和无用产生式的消除定义：设G=(VN，VT，P，S)是一文法，我们说G中的一个符号x(VN∪VT)是有用的指x至少出现在一个句子的推导过程中。即x必须同时满足以下两个条件：存在α、β

V*，有S⇒*∈αxβ存在w

VT*,αxβ⇒*w否则就说x是无用的。如果一个产生式的左部或右部含有无用符号，则此产生式称之为无用产生式。消除算法算法1算法2示例59编译原理第03章文法和语言算法11、分别置VN(1)和P(1)

为

；2、对于P中的每一产生式A→

，若

VT*，则将A置于VN(1)

中；3、对于P中的每一产生式A→x1x2…xm若每个xi都属于VN(1)

或VT

，则将A置于VN(1)

；4、重复步骤3，直到VN(1)不再增大为止；5、对于P中的每一产生式B→y1y2…yn

，若B及每一个yi都属于VN(1)∪VT

，则将此产生式B→y1y2…yn置于P(1)。60编译原理第03章文法和语言算法21、分别置VN’、VT’和P’

为

；2、将文法的开始符号S置入VN’中；3、对于G(1)中任何形如A→x1|x2|

…|

xm的产生式，若A

VN’，则将符号串x1，x2，

…，

xm中的全部非终结符号置于VN’中，而将其中的全部终结符号置于VT’中；4、重复步骤3，直到VN’和VT’都不再增大为止；5、将P中左右部仅含VN’∪VT’中符号的所有产生式置P’

。61编译原理第03章文法和语言示例文法的定义已知文法G=（{S,U,V,W}，{a,b,c}，P，S），产生式P的组成如下：S→aSS→WS→UU→aV→bVV→acW→aW执行算法1执行算法262编译原理第03章文法和语言执行算法1第一步，由于产生式U→a、V→ac的右部均为终结符号串，故置VN(1)

={U，V}；第二步，对于产生式S→U，由于U

VN(1)

，故将S置于中，所以VN(1)

={S，U，V}；于是得到以下文法G1：G1=（{S,U,V},{a,b,c},P(1),S），其中P(1)由如下产生式组成：S→aSS→UU→aV→bVV→ac63编译原理第03章文法和语言执行算法2第一步，置VN’={S}；第二步，因为G1中含有产生式S→U、U→a，故应将U、a分别置于，即VN’={S，U}VT’={a};因此得到等价的且不含无用符号和无用产生式的文法为G2=（{S，U}，{a}，P’，S），其中，P’由如下产生式组成：S→aSS→UU→a64编译原理第03章文法和语言ε-产生式的消除算法3算法4（ε不属于文法所产生的语言）算法5（ε属于文法所产生的语言）示例：ε不属于文法所产生的语言ε属于文法所产生的语言65编译原理第03章文法和语言算法31、作集合W1={A|产生式A→εP}；2、作集合序列

WK+1=WKU{B|B→

P,且

WK+}；K

1

并使WK+1

收敛；令W=WK+1,则对于每一个AW，有A⇒*ε。对于上述W，如果G中不含有可能导出ε的符号，则W=

。66编译原理第03章文法和语言算法41、利用算法3，可将分