《程序设计语言与编译》课程PPT教学课件（高职）第十五讲 自底向上语法分析

3角三节自麻向上语法分析之 方法从输入串开始,归约直至文法开 始符

第三节 自底向上语法分析 方法:从输入串开始,归约,直至文法开 始符

O.规范归约简介 1.什么叫规范归约? 假定α是文法G的一个句子序列nOxn1,0 满足下述条件时称为规范归约 (1)n= (2)α为文法的开始符即α0=S; (3)对vi0<isn,α1是从α经把句柄替换为相 应产生式的左部符号而得到的

O. 规范归约简介 1. 什么叫规范归约? 假定是文法G的一个句子,序列n ,n-1 ,…,0 满足下述条件时称为规范归约。 (1) n=α; (2) 0为文法的开始符,即0 =S; (3)对i,0<in, i-1是从i经把句柄替换为相 应产生式的左部符号而得到的

2.分析过程 例1:G(E)E→E+TT T→T*FF F→(E)i 计+i的分析过程

2. 分析过程 例1: G(E) E→E+T│T T→T*F│F F→(E) │i i+i*i的分析过程

ii* 1 E eF+i* E T T +11 E+i i F T E+F* F F E+T* E+TRF E+ E

E E + T T Fi i * F TiF i+i*i F+i*i T+i*i E+ i*i E+ F*i E+T* i E+T*F E+T E

例2:G(S) S→ aacBe A→Abb B→→d abode的分析过程

例2: G(S) S→aAcBe A→Ab|b B→d abbcde的分析过程

abbcae aA c B aBode aAcde a b aAcBe S

S a A c B e A b d b abbcde aAbcde aAc d e aAcBe S

算符优先分析法 1.算符文法 上下文无关文法G,没有形如P→或 P→..QR.的产生式则称G为算符文法

一. 算符优先分析法 1. 算符文法 上下文无关文法G,没有形如P→ε或 P→. . .QR. . .的产生式,则称G为算符文法

2终结符之间的优先关系 对算符文法G,ab∈Ⅵ定义 (1)a=b;G中有P→.ab 或P→>.aQb (2)ab:G中有P→..Qb.且Q→.a 或Q→…aR

2. 终结符之间的优先关系 对算符文法G, a,bVT 定义 (1)a=b: G中有P→. . .ab. . . 或P→. . .aQb. . . (2)ab: G中有P→. . .Qb. . . 且Q. . .a 或Q…aR + + + +

3.算符优先文法 若算符文法G的任何终结符ab之间 的优先关系至多有=、>、<中的一个 则G为一算符优先文法 据定义,构造下述文法G的优先关系表 Go(E) E→E+TT T→T*FF F→(E)i

3. 算符优先文法 若算符文法G的任何终结符a,b之间 的优先关系至多有= 、>、<中的一个, 则G为一算符优先文法。 据定义，构造下述文法G0的优先关系表 G0（E）: E→E+T|T T→T*F|F F→(E)|i

算符优先关系表 +> $

+ + * * i i ( ( ) ) $ $ > > > > > > > > > > > > = = 算符优先关系表