北京航空航天大学计算机学院第四章第四章语法分析语法分析

_C___O___L_______H____e___r_

第四章语法分析

•语法分析的功能、基本任务

•自顶向下分析法

•自底向上分析法

Excellencein

BUAASEI

北京航空航天大学计算机学院

Coh以ler

复习：第一章概述

编译过程是指将翻译为等价的目标程

序的过程。

习惯上是将编译过程划分为5个基本阶段：

墨法分析

语义分析£空中间代码

代码优化

生最目看程序

Excellencein

BUAASEI

北京航空航天大学计算机学院

4.1语法分析概述

功能：根据文法规则,

分，并进行语法检查。

两大类分析方法:

自顶向下分析

自底向上分析

Excellencein

BUAASEI

北京航空航天大学计算机学院

Co/i触

自顶向下分析算法的基本思想为:

?主要问题：■主要方法：

>左递归问题•递归子程序法

>回溯问题•LL分析法

北京航空航天大学计算机学院

Co/i触

自底向上分析算法的基本思想为:

若ZuS贝4SwL(G[Z])否贝4S£L(G[Z])

G[Z]

?主要问题：■主要方法：

＞句柄的识别问题•算符优先分析法

•LR分析法

北京航空航天大学计算机学院

4.2自顶向下分析

4.2.1自顶向下分析的一般过程

AJIrrlzQ曰-t|*：::::：::■工、LJL?/VKT»1-LIf?it?

给定1付万用s,若预测是某一语法成分，则可根据建

胃■口工法JU成*白z2L^5"勺、玉丸、兀、上法、七bc构、xt法、工、工J^L＞

:若成功.则s最终被识别为某语^法成时Hijimjjjj"jjjjm

《工「*]、击/[*]^守

书井杵件杵杵杵T喃/r彳挤井二;^*P柑二侪

■LLMRIW*IJ1BlUillIH出l蟒ilHK鞘H」.U解川见魁就I楠疆朋渊期越H鞘11111鞘11H出鞘:出:鞘出:出鞘1111鞘11111鞘11111鞘111111鞘11111鞘11111鞘11111鞘111II裆IIH=l:鞘出:出鞘土出土辘1:出

•可以通过一例子来说明语法分析过程

Excellencein

BUAASEI

北京航空航天大学计算机学院

例:

分析过程是设法建立一

棵语法树，使语法树的末端结

点与给定符号串相匹配。

1.

2.用Z的右部符号串去匹配输入串

完成一步推导ZncAd

检查，c・c匹酉己

A是非终结符，将匹配任务交给A

Excellencein

BUAASEI

北京航空航天大学计算机学院

S=cadG[Z]:Z：：=cAd

A：：=abla

Z

3.选用A的右部符号串匹配输入串

A有两个右部，选第一个

完成进一步推导Anab

检查加a匹配,b-d不匹配(失败)

但是还不能冒然宣布SeL(G[Z])ab

4.回溯即砍掉A的子树

改选A的第二右部

Ana检查a-a匹配

d-d匹配

建立语法树，末端结点为cad,与输入cad相匹配,

建立了推导序列ZncAdncad

/.cad€L(G(Z))

Excellencein

北京航空航天大学计算机学院BUAASEI

1.分析过程是带预测的，对输入符号串要预测属于什么

语法成分，然后根据该语法成分的文法建立语法树。

2.分析过程是一种试探过程，是尽一切办法（选用不同

规则）来建立语法树的过程，由于是试探过程,难免

有失败,所以分析过程需进行回溯，因此也称这种方法

是带回溯的自顶向下分析方法。

3.最左推导可以编写程序来实现,但带溯的自顶向下分

析方法在实际上价值不大，效率低。

北京航空航天大学计算机学院

有如下文法：

令U是文法的任一非终结符，文法中有规则

U：：=U・・••或者U王＞u・・・・

北京航空航天大学计算机学院

如果在匹配输入串的过程中，假定正好轮到要用非终结

符U直接匹配输入串,即要用U的右部符号串U一••去匹配，

为了用u・・•,去匹配，又得用U去匹配，这样无限的循环下

去将无法终止。

如果文法具有间接左递归，则也将发生上述问题，只不

过环的圈子兜得更大。

要实行自顶向下分析，必须要消除文法的左递归，下面

将介绍直接左递归的消除方法,在此基础上再介绍一般左递

归的消除方法。

Excellencein

BUAASEI

北京航空航天大学计算机学院

消除直接左递归

方法一，使用扩充的BNF表示来改写文法

例：⑴E：：=E+TIT=>E：：=T{+T}

(2)T：：=T*FIT/FIFnT：：=F{*FI/F}

a.改写以后的文法消除了左递归。

b.可以证明，改写前后的文法是等价的，表现在

L(G改前)=L(G%)

如何改写文法能消除左递归，又前后等价,

可以给出两条规则：

Excellencein

BUAASEI

北京航空航天大学计算机学院

若：U：：=xylxwl・・・・lxz

则可改写为：U：：=x(ylwl….lz)

若：y二ym，w二y/2

则u：：=x(y1(y2lw2)l....lz)

提

因

且

压

缩

子

北京航空航天大学计算机学院

Colder

规则二

若有文法规则：U：：=xlyl.......IzlUv

其特点是：具有一个直接左递归的右部并位于最后,

这袤明该语法美U是由x或y或z其片■应有零个量

或多个v组成。

UnUvnUvv=>Uvvv=>.......

・•・可以改写为U：：=(xlyl......Iz){v}

幅椭栅|匍跚•删”］网■跚M楣UMUlfO唧

并保持文法商等价性。HHHHHHM

Excellencein

BUAASEI

北京航空航天大学计算机学院

方法二，将左递归规则改为右递归规则

若：P：：=Palp

则可改写为：P：：=pP?

P'：：=aP'ls

Excellencein

BUAASEI

北京航空航天大学计算机学院

◎规则一：(提因子)

—规则二：U：：=xlyl.......IzlUv,则U：：=(xlyl........Iz){v}

规贝4三：右递归P：：=Palp,则P：：=|3P"P，：：=aP，l8

例1E：：=E+TIT例2T：：=T*FIT7FIF

右部无公因子，所以不能蝴端脚IM；规则年

用规则一。T：：=FIT(*FI/F)

为了使用规则二，T：：=F{(*FI/F)}规则二

令E：：=TIE+T即T：：=F{*FI/F}

・.・由规则二可以得到

E：：=T{+T}右递归：

T::=FT?

T'::=*FT'I/FT'Is

北京航空航天大学计算机学院

Co/i触

消除一般左递归

一般左递归也可以通过改写文法予以消除。

北京航空航天大学计算机学院

Excellencein

BUAASEI

北京航空航天大学计算机学院

COLHer

该文法无直接左递归，但有间接左递归

S=>Qc=>Rbc=>Sabc-*•S-^>Sabc

Excellencein

BUAASEI

北京航空航天大学计算机学院

R：：=Sala

Q：：=Rblb

S：：=Qclc

1.检查规则R是否存在直接左递归R：：=Sala

2.把R代入Q的有关选择，改写规则QQ：：=Sablablb

3.检查Q是否存在直接左递归

4.把Q代入S的右部选择S：：=Sabclabclbclc

5.消除S的直接左递归S：：=(abclbclc){abc}

Excellencein

BUAASEI

北京航空航天大学计算机学院

Co/哪r

最后得到文法为:

：=(abclbclc){abc}

Q：：=Sablablb

R：：=Sala

可以看出其中关于Q和R的规则是多余的规则

经过压缩后S::=(abclbclc){abc}

可以证明改写前后的文法是等价的

应该指出，由于对非终结符的排序不同，最后得到的文法在形

式上可能是不一样的，但是不⑥证明它们的等价。

Excellencein

BUAASEI

北京航空航天大学计算机学院

Con"

ai

U------a2

分析工作要部分地或全部地退回去a3

、乱w-9L々IJL

造成回溯的条件:U::=a11a2Ia3

文法中，对于某平非终结符号的规则其右部

有多个选择，并根据所面临的输入符号不能准确

地确定所要的选择时，就可能出现回溯。

回溯带来的问题:

严重的低效率，只有在理论上的意义而无实际意义

Excellencein、

VBUAASEI

北京航空航天大学计算机学院

效率低的原因

1）语法分析要重做

2）语义处理工作要推倒重来

设文法G（不具左递归性），UeV

U::=a11a2Ia3

［定义］FIRST(oc0={aIa...9aeVt}

为避免回溯，对文法的要求是:

a0Clj)="

FIRST(\FIRJSTV(aJ/T(\i藕tJZ

Excellencein

BUAASEI

北京航空航天大学计算机学院

Con阚

ill除回溯的途径I

L改写文法

对具有多个右部的规则.复提取左因子

例1U：：=xVlxWU,V,W£Vn,x6Vt+

改写为U：：=x(VIW)注意：问题到此并没有结束，还需要

进一步检查V和W的首符号是否相交

更清楚地表示为：

若V::=ablcdFIRST(V)={a,c}

U：：=xZW：：=delfgFIRST(W)={d,f}

只要不相交就可以根据输入符号确定

Z：：=VIW

目标，若相交，则要代入，并再次提

取左因子。如：V::=abw::=ac

则:Z::=a(blc)

北京航空航天大学计算机学院

COLHer

例2:文法G[v程序＞]

V程序〉：：二V分程序＞1〈复合语句〉

〈分程序〉：：=beginv说明串〉；〈语句串〉end

v复合语句＞：：=beginv语句串》end

FIRST（v分程序＞）={begin}

FIRST（v复合语句〉）={begin}

改写文法：

v程序＞：：=begin（v说明串〉；〈语句串〉endI

〈语句串〉end）

引入〈程序*〉

v程序＞：：=begin〈程序*〉

v程序*＞：：=〈说明串〉；〈语句串〉endIv语句串〉end

Excellencein、

北京航空航天大学计算机学院巴’

Co/i触

v程序＞：：=begin〈程序*〉

〈程序*〉：：=〈说明串〉；〈语句串〉endIv语句串〉end

对于：〈程序*〉

FIRST（v说明串〉；〈语句串〉end）

={real,integer,boolean,array,function,procedure}

FIRST（〈语句串＞end）

={标识符，goto,begin,if,for}

不相交。

Exceiiencnm

BUAASEI

北京航空航天大学计算机学院

.V程序〉：：二V分程序＞1〈复合语句〉

v分程序＞：：=beginv说明串〉；〈语句串〉end

v复合语句＞：：=beginv语句串〉end

ffiTFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFff

北京航空航天大学计算机学院

Coh啊__________

文法的两个条件

为了在不采取超前扫描的前提下实现不带回溯的自顶向

下分析，文法需要满足两个条件：

1、文法是非左递归的；

2、对文法的任一非终结符，若其规则右部有多个选择时，各选择

所推出的终结符号串的首符号集合要两两不相交。

［定义］设文法G（不具有左递归性），UGV

U::=a11a2Ia3*

FIRST(ai)={aIai=>a...,aeVt}

为避免回溯，对文法的要求是:

FIRST(at)DFIRST(a.i)=4)(的)

在上述条件下，就可以根据文法构造有效的、不带回溯的

吊顶而下令和富llllllllllllllllllllllllBIIIIIIIIIIIIIIIIIIIIIIBIIIIIIII『|||||||||||1lllllllltif

yExcellencei»*

北京航空航天大学计算机学院I'皿汽J>

Excellencein

BUAASEI

北京航空航天大学计算机学院

_C__O__L____川___e__r_

如文法G[Z]:z：：=uv

TT>•~~••••

v▼••••••

Z的分析程序u的分析程序V的分析程序

注：消除左递归后，可有其它递归:

TTTT•••U::=..・W・・.

W•・•・~一~•••TKTJ•••

北京航空航天大学计算机学院

COL川er

例：文法G[Z]

Z：：—(U)1aUb

U：：=dZIUdle

1（.，检入J查r并*改与天Jr*:法>X

COL"

程序的功能

也4-

Excellencein

BUAASEI

北京航空航天大学计算机学院

CofimjlerZ：：=，(U)1aUb

北京航空航天大学计算机学院

_C___O___L_______川___e____r_Z：：='CU')'laUb

Exceiiencnm

BUAASEI

北京航空航天大学计算机学院

Excellencein

BUAASEI

北京航空航天大学计算机学院

COL"

4.2.4用递归子程序法构造语法分析程序的例子

文法：v语句＞：：二v变量〉：二〈表达式〉

IIFv表达式》THENv语句》

IIFv袤达式〉THENv语句＞ELSEv语句》

v变量〉：：=iliTv表达式＞了

〈表达式〉：：=V项＞1〈表达式〉+V项〉

〈项〉：：二V因子＞|V项〉*V因子〉

v因子〉：：=〈变量＞1表达式

改写文法：v语句＞：：二v变量〉:三V表达式［口，嘀

隰袤达式〉THENv语句》［ELSE〈语句

项）::=〈因子＞{*V因子〉}

牖哪腓M黑嵋聊游卿林跚跚

Excellencein

北京航空航天大学计算机学院‘皿巴/

语法分析程序所要调用的子程序：

nextsym:词法分析程序,每调用一次读进一个单词，

单词的类别码放在sym中。

error:出错处理程序。

北京航空航天大学计算机学院

"i/pKv语句＞：：二v变量〉：二〈表达式〉

^—IIFv表达式＞THENv语句＞[ELSE〈语句＞]

PROCEDUREstate;/*语句分析子程序*/

IFsym='IF'THEN

BEGINnextsym;expr;

IFsym-THEN，THENerror

ELSEBEGINnextsym;state;

IFsym='ELSE'

THENBEGIN

nextsym;

state;

END

END

END

ELSEBEGINvar;

IFsym"：='

THENerror

ELSEBEGIN

nextsym;

expr;

END

END

北京航空航天大学计算机学院

_C____o__n_______H____e____r_

〈变量＞：：=表达式＞11

PROCEDUREvar;/*变量*/

IFsym丰'i'THENerror

ELSEBEGINnextsym;

IFsym='「THEN

BEGINnextsym;

expr;

IFsym*

THENerror

ELSEnextsym;

END

END

Excellencein

BUAASEI

北京航空航天大学计算机学院

_C___O___L_______川___e____r_

〈语句〉：：=V变量＞：=＜表达式＞

IIFv表达式〉THENv语句＞[ELSEv语句＞]

v变量＞：：=i＞「v表达式＞了]

〈表达式〉：：=〈项〉｛+＜项〉｝

＜项＞：：=v因子＞｛*〈因子〉｝

v因子〉：：=＜变量＞*'＜表*式＞')'

PROCEDUREexpr;/*表达式*/

BEGINterm;

WHILEsym='+'DO

BEGINnextsym;

term;

END

END;

Excellencein

BUAASEI

北京航空航天大学计算机学院

〈项〉：：=V因子＞{*〈因子〉}

V因子〉：：二V变量〉卜（々表金式＞，），

PROCEDUREterm;/*项*/

BEGINfactor;

WHILEsym='*'DO

BEGINnextsym;factorEND

END;

PROCEDUREfactor;/*因子*/

BEGIN

IFsym='('THEN

BEGINnextsym;expr;

IFsym*')'

THENerror

ELSEnextsym

END

ELSEvar;

END

北京航空航天大学计算机学院

〈语句〉：：=v变量＞：=＜表达式,

lIFv表达式〉THENv语句》[ELSE〈语句＞]

voidstatement()

V变量＞：：=表达式＞1']

if(sym=="IF"){voidvar()

getsym();{if(sym!="i")error();

expr();else{getsym();

if(sym!="THEN“)if(sym==“[”){

error();getsym();

else{getsym();expr();

statement();if(sym!=”)

if(sym=="ELSE")error();

getsym();elsegetsym();

statment()；

v表达式,：：=〈项〉{+v项〉}

else{var();1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111卜

if(sym!=":"”)voidexpr()

error();{term();

else{getsym();while(sym=="+")

expr();getsym();

}term();

)

北京航空航天大学计算机学院

〈项〉：：=〈因子>{*v因子〉}

v因子,：：=v变*>l"，v表*式

voidterm()

{factor();

voidmain()

while(sym=="*")

getsym();

factor();

getsym();

statement();

■sssssssssssssssssssssssssssssssssessessessessessessessB)

voidfactor()

{if(sym=="("){

getsym();

expr();

if(sym!=“)”)error();

elsegetsym();

}

elsevar();

)

北京航空航天大学计算机学院

_C___O___L_______川___e____r_

举例分析

if(i+i)theni:=i*i+ielse

i[i]:=i+i[i*i]*(i+i)

作业：

p80:1-3

Excellencein

BUAASEI

北京航空航天大学计算机学院

〈语句〉：：二V变量＞：=＜表达式,

Co/i/erlIFv表达式〉THENv语句》[ELSE〈语句＞]

voidstatement()voidvar()〈变量＞：：=表达式＞T]

{if(sym!="i")error

if(sym=="if"){else{getsym();

getsym();if(sym=="”)

expr();getsym();

if(sym!="then“)expr();

error();if(sym!="]”)

else{getsym();

statement();error();

if(sty=="else")elsegetsym();

{

getsym();

statment()；

printf("itisa

睢

Xr4af,iab1^^：：二〈项＞J

while(sym==){

statementgetsym();

term();

}>

、printf("itisa

xpresson'n");

、力UAASEI

〈项〉：：=〈因子＞{*v因子〉}

V因子,：：=〈变量＞11々表*式〉T

voidterm()

{factor();voidmain()

while(sym==){

getsym();

factor();getsym();

state();

error

getsym();

expr();

printf("syntexerror

if(sym!=")error();

)

elsegetsym();皿」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」

itis

北京航空航天大学计算机学院

举例：

V语句＞：：二V变量〉：二V表达式〉

IIFv表达式〉THENv语句＞[ELSE〈语句＞]

v变量＞：：=i「「v表达式＞T]

〈表达式〉：：=〈项〉｛+＜项〉｝

〈项〉：：=V因子＞｛*〈因子〉｝

V因子》：：二V变量方,V表达式》）

if(i+i)theni:=i*i+ielse

北京航空航天大学计算机学院

LL-自左向右扫描、自左向右地分析和匹配输入串

・•・分析过程表现为最左推导的性质。

LL分析程序构造及分析过程

输入串

#

由三部分组成：

分析表符号栈执行程序

执行程序（总控程序）#

分析表

符号栈（分析栈）

北京航空航天大学计算机学院

Excellencein

BUAASEI

北京航空航天大学计算机学院

Exceiiencnm

BUAASEI

北京航空航天大学计算机学院

(2)符号栈：有四种情况

•开始状态

XXXXXX#

北京航空航天大学计算机学院

Cooler

•出错状态

a.......#查分析表得：

符号栈K

vX6Vn,M[X,a]=error

无XSa…

X....#

X£Vt,Xwa

•结束状态

#

符号栈R

4#

北京航空航天大学计算机学院

#

COL的栈

执行程序主要实现如下操作:

1.把#和文法识别符号E推进栈,读入下一个符号，

重复下述过程直到正常结束或出错。

2.测定栈顶符号X和当前输入符号时执行如下操作：

(1)若*=2=#分析成功，停止。E匹配输入串成功

(2)若X=aK#把X推出栈，再读入下一个符号。

⑶若X£查分析表M。

北京航空航天大学计算机学院

#..…X#..…WVU

X....#UVW....#

rT

北京航空航天大学计算机学院

_C___O___L_______川___e____r_

例：文法G[E]

E::=E+TIT

T::=T*FIF消除左递归E::=TE,

F::=(E)liE::=+TE?I8

T::=FT'

T，：：=*FT'I6

F::=(E)li

Excellencein

BUAASEI

北京航空航天大学计算机学院

Con"

分析表

i+*()#

EE::=TEE::=

TE,

E*E::=E'::=eE'::=e

+TE*

TT::=FT,T::=

FT1

T,T::=T::=T::=eT'：：=8

s*FT，

FF::=iF::=

(E)

★注：矩阵元素空白表示Error

Excellencein

BUAASEI

北京航空航天大学计算机学院

/___1i+*

UEE::=TE1

E1F::=iE1::=

+TE1

TT::=FT'T::

T，T'::=T

8

FF::=iF::

(E)

输入串为：i+i*i#

步骤符号栈读入符号剩余符号串使用规则

1.#EE#i+i*i#

2.#E'TTE'#i+i*i#E::=TE,

3.#E'T'FFTE#j+i*i#T::=FT,

4.#ETiiT'E'#i+i*i#F::=i

5.#ETTE#+i*i#（出栈，读下一个符号）

6.#E，E'#+i*i#T：：=£

7.#E'T++TE'#+i*i#E'::=+TE'

、EUAASEI

北京航空航天大学计算机学院

i+*()#

COLEE::=TE1E::=

TE'।

1

E'F::=iE'::=E::=eE'::二e

+TE'

TT::=FT1T::=

FT'

1

T'T,：:=T•♦二T:：=8T':：=6

8*FT'

FF::=iF::=

(E)

步骤

8.#E'Ti*i#

9.#ETFi*i#T::=FT,

10.#ETii*i#F::=i

11.#ET*i#

12.#ETF**i#T'::=*FT'

13.#ETFi#

14.#ETii#F::=i

15.#ET#

16.#E'#T'::二s

17.##E'：：二8

BUAASEI

北京航空航天大学计算机学院

ConQiler

推导过程：

E=>TE=>FTE=>iTE=>iEf

=>i+TE'=>i+FTEni+iTE'

=>i+i*FTEni+i*iTE

ni+i*iEni+i*i

最左推导。

Excellencein

BUAASEI

北京航空航天大学计算机学院

#

COL的符号栈

X....#