安徽大学编译原理课件第三章详解

安徽大学编译原理课件第三章详解演示文稿1第1页，共130页。优选安徽大学编译原理课件第三章2第2页，共130页。知识结构3第3页，共130页。3.1文法的直观概念第三章文法和语言所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序目前广泛使用的手段是上下文无关文法，即用上下文无关文法作为程序设计语言语法的描述工具4第4页，共130页。程序设计语言的描述：语法：语义：语用：程序的结构或形式语言所代表的含义语言的实际应用5第5页，共130页。例如，对于赋值语句x:=a+b*c的非形式描述是：语法：赋值语句＝变量＋:=＋表达式语义：先求右部，然后把结果给左部变量语用：赋值语句可用来计算和保存表达式的值形式化方法：用一整套带有严格规定的符号体系来描述问题的理论和方法形式语言：一种不考虑含义的符号语言6第6页，共130页。程序设计语言的语义分成：静态语义：是一系列限定规则，并确定哪些合乎语法的程序是合适的动态语义（运行语义、执行语义）：表明程序要做什么，要计算什么7第7页，共130页。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构：8第8页，共130页。例如,有一组规则:<句子>::=<主语><谓语><主语>::=<冠词><形容词><名词><冠词>::=the<冠词>::=a<形容词>::=big<谓语>::=<动词><直接宾语><动词>::=ate<直接宾语>::=<冠词><名词><名词>::=cat<名词>::=mouse显然,由这一组规则可以产生句子:

Thebigcat/mouseateamouse/cat9第9页，共130页。这样的语言描述称为文法使用文法作为工具，不仅为了严格地定义句子的结构，也是为了适当条数的规则把语言的全部句子描述出来，可以说文法是以有穷的集合刻画无穷的集合的一个工具。10第10页，共130页。3.2符号和符号串一.字母表和符号串1.语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合2.字母表（符号集）：是一个非空有穷集合3.符号（字符）：字母表中的元素4.符号串：符号的有穷序列。注意：

表示空符号串！5.符号串集合：字母表

上若干个符号串组成的集合11第11页，共130页。重要约定：小写字母a,b,c,•••,r表示符号小写字母s,t,u,•••,z表示符号串大写字母A,B,C,•••,Z表示符号串集合12第12页，共130页。二.符号串的运算1.符号串相等

设x、y是字母表

上的两个符号串，若x与y的诸符号依次相等，则该两符号串相等，记为x=y。13第13页，共130页。2.符号串长度

设x是字母表

上的符号串，符号串中包含符号的个数称为符号串x的长度，用

x

表示例:（1）|

|=0;（2）|ax|=|xa|=|x|+1(a∈∑)【注】对于字母表A={begin,if,real,end}【1】符号串beginif的长度是多少？2【2】begini或eginif是不是A上的符号串14第14页，共130页。3.符号串的连结设x与y是字母表

上的两个符号串，把y的所有符号相继写在x的符号之后所得到的符号串称为x与y的连结，用xy表示

注意:

|xy|=|x|+|y|

x=x

=xxy≠yx(一般说来)15第15页，共130页。4.符号串的逆(1)若x=abcd,则=dcba(2)=

设x是字母表

上的符号串，其逆为符号串x的倒置，记为。16第16页，共130页。5.符号串的前缀、后缀和子串

设x、y、z是字母表

上的符号串，则称x为符号串xy的前缀，y是符号串xy的后缀，x、y、z、xy、yz是符号串xyz的子串例:字母表A={a,b,c}上的符号串x=abc，则x的

前缀有,a,ab,abc；后缀有,c,bc,abc；真前缀有,a,ab；真后缀有,c,bc。17第17页，共130页。6.符号串集合的乘积设A、B为两个符号串集合，其乘积为AB={xy|xA,yB}例:(1)若A={ab,cd},B={ef,gh}则AB={abef,abgh,cdef,cdgh}(2)∵

x=x

=x∴{

}A=A{

}=A18第18页，共130页。7.空集不含任何元素的集合，记为Ø注意:(1)ØA=AØ=Ø;(2)

Ø19第19页，共130页。8.符号串的幂设x是字母表

上的符号串，则x的幂运算为x0=

x1=xx2=xx••••••xn=xn-1x(xxn-1)例:若x=ab,则x0=

,x1=ab,x2=abab,••••••,xn=abab•••ab20第20页，共130页。9.符号串集合的幂设A是符号串集合，则符号串A的幂运算为：A0={}A1=AA2=AA••••••An=An-1A(AAn-1)例:若A={ab,cd}则:A0={},A1={ab,cd},A2={abab,abcd,cdab,cdcd},••••••21第21页，共130页。注意:A*=A0∪A+

A+=AA*=A*A若A={a,b}则:A*={

,a,b,aa,ab,ba,bb,aaa,•••}A+={a,b,aa,ab,ba,bb,aaa,•••}10.集合A的闭包与正闭包正闭包表示为A+，集合A的闭包表示为A*，22第22页，共130页。3.3文法和语言的形式定义一.如何来描述一种语言如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，（要么永远继续下去）

23第23页，共130页。二.相关概念1.规则（重写规则、产生式、生成式）

一个规则是一个二元组,通常写作α::=β或α→βα称为规则的左部，是字母表V的正闭包V+中的一个符号；β称为规则的右部，是V*中的一个符号；(::=)读作“定义为”，这是一条关于α的规则（产生式）24第24页，共130页。2.文法定义3.1：文法G定义为四元组（VN，VT，P，S）VN：非终结符（语法实体、变量）集VT：终结符集P：产生式（αβ）集合，α∈(VN∪VT)*且至少包含一个非终结符，β∈(VN∪VT)*VN、VT、P是非空有穷集出现在规则的左部、用<>括起来、表示一定语法概念的词。

语言中不可再分割的字符串(包括单个字符组成的串)。注：终结符是组成句子的基本单位。

用来定义符号串之间关系的一组(语法)规则

25第25页，共130页。S：开始符（识别符），它是一个非终结符，至少要在一条规则中作为左部出现VN∩VT=ØV=VN∪VT，称为文法G的字母表（字汇表）26第26页，共130页。例3.1文法G=（VN，VT，P，S），其中VN={S}，VT={0,1}，P={S0S1,S01}

27第27页，共130页。例3.2文法G=（VN，VT，P，S），其中VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P＝{<标识符><字母><标识符><标识符><字母><标识符><标识符><数字><字母>a┇<字母>z<数字>0┇<数字>9}S=<标识符>28第28页，共130页。很多时候，不用将文法G的四元组显式地表示出来，而只将产生式写出29第29页，共130页。一般约定：第一条产生式的左部是识别符用尖括号括起来的是非终结符（或者用大写字母表示）不用尖括号括起来的是终结符（或者用小写字母表示）将G也写成G[S]，其中S是识别符30第30页，共130页。推导：定义V*中的符号之间的关系：直接推导：长度为n(n≥1)的推导：长度为n(n≥0)的推导：*+31第31页，共130页。定义3.2：文法G＝（VN，VT，P，S），αβ是一条规则，γ和δ是V*中的任意符号，若有符号串v、w满足：v=γαδ，w=γβδ，则称v直接推导到w，v

w，或w直接归约到v例：G：S

0S1，S

01

S

0S100S11000S1110000111132第32页，共130页。定义3.3：如果存在直接推导的序列：v=w0w1w2…wn=w(n>0)则称v推导出w（推导长度为n），或称w归约到v，记作+33第33页，共130页。定义3.5：若有Sx，则称x是文法G[S]的句型，若x仅由终结符组成，则称x为G[S]的句子*定义3.4：若有vw，或v=w，则记作：vw+*34第34页，共130页。定义3.6：文法G所产生的语言定义为集合L(G)=｛x|Sx，其中S为文法识别符号，且x∈VT*｝文法描述的语言是该文法一切句子的集合例：G：S0S1，S01L(G)={0n1n|n≥1}*35第35页，共130页。例3.3文法文法G[S]：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL（G）={anbnen|n≥1}思考：a4b4e4怎么推导？36第36页，共130页。定义3.7：若L(G1)＝L(G2)，则称文法G1和G2是等价的例如文法G[A]：A0RA01RA1和文法G[S]：S0S1S01等价L(G)={0n1n|n≥1}37第37页，共130页。3.4文法的类型乔姆斯基(Chomsky)于1956年建立形式语言的描述他把文法分成：0型、1型、2型、3型设G＝（VN，VT，P，S），如果它的每个产生式αβ是这样一种结构：α∈(VN∪VT)*且α至少包含一个非终结符，β∈(VN∪VT)*，则G是一个0型文法（短语结构文法、无限制文法），简称PSG。38第38页，共130页。设G＝（VN，VT，P，S），如果它的每个产生式αβ是这样一种结构：α∈(VN∪VT)+，β∈(VN∪VT)*，则G是一个0型文法思考：这样定义可以吗？39第39页，共130页。设G＝（VN，VT，P，S），如果它的每个产生式αβ均满足：|β|≥|α|，仅仅Sε除外，则文法G是1型文法（上下文有关文法，上下文敏感文法），简称CSG。例3.1、3.2、3.340第40页，共130页。例：文法G[S]：SCD AbbA CaCA BaaB CbCB BbbB ADaD Cε BDbD Dε AabDL(G)={w|w∈{a,b}*}41第41页，共130页。有些定义中，将上下文有关文法的产生式的形式描述为α1Aα2α1βα2，其中α1、α2和β都在V*中，β≠ε，A在VN中42第42页，共130页。设G＝（VN，VT，P，S），如果它的每个产生式αβ均满足：α是一个非终结符，β∈V*，则文法G是2型文法（上下文无关文法），简称CFG。43第43页，共130页。有时将2型文法的产生式表示为Aβ的形式，其中A∈VN，也就是用β取代非终结符A时，与A所在的上下文无关，因此取名为上下文无关。例3.1、3.244第44页，共130页。例3.4：文法G[S]：SaB|bA Aa|aS|bAA Bb|bS|aBB45第45页，共130页。设G＝（VN，VT，P，S），如果它的每个产生式AαB或Aα（ABα或Aα），其中A和B都是非终结符，α∈VT*，则文法G是3型文法（正规文法，正则文法，有穷状态文法），简称RG。

例3.5-1：文法G[S]：S0A|1B|0 A0A|1B|0S B1B|1|0若文法中所有的产生式均为A

αB或A

α形式，则此文法为右线性的若文法中所有的产生式均为A

Bα或A

α形式，则此文法为左线性的46第46页，共130页。例3.5-2：文法G[S]：S0A|1B|0 AA0|B1|0S BB1|1|0第一，左边有非终结符，所以此文法是0型文法；第二，左边符号串长度不大于右边，所以此文法是1型文法；第三，左边只有一个非终结符，所以此文法是2型文法；第四，由于文法中既有左线性文法又有右线性文法，所以此文法不是3型文法；综上所述，此文法是2型文法。47第47页，共130页。四个文法类的定义是逐渐增加限制的0型1型2型3型因此，每一种正规文法（3型）都是上下文无关的，每一种上下文无关文法（2型）都是上下文有关的，而每一种上下文有关文法（1型）都是0型文法。各类文法对应的语言叫各类文法语言。48第48页，共130页。0型语言---------------图灵机四类语言与自动机1型语言---------------线性界限自动机2型语言---------------下推自动机3型语言---------------有穷状态自动机49第49页，共130页。通常自然语言是上下文有关的，程序设计语言也不例外。四类语言与程序设计语言例1语言{wcw｜w

(a,b)*}表示一个句子中出现有第二个w时必须同时出现有第一个w，如果让w表示标识符，且第一个w代表说明部分，第二个w代表语句部分，则表明标识符w可以任意长，且标识符w必须先说明后使用。这类语言是上下文有关的。50第50页，共130页。例2设有语言{anbmcndm｜n,m≥1},其中an与bm可以表示两个过程中的形参表，分别有n个和m个参数，而cn与dm则分别表示调用这两个过程的实参表。an与cn中及bm与dm中分别具有相同的指数，表示实参与形参的个数必须相同。这类语言也是上下文有关的。与词法有关的规则属于正则文法与局部语法有关的规则属于上下文无关文法与全局语法和语义有关的规则属于上下文有关文法51第51页，共130页。3.5上下文无关文法及其语法树【注】上下文无关文法所定义的语法范畴是完全独立于这种范畴可能出现的环境的，即是和其上下文无关的，不同于自然语言。一.上下文无关文法Context-FreeGrammar

（2型文法CFG）设G＝（VN，VT，P，S），如果它的每个产生式αβ均满足：α是一个非终结符，β∈V*，则文法G是上下文无关文法。1.定义52第52页，共130页。上下文无关文法有足够的能力描述现今程序设计语言的语法结构。

算术表达式语句赋值语句条件语句读语句……2.描述对象53第53页，共130页。算术表达式文法表示例3.6文法G=({E},{+,*,i,(,)},P,E} P:E→i E→E+E E→E*E E→(E)赋值语句文法表示<赋值语句>→i=E条件语句文法表示<条件语句>→if<条件>then<语句>|

if<条件>then<语句>else<语句>注：无特殊说明，“文法”均指上下文无关文法54第54页，共130页。一.语法树(推导树ParseTree)1.定义

语法树是这样的一个语法结构，它的结点由符号组成。根结点对应于识别符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。55第55页，共130页。

语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。

结点：符号

根结点：识别符号

中间结点：非终结符

叶结点：终结符或非终结符

有向边：表示结点间的派生关系56第56页，共130页。2.引入语法树的意义作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。3.作用直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树。57第57页，共130页。4.语法树的相关概念结点：每个树的结点对应于一个符号。结点的名字就是该符号。边：两个结点之间的连线。根结点：没有边进入的结点。分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）子树：语法树的某个结点和它向下射出的部分末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。58第58页，共130页。4.语法树的特征给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征：1、根结点的标记是开始符号S；2、每个结点的标记都是V中的一个符号；3、若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么

A→A1A2…AR一定是P中的一条规则；59第59页，共130页。4、若一标记为A的结点至少有一个除它以外的子孙，则A∈VN5、若树的所有叶结点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。60第60页，共130页。线性推导：我们称用

符号进行的推导为线性推导。树型推导与线性推导的不同：线性推导指明了推导的顺序，而树型推导则没有指明推导的顺序。因此，句型一般只有一棵语法树(如果无二义性)，而线性推导则可很多。句型推导过程<==>句型语法树的生长过程61第61页，共130页。从推导构造语法树方法：把识别符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。从识别符号开始，逐步建立推导序列。由根结点开始，自上而下建立语法树。62第62页，共130页。例如：推导SBBdbaAcdcABAcBd

AccddabccddS63第63页，共130页。从语法树构造推导自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。从句型开始，自右向左地逐步进行归约，建立推导序列。64第64页，共130页。方法：从分支建立直接推导，然后从语法树中剪去这个分支，直到无分支可剪。语法树表明了在推导过程中使用了哪条规则和使用在哪个非终结符号上，但它并没有表明使用规则的顺序。一棵语法树可能对应不止一种推导。65第65页，共130页。从语法树构造推导的过程SBBdbaAcdc(1)(2)(3)(4)例如文法G[S]：S→ABA→aAb|abB→cBd|cd存在下面的推导可能：S

AB

AcBd

(4)(3)

Accdd

abccdd(2)(1)S

AB

abB

abcBd

abccdd对于同一个句型或句子，可以通过不同的推导序列推导出来，这是因为在推导过程中所选择的非终结符的次序不同。

66第66页，共130页。例3.7句型aabbaa的可能推导序列和语法树G[S]:S→aASA→SbAA→SSS→aA→baS

aASSbAa

a

b

aS

aAS

aAa

aSbAa

aSbbaa

aabbaaSaASaSbASaabASaabbaS

aabbaaSaASaSbAS

aSbAa

aabAa

aabbaa67第67页，共130页。二.规范推导与规范归约最左(右)推导指对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最左(右)非终结符号。最右推导也称为规范推导。规范推导的逆过程，称为最左归约，也称为规范归约。用最左推导所推导出的句型称为最左句型用最右推导所推导出的句型称为最右句型，通常称为规范句型68第68页，共130页。【例】给出了下列文法G（1）<无正负号整数>

<数字序列>（2）<数字序列>

<数字序列><数字>|<数字>（3）<数字>

0|1|2|3|4|5|6|7|8|9VT={0,1,2,3,4,5,6,7,8,9}VN={<无正负号整数>,<数字序列>,<数字>}判断数据2634是否是C语言合法的数据。【解】（1）用最右推导，每次用产生式的规则替换最右边的非终结符，推导过程如下：<无正负号整数>

<数字序列>

<数字序列><数字>

<数字序列>4

<数字序列><数字>4

<数字序列>34

<数字序列><数字>34

<数字序列>634

263469第69页，共130页。（2）用最左推导，每次直接推导都替换最左边的非终结符，推导过程如下：<无正负号整数>

<数字序列>

<数字序列><数字>

<数字序列><数字><数字>

<数字序列><数字><数字><数字>

<数字><数字><数字><数字>

2<数字><数字><数字>

26<数字><数字>

263<数字>

263470第70页，共130页。疑问

一个句型是否只对应唯一的一棵语法树？一个句型是否只有唯一的一个最左（最右）推导？不是课堂练习：G[E]：E→E+E|E*E|(E)|i对于句子i＋i*i，给出两种不同的规范推导，并画出语法树。71第71页，共130页。EEE+EE*iiiEEE*EE+iii这两种不同的推导对应了两种不同的语法树(1)E==>E+E==>E+E*E==>E+E*i==>E+i*i==>i＋i*i(2)E==>E*E==>E*i==>E+E*i==>E+i*i==>i＋i*i72第72页，共130页。

我没说她偷了我的钱。（可是有人这么说）我没说她偷了我的钱。（我确实没这么说）我没说她偷了我的钱。(可是我是这么暗示的）我没说她偷了我的钱。（可是有人偷了）我没说她偷了我的钱。(但她用这钱做了某事)我没说她偷了我的钱。（她偷了别人的钱）我没说她偷了我的钱。（她偷了别的东西）

二义性73第73页，共130页。三.二义性文法1.定义（1）文法二义性若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。（或者，若一个文法存在某个句子有两个不同的最左（右）推导）。（2）语言先天二义产生某上下文无关语言的每一个文法都是二义的。74第74页，共130页。2.二义性文法的证明要判定一个文法是否是二义性文法，或它是否产生一个先天二义性的上下文无关语言，是个递归不可解的。即不存在一个算法，它能在有限的步骤内，确切地判断出某个给定的文法是否是一个二义性文法。我们要证明一个文法是否是一个二义性文法，就是找到该文法的一个句型特例，能够画出这个句型的两棵语法树，该文法就是二义性文法。75第75页，共130页。3.为什么要避免文法有二义性二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。76第76页，共130页。4.解决途径可以采用两种途径来解决文法的二义性问题1不改变文法中原有的规则，仅加进一些语法的非形式规定。如1：对于文法G[E]:E→iE→E+EE→E*EE→(E)规定运算符优先顺序和结合律，即*优先于+，+、*服从左结合。

如2：C语言中二义性的消除是通过约定，在符合if语句中，else子句总是属于最近的尚无else子句的那个if语句。77第77页，共130页。SifBthenSifBthenelseSSSifBthenelseSSifBthenS设文法G[S]：S→ifBthenS|ifBthenSelseS|i：=E给出符号串ifBthenifBthenSelseS的语法树。78第78页，共130页。改写文法，把排除二义性的规则合并到原有文法中。2EiET+TF*iFTFi例:算术表达式的文法E::=E+T|TT::=T*F|FF::=(E)|iG[E]：E→E+E|E*E|(E)|i

79第79页，共130页。3.6句型的分析任务:句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。

对于程序设计语言来说，句型分析就是一个识别输入符号串是否为语法上正确的程序的过程。80第80页，共130页。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串。句型分析算法采用从左到右的分析算法。句型的分析算法分类自上而下分析法(Top-Downparsing)从文法的开始符号出发，反复使用各种产生式，寻找与输入符号串匹配的推导。自下而上分析法(Bottom-Upparsing)从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。

81第81页，共130页。两种方法反映了两种语法树的构造过程：自上而下方法是从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树82第82页，共130页。一.基本思想

自上而下的分析方法就是从识别符号出发，看是否能推导出待检查的符号串，如果能推导出这个符号串，则表明此符号串是该文法的句型或句子，否则就不是。或者说，以文法的识别符号作为根结点，看是否能构造出一棵语法树，而且此语法树所有叶子结点从左到右所构成的符号串恰好是待检查的符号串。如果能生成这样的语法树，则表明待检查的符号串是该文法的一个句型或句子，否则就不是。3.6.1自上而下的分析方法83第83页，共130页。例3.9：文法G：S→cAd

A→ab

A→a

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

c A d

c A d

a

b推导过程：S

cAd

cAd

cabd二.例题

84第84页，共130页。一.基本思想

自下而上的分析方法是从待检查的符号串出发，看最终是否能归约到文法的识别符号。如果能归约到文法开始的识别符号，则表明此待检查的符号串是该文法的一个句型或句子，否则便不是。3.6.2自下而上的分析方法85第85页，共130页。例3.9：文法G：S→cAd

A→ab

A→a

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

A

A

cabd

ca

bd

ca

b

d

规约过程构造的推导：cAd

cabdS

cAd二.例题

86第86页，共130页。3.6.3句型分析的有关问题一.自上而下方法的主要问题对输入串cabd自上而下构造语法树的另一过程不成功，不成功的原因是选错产生式A→a自上而下分析的主要问题是如何选择使用哪个产生式进行推导:假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？ScAda87第87页，共130页。有一种解决方法是从各种可能的选择中挑选一种，并希望它是正确的。如果发现它是错误的，我们必须退回，再试着进行另外的选择，这种方式称为回溯。【总结】自上而下分析方法是从文法的识别符号开始，选择相应的产生式规则进行推导。但在推导过程中会出现回溯现象。我们把出现回溯的分析称为不确定的自顶向下分析方法。这种方法花费时间多，效率低，编程实现时复杂，如果对文法加以限制，就可以避免回溯，这就出现了我们后面要提到的LL(1)分析方法。88第88页，共130页。二.自下而上分析的主要问题对输入串cabd的两种归约过程 （1）cabd|-cAd|-S归约到开始符 （2）cabd|-cAbd不能归约到开始符自下而上分析的主要问题是如何识别可归约的串：

在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”为了刻划“可归约串”,引入下面的概念89第89页，共130页。短语，直接短语和句柄定义: 设αβδ是文法G[S]中的一个句型，如果有S=*>αAδ且A=+>β，则称β是句型αβδ相对于非终结符A的短语。 特别的如有A=>β，则称β是句型αβδ相对于规则A→β的直接短语。 一个句型的最左直接短语称为该句型的句柄(Handle)。句柄就是“可归约串”90第90页，共130页。例.设有文法G[S]：S→aAcBe,A→Ab︱b,B→d。给出句型aAbcde的所有短语、所有直接短语和唯一的句柄。解：（1）∵SaAcBeaAcde且AAb∴Ab是句型aAbcde相对于非终结符A的短语

∵SaAcBeaAbcBe且Bd∴d是句型aAbcde相对于非终结符B的短语∵SaAcBeaAbcBeaAbcde且S=S∴aAbcde是句型aAbcde相对于非终结符S的短语91第91页，共130页。（2）∵S=*>aAbcde且A→Ab是该文法的产生式∴Ab是句型aAbcde相对于产生式A→Ab的直接短语∵S=*>aAbcde且B→d是该文法的产生式∴d是句型aAbcde相对于产生式B→d的直接短语（3）句型aAbcde的句柄是唯一的，它就是Ab。（Ab是在句型最左边的直接短语）92第92页，共130页。从句型的推导树上很容易找出句型的短语和直接短语。设A是句型αβδ的某一子树的根，其中β是形成此子树的末端结点的符号串，则其中β是句型αβδ相对于A的短语。若这个子树只有一层分支，则β是句型αβδ的直接短语。93第93页，共130页。求一个句型的句柄

给定某个句型，要求出该句型的句柄，比较直观的方法就是画出该句型的语法树。该语法树的一棵子树的叶子结点（从左到右）组成的符号串便是这个句型关于子树根结点的一个短语。语法树的一棵简单子树（只有单层子树）的叶子结点组成的符号串是这个句型关于简单子树根结点的一个直接短语。语法树的最左的简单子树叶子结点组成的符号串就是这个句型的句柄。94第94页，共130页。子树与短语的关系：①每个子树的叶子串是相对于该子树的根的短语②每个叶子分支(简单子树)的叶子串是一简单短语③最左的叶子分支的叶子串是句柄（最左简单短语）95第95页，共130页。例G[E]:ET|E+TTF|T*FF（E）|i句型i*i+iETF*i3+ETTFFi1i2短语：i1、i2、i3、i1*i2

、i1*i2+i3直接短语：i1、i2、i3句柄：i1i196第96页，共130页。3.7有关文法实用中的一些说明引入文法的目的：描述程序设计语言一方面，对文法提出一些限制条件，但并不真正限制语言；另一方面，对文法进行扩充97第97页，共130页。3.7.1有关文法的实用限制1、若文法中有如U::=U的规则，则这就是有害规则，它会引起二义性，而无任何用处。例如存在U::=U，U::=a|b,则有两棵语法树：UaUUa文法中不能含有有害规则和多余规则98第98页，共130页。2、多余规则：（1）某条规则U::=u的左部非终结符U（U不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此规则。【不可到达】（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。【不可终止】例如给定G[S]，若其中关于U的规则只有如下一条： U::=xUy该规则是多余规则。若还有U::=a，则此规则并非多余若某文法中无有害规则或多余规则，则称该文法是压缩过的。99第99页，共130页。文法化简的步骤查找有无形如P

P的产生式，若有则删除；若某个产生式在推导过程中永远不会被用到，删除它；若某个产生式在推导过程中不能从中导出终结符，删除它。最后，整理所有剩余产生式，就得到简化的文法。100第100页，共130页。例3.10文法G[S]：

1)S→Be 2)S→Ec 3)A→Ae 4)A→e 5)A→A6)B→Ce 7)B→Af 8)C→Cf9）D→f

G[S]:

S→BeA→AeA→eB→Af化简文法【1】【2】【3】【3】【3】101第101页，共130页。上下文无关文法限制：(化简后)不存在任何形如PP的产生式(多余)每个非终结符P必须都有用处b.必须存在终结符串，使P，即P不存在永不终结的回路。a.从S出发，存在SP*+102第102页，共130页。ε规则：形如A→ε的产生式，其中A∈VN某些著作和讲义中限制这种规则的出现。因为ε规则会使有关文法的一些讨论和证明变得复杂两种定义的唯一差别是ε句子在不在语言中如果语言L有一个有穷的描述，则L∪{ε}也同样有一个有穷描述。并且可以证明，若L是上下文有关语言、上下文无关语言或正规语言，则L∪{ε}和L-{ε}分别是上下文有关语言、上下文无关语言和正规语言3.7.2上下文无关文法中的ε规则103第103页，共130页。定理3.1若L是由文法G=(VN,VT,P,S)产生的语言，P中的每一个产生式的形式均为A→α,其中A∈VN，α∈V*，则L能由这样的一种文法产生，即每一个产生式或者为A→β形式，其中A∈VN，β∈V+,或者A→ε形式，且S不出现在任何产生式右边。104第104页，共130页。定理3.2如果G是上下文有关文法，则存在另一个上下文有关文法G1，L(G)=L(G1)，且G1的开始符号不出现在G1的任何产生式的右边。又如果G是一个上下文无关文法，也能找到这样一个上下文无关文法G1，如果G是是一个正规文法，则也能找到这样一个正规文法G1。105第105页，共130页。3.8典型例题及解答一.设计一个文法定义一个已知的语言1.文法是一个四元组G=(VN,VT,P,S)，文法四大要素中，关键是一组规则,它定义（或描述）了一个语言的结构。从文法定义可知,文法对于程序设计者来说，文法给出了语言的精确定义和描述。106第106页，共130页。3.设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。4.若语言是无穷集合,设计该语言的文法一定是递归的。2.分析已知语言句子的结构特征,设计出相应的一组规则，但不唯一。107第107页，共130页。例1.设L1={a2nbn|n>=1}，试构造生成L1的文法G1。【解】设n=1，L1=aabn=2，L1=aaaabbn=3，L1=aaaaaabbb

……所以得：S

aaSbS

aab108第108页，共130页。例2.设L2={abna|n>=1}，试构造生成L2的文法G2。【解】首先固定不变的，有S→aAa然后递归定义变化的，有A→bA∣b【注】若改为n≥0，文法怎么改？只修改最后一条规则：A→bA∣b∣ε109第109页，共130页。【解一】S→aSS→aBB→bBB→bCC→cC|c例3.给出语言L3={aibjck|i,j,k≥1}的文法。【注】若改为k≥0，文法怎么改？只修改最后一条规则：C→cC∣c∣ε110第110页，共130页。【解二】可以采用拆分法把字符串分块考虑，然后再各个分别写出产生式。【解题】S→ABCA→aA∣aB→bB∣bC→cC∣c111第111页，共130页。例4.考虑下述两个语言L1={anb2ncm|n,m>=0}L2={anbmc2m|n,m>=0}通过分别给出上述语言的文法来证明这些语言都是上下文无关的。【解】G1:S→ABA→ε∣aAbbB→ε∣cBG2:S→ABA→ε∣aAB→ε∣bBcc112第112页，共130页。例5.设L4={

|

(a,b)*且

中含有相同个数的a和b}试构造生成L4的文法G4。

【解】S

S

bB，S

aAA

bS|bA

aAAB

aS|a|bBB

S→

S→aSbSS→bSaS

113第113页，共130页。例6.设L5={

|

(0,1)*且

中1的个数为偶数}试构造生成L4的文法G5。【解】S

S

0S，S

1AA

0A,A

1S114第114页，共130页。例7.写一个上下文无关文法，使其语言是能被5整除且不以0开头的无符号整数的集合。(如{5，10，15，…})【解】能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。G[S]:S→MF|5F→5|0N→1|2|3|4|5|6|7|8｜9D→N|0M→MD|N115第115页，共130页。语言L(G)=L(G’){bn|n>0}{bn|n>=0}{abn|n>0}{bna|n>=0}语言和文法构造方法小结文法G文法G’S→bS|bS→Sb|bS→bS|εS→Sb|εS→DBB→bB|bD→aS→aBB→Bb|bS→PDD→aP→bP|εS→PaP→Pb|ε116第116页，共130页。{(ab)n|n>0}{ambn|m>0,n>0}{ambn|m>=0,n>0}{anbn|n>0}{a2nbn|n>=0}

S→ES|EE→abS→Sab|abS→ABA→aA|aB→bB|bS→aS|aBB→Bb|bS→ABA