第二章-文法与语言

编译原理

CompilerPrinciples2013年9月闫雷鸣第二章文法与语言讨论问题：文法和语言的概念和定义文法和语言的分类文法等价变换句型分析简单回顾对程序的理解程序是计算机执行的一系列指令；程序是计算任务的处理对象和处理规则的描述。

•对程序设计语言的理解程序设计语言是程序的书写规范；程序设计语言的要素：一组记号(符号)和一组规则。程序设计语言程序是程序设计语言之符号集合上的、按一定规则组成的符号串。•语言是一切句子的集合；程序设计语言是一切程序的集合；把程序看做程序设计语言的句子。•程序是(程序设计）语言的句子•如何系统地构造程序？或者，一般地，如何为一个(程序设计)语言生成句子？

2.1符号串与符号串集合语言实际上是一个符号串集合；文法规定语言中句子的构造规则。句子是一个语言之字母表上按一定规则构造的符号串。2.1.1字母表字母表:有穷非空的符号集合。例A={a,b,c}∑={0,1}C语言字母表={字母，数字，界限符}

不同的语言有不同的字母表。字母表上的元素（即符号）组成符号串。2.1.2

符号串:1.符号串及其长度

符号串:由字母表上的符号所组成的有穷序列。字母表A={a,b,c}上的符号串：

a,b,c,ab,ba,aaa,aab,baa,abcab,ε(空串)

注意：顺序是重要的,ab≠baC语言字母表上的符号串？长度：|aabcaca|=7|ε|=02.子符号串若u=xvy，其中|v|≠0（|u|>=|v|）则v是u中的子符号串。（非空符号串）例a+(b-c)/d中的子符号串3.符号串的头与尾（前缀、后缀）

abc的头：a,ab,abc,Ɛx=t…

abc的尾：c,bc,abc,Ɛx=…t

4.对符号串的运算联结（或并置）：

x=aby=baxy=abbayx=baab

对任何符号串x，有x=x=x。

方幂：xn=xx…x(x自身联结n次)xn=xn-1x=xxn-1

x0=Ɛ

x3=(ab)3=ababab|xy|=|x|+|y||xn|=n|x||x0|=02.1.3

符号串集合（语言）1.符号串集合的定义1)它是一切元素都是某字母表上的符号串的集合。

2)表示法枚举法{1，11，111，1111}

省略法{1，11，111，1111，┅}

描述法{1i|i≥1}或{x|x全由1组成,|x|≥1}

注意：一定不能涉及含义,如{x|x=∑10i}。字母表∑上的一个语言就是∑上的一些符号串组成的集合。

空集ф

是一个语言，仅含一个空符号串集合{ф}也是一个语言。特别需要指出的是，Ɛ和{Ɛ}是不同的语言。2.对符号串集合的运算乘积：AB={xy|x∈A且y∈B}{1,0}{a,b,c}=?

对任何符号串x有x=x=x，A0={ε}因此，{}A=A{}=A，但ØA=AØ=Ø。

方幂：An=AA…A(n个A乘积）

An=An-1A=AAn-1

特例，字母表A的方幂，x∈An,|x|=n{1,0}3=?{1,0}n=?3.字母表的闭包与正闭包闭包A*=A0∪A1∪┅∪An∪┅{0，1，2}*

正闭包A+=A1∪┅∪An∪┅=A*-{}{0，1，2}+

x∈A+,则|x|>=1

x∈A*,则|x|>=0

任何一个语言是其字母表之正闭包的真子集。如何找出此真子集？或说，如何找出其句子？2.2文法与语言的形式定义2.2.1文法的形式定义1.重写规则（产生式规则）定义：有序对（U，u)或U::=u

A→α（或A::=α）其中，A是一个符号，称为产生式规则的左部，而α是有穷非空符号串，称为产生式规则的右部，“→

”和“::=”表示“定义为”或“由……组合成的”或“生成”，其含义是左部符号用右部的符号串定义或左部符号生成右部符号串。产生式规则可合写，如：A→α和A→β可写为A→α|β

1.重写规则（产生式规则）规则表示法：通常的E::=E+TE::=T

或E::=E+T|T

扩充的E::=T{+T}

术语：非终结符号，非终结符号集VN

终结符号，（不会出现在规则左部）终结符号集VT

（

VN∩VT=ØV=

VN∪VT）单规则：右部是单个非终结符{}用于指定重复次数<标识符>::=<字母>{<字母数字>}05[]内中符号至多出现一次<整数>::=[+|-]<数字>{<数字>}()提公因子E::=E+T|E-T可改写为E::=E(+|-)T16规则构造的例子C语言标识符的规则：<标识符>::=<字母下划线><标识符>::=<标识符><字母下划线><标识符>::=<标识符><数字><字母下划线>::=A|…|Z<字母下划线>::=a|…|z<字母下划线>::=_<数字>::=0|…|917用规则产生句子的例子如：用标识符产生式规则产生句子area.<标识符><标识符><字母下划线><标识符>a

<标识符><字母下划线>a <标识符>ea <标识符><字母下划线>ea <标识符>rea<字母下划线>rea

area其中，“=>”为推导。2.文法的定义文法G[Z]是非空有穷的重写规则集合，其中Z是识别符号（或称开始符号），G是文法名。例G1[E]：E::=E+TE::=TT::=T*FT::=FF:=(E)F::=iG2[E]：E::=E+T|TT::=T*F|FF::=(E)F::=iG[E]：E::=T{+T}T::=F{*F}F::=(E)|i文法的四要素：VN，VT，P，ZP有穷非空的重写规则集，识别符号ZVN3.

应用文法产生语言的句子

G[<句子>]:1.<句子>::=<主语><谓语><状语>2.<主语>::=<名词>3.<谓语>::=<动词>4.<状语>::=<介词><名词>5.<名词>::=Peter6.<名词>::=Berry7.<名词>::=river8.<动词>::=swims9.<介词>::=in例试以文法G[<句子>]为例考察如何应用文法来生成句子。

替换为‹句子›=>‹主语›‹谓语›‹状语›

(规则1)

=>‹名词›

‹谓语›

‹状语›(规则2)=>Peter‹谓语›‹状语›

(规则5)=>Peter‹动词›

‹状语›(规则3)=>Peterswims

‹状语›(规则8)=>Peterswims‹介词›‹名词›

(规则4)=>Peterswims

in

‹名词›(规则9)=>Peterswimsinriver(规则7)应用文法生成句子的步骤：步骤1以识别符号为当前符号串；步骤2对当前符号串中的一个非终结符号进行替换，把它替换为以此非终结符号为左部的规则之右部符号串，生成新的当前符号串；步骤3重复步骤2,直到当前符号串中不包含非终结符号，最终不包含非终结符号的符号串就是所生成的句子。说明：每步的当前符号串将称为句型，最终的终结符号串称为句子。

按上述步骤应用各个规则，可生成：

Berryswimsinriver

甚至可生成：riverswimsinPeter

表明：语法上的正确性不能保证语义上的正确性。

对当前句型中任一非终结符号进行替换，都将生成新的句型，最终生成句子。但宜用系统的方式进行推导，如，每步对最左的或最右的非终结符号进行替换。这时，分别称为最左推导与最右推导。引进句子生成中的两个重要概念：推导与归约。直接推导：=>xUy=>xuy

‹句子›=>‹主语›‹谓语›‹状语›

‹主语›‹谓语›‹状语›=>‹名词›‹谓语›‹状语›

‹名词›‹谓语›‹状语›=>Peter‹谓语›‹状语›Peter‹谓语›‹状语›=>Peter‹动词›‹状语›Peter‹动词›‹状语›=>Peterswims‹状语›Peterswims‹状语›=>Peterswims‹介词›‹名词›Peterswims‹介词›‹名词›=>Peterswimsin‹名词›Peterswimsin‹名词›=>Peterswimsinriver

直接推导时，给定v=xUy,

找到规则U::=u，把u代替U，

得到w=xuy称v直接推导到w，记为：v=>w或xUy=>xuy推导（直接推导序列）：=>+<句子>

=>‹主语›‹谓语›‹状语›=>‹名词›‹谓语›‹状语›=>Peter‹谓语›‹状语›=>Peter‹动词›‹状语›=>Peterswims‹状语›=>Peterswims‹介词›‹名词›=>Peterswimsin‹名词›=>Peterswimsinriver

推导时，给定符号串v,

找到v=>u1=>u2=>…=>un-1=>w,

得到符号串w,称v推导到w，记为：v=>+w。一般，从识别符号开始推导，例如，

<句子>=>+Peter‹谓语›‹状语›<句子>=>+Peterswimsinriver

推导长度：直接推导的步数。直接推导

:=>

直接推导时，给定v=xUy，在其中找出U，应用规则U::=u,

得到w=xuy，称v直接推导到w,或w直接归约到v,记为v=>w

一般，总有：U::=uxUy=>xuy推导:=>+

推导时，给定符号串v,找出直接推导序列：

v=>u1=>u2=>…=>un-1=>w得到符号串w,称v推导到w,或w归约到v,记为:v=>+wn称为推导的长度。

广义推导：=>*

若v=>+w或v=w，则称v广义推导到w,或广义归约到v。对照：直接推导v=>w(U::=uv=xUyw=xuy)(推导长度=1)

推导v=>+w(v=>u1=>…=>un-1=>w)(推导长度1)

广义推导v=>*w(v=>+w或v=w)(推导长度0)通常考虑的都是从识别符号出发的推导：

Z=>*xx∈(VN

∪VT)+

直接归约：v=>ww直接归约为v

归约:v=>+ww归约为v

广义归约:v=>*ww广义归约为v

请对照比较推导与归约这两个概念。重要概念：句型、句子句型：Z=>*x,x∈(VN∪VT)+

句子：Z=>*x,x∈VT+

例Peterswimsinriver注意：句子和<句子>在概念上的区别注意：应用文法生成句子仅是形式上的。例riverswimsinPeter注：句子也是句型，但句型不一定是句子。文法产生句型和句子的例子【例】设有文法G[Z]:Z::=aZb|Ɛ有推导：Z=>*ƐZ=>*aZb=>aaZbb=>*aaabbb可见，符号串

ε，aZb，aaZbb和aaabbb都是文法G[Z]的句型，而

ε

和aaabbb才是文法G[Z]的句子。30文法产生句型和句子的例子

【例】设有文法G[E]:

E::=E+T|E-T|TT::=T*F|T/F|FF::=(E)|i

试证明i+i*i是它的一个句子。

分析：只有证明i+i*i可由文法G从开始符号E推导出，即可证明i+i*i是它的一个句子。

证明：

EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i

即有E

*i+i*i

又因i+i*i中的每个符号均为终结符号，故i+i*i是它的一个句子。思考设计编程语言时，是先设计语言形式，还是先设计BNF形式的文法？例如要表示形如i+i,i+i*i的表达式建议：学习时注意积累，何种典型文法可以得到某种典型的语言形式考试考查：能够由文法写出语言，也能由语言设计出文法为什么有穷规则集合的文法能定义无穷的语言？文法G[<无正负号整数>]：

1）<无正负号整数>::=<数字序列>2）<数字序列>::=<数字序列><数字>3）<数字序列>::=<数字>4）<数字>::=05)<数字>::=16）<数字>::=27)<数字>::=38)<数字>::=49)<数字>::=510)<数字>::=611)<数字>::=711)<数字>::=812)<数字>::=9VN={<无正负号整数>,<数字序列>,<数字>}VT={0,1,2,3,4,5,6,7,8,9}<无正负号整数>=><数字序列>=><数字序列><数字>=><数字序列><数字><数字>=><数字><数字><数字>=>1<数字><数字>=>12<数字>=>123<无正负号整数>=><数字序列>=><数字序列><数字>=><数字序列><数字><数字>=><数字序列><数字><数字><数字>=>…

递归地定义规则，即，U::=U…,使得有穷个规则可能定义潜在地无穷的语言。重要概念：短语、简单短语

已知w=xuy是文法G的句型,

短语

u:Z=>*xUyU∈VN

U=>+u

简单短语

u:Z=>*xUyU∈VN

U=>u

理解：句型w=xuy中

⑴可(直接)归约且

⑵(直接)归约后所得新符号串仍为句型

的子符号串u。

例句子123中,1、2、3都是简单短语。

1、12、123、2、3都是短语。

句型<数字序列>1<数字>2

中：

简单短语有：1、2

短语有：<数字序列>1、1、<数字序列>1<数字>、2

句柄

:句型中最左的简单短语。句柄是重要概念之一。归约是自底向上的语法分析关键，何时进行归约则必须依赖句柄。分析句型时，要搞清楚哪些符号串能构成短语和直接短语。36求短语、直接短语和句柄的例子

【例】设有文法G[E]:

求出句型(F+i)－T*(E－T)的短语、简单短语和句柄。

分析：从句型的推导过程中找出其全部短语、直接短语和句柄。37

可以看出：

句型(F+i)－T*(E－T)包含以下短语：

F，i，F+i，(F+i)，E－T，(E－T)，T*(E－T)，(F+i)－T*(E－T)；简单短语有：F，i，E－T；句柄为F。注意：选择符号串判断是否短语时，必须同时满足两个条件：1）可归约；2）归约后仍是句型（即可由识别符号推导出）概括文法G:有穷非空的重写规则集合四要素：VN，VT，P，Z句型：Z=>*t,t∈(VN∪VT)+句子：Z=>*t,t∈VT+概念：推导，归约简单短语，短语，句柄4.文法句子之生成的实现实质是推导的构造。要点是推导在计算机内的存储表示。文法符号序号

后继符号结点指针其中包含两类结点，一类结点结构形如：另一类结点结构形如：这易于用C语言结构类型实现，例如，对第一类，

typedefstruct直接推导链首结点{struct符号结点*句型首符号结点指针；

struct直接推导链首结点*下一直接推导链头指针；}直接推导链首结点类型；

句型首符号结点指针

下一直接推导链头指针显然每一“列”（垂直链）中各结点相应的符号组成一个句型。这易于用C语言结构类型实现。以最左推导的建立为例，程序控制流程示意图如下。

建立最左推导

置初值

把识别符号置为当前句型,

建立一“列”结点

当前句型中包含

N

非终结符号

Y

复制当前句型一“列”结点，把所复制的作为当前句型，并建立与原有当前句型的链接

取到当前句型的最左非终结符号U相应的结点

以U为左部的Y

规则仅一个

N

显示以U为左部的各规则

用户选择一个规则，

k=规则序号

关于规则k的右部生成结点链，代替U相应的结点出口k=规则序号

由于推导过程中，进行替换的非终结符号可能作为多个规则的左部，在尚未讨论分析技术的情况下，宜于采用交互方式由用户自己选择进行直接推导的规则。这涉及到文法规则在计算机内的存放。文法的存储表示：

•一种是数组表示

•一种是链表表示

例G[E]：

E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i•数组表示：左部右部符号串右部长度C语言数据结构定义：typedefstruct{符号左部符号；符号右部符号串[MaxRightPartLength+1];int右部长度；}规则;规则

文法[MaxRuleNum+1];其中，typedefchar符号[MaxLength+1]；符号

非终结符号集[MaxVnNum+1];

符号

终结符号集[MaxVtNum+1];

为便于处理，以符号的序号代替符号本身：typedefstruct{int左部符号序号；

int右部符号串[MaxRightPartLength+1];int右部长度；}规则;规则

文法[MaxRuleNum+1];为区分非终结符与终结符，将非终结符的序号+100文法[1]中的规则E::=E+T,在计算机内的存储表示:

文法[1]：

{101，

{0，101，

1，

102}，

3}文法[2]中的规则E::=T，在计算机内的存储表示：文法[2]：

{101，

{0，102}，

1}T∈VT：T在VT中的序号

U∈VN：U在VN中的序号+100

注意：C语言数组元素的下标值从0开始，已把0号元素弃之不用。文法的链式表示：文法G[E]的数据结构G[E]：E::=E+TE::=TT::=T*FT::=FF::=(E)F::=i2.2.2语言的定义程序设计语言L是一切程序P的集合。

PL

L∑+

（∑=VT

）语言是相应文法一切句子的集合。

L(G[Z])={x|Z=>*x,x∈VT+

}

一个文法确定唯一的语言。反之？

L(G[<程序>])={P|<程序>=>*P,P∈VT+

}

语言可能是有穷的，也可能是无穷的。重要概念：递归规则递归规则左递归：U::=U…

一般递归：U::=…U…

规则右递归：U::=…U文法递归文法左递归:U=>+U…

一般递归：U=>+…U…

文法右递归：U=>+…U递归，使有穷多个规则定义的语言可以是无穷的。C语言中的规则递归和文法递归规则左递归有：

<整型常量>::=<整型常量><数字>

规则右递归有：

<因式>::=!<因式>

文法右递归于<语句>：

<语句>::=<控制语句><控制语句>::=<条件语句><条件语句>::=if(<表达式>)<语句>else<语句>

因此，

<语句>=>+…<语句>

也可以说，C语言文法递归于<语句><语句>=>+…<语句>…为语言构造文法

L1={aibjck|i,j,k≥1}aa…aabb…bbcc…ccABCABCABCSG1[S]:S::=ABCA::=Aa|aB::=Bb|bC::=Cc|c

aa…aabb…bbcc…ccAAABBSSG1’[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a注：同一种语言可设计出不同的文法；注意扩展！L2={aibick|i,k≥1}

a…aabb…bcc…cAAASSG2[S]:S::=Sc|AcA::=aAb|ab

L3={aibici|i≥1}G3[S]:S::=abC|aSBCCB::=CDCD::=BDBD::=BCbB::=bbbC::=bccC::=ccL4={a2i|i≥1}G4[S]:S::=ACaBCa::=aaCCB::=DBCB::=EaD::=DaAD::=ACaE::=EaAE::=ε56文法产生语言的例子【例1】设有文法G[Z]:Z::=aaZbb|ab求该文法所描述的语言。

分析：语言：57文法产生语言的例子【例2】设有文法G[Z]:求该文法所描述的语言。

分析：由括号组成的终结符号，且左右括号匹配。

【例3】设有文法G[Z]:求该文法所描述的语言。

分析：1后面紧跟的符号必为0或为空，即该文法产生的是不包括两个相邻1的所有0、1串。

语言：

概括1.程序设计语言是一切程序的集合；程序是在程序设计语言字母表上按一定规则构造的符号串；程序设计语言是其字母表正闭包的真子集。2.文法是重写规则的集合文法四要素：VN、VT、P、Z

文法的句型：由识别符号推导所得的符号串。文法的句子：全由终结符号组成的句型。3.语言是一切句子的集合；文法确定，则语言确定，语言给定，但可为该语言构造若干文法。递归，使有穷多个规则能定义无穷的语言。4.重要概念句型、句子推导、归约短语、简单短语、句柄递归（规则递归、文法递归）应用文法生成句子的步骤：步骤1以识别符号为当前句型步骤2对当前句型进行直接推导（把其中一个非终结符号替换为以其为左部的规则之右部符号串）步骤3重复步骤2，直到无非终结符号可被替换。通常应以系统的有规则的方式进行替换

·对最左的非终结符号进行替换（最左推导）

·对最右的非终结符号进行替换（最右推导）2.3.1Chomsky文法类和语言类1.Chomsky分类法对文法四要素概括与抽象。定义：Chomsky文法G=（VN,VT,P,Z)VNVTPZ文法及例：

G[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a2.3语言的分类2.3.1Chomsky文法类和语言类1.Chomsky分类法对文法四要素概括与抽象。定义：Chomsky文法G=（VN,VT,P,Z)VNVTPZ文法及例：

G[S]:S::=Sc|BcB::=Bb|AbA::=Aa|a

G1=（VN,VT,P1,S1)VN={S1,A,B}VT={a,b,c}P1:S1::=S1c|BcB::=Bb|AbA::=Aa|aL(G1)={aibjck|i,j,k≥1}G2=（{S2,A},{a,b,c},P2,S2)P2:S2::=S2c|AcA::=aAb|abL(G2)={aibick|i,k≥1}G3=({S3,B,C,D},{a,b,c},P3,S3)P3:S3::=abC|aS3BCCB::=CDCD::=BDBD::=BCbB::=bbbC::=bccC::=ccL(G3)={aibici|i≥1}G4=({S4,A,B,C,D,E},{a},P4,S4)P4:S4::=ACaBCa::=aaCCB::=DBCB::=EaD::=DaAD::=ACaE::=EaAE::=εL(G4)={a2i

|i≥1}分类：按规则的定义形式对文法分类

0型文法（短语结构文法PSG）：

u::=v

u∈(VN∪VT)+,v∈(VN∪VT)*1型文法（上下文有关文法CSG）：

xUy::=xuyU∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+2型文法（上下文无关文法CFG）：

U::=xuy

U∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+3型文法（正则文法RG）：

U::=VT

或U::=T

U,V∈VN,T∈VT

相应地有4类Chomsky语言：

0型语言（短语结构语言PSL）

1型语言（上下文有关语言CSL）

2型语言（上下文无关语言CFL）

3型语言（正则语言RL）注意：有时对2型文法，扩充有ε规则与ε句子

ε规则：U::=εε句子：Z=>*ε2.3.2*

形式语言与自动机Chomsky语言类和自动机的对应关系：

3型语言~有穷状态自动机

FA2型语言~下推自动机PDA1型语言~线性界限自动机LBA0型语言~图灵机TM

2.3.3形式语言的分类与程序设计语言

1.程序设计语言一般用上下文无关文法定义：

U::=u2.但语言一般是上下文有关的

(1)<标号>::=<标识符><变量>::=<标识符>goto<标号>::=goto<标识符>

<标号>:<语句>::=<标识符>:<语句>

(标识符由所在上下文确定是否标号)(2)<函数标识符>'('<实在参数表>')

'

<数组变量>'['<下标表达式表>']

'<变量>=<表达式>(标识符由后跟符号确定是函数标识符、数组变量还是变量)3.通常：词法正则文法语法上下文无关文法语义口语2.3.4对上下文无关文法的进一步讨论1*.上下文无关文法的自嵌套特性如果一个上下文无关文法G中存在具有下列特性的非终结符号U：

U=>*xUy其中x,y∈V+，则称U为自嵌套的非终结符号，包含自嵌套非终结符号的文法G称为自嵌套的上下文无关文法。

若一个上下文无关文法G不是自嵌套的，则L(G)是一个正则语言。

对任何一个正则语言，必定可构造不是自嵌套的文法。一个严格的上下文无关语言，必不能构造非自嵌套的文法。自嵌套特性把正则语言与严格的上下文无关语言区别开来。

2.与推导有关的特性⑴对于CFG，若存在句型x=x1x2…xn,有

x1x2…xn=>*y,

则必存在y1,y2,…,yn，使得

xi=>*yi(i=1,2,…,n),Z

且y=y1y2…yn。⑵设x=>*y,若x的首符号∈VT,X1X2…Xn

则y的首符号也∈VT

。反之，y的首符号∈VN,则y1y2…yn

x的首符号也∈VN

。3.ε规则

ε规则：U::=ε

Chomsky2型文法U::=u中，u∈VT+,

不包含ε规则，但有时让u∈VT*,

例如进行文法等价变换，便引进ε规则。引进ε规则，便可能产生ε句子：

Z=>*ε

对于所有非0型的语言，包括上下文无关语言，删去或添加一个ε句子，不改变原来的语言类。4*.上下文无关语言的可判定性对于一个程序设计语言来说，重要的是能机械且高效地在有限的时间内判定一个符号串是否是语法上正确的程序，换句话说，就是判定一个符号串是否是属于该(程序设计)语言的句子。这就是可判定性问题。一般地，可判定性问题可以这样描述：设集合L是集合S的一个子集，而x是S的一个任意元素,问:是否可能机械而高效地判定x是否L的一个成员?

对于上下文无关语言，这问题的答案是肯定的。

2.4文法等价和等价变换2.4.1文法等价的概念文法G1与G2等价，若L(G1)=L(G2)。1.例L1={aibjck|i,j,k≥1}G1[S]:S::=ABCA::=Aa|aB::=Bb|bC::=Cc|cG1'[S]:S::=Sc|BcB::=Bb|AbA::=Aa|aG1与G1'等价。2.文法等价变换的必要性文法等价变换的概念：对文法进行变换，使得变换后的文法满足某种要求，并且与原文法等价，这种变换称为文法的等价变换。文法等价变换的必要性

•使文法类与语言类一致

•消去二义性

•使文法适用于某种分析技术

•特殊需要文法等价变换的种类：

•压缩文法等价变换

•消去左递归文法等价变换

•消除单规则文法等价变换

•增广文法等价变换

2.4.2压缩文法等价变换1.压缩了的文法目的：使文法中任一规则都能用来生成文法的句子，使文法中无多余规则。多余规则：U::=U形规则不满足下列条件的规则Ｕ::=u：条件１Ｚ=>*…U…(U出现在句型中）条件２u=>*tt∈VT+(可推导到终结符号串）概念：若文法中任一规则都满足上述条件１和条件2,则称压缩了的文法。

Z=>*xUy=>xuy=>*tt∈VT+,即，t是句子。76文法压缩（化简）的基本思想条件1）若一符号不能出现在文法的任何句型中，则该符号是无用的。

条件2）若一个非终结符不能推导出终结符号串，则该非终结符是无用的。

从识别符号开始或从终结符号开始。删除这些规则，不会改变文法描述的语言2.无用规则的判别算法

算法步骤如下:

步骤１规则展开成非缩写形式并删除U::=U形规则;

步骤２判别条件１，删除不满足条件１的规则;

步骤３判别条件２，删除不满足条件２的规则;

步骤４重复步骤２和步骤３，直到无规则被删除。实现：采用加标记的算法。

采用加标记的算法。对条件1：U::=xVy中，若规则左部U加过标记，则对右部非终结符号V加标记。对条件2：U::=xVy,若规则右部全由终结符号和加过标记的非终结符号组成,则对左部非终结符号加标记。对于文法G[Z]：

Z∷=BeA∷=Ae｜A｜eB∷=Ce｜AfC∷=CfD∷=f

步骤1展开并删除U::=U形规则成：

Z∷=BeA∷=AeA∷=eB∷=CeB∷=AfC∷=CfD∷=f步骤2判条件1，加标记：

*******

Z∷=BeA∷=AeA∷=eB∷=Ce

****

B∷=AfC∷=CfD∷=f规则D∷=f是多余的,应删除。从而得到文法

G'[Z]：

Z∷=BeA∷=AeA∷=eB∷=CeB∷=AfC∷=Cf

步骤3判条件2，加标记：

*****

Z∷=BeA∷=AeA∷=e

*

*

B∷=CeB∷=AfC∷=Cf

规则B∷=Ce与C∷=Cf是多余的，应删除。

重复判条件1与2，最终得到与文法G[Z]等价的压缩了的文法G″[Z]:Z∷=BeA∷=AeA∷=eB∷=Af

压缩文法等价变换的规范步骤：步骤１规则展开成非缩写形式并删除U::=U形规则;步骤２判别条件１，删除不满足条件１的规则;步骤３判别条件２，删除不满足条件２的规则;步骤４重复步骤２和步骤３，直到无规则被删除。3.*

实现之考虑2.4.3消去左递归的文法等价变换左递归的存在将导致自顶向下语法分析失败自顶向下：即从识别符号出发，使用不同规则进行推导。左递归可使分析陷入无穷循环，导致栈溢出U=>Ux=>Uxx=>Uxxx=>…=>因此，对自顶向下分析技术，需要消除左递归。2.4.3消去左递归的文法等价变换1.规则左递归的消去(U::=Ux|y)U=>Ux=>Uxx=>Uxxx=>…=>yxx…xx例G[E]：E::=E+T|TU'T::=T*F|FF::=(E)|iE=>E+T=>E+T+T=>…U'=>T+T+T…+T+TU'a.改成右递归T+T+T…+T+TU::=Ux|y→U::=yU'U'::=xU'|εE'例E::=TE'E'::=+TE'|ƐE'T::=FT'T'::=*FT'|ƐE'一般情况下，U::=Ux1|Ux2|…|Uxm|y1|y2|…|ynU::=Ux1|Ux2|…|Uxm|y1|y2|…|yn→U::=U(x1|x2|…|xm)|(y1|y2|…|yn)→U::=(y1|y2|…|ym)U'U’::=(x1|x2|…|xn)U'|ε

b.用扩充表示法

U::=Ux|y→U::=y{x}一般情况下，

U::=Ux1|Ux2|…|Uxn|y1|y2|…|ym→U::=U(x1|x2|…|xn)|(y1|y2|…|ym)→U::=(y1|y2|…|ym){x1|x2|…|xn}2.文法左递归的消去（间接的规则左递归）基本思想:对非终结符号排序成U1、U2、…、Un后文法等价变换成呈下形:U1::=Ui1…(或U1::=T…)i1>1U2::=Ui2…(或U2::=T…)i2>2…Uj::=Uij…(或Uj::=T…)ij>j…Un-1::=Un…(或Un-1::=T…)Un::=T…T∈VT一般地，对于Ui::=Uj…必有：j>i,从而不可能产生U=>+U…U->…->Ua文法左递归消去文法左递归的算法步骤:

步骤１把非终结符号排序成U1,U2,…,Un

步骤２以上列顺序执行下列程序：

for(i=1;i<=n;i++){for(j=1;j<=i-1;j++){把形如Ui::=Ujr的规则改写成:Ui::=xj1r|xj2r|…|xjkr

其中Uj::=xj1|xj2|…|xjk是对于Uj的一切规则

}

消除关于Ui的规则左递归;}消去文法左递归等价变换的解题规范：步骤1识别是规则左递归还是文法左递归步骤2进行相应的文法等价变换步骤3给出消去了左递归的等价文法例设有文法G[S]：

G[S]：S∷=Sa｜Tbc｜Td

T∷=Se｜gh

试消去其文法左递归。

G[S]：S∷=Sa｜Tbc｜Td

T∷=Se｜gh解:步骤1排序：U1=SU2=T(n=2)

步骤2执行循环：

i=1，j=1：j＞i－1，不执行关于j的循环，消去关于U1=S的规则左递归（改写成右递归）：

S∷=(Tbc|Td)S'S'∷=aS'|εi=2，j=1：有规则T∷=Se|gh，呈U2::=U1…形，把S∷=(Tbc|Td)S'代入，得

T∷=(Tbc|Td)S'e|gh因此,T∷=T((bc|d)S'e)|gh

消去关于U2=T的规则左递归如下:T∷=ghT'T'∷=(bc|d)S'eT'|ε最后得到文法G[S]：

G[S]：S∷=Sa｜Tbc｜TdT∷=Se｜gh消去了左递归的等价文法G'[S]：

S∷=T(bc｜d)S'S'∷=aS'|εT∷=ghT'T'∷=(bc|d)S'eT'|ε例设有文法G[A]：

G[A]:A∷=Ba|Cb|c

B∷=dA|Ae|f

C∷=Bg|Ah

试消去该文法的左递归。

G[A]:A∷=Ba|Cb|c

B∷=dA|Ae|f

C∷=Bg|Ah解：首先判别知，该文法存在文法左递归。步骤1排序成：U1=A，U2=B,U3=C；步骤2执行循环：

i=1,j=1:j＞i－1，不执行关于j的循环，且关于U1=A不存在规则左递归。

i=2,j=1:有规则B∷=Ae|dA|f，呈U2::=U1…形，把规则A∷=Ba|Cb|c代入，得

B∷=(Ba|Cb|c)e|dA|f或B∷=Bae｜Cbe｜ce｜dA｜f消去关于U2=B的规则左递归，所以,B∷=(Cbe|ce|dA|f)B'B'::=aeB'|ε

i=3,j=1:有规则C::=Ah|Bg，呈U3::=U1…形，把规则A::=Ba|Cb|c代入,C::=(Ba|Cb|c)h|Bg或C::=B(ah|g)|(Cb|c)hi=3,j=2:由规则C∷=B(ah|g)|(Cb|c)h,呈U3::=U2…形，把规则B∷=(Cbe|ce|dA|f)B'代入，得

C::=(Cbe|ce|dA|f)B'(ah|g)|(Cb|c)h或C::=C(beB'(ah|g)|bh)|(ce|dA|f)B'(ah|g)|ch消去关于U3=C的规则左递归，得到

C∷=((ce|dA|f)B'(ah|g)|ch)C'|εC'::=(beB'(ah|g)|bh)C'|ε最后得到消去了左递归的等价文法

G'[A]:A∷=Ba｜Cb｜cB∷=(Cbe|ce|dA|f)B'

B'::=aeB'|εC∷=((ce|dA|f)B'(ah|g)|ch)C'|εC'::=(beB'(ah|g)|bh)C'|ε3.*

实现之考虑要点:·识别文法是规则左递归还是文法左递归

·文法在计算机内的存储表示2.5

语法分析树与句型分析

2.5.1语法分析树的概念1.语法分析树的引进

<句子>

术语：结点根结点末端结点

<主语><谓语><状语>

边

分支

<名词><动词><介词><名词>

分支名字结点

分支结点

Berryswimsinriver

分支结点符号串子树子树末端结点符号串树末端结点符号串语法分析树

一个句型推导过程的树形表示称为语法分析树，或简称语法树。语法树的优点是：它有助于理解一个句子语法结构的层次。语法树通常表示成一棵倒立的树，根在上，树叶在下。

语法树离不开句型，一棵语法树是相对于某个句型而存在，脱离句型的语法树是不存在的。句子

Berryswinsinriver的推导：<句子>=><主语><谓语><状语>=><名词><谓语><状语>=>Berry<动词><状语>=>Berryswins<状语>=>Berryswins<介词><名词>=>Berryswinsin<名词>

=>Berryswinsinriver如何为它构造语法分析树？2.从推导构造语法分析树从推导构造语法分析树的步骤如下.

步骤1以识别符号为根结点，对应于第一个直接推导向下作分支。步骤2从第二个直接推导左边被替换的非终结符号相应的结点向下作分支,对应于此直接推导。步骤3类似地对应于每个直接推导,从左边被替换的非终结符号对应的结点向下作分支,相应于此直接推导。如此继续，直到推导完。重要性质：

分支的分支结点符号串是相应句型中相对于分支名字结点的简单短语。

Z=>*xUy=>xuyU=>u

子树的末端结点符号串是相应句型中相对于子树根结点的短语。

Z=>*xUy=>+xuyU=>+u利用语法分析树寻找句型中的简单短语和短语。3.从语法分析树构造推导这是从推导构造语法分析树的逆过程。

EF*i+i=>i*i+iT*i+i=>F*i+i=>i*i+iE+TT*F+i=>T*i+i=>F*i+i=>i*i+i