北京航空航天大學(xué)計(jì)算機(jī)學(xué)院第四章第四章語(yǔ)法分析語(yǔ)法分析

_C___O___L_______H____e___r_

第四章語(yǔ)法分析

?語(yǔ)法分析的功能、基本任務(wù)

?自頂向下分析法

?自底向上分析法

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Coh以ler

復(fù)習(xí)：第一章概述

編譯過程是指將翻譯為等價(jià)的目標(biāo)程

序的過程。

習(xí)慣上是將編譯過程劃分為5個(gè)基本階段：

墨法分析

語(yǔ)義分析￡空中間代碼

代碼優(yōu)化

生最目看程序

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

4.1語(yǔ)法分析概述

功能：根據(jù)文法規(guī)則,

分，并進(jìn)行語(yǔ)法檢查。

兩大類分析方法:

自頂向下分析

自底向上分析

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Co/i觸

自頂向下分析算法的基本思想為:

?主要問題：■主要方法：

>左遞歸問題?遞歸子程序法

>回溯問題?LL分析法

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Co/i觸

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

若ZuS貝4SwL(G[Z])否貝4S￡L(G[Z])

G[Z]

?主要問題：■主要方法：

＞句柄的識(shí)別問題?算符優(yōu)先分析法

?LR分析法

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

4.2自頂向下分析

4.2.1自頂向下分析的一般過程

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

給定1付萬用s,若預(yù)測(cè)是某一語(yǔ)法成分，則可根據(jù)建

胃■口工法JU成*白z2L^5"勺、玉丸、兀、上法、七bc構(gòu)、xt法、工、工J^L＞

:若成功.則s最終被識(shí)別為某語(yǔ)^法成時(shí)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:出

?可以通過一例子來說明語(yǔ)法分析過程

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

例:

分析過程是設(shè)法建立一

棵語(yǔ)法樹，使語(yǔ)法樹的末端結(jié)

點(diǎn)與給定符號(hào)串相匹配。

1.

2.用Z的右部符號(hào)串去匹配輸入串

完成一步推導(dǎo)ZncAd

檢查，c?c匹酉己

A是非終結(jié)符，將匹配任務(wù)交給A

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

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

A：：=abla

Z

3.選用A的右部符號(hào)串匹配輸入串

A有兩個(gè)右部，選第一個(gè)

完成進(jìn)一步推導(dǎo)Anab

檢查加a匹配,b-d不匹配(失敗)

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

4.回溯即砍掉A的子樹

改選A的第二右部

Ana檢查a-a匹配

d-d匹配

建立語(yǔ)法樹，末端結(jié)點(diǎn)為cad,與輸入cad相匹配,

建立了推導(dǎo)序列ZncAdncad

/.cad€L(G(Z))

Excellencein

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院BUAASEI

1.分析過程是帶預(yù)測(cè)的，對(duì)輸入符號(hào)串要預(yù)測(cè)屬于什么

語(yǔ)法成分，然后根據(jù)該語(yǔ)法成分的文法建立語(yǔ)法樹。

2.分析過程是一種試探過程，是盡一切辦法（選用不同

規(guī)則）來建立語(yǔ)法樹的過程，由于是試探過程,難免

有失敗,所以分析過程需進(jìn)行回溯，因此也稱這種方法

是帶回溯的自頂向下分析方法。

3.最左推導(dǎo)可以編寫程序來實(shí)現(xiàn),但帶溯的自頂向下分

析方法在實(shí)際上價(jià)值不大，效率低。

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

有如下文法：

令U是文法的任一非終結(jié)符，文法中有規(guī)則

U：：=U????或者U王＞u????

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

如果在匹配輸入串的過程中，假定正好輪到要用非終結(jié)

符U直接匹配輸入串,即要用U的右部符號(hào)串U一??去匹配，

為了用u???,去匹配，又得用U去匹配，這樣無限的循環(huán)下

去將無法終止。

如果文法具有間接左遞歸，則也將發(fā)生上述問題，只不

過環(huán)的圈子兜得更大。

要實(shí)行自頂向下分析，必須要消除文法的左遞歸，下面

將介紹直接左遞歸的消除方法,在此基礎(chǔ)上再介紹一般左遞

歸的消除方法。

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

消除直接左遞歸

方法一，使用擴(kuò)充的BNF表示來改寫文法

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

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

a.改寫以后的文法消除了左遞歸。

b.可以證明，改寫前后的文法是等價(jià)的，表現(xiàn)在

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

如何改寫文法能消除左遞歸，又前后等價(jià),

可以給出兩條規(guī)則：

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

若：U：：=xylxwl????lxz

則可改寫為：U：：=x(ylwl….lz)

若：y二ym，w二y/2

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

提

因

且

壓

縮

子

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Colder

規(guī)則二

若有文法規(guī)則：U：：=xlyl.......IzlUv

其特點(diǎn)是：具有一個(gè)直接左遞歸的右部并位于最后,

這袤明該語(yǔ)法美U是由x或y或z其片■應(yīng)有零個(gè)量

或多個(gè)v組成。

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

???可以改寫為U：：=(xlyl......Iz){v}

幅橢柵|匍跚?刪”］網(wǎng)■跚M楣UMUlfO唧

并保持文法商等價(jià)性。HHHHHHM

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

方法二，將左遞歸規(guī)則改為右遞歸規(guī)則

若：P：：=Palp

則可改寫為：P：：=pP?

P'：：=aP'ls

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

◎規(guī)則一：(提因子)

—規(guī)則二：U：：=xlyl.......IzlUv,則U：：=(xlyl........Iz){v}

規(guī)貝4三：右遞歸P：：=Palp,則P：：=|3P"P，：：=aP，l8

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

右部無公因子，所以不能蝴端腳IM；規(guī)則年

用規(guī)則一。T：：=FIT(*FI/F)

為了使用規(guī)則二，T：：=F{(*FI/F)}規(guī)則二

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

?.?由規(guī)則二可以得到

E：：=T{+T}右遞歸：

T::=FT?

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

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Co/i觸

消除一般左遞歸

一般左遞歸也可以通過改寫文法予以消除。

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

COLHer

該文法無直接左遞歸，但有間接左遞歸

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

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

R：：=Sala

Q：：=Rblb

S：：=Qclc

1.檢查規(guī)則R是否存在直接左遞歸R：：=Sala

2.把R代入Q的有關(guān)選擇，改寫規(guī)則QQ：：=Sablablb

3.檢查Q是否存在直接左遞歸

4.把Q代入S的右部選擇S：：=Sabclabclbclc

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

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Co/哪r

最后得到文法為:

：=(abclbclc){abc}

Q：：=Sablablb

R：：=Sala

可以看出其中關(guān)于Q和R的規(guī)則是多余的規(guī)則

經(jīng)過壓縮后S::=(abclbclc){abc}

可以證明改寫前后的文法是等價(jià)的

應(yīng)該指出，由于對(duì)非終結(jié)符的排序不同，最后得到的文法在形

式上可能是不一樣的，但是不⑥證明它們的等價(jià)。

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Con"

ai

U------a2

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

、亂w-9L々IJL

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

文法中，對(duì)于某平非終結(jié)符號(hào)的規(guī)則其右部

有多個(gè)選擇，并根據(jù)所面臨的輸入符號(hào)不能準(zhǔn)確

地確定所要的選擇時(shí)，就可能出現(xiàn)回溯。

回溯帶來的問題:

嚴(yán)重的低效率，只有在理論上的意義而無實(shí)際意義

Excellencein、

VBUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

效率低的原因

1）語(yǔ)法分析要重做

2）語(yǔ)義處理工作要推倒重來

設(shè)文法G（不具左遞歸性），UeV

U::=a11a2Ia3

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

為避免回溯，對(duì)文法的要求是:

a0Clj)="

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

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Con闞

ill除回溯的途徑I

L改寫文法

對(duì)具有多個(gè)右部的規(guī)則.復(fù)提取左因子

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

改寫為U：：=x(VIW)注意：?jiǎn)栴}到此并沒有結(jié)束，還需要

進(jìn)一步檢查V和W的首符號(hào)是否相交

更清楚地表示為：

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

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

只要不相交就可以根據(jù)輸入符號(hào)確定

Z：：=VIW

目標(biāo)，若相交，則要代入，并再次提

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

則:Z::=a(blc)

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

COLHer

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

V程序〉：：二V分程序＞1〈復(fù)合語(yǔ)句〉

〈分程序〉：：=beginv說明串〉；〈語(yǔ)句串〉end

v復(fù)合語(yǔ)句＞：：=beginv語(yǔ)句串》end

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

FIRST（v復(fù)合語(yǔ)句〉）={begin}

改寫文法：

v程序＞：：=begin（v說明串〉；〈語(yǔ)句串〉endI

〈語(yǔ)句串〉end）

引入〈程序*〉

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

v程序*＞：：=〈說明串〉；〈語(yǔ)句串〉endIv語(yǔ)句串〉end

Excellencein、

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院巴’

Co/i觸

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

〈程序*〉：：=〈說明串〉；〈語(yǔ)句串〉endIv語(yǔ)句串〉end

對(duì)于：〈程序*〉

FIRST（v說明串〉；〈語(yǔ)句串〉end）

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

FIRST（〈語(yǔ)句串＞end）

={標(biāo)識(shí)符，goto,begin,if,for}

不相交。

Exceiiencnm

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

.V程序〉：：二V分程序＞1〈復(fù)合語(yǔ)句〉

v分程序＞：：=beginv說明串〉；〈語(yǔ)句串〉end

v復(fù)合語(yǔ)句＞：：=beginv語(yǔ)句串〉end

ffiTFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFff

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Coh啊__________

文法的兩個(gè)條件

為了在不采取超前掃描的前提下實(shí)現(xiàn)不帶回溯的自頂向

下分析，文法需要滿足兩個(gè)條件：

1、文法是非左遞歸的；

2、對(duì)文法的任一非終結(jié)符，若其規(guī)則右部有多個(gè)選擇時(shí)，各選擇

所推出的終結(jié)符號(hào)串的首符號(hào)集合要兩兩不相交。

［定義］設(shè)文法G（不具有左遞歸性），UGV

U::=a11a2Ia3*

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

為避免回溯，對(duì)文法的要求是:

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

在上述條件下，就可以根據(jù)文法構(gòu)造有效的、不帶回溯的

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

yExcellencei?*

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院I'皿汽J>

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

_C__O__L____川___e__r_

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

TT>?~~????

v▼??????

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

注：消除左遞歸后，可有其它遞歸:

TTTT???U::=..?W??.

W????~一~???TKTJ???

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

COL川er

例：文法G[Z]

Z：：—(U)1aUb

U：：=dZIUdle

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

COL"

程序的功能

也4-

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

CofimjlerZ：：=，(U)1aUb

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

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

Exceiiencnm

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

COL"

4.2.4用遞歸子程序法構(gòu)造語(yǔ)法分析程序的例子

文法：v語(yǔ)句＞：：二v變量〉：二〈表達(dá)式〉

IIFv表達(dá)式》THENv語(yǔ)句》

IIFv袤達(dá)式〉THENv語(yǔ)句＞ELSEv語(yǔ)句》

v變量〉：：=iliTv表達(dá)式＞了

〈表達(dá)式〉：：=V項(xiàng)＞1〈表達(dá)式〉+V項(xiàng)〉

〈項(xiàng)〉：：二V因子＞|V項(xiàng)〉*V因子〉

v因子〉：：=〈變量＞1表達(dá)式

改寫文法：v語(yǔ)句＞：：二v變量〉:三V表達(dá)式［口，嘀

隰袤達(dá)式〉THENv語(yǔ)句》［ELSE〈語(yǔ)句

項(xiàng)）::=〈因子＞{*V因子〉}

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

Excellencein

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院‘皿巴/

語(yǔ)法分析程序所要調(diào)用的子程序：

nextsym:詞法分析程序,每調(diào)用一次讀進(jìn)一個(gè)單詞，

單詞的類別碼放在sym中。

error:出錯(cuò)處理程序。

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

"i/pKv語(yǔ)句＞：：二v變量〉：二〈表達(dá)式〉

^—IIFv表達(dá)式＞THENv語(yǔ)句＞[ELSE〈語(yǔ)句＞]

PROCEDUREstate;/*語(yǔ)句分析子程序*/

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

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

_C____o__n_______H____e____r_

〈變量＞：：=表達(dá)式＞11

PROCEDUREvar;/*變量*/

IFsym豐'i'THENerror

ELSEBEGINnextsym;

IFsym='「THEN

BEGINnextsym;

expr;

IFsym*

THENerror

ELSEnextsym;

END

END

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

_C___O___L_______川___e____r_

〈語(yǔ)句〉：：=V變量＞：=＜表達(dá)式＞

IIFv表達(dá)式〉THENv語(yǔ)句＞[ELSEv語(yǔ)句＞]

v變量＞：：=i＞「v表達(dá)式＞了]

〈表達(dá)式〉：：=〈項(xiàng)〉｛+＜項(xiàng)〉｝

＜項(xiàng)＞：：=v因子＞｛*〈因子〉｝

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

PROCEDUREexpr;/*表達(dá)式*/

BEGINterm;

WHILEsym='+'DO

BEGINnextsym;

term;

END

END;

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

〈項(xiàng)〉：：=V因子＞{*〈因子〉}

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

PROCEDUREterm;/*項(xiàng)*/

BEGINfactor;

WHILEsym='*'DO

BEGINnextsym;factorEND

END;

PROCEDUREfactor;/*因子*/

BEGIN

IFsym='('THEN

BEGINnextsym;expr;

IFsym*')'

THENerror

ELSEnextsym

END

ELSEvar;

END

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

〈語(yǔ)句〉：：=v變量＞：=＜表達(dá)式,

lIFv表達(dá)式〉THENv語(yǔ)句》[ELSE〈語(yǔ)句＞]

voidstatement()

V變量＞：：=表達(dá)式＞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表達(dá)式,：：=〈項(xiàng)〉{+v項(xiàng)〉}

else{var();1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111卜

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

error();{term();

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

expr();getsym();

}term();

)

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

〈項(xiàng)〉：：=〈因子>{*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();

)

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

_C___O___L_______川___e____r_

舉例分析

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

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

作業(yè)：

p80:1-3

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

〈語(yǔ)句〉：：二V變量＞：=＜表達(dá)式,

Co/i/erlIFv表達(dá)式〉THENv語(yǔ)句》[ELSE〈語(yǔ)句＞]

voidstatement()voidvar()〈變量＞：：=表達(dá)式＞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^^：：二〈項(xiàng)＞J

while(sym==){

statementgetsym();

term();

}>

、printf("itisa

xpresson'n");

、力UAASEI

〈項(xiàng)〉：：=〈因子＞{*v因子〉}

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

voidterm()

{factor();voidmain()

while(sym==){

getsym();

factor();getsym();

state();

error

getsym();

expr();

printf("syntexerror

if(sym!=")error();

)

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

itis

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

舉例：

V語(yǔ)句＞：：二V變量〉：二V表達(dá)式〉

IIFv表達(dá)式〉THENv語(yǔ)句＞[ELSE〈語(yǔ)句＞]

v變量＞：：=i「「v表達(dá)式＞T]

〈表達(dá)式〉：：=〈項(xiàng)〉｛+＜項(xiàng)〉｝

〈項(xiàng)〉：：=V因子＞｛*〈因子〉｝

V因子》：：二V變量方,V表達(dá)式》）

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

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

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

???分析過程表現(xiàn)為最左推導(dǎo)的性質(zhì)。

LL分析程序構(gòu)造及分析過程

輸入串

#

由三部分組成：

分析表符號(hào)棧執(zhí)行程序

執(zhí)行程序（總控程序）#

分析表

符號(hào)棧（分析棧）

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Exceiiencnm

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

(2)符號(hào)棧：有四種情況

?開始狀態(tài)

XXXXXX#

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

Cooler

?出錯(cuò)狀態(tài)

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

符號(hào)棧K

vX6Vn,M[X,a]=error

無XSa…

X....#

X￡Vt,Xwa

?結(jié)束狀態(tài)

#

符號(hào)棧R

4#

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

#

COL的棧

執(zhí)行程序主要實(shí)現(xiàn)如下操作:

1.把#和文法識(shí)別符號(hào)E推進(jìn)棧,讀入下一個(gè)符號(hào)，

重復(fù)下述過程直到正常結(jié)束或出錯(cuò)。

2.測(cè)定棧頂符號(hào)X和當(dāng)前輸入符號(hào)時(shí)執(zhí)行如下操作：

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

(2)若X=aK#把X推出棧，再讀入下一個(gè)符號(hào)。

⑶若X￡查分析表M。

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

#..…X#..…WVU

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

rT

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

_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

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

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

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

/___1i+*

UEE::=TE1

E1F::=iE1::=

+TE1

TT::=FT'T::

T，T'::=T

8

FF::=iF::

(E)

輸入串為：i+i*i#

步驟符號(hào)棧讀入符號(hào)剩余符號(hào)串使用規(guī)則

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#（出棧，讀下一個(gè)符號(hào)）

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

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

、EUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

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

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

ConQiler

推導(dǎo)過程：

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

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

=>i+i*FTEni+i*iTE

ni+i*iEni+i*i

最左推導(dǎo)。

Excellencein

BUAASEI

北京航空航天大學(xué)計(jì)算機(jī)學(xué)院

#

COL的符號(hào)棧

X....#