編譯原理簡明教程（第3版）-課件 第4-6章 詞法分析、語法分析-自頂向下、語法分析-自底向上

新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理16目錄第一章

概述第二章形式語言理論基礎(chǔ)第三章自動機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯(cuò)處理第十一章

面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造4詞法分析學(xué)習(xí)目標(biāo)詞法分析是編譯過程的第一步，其主要任務(wù)是對源程序進(jìn)行掃描，從中識別出單詞，是編譯過程中不可缺少的部分。重點(diǎn)：詞法分析的過程；單詞的形式、種類；詞法分析程序的設(shè)計(jì)方法3

目錄4.1詞法分析概述4.2詞法分析程序4.3詞法分析程序的自動生成4.4本章小結(jié)44.1詞法分析概述4.1.1詞法分析的功能詞法分析程序的主要功能

輸入源程序輸出單詞符號單詞符號（單詞）：程序語言具有獨(dú)立意義的最小語法單位屬性字：單詞的一種機(jī)內(nèi)表示(反映單詞的有關(guān)特性).54.1.1詞法分析的功能包括處理說明部分·把單詞的全部屬性都識別出來不必包括處理說明部分·不把單詞的全部屬性都識別出來詞法分析分為兩類64.1.1詞法分析的功能識別單詞從用戶的源程序中把單詞分離出來;生成屬性字把單詞轉(zhuǎn)換成機(jī)內(nèi)表示，便于后續(xù)處理。詞法分析又稱為掃描器，任務(wù)有兩個(gè)：74.1.2詞法分析的兩種處理結(jié)構(gòu)詞法分析是主程序:詞法分析程序字符串表示的源程序源程序字符字符語法分析是主程序，詞法分析是子程序:源程序字符詞法分析程序單詞回送8符號表語法分析程序4.1.3單詞符號的種類保留字(關(guān)鍵字)常數(shù)標(biāo)識符界限符(特殊符號)程序語言定義的具有固定意義的標(biāo)識符如:Pascal中的begin、end、if、while…。用來表示各種名字.如:變量名、數(shù)組名、過程名等。如:128、0.123、3.14E-2…。如:+、-、*、/、>=、<=、》=、《=等。單詞符號94.1.4詞法分析程序的輸出形式

一般采用二元式

一個(gè)語言的單詞符號分為幾類，如何分類、怎樣編碼,是一個(gè)技術(shù)性問題，主要取決于處理上的方便。

如：標(biāo)識符分為一類

常數(shù)且按類型（整數(shù)、實(shí)數(shù)）分類

保留字可分為一類，也可一字一類

界限符可分為一類，也可一符一類

單詞類別單詞符號的屬性值對于采用一字一類、一符一類，不需再給出單詞的值。10

但若一個(gè)類別中含多個(gè)單詞符號，還需給出相應(yīng)的值（按某種編碼）例如：對于標(biāo)識符，常把存放它的有關(guān)信息的符號表項(xiàng)的指針作為屬性值。對于常數(shù)，常把存放它的常數(shù)表項(xiàng)的指針作為屬性值。11標(biāo)識符保留字常數(shù)特殊符號4.2詞法分析程序4.2.1詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)初始化讀字符是字母?讀標(biāo)識符數(shù)字?取數(shù)字查常量表生成屬性字寫到輸出流是否分析結(jié)束結(jié)束特殊符號?出錯(cuò)查特殊符號表生成屬性字查保留字表查到?查名字表生成屬性字生成屬性字YYYYNNNNYN124.2.2單詞的識別單詞的文法規(guī)則:<標(biāo)識符>→<字母>|<標(biāo)識符><字母>|<標(biāo)識符><數(shù)字><無符號整數(shù)>→<數(shù)字>|<無符號整數(shù)><數(shù)字><特殊符號>→+|-|*|<=|…單詞的狀態(tài)轉(zhuǎn)換圖如下13標(biāo)識符或保留字

整

數(shù)實(shí)數(shù)（無指數(shù)部分）帶指數(shù)的實(shí)數(shù)

加號

減號

乘號

除號

等于

小于

小于等于

不等于144.2.3無符號數(shù)的識別文法規(guī)則如下：<無符號數(shù)>→<無符號實(shí)數(shù)>|<無符號整數(shù)><無符號實(shí)數(shù)>→<無符號整數(shù)>.<數(shù)字串>[E<比例因子>]|<無符號整數(shù)>E<比例因子><比例因子>→<有符號整數(shù)><有符號整數(shù)>→[+|-]<無符號整數(shù)><無符號整數(shù)>→<數(shù)字串><數(shù)字串>→<數(shù)字>{<數(shù)字>}<數(shù)字>→0|1|2…|915

設(shè)無符號數(shù)為：

t=….…E…(整數(shù)部分)(小數(shù)部分)(指數(shù)部分)

令W=…

…1

P=…

e=

則t=W-1

讀無符號數(shù)的程序流程圖見圖4.7164.2.4標(biāo)識符的識別<標(biāo)識符>→<字母>{<字母>|<數(shù)字>}<字母>→A|B|C|…|Z|a|b|…|z<數(shù)字>→0|1|2|…|9保留字是特殊的標(biāo)識符特殊處理事先構(gòu)造保留字表事先構(gòu)造保留字樹規(guī)定保留字在源程序中用分界符括起來

174.3詞法分析程序的自動生成4.3.1基本思想通?？赏ㄟ^兩種途徑來構(gòu)造詞法分析程序：

手工方式和自動生成

1、手工方式根據(jù)對語言中各類單詞的描述或定義，手工構(gòu)造詞法分析程序。如：可根據(jù)文法或狀態(tài)轉(zhuǎn)換圖構(gòu)造相應(yīng)的狀態(tài)矩陣，讀狀態(tài)矩陣同控制程序一起組成了編譯程序的詞法分析程序。

也可根據(jù)文法或狀態(tài)轉(zhuǎn)換圖利用某種語言（匯編或高級語言）直接編寫詞法分析程序。184.3詞法分析程序的自動生成2、自動生成

只要給出某語言各類單詞詞法結(jié)構(gòu)的文法描述（如正則式），以及各類單詞在詞法分析時(shí)應(yīng)采取的語義動作，自動生成系統(tǒng)。對上述信息進(jìn)行加工，即可得到所需的詞法分析程序，例：RWORD、LEXLEX是美國Bell實(shí)驗(yàn)室1975年用C語言研制的一個(gè)詞法分析程序的自動生成工具。

LEX源程序LEX編譯系統(tǒng)詞法分析程序194.3.2LEX源程序結(jié)構(gòu)輔助定義轉(zhuǎn)換規(guī)則（識別規(guī)則）用戶子程序（代碼）LEX源程序201、輔助定義在使用LEX語言時(shí)，先將高級語言的詞法寫成輔助定義式（類似宏定義）。例：⑴標(biāo)識符letter→A|B…|a|b…|zdigit→0|1|…|9ident→letter(letter|digit)*⑵整常數(shù)integer→digit(digit)*21⑶一般實(shí)常數(shù)

sign→+|-|εsigninteger→signintegerdecimal→eger|eger⑷

含指數(shù)部分的實(shí)數(shù)

exprel→(decimal|signinteger)E

signinteger⑸

實(shí)常數(shù)real→decimal|exprel222.識別規(guī)則（規(guī)定了相應(yīng)詞法分析程序的功能）{}是定義在υ{,,…,}上的正則表達(dá)式—詞型{}是語義動作（一個(gè)可執(zhí)行的程序段）例：整常數(shù)：digit{val=int(id);求整型值return(16);return(val)}return()子程序;16:單詞的類別編碼23標(biāo)識符:

letter

{if(keyword(id)!=0)return(keyword(id));else{return(15);return(id)}}

keyword()查保留字表，=0未查到243.用戶子程序（輔助函數(shù)部分）

用戶編寫的函數(shù)代碼（可被識別規(guī)則調(diào)用）4.3.3LEX編譯程序工作過程

Ⅰ根據(jù)每條Pi，構(gòu)造相應(yīng)NFAⅡ?qū)⒏鱊FA連成一個(gè)完整的NFAⅢ由NFA構(gòu)造狀態(tài)轉(zhuǎn)換矩陣ⅣNFA→DFAⅤ根據(jù)DFA及識別規(guī)則構(gòu)造詞法分析程序254.3.4LEX的實(shí)現(xiàn)

經(jīng)LEX編譯后得到詞法分析程序由兩部分組成：

一張狀態(tài)轉(zhuǎn)換矩陣表(DFA)和一個(gè)控制程序可看作是如下形式的有限自動機(jī)

P1|P2|…|Pn

當(dāng)輸入的單詞與Pj匹配時(shí)，就進(jìn)行相應(yīng)的動作(返回Ai所定義的單詞屬性)Pi例P66264.3.5LEX的使用方式

單獨(dú)使用：開發(fā)編輯器、模式識別等

與YACC等結(jié)合使用：生成掃描器和語法分析器27284.4本章小結(jié)1．詞法分析程序的工作是從輸入源代碼中取得單詞，以作為語法分析的輸入2．一般單詞被分成多種類型，并用二元式表示一個(gè)單詞的內(nèi)部形式3．詞法分析程序的設(shè)計(jì)采用程序流程圖和狀態(tài)轉(zhuǎn)換圖4．LEX是一種自動生成工具，可以實(shí)現(xiàn)詞法分析程序的自動生成29總結(jié)

本章我們學(xué)習(xí)了詞法分析的基本任務(wù)、詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn)、詞法分析程序的自動生成等內(nèi)容。

下一章將學(xué)習(xí)編譯過程的第二步----語法分析方法（自頂向下）。THANKSTHANKS新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理316目錄第一章

概述第二章形式語言理論基礎(chǔ)第三章自動機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯(cuò)處理第十一章

面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

并行編譯技術(shù)325語法分析

----自頂向下分析方法學(xué)習(xí)目標(biāo)自上而下語法分析的基本思想自上而下語法分析面臨的問題及解決方法消除左遞歸的方法First集、Follow集、Select集的求法LL（1）分析方法遞歸子程序分析方法33語法分析是編譯過程的核心部分。

-----在詞法分析識別出單詞符號串的基礎(chǔ)上，分析并判定程序的語法結(jié)構(gòu)是否符合語法規(guī)則。語法分析自頂向下如LL(k)，遞歸下降分析法等自底向上如LR(K)，簡單優(yōu)先分析法等34

目錄5.1自頂向下語法分析技術(shù)5.2LL(K)語法分析方法5.3遞歸下降語法分析方法5.4本章小結(jié)355.1自頂向下語法分析技術(shù)

從文法的開始符號出發(fā),向下推導(dǎo),看能否推出待分析的符號串,如果能推出,說明該符號串是符合語言語法的句子,否則不是句子。361231.從文法的開始符號出發(fā)2.

向下推導(dǎo)3.推導(dǎo)出句子

5.1.1自頂向下語法分析思想例:文法G[S]:SABAab

Bcd|cBd判斷abccdd是否是句子。(1)自頂向下構(gòu)造語法樹SABabcBdcd(2)推導(dǎo)SABAcBd

Accdd

abccdd375.1.2三種終結(jié)符號集1.First集(首符號集)

定義:文法G[S]:字匯表V,則符號串β的首符號集

First(β)={a|βay,a∈VT,y∈V*}特別,若β=ε,則First(β)=Φ*例：G[S]：SApSBqAa|cAFirst(dB)=j9powxiBb|dBFirst(Ap)={a,c}First(Bq)={b,d}38例:G[E]:EE+T|TTT*F|FF(E)|i則:First(E+T)={(,i}First(T)={(,i}First(T*F)={(,i}First(F)={(,i}First((E))={(}First(i)={i}392.Follow集(向前看集)定義:文法G[S],非終結(jié)符號U的向前看集

Follow(U)={a|S

…Ua…,a∈VTU{#}}

特別,當(dāng)a=ε時(shí),視U后面的符號為”#”****∵E

E,E

E+T,E

(E)∴Follow(E)={#,+,)}Follow(T)={#,+,*,)}Follow(F)={#,+,*,)}403.Select集(可選集)定義:文法G[S],有規(guī)則A

β

則該規(guī)則的可選集為:41例:對于G[E]select(EE+T)=First(E+T)={(,i}select(ET)=First(T)={(,i}select(TT*F)=First(T*F)={(,i}select(TF)=First(F)={(,i}select(F(E))=First((E))={(}select(Fi)=First(i)={i}42例:G[S]:SaBc|bBBbB|d|εSelect(Bε)=Follow(B)={#,c}435.1.3自頂向下語法分析難點(diǎn)1.左遞歸問題例:G[S]:

SSa|b

分析baaSS

S

S

S

SbSaSaSaSaSa

bSaSaSab…44分析時(shí)可能出現(xiàn):

(1)回溯

(2)死循環(huán),在沒有對當(dāng)前輸入符號匹配就進(jìn)入處理S的過程，無法確定什么時(shí)候才用Sb替換,

造成死循環(huán).解決方法:

文法的實(shí)用限制(算法6)消除左遞歸擴(kuò)充的BNF表示法452.回溯問題

在分析中，假定被代換的最左非終結(jié)符A存在n條規(guī)則,Ax1|x2|…|xn，難以確定采用哪個(gè)規(guī)則，若從x1到xn逐個(gè)來試,則效率太低。A的候選式:x1,x2,…xn

在自頂向下分析過程中，對候選式的選擇可根據(jù)當(dāng)前輸入符號來決定.46首先:對每條規(guī)則A

β,

First(β)β≠ε求Select(Aβ)=

Follow(A)β=ε當(dāng)β≠ε時(shí),對于當(dāng)前輸入符號a,若

a∈First(β)則可選Aβ進(jìn)行推導(dǎo),但A有n個(gè)候選式,∴分兩種情況.47

(1)首符號不同例:G[A]:AaB|bA

BbaA|c

{First(aB)={a}}∩{First(bA)=}=Φ{First(baA)=}∩{First(c)={c}}=Φ

分析符號串bbabaacAbA

bbA

bbaB

bbabaA

bbabaaB

bbabaacFirst(xi)∩First(xj)=Φ(i≠j)若a∈First(xk),則選用Axk來推導(dǎo)48

(2)首符號相同即對于A

αx1|αx2...|αxn改為A

α(x1|x2...|xn)進(jìn)一步A

αBBx1|x2...|xn

First(xi)∩First(xj)≠Φ(i≠j)解決方法:“左提左因子”修改文法49例:U

αx1|αx2|x3|…|xn

且First(xi)∩First(xj)=Φ,(i,j≥3,i≠j)

First(xi)≠α,(i=3,4,…n)

采用

UαV|x3|…|xn

Vx1|x250例:G[S]:SifBthenS1elseS2|ifBthenS1

改為:

SifBthenS1TTelseS2|ε515.1.4確定的自頂向下語法分析思想52不確定的自頂向下分析思想例:G[S]:SxAy

Aab|a

分析xay是否句子

SxAy

a(3)SxAy

(1)SxAy

ab(2)分析過程:(1)(2)(1)(3)出現(xiàn)回溯.53例:

G[E]:ET|EATTF|TMFF(E)|i分析符號串i+i*iA+|-M*|/54推導(dǎo):E

T

F

i

T

TMF

FMF

iMF

i*F

i*i

EAT

EAF

TAF

FAF

i+i

TAT

i+T

i+TMF

i+i*i

++推導(dǎo)過程是一個(gè)不斷試探的過程,出現(xiàn)回溯現(xiàn)象，所以又稱帶回溯的自頂向下分析方法(效率低，代價(jià)高)原因:推導(dǎo)過程中有多個(gè)侯選式可供選擇.555.2LL(K)語法分析方法

LL(k)是一種確定的自頂向下分析法:掃描輸入串,同時(shí)從文法的識別符號開始產(chǎn)生句子的最左推導(dǎo),每一步推導(dǎo)時(shí)向前看k個(gè)符號,以確定當(dāng)前應(yīng)選規(guī)則.k=1,即LL(1),簡單易懂,應(yīng)用較多.565.2.1LL(1)語法分析思想例:

G[S]:SaBc|bB

BbB|d

對句子abbdc進(jìn)行分析.

從左到右掃描abbdc,對照規(guī)則，對第一個(gè)字符a,只能用

SaBc,第二個(gè)符號b,只能用BbB

SaB

cbB

bB

d

由此,LL(1)的基本思想就是根據(jù)輸入串的當(dāng)前符號唯一確定所選規(guī)則進(jìn)行推導(dǎo).

abbBcabbdcSaBc

abBc575.2.2LL(1)語法分析方法的邏輯結(jié)構(gòu)a1a2a3…ai…am#輸入串

控制程序分析表分析器x1x2….xn#分析棧輸入串a(chǎn)1a2a3…am#,以定界符”#”作為結(jié)尾分析表:M[A,a](A為棧中元素,a為輸入字符585.2.3LL(1)語法分析方法1.LL(1)文法

對于文法G[S],其每個(gè)非終結(jié)符的不同規(guī)則具有不相交的select集.即對于Ux1|x2|…|xn,有select(Uxi)∩select(Uxj)=Φ,(i≠j)592.LL(1)語法分析表的生成LL(1)分析過程當(dāng)前句型的右端部分x1x2…xm#(xi∈V)待分析串的右端部分y1y2…yn#(yi∈VT)

x1x2…xm#605.2.3LL(1)分析方法分幾種情況:1)當(dāng)x1∈VN，由y1選擇相應(yīng)規(guī)則替換x12)當(dāng)x1∈VT,若x1=y1≠#,則說明x1與y1匹配,分別刪去x1,y1,繼續(xù)分析.

若x1≠

y1,則說明不匹配，進(jìn)行出錯(cuò)處理3)若x1=y1=#,說明全部匹配,分析成功.LL(1)分析程序見P77--78615.2.3LL(1)分析方法例:G[A]:AaBc

BbB|eB|d

分析abbdc#設(shè)計(jì)文法的分析表:

abcdeAAaBcBBbBBdBeB625.2.3LL(1)分析方法分析棧輸入符號產(chǎn)生式匹配刪除#A abbdc##cBa abbdc# AaBc#cB bbdc#a#cBb bbdc# BbB#cB bdc#b#cBb bdc# BbB#cB dc#b#cd dc# Bd#c c#d# #c63(1)LL(1)分析器工作過程(2)LL(1)語法分析表的構(gòu)造

LL(1)分析表反映分析棧中元素與輸入串中元素的匹配關(guān)系.記M[A,a]幾個(gè)約定:

C:繼續(xù)讀入下一字符

R:重讀當(dāng)前字符RE(β):用β的逆串替換棧頂符號.64構(gòu)造LL(1)分析表的算法如下:65

66例:G’[A]:AaBc

BbB|eB|d先求各規(guī)則的select集Select(AaBc)={a}Select(BbB)=Select(BeB)={e}Select(Bd)=ya6kqhi且c不出現(xiàn)在任何規(guī)則右部的首部.67構(gòu)造LL(1)分析表:abcde#ABc#cB/CB/Cε/CB/Cε/Csucc68分析abbedc的過程分析棧余留輸入串 動作#Aabbedc# cB/C#cBbbedc#B/C#cBbedc# B/C#cBedc# B/C#cBdc# ε/C

#cc# ε/C

## succ69例5－6表達(dá)式文法G[E]：E→EAT|TT→TMF|FF→(E)|iA→+|-M→*|/消除左遞歸求select集構(gòu)造分析表分析符號串70例5－61.消除左遞歸71例5－62.求select集723.構(gòu)造分析表734.分析符號串74例文法G[S]S

abB

A

SC|BAA|εVN={S,A,B,C}B

AbAVT={a,b,c}C

B|c75判斷此文法是不是LL(1)文法:Select(SabB)={a}Select(ASC)={a}Select(ABAA)={a,b}Select(Aε)={a,b,#}Select(CB)={a,b}Select(Cc)={c}Selcet(BAbA)={a,b}

∴不是LL(1)文法。構(gòu)造出的分析表含有多重定義?！?Φ∩≠Φ76注：有些不是LL(1)文法的文法，經(jīng)過修改（如左提左因子，消除左遞歸等）可化為LL(1)文法，但并不是所有的非LL(1)文法都能改造為LL(1)文法。77例對于文法G[Z]:

ZAU|BR

AaAU|b

BaBR|b

Uc

Rd

First(AU)∩First(BR)={a,b}≠Φ

所以，不是一個(gè)LL(1)文法

785.3遞歸下降語法分析方法5.3.1遞歸下降語法分析方法的實(shí)現(xiàn)思想是一種確定的自頂向下分析法。又稱遞歸子程序分析法。思想：對文法中每個(gè)非終結(jié)符（代表語法成分）編寫一個(gè)子程序（或遞歸過程），用來識別它所表示的語法范疇。有些語言（如PASCAL)的語法成分都是遞歸定義的（不含左遞歸），將其用遞歸過程來表示，即構(gòu)成了遞歸下降語法分析方法。795.3.2遞歸子程序及其性質(zhì)80

為了保證子程序的正確返回，必須保護(hù)返回地址。81825.3.2遞歸子程序及其性質(zhì)5.3.3遞歸下降語法分析方法例：賦值語句

SV:=E變量

Vi|i(E)表達(dá)式

EE+T|E-T|T項(xiàng)

TT*F|T/F|F因子

FF↑P|P初等量

P(E)|i83消除左遞歸：

SV:=EVi|i(E)ET{(+|-)T}TF{(*|/)F}FP{↑P}P(E)|i遞歸子程序如圖5.8－5.1384賦值語句處理流程圖85

變量處理流程圖86

表達(dá)式處理流程圖87

項(xiàng)處理流程圖88

因子處理流程圖89

初等量處理流程圖90915.4本章小結(jié)1．自頂向下語法分析方法是尋找輸入串的最左推導(dǎo)，從而分析出該輸入串的語法結(jié)構(gòu)2．自頂向下語法分析方法需要解決文法的二義性問題、左遞歸問題、回溯問題3．LL(1)文法是一種確定的自頂向下語法分析方法4．遞歸下降語法分析方法同樣是一種確定的自頂向下分析方法92總結(jié)

本章我們學(xué)習(xí)了自頂向下分析技術(shù)、不確定的自頂向下分析技術(shù)、確定的自頂向下分析技術(shù)、三種終結(jié)符號集、LL(1)分析方法和遞歸下降分析方法等內(nèi)容。

下一章將學(xué)習(xí)自底向上的語法分析方法。THANKS93THANKS新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理946目錄第一章引言第二章形式語言理論基礎(chǔ)第三章自動機(jī)理論基礎(chǔ)第四章詞法分析第五章語法分析—自頂向下分析方法第六章語法分析—自底向上分析方法第七章語義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號表和出錯(cuò)處理第十一章

面向?qū)ο笳Z言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造95自下而上語法分析的基本思想自下而上語法分析面臨的問題及解決方法簡單優(yōu)先分析法算符優(yōu)先分析法LR(K)四種語法分析方法966語法分析

----自底向上分析方法學(xué)習(xí)目標(biāo)

目錄6.1自底向上語法分析技術(shù)6.2自底向上優(yōu)先分析方法6.3LR(K)分析方法6.4本章小結(jié)976.1自底向上語法分析技術(shù)6.1.1自底向上語法分析思想從輸入串開始，逐步進(jìn)行“歸約”,直到歸約到文法的開始符號。又稱為“移進(jìn)-歸約”分析法。

分析過程：采用一個(gè)先進(jìn)后出的分析棧，分析開始后，將輸入串自左向右逐個(gè)移進(jìn)分析棧，邊移入邊分析，一旦棧頂形成某個(gè)句型的句柄時(shí)，就進(jìn)行歸約，歸約后的非終結(jié)符入棧，繼續(xù)分析,直到輸入串處理完畢，同時(shí)棧中只有文法的開始符號。98例6.1G[S]：S→aAbBA→c|AcB→d|dB分析符號串a(chǎn)ccbdd99表6.1自底向上分析法對輸入串a(chǎn)ccbdd的分析過程

步驟分析棧句柄輸入符號串動作1#accbdd#移進(jìn)2#a

ccbdd#移進(jìn)3#ac

cbdd#移進(jìn)4#aAc

cbdd#歸約（A→c）5#aAc

bdd#移進(jìn)6#aAAc

bdd#歸約（A→Ac）7#aAb

dd#移進(jìn)8#aAbd

d#移進(jìn)9#aAbdd#移進(jìn)10#aAbdBd#歸約（B→d）11#aAbBdB#歸約（B→dB）12#S

aAbB#歸約（S→aAbB）100分析符號串#accbdd#分析過程見表6.1,共用了12步,其中”移進(jìn)7步”,歸約5步。規(guī)范歸約序列:accbddaAcbddaAbddaAbdBaAbBS

構(gòu)造語法樹過程見圖

?????1.如何確定句柄例：表6.1中第5步棧內(nèi)符號aAc

棧頂c或Ac可選規(guī)則A→c或A→Ac，選擇了A→Ac，

同樣，在第8步棧頂是d，可用B→d歸約但沒用，而

是在第9步用A→d歸約?！叩?步c不是句柄，第8步d也不是句柄?！?/p>

但不可能依靠事先給出句子的最右推導(dǎo)或語法樹來尋找

句柄。6.1.2自底向上分析難點(diǎn)102

2.文法中出現(xiàn)兩條以上規(guī)則右部相同的規(guī)則例：A→eB→eC→e

如何確定選擇哪條規(guī)則？例：G[S]：S→AB|cA→bA|aB→aSb|c

分析bbaacb

S→cB→cSABbAaSbbAca103

步驟

分析棧

規(guī)則

句柄

余留輸入串

1

#bbaacb#

2

#bbaacb#

3

#bbaacb#

4

#bbaacb#

5

#bbAAaaacb#

6

#bAAbAbAacb#

7

#AAbAbAacb#

8

#Aacb#

9

#Aacb#

10

#AaSSccb#

11

#AaSb#

12

#ABBaSbaSb#

13

#SSABAB#104

在第8步，a出現(xiàn)在棧頂，能否用A→a歸約？

在第9步，c出現(xiàn)在棧頂，能否用B→c歸約？1056.2自底向上優(yōu)先分析方法優(yōu)先分析方法:簡單優(yōu)先分析方法算符優(yōu)先分析方法6.2.1簡單優(yōu)先分析方法1061.簡單優(yōu)先關(guān)系

文法中兩個(gè)符號之間的三種優(yōu)先關(guān)系:"=，>，<"。

注：“=、<、>”不同于數(shù)學(xué)中的“=、>、<”，A>B并不一定意味著B<A，A=B也并不代表B=A。107A=B表示A和B優(yōu)先關(guān)系相等A>B表示A的優(yōu)先性高于BA<B表示A的優(yōu)先性低于B三種優(yōu)先關(guān)系的定義：

設(shè)A、B是文法G中任意兩個(gè)符號108++2、簡單優(yōu)先文法

定義6.1：文法G中①任意符號之間至多存在一種優(yōu)先關(guān)系。②任意產(chǎn)生式右部均不相同，則稱G為簡單優(yōu)先文法。

例：文法G[S]：S→bAb

A→(B|a

B→Aa)109110（1）求=關(guān)系由S→bAb,A→(B,B→Aa)

可得b=A,A=b,(=B,A=a,a=)（2）求<關(guān)系由S→bAb,且A(B,Aa得b<(,b<a

由A→(B，且B(B…,Ba…,BA…

得(<(,(<a,(<A（3）求>關(guān)系,由S→bAb,且A…),A…B,A…a

得)>b，B>b，a>b

由B→Aa）且A…),Aa,A…B

得)>a,a>a,B>a+++++++++++

上述關(guān)系也可用語法樹結(jié)構(gòu)表示SSSSbAbbAbbAbbAb

（Ba（B（BAa）Aa）

（BaAa）

B>ba>b)>a,B>a,a>ab<(b<ab<(,(<(,(<A（<a111把文法符號之間的關(guān)系用矩陣表示

——優(yōu)先關(guān)系矩陣SbA（Ba

）#S>b=<<>A==(<<=<B>>a>>=)>>#<<=112113

說明:

①文法符號相互之間的優(yōu)先關(guān)系是唯一的。共有四種情況“=、<、>、空”，其中“空”表示兩符號之間無相鄰關(guān)系。

②“#”定界符，“#”<所有符號，所有符號>“#”，當(dāng)然僅對與“#”有相鄰關(guān)系的文法符號而言。#S##bAb#.114

例6.2已知文法G[A]：

A→aAb|cd|e試判斷該文法是否是簡單優(yōu)先文法。首先，求=、<、>關(guān)系.115

.

Aabcde#A

=

a=<

<

<b

>

>c

=d

>

>e

>

>#<<<=例6.2文法的優(yōu)先關(guān)系矩陣3、簡單優(yōu)先分析算法①根據(jù)文法構(gòu)造優(yōu)先關(guān)系矩陣。②設(shè)有符號棧S，將輸入符號串“#…#”依次壓入S棧，同時(shí)檢查相鄰符號與的優(yōu)先關(guān)系，一旦>

出現(xiàn)時(shí)，停止入棧。③當(dāng)前棧頂符號為，從開始向左在棧中查找符號，直到找到<

為止。116④符號串…即為當(dāng)前句型的句柄，查找規(guī)則右部…

的產(chǎn)生式，若找到則將…

歸約為左部，若找不到則為出錯(cuò)。⑤重復(fù)②~④步，直到分析完所有輸入符號，棧中只剩文法的開始符號，則分析成功，否則分析失敗。1173、簡單優(yōu)先分析算法例：分析#aeb#步驟S棧優(yōu)先關(guān)系

輸入符號串

句柄

1#<aeb#2#a<eb#3#aeb#4#aAb#e5#aAb=#6#A分析成功#>aAb118>6.2.2算符優(yōu)先分析法

1、簡單表達(dá)式表示法中綴表示法a+b(a+b)*ca+b/c

前綴表示法+ab*+abc+a/bc（波蘭式）

后綴表示法ab+ab+c*abc/+（逆波蘭式）基本思想：算符優(yōu)先分析法是按照終結(jié)符的優(yōu)先關(guān)系確定“句柄”并進(jìn)行歸約。算符優(yōu)先分析法：一種分析速度快，使用較多的自底向上分析方法。事實(shí)上，不是一種規(guī)范歸約，適用于表達(dá)式的分析。1191.逆波蘭式

無括號，形式簡單

運(yùn)算符次序與運(yùn)算次序完全相同

逆波蘭式：120波蘭邏輯學(xué)家1929年發(fā)明，在編譯程序出現(xiàn)之前，已用于算術(shù)表達(dá)式。逆波蘭式易于計(jì)算機(jī)處理（僅需一個(gè)棧，自左向右掃描逆波蘭式，遇運(yùn)算量壓棧，遇運(yùn)算符從棧頂取一個(gè)或兩個(gè)運(yùn)算量進(jìn)行運(yùn)算，運(yùn)算結(jié)果壓棧，繼續(xù)掃描…，直到整個(gè)表達(dá)式處理完畢）。在編譯程序中逆波蘭式可作為一種中間語言代碼。2.逆波蘭式的生成算術(shù)運(yùn)算遵守一定的運(yùn)算規(guī)則：

（，）→↑→*，/→+，-由此可得到一個(gè)運(yùn)算符優(yōu)先關(guān)系矩陣（見下頁）。逆波蘭表達(dá)式生成算法見圖6.3關(guān)鍵:比較當(dāng)前運(yùn)算符與棧頂運(yùn)算符的優(yōu)先關(guān)系.當(dāng)

前的高,當(dāng)前進(jìn)棧,棧頂?shù)母?棧頂退棧。例：表達(dá)式(a+b）*c/d→ab+c*d/

轉(zhuǎn)換過程如表6.5121運(yùn)算符優(yōu)先關(guān)系矩陣122關(guān)系右左

+-*/

↑（

）+>><<<<>->><<<<>*>>>><<>/>>>><<>↑>>>>><>

（<<<<<<=

）>>>>>>123表達(dá)式(a+b）*c/d→ab+c*d/124步驟輸入串當(dāng)前符號運(yùn)算符棧輸出串1(a+b)*c/d((

2a+b)*c/da(a3+b)*c/d+(+a4b)*c/db(+ab5)*c/d)(ab+6*c/d)

ab+7*c/d**ab+8c/dc*ab+c9/d//ab+c*10dd/ab+c*d11

ab+c*d/3.算符優(yōu)先文法定義6.3:算符優(yōu)先關(guān)系=、<、>a、b∈VT，A、B、C∈VN

①a=b，當(dāng)且僅當(dāng)文法中含有形如“A→…ab…”或“A→…aBb…”的產(chǎn)生式。定義6.2：算符文法-文法G中，A、B∈VN,若G中不會有形如“V→…AB…”的產(chǎn)生式。125例：G[E]：E→E+E|E*E|(E)|i算符文法②a<b，當(dāng)且僅當(dāng)文法中含有形如“A→…aB…”的產(chǎn)生式，其中Bb…或BCb…。③a>b，當(dāng)且僅當(dāng)文法中含有形如“A→…Bb…”的產(chǎn)生式，其中B…a或B…aC。++++126127定義算符優(yōu)先文法例G[E]:E→E+E|E*E|(E)|i(不是一個(gè)算符優(yōu)先文法)E→E+EE→E*EEE*EEE+E+<*+>*定義6.4：算符優(yōu)先文法-文法G是一個(gè)不含有空產(chǎn)生式的算符文法，且G中的兩個(gè)終結(jié)符之間，至多只有一種優(yōu)先關(guān)系。4.算符優(yōu)先關(guān)系矩陣的構(gòu)造方法⑴首先對文法G的每個(gè)非終結(jié)符A構(gòu)造兩個(gè)集合。FIRSTVT(A)={a|Aa…或ABa…，其中a∈,B∈}LASTVT(A)={a|A…a或A…aB，其中a∈,B∈}⑵確定終結(jié)符對之間的優(yōu)先關(guān)系。++++128＝關(guān)系，逐個(gè)查看產(chǎn)生式，由A→…ab…或A→…aBb…，找到a＝b。1<關(guān)系，查找文法中形“P→…aA…”的產(chǎn)生式，則對任何b∈FIRSTVT(A)，有a<b。2>關(guān)系，查找文法中形如“P→…Ab…”的產(chǎn)生式，則對任何a∈LASTVT(A)，有a>b。3129例:G[E]E→E+T|TT→T*F|FF→(E)|i計(jì)算FIRSTVT、LASTVT集FIRSTVT(E)={(,i,+,*}FIRSTVT(T)={(,i,*}FIRSTVT(F)={(,i}LASTVT(E)={+,*,),i}LASTVT(T)={*,),i}LASTVT(F)={),i}=關(guān)系

由F→(E)得(=)13012<關(guān)系由E→E+T+<FIRSTVT(T)即+<{*,(,i}由T→T*F*<FIRSTVT(F)即*<{(,i}由F→(E)(<FIRSTVT(E)即(<{+,*,(,i}3>關(guān)系由E→E+TLASTVT(E)>+即{+,*,),i}>+由T→T*FLASTVT(T)>*即{*,),i}>*由F→(E)LASTVT(E)>)即{+,*,),i}>)4131G[E]的算符優(yōu)先關(guān)系矩陣

+*()i#+><<><>*>><><>(<<<=<)>>>>i>>>>#<<<<=1325.算符優(yōu)先分析算法

算符優(yōu)先分析法是一種自底向上的方法，但不是規(guī)范歸約，即歸約時(shí)不一定是句柄。

定義：素短語——至少包含一個(gè)終結(jié)符，且除自身不含其它素短語的短語。

最左素短語——句型最左邊的素短語。E

E+T

E+TFTT*Fi例：句型：T+T*F+i

短語：T,T*F,iT+T*F,T+T*F+i

素短語：T*F,i

最左素短語：T*F133

#---定界符，終結(jié)符，可有可無的非終結(jié)符

最左素短語

…

滿足：

<

=,=,…,=>

算符優(yōu)先分析類似于簡單優(yōu)先分析法，只是歸

約的不是句柄，而是最左素短語。##…134句型的一般形式

步驟

當(dāng)前句型

優(yōu)先關(guān)系最左素短語歸約符號12345.#T+T*F+i# #<+,+<*,*>+T*F T#T+T+i# #<+,+>+ T+T E#E+i# #<+,+<i,i># i F#E+F# #<+,+># E+F E#E#135表6.7T+T*F+i的分析過程設(shè)：…最左素短語中包含，非終結(jié)符。

這種分析方法起主導(dǎo)作用的是終結(jié)符之間的優(yōu)先關(guān)系，非終結(jié)符的名字無所謂，且單個(gè)非終結(jié)符也不是素短語。所以，歸約過程得到一個(gè)語法樹的樹架。

NN+NN+NiN*N

算符優(yōu)先分析法的流程圖見下圖（圖6.6）

136表6.8句子(i+i)*i的分析過程

137步驟符號棧S[i]優(yōu)先關(guān)系輸入符號(a)待分析串1#<(i+i)*i#2#(<i+i)*i#3#(i>+i)*i#4#(N<+i)*i#5#(N+<i)*i#6#(N+i>)*i#7#(N+N>)*i#8#(N=)*i#9#(N)>*i#10#N<*i#11#N*<i#12#N*i>#

13#N*N>#

14#N分析成功1386.優(yōu)先函數(shù)

優(yōu)先關(guān)系矩陣，當(dāng)文法符號或終結(jié)符較多時(shí)會變得很大。解決方法：壓縮矩陣，去掉空元素。

構(gòu)造優(yōu)先函數(shù)。定義6.6：優(yōu)先函數(shù)f、g

已知文法G，由算符優(yōu)先關(guān)系矩陣，若文法的每個(gè)終結(jié)符x、y滿足：1）當(dāng)x>y時(shí)，f(x)>g(y)2）當(dāng)x<y時(shí)，f(x)<g(y)3）當(dāng)x=y時(shí)，f(x)=g(y)f—內(nèi)優(yōu)先函數(shù)（入棧優(yōu)先函數(shù)）g—外優(yōu)先函數(shù)（比較優(yōu)先函數(shù)）1396.優(yōu)先函數(shù)

表6.9G(E

)的優(yōu)先函數(shù)終結(jié)符優(yōu)先函數(shù)+*()i#f351551g2461616.3LR(K)分析方法

LR(K)根據(jù)分析棧的當(dāng)前內(nèi)容以及向前查看k個(gè)符號來決定是否移進(jìn)或歸約。141知識回顧自底向上語法分析思想和分析難點(diǎn)簡單優(yōu)先和算符優(yōu)先分析方法6.3LR(K)分析方法

LR(K)是一種有效的自底向上語法分析方法。它的適應(yīng)范圍廣，分析速度快，且能準(zhǔn)確及時(shí)地發(fā)現(xiàn)語法錯(cuò)誤，所以是當(dāng)前最一般的語法分析方法。

LR(K):根據(jù)分析棧的當(dāng)前內(nèi)容以及向前查看k個(gè)符號來決定是否移進(jìn)或歸約。142

LR(0)是基礎(chǔ)，但分析能力低，局限性大

SLR(1)“簡單LR”實(shí)現(xiàn)容易，能力較強(qiáng)，不適合有些文法

LR(1)分析能力最強(qiáng)，適用于大多數(shù)文法，但工作量大

LALR(1)能力介于SLR(1)與LR(1)之間，空間節(jié)省6.3LR(K)分析方法1431234LR語法分析方法類型6.3.1LR分析思想及邏輯結(jié)構(gòu)1、LR分析思想及邏輯結(jié)構(gòu)基本思想：掃描輸入串，進(jìn)行自底向上分析，在分析每一步記住當(dāng)前已移進(jìn)和歸約的文法符號，同時(shí)向前查看k個(gè)輸入符號，由此確定棧頂是否出現(xiàn)句柄，從而進(jìn)行歸約或移進(jìn)，直至分析完畢。144

→輸入串

#…

…#

分析表總控程序控制機(jī)構(gòu)……#下推分析棧145LR分析法的邏輯結(jié)構(gòu)

2.

LR分析表組成

兩部分：ACTION—分析動作表

GOTO—狀態(tài)轉(zhuǎn)換表

~為分析器的狀態(tài)，~為文法終結(jié)符和定界

符，~為文法符號

ACTION表：

輸入符號狀態(tài)…ACTION[，]

………ACTION[，]…ACTION[，]146GOTO表:

分析動作表中，ACTION[，]規(guī)定棧頂狀態(tài)為，輸入符號為時(shí)，所執(zhí)行的動作，有以下四種：

文法符號狀態(tài)…GOTO[，]……GOTO[，]…GOTO[，]1472.

LR分析表組成移進(jìn)（S），把（Si,aj）的下一個(gè)狀態(tài)移入狀態(tài)棧，輸入符號移入文法符號棧，繼續(xù)掃描下個(gè)符號。歸約（r），當(dāng)棧頂形成句柄時(shí)，按相應(yīng)的產(chǎn)生式進(jìn)行歸約，若產(chǎn)生式右端長度為n，則從狀態(tài)棧和文法符號棧的棧頂退n個(gè)符號，再將歸約后的文法符號移入符號棧，新的狀態(tài)進(jìn)入狀態(tài)棧。接受（acc），當(dāng)輸入串分析結(jié)束（只剩下“#”）時(shí)，文法符號棧中只剩下文法的開始符號時(shí)，分析成功，終止分析。報(bào)錯(cuò)（error），當(dāng)狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時(shí)，說明輸入串有錯(cuò)，報(bào)告出錯(cuò)信息。狀態(tài)轉(zhuǎn)換表中，GOTO[Si，xj]規(guī)定了當(dāng)棧頂狀態(tài)為Si，文法符號為Sj時(shí),xj應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài)(用j表示）。148231413、LR分析過程例6.3G[A]：A→B，AA→BB→aB→bG[A]的LR分析表狀態(tài)ab,#AB

ACTIONGOTOS0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S426S6r1149對符號串＃a，b＃的分析過程

步驟狀態(tài)棧符號棧余留符號產(chǎn)生式ACTION/GOTO12345678S0 # a,b# S3S0S3 #a ,b# γ32S0S2 #B ,b#B→a S5S0S2S5 #B, b# S4S0S2S5S4#B,b # γ42S0S2S5S2#B,B #B→b γ26S0S2S5S6#B,A #A→B γ11S0S1 #A #A→B,A acc1506.3.2LR(0)的分析方法

LR(k)中k=0說明無須向前查看符號.LR(0)是其它LR分析法的基礎(chǔ).

例6.1

在分析的第5步棧中符號為#aAc時(shí),

用A→Ac歸約而沒有A→c.

實(shí)際上與棧中符號串的前綴有關(guān).151表6.1自底向上分析法對輸入串a(chǎn)ccbdd的分析過程

步驟分析棧句柄輸入符號串動作1#accbdd#移進(jìn)2#a

ccbdd#移進(jìn)3#ac

cbdd#移進(jìn)4#aAc

cbdd#歸約（A→c）5#aAc

bdd#移進(jìn)6#aAAc

bdd#歸約（A→Ac）7#aAb

dd#移進(jìn)8#aAbd

d#移進(jìn)9#aAbdd#移進(jìn)10#aAbdBd#歸約（B→d）11#aAbBdB#歸約（B→dB）12#S

aAbB#歸約（S→aAbB）152分析符號串#accbdd#分析過程見表6.1,共用了12步,其中”移進(jìn)7步”,歸約5步。規(guī)范歸約序列:accbddaAcbddaAbddaAbdBaAbBS

構(gòu)造語法樹過程見圖

?????問題

154?LR分析過程中，需要確定當(dāng)前句型的句柄進(jìn)行歸約，如何在當(dāng)前句型中尋找句柄？解決：直接尋找句柄有困難，可以迂回尋找含有句柄的字符串總結(jié)與思考LR方法的分析思想與分析過程LR分析方法與優(yōu)先方法的區(qū)別延展學(xué)習(xí)：DonaldErvinKnuth生平以及對計(jì)算機(jī)所作出的貢獻(xiàn)基礎(chǔ)軟件領(lǐng)域中編譯技術(shù)發(fā)展現(xiàn)狀1.規(guī)范前綴和可歸前綴定義6.7:已知文法G[S],若有規(guī)范推導(dǎo)S

αβ,β∈

則稱α為規(guī)范前綴,又稱活前綴.(規(guī)范前綴中不含句柄之后的符號)若α是句柄的活前綴,且句柄處在α的最右端,則稱α是可