第3章80x86微處理器北京外國語大學(xué)《編譯原理》第3章80x86微處理器語法分析的若干問題上下文無關(guān)文法(Context

Free

Grammar,CFG)語言與文法簡介自上而下語法分析自下而上語法分析本章小結(jié)第3章80x86微處理器3.1

80x86微處理器簡介語法分析器的作用語法分析器是編譯器前端的重要組成部分，許多編譯器，特別是由自動生成工具構(gòu)造的編譯器，往往其前端的中心部件就是語法分析器。語法分析器在編譯器中的位置和作用如圖3.1所示，它的主要作用有兩點(diǎn)：根據(jù)詞法分析器提供的記號流，為語法正確的輸入構(gòu)造分析樹(或語法樹)。這是本章的重點(diǎn)，在以后各節(jié)中詳細(xì)討論；檢查輸入中的語法(可能包括詞法)錯(cuò)誤，并調(diào)用出錯(cuò)處理器進(jìn)行適當(dāng)處理。下邊簡單介紹語法錯(cuò)誤處理的基本原則，而在以后的討論中忽略此問題。第3章80x86微處理器圖3.1語法分析器在編譯器中的位置與作用第3章80x86微處理器3.1.2語法錯(cuò)誤的處理原則1．源程序中可能出現(xiàn)的錯(cuò)誤源程序中可能出現(xiàn)的錯(cuò)誤可以分為兩類：語法錯(cuò)誤和語義錯(cuò)誤。其中，語法錯(cuò)誤又包括詞法錯(cuò)誤和語法錯(cuò)誤。詞法錯(cuò)誤指出現(xiàn)非法字符或關(guān)鍵字、標(biāo)識符拼寫錯(cuò)誤等；語法錯(cuò)誤是指語法結(jié)構(gòu)出錯(cuò)，如少分號、begin/end不配對等。語義錯(cuò)誤包括靜態(tài)語義錯(cuò)誤和動態(tài)語義錯(cuò)誤。靜態(tài)語義錯(cuò)誤涉及的是編譯時(shí)可檢查出來的錯(cuò)誤，如類型不一致、參數(shù)不匹配等；動態(tài)語義錯(cuò)誤一般是指程序運(yùn)行時(shí)的邏輯錯(cuò)誤，如無窮遞歸、變量為零時(shí)作除數(shù)等。大多數(shù)錯(cuò)誤的診斷和恢復(fù)集中在語法分析階段，一個(gè)原因是大多數(shù)錯(cuò)誤是語法錯(cuò)誤，另一個(gè)原因是語法分析方法的準(zhǔn)確性，它們能以非常有效的方法診斷語法錯(cuò)誤。在編譯的時(shí)候，想要準(zhǔn)確地診斷語義或邏輯錯(cuò)誤有時(shí)是很困難的。第3章80x86微處理器2．語法錯(cuò)誤處理的目標(biāo)對語法錯(cuò)誤的處理，一般希望達(dá)到以下基本目標(biāo)：①清楚而準(zhǔn)確地報(bào)告錯(cuò)誤的出現(xiàn)，地點(diǎn)正確、不漏報(bào)、不錯(cuò)報(bào)也不多報(bào)；②迅速地從每個(gè)錯(cuò)誤中恢復(fù)過來，以便分析繼續(xù)進(jìn)行；③對語法正確源程序的分析速度不應(yīng)降低太多。第3章80x86微處理器這些目標(biāo)看起來容易，但是實(shí)現(xiàn)起來并不簡單。幸好常見的錯(cuò)誤是簡單的，直接了當(dāng)?shù)某鲥e(cuò)處理機(jī)制一般就足以應(yīng)付。但有些時(shí)候，錯(cuò)誤的實(shí)際位置遠(yuǎn)遠(yuǎn)前于發(fā)現(xiàn)它的位置，并且這種錯(cuò)誤的準(zhǔn)確性也難以推斷。在某些場合，出錯(cuò)處理程序可能需要猜測程序員的本意。有些分析方法，如LL和LR方法，可以盡可能快地檢測語法錯(cuò)誤。更準(zhǔn)確地說，它們具有“活前綴”(viable-prefix

property性質(zhì)，這指的是，它們一看見輸入的前綴不是該語言任何串的前

綴時(shí)，就能報(bào)告錯(cuò)誤。出錯(cuò)處理的關(guān)鍵是如何從錯(cuò)誤中恢復(fù)，使

分析可以進(jìn)行下去，而不是遇到第一個(gè)錯(cuò)誤就停止分析。第3章80x86微處理器3．語法錯(cuò)誤的基本恢復(fù)策略若希望編譯器的語法分析方式是每次對輸入源程序完整地掃描一遍，而不是遇到第一個(gè)語法錯(cuò)誤就停止的話，就需要采取某種恢復(fù)策略，使得分析在遇到錯(cuò)誤時(shí)還能夠繼續(xù)進(jìn)行。以下是一些可能的恢復(fù)策略。(1)緊急方式恢復(fù)(Panic-mode

recovery)：這是最簡單的方法適用于大多數(shù)分析方法。發(fā)現(xiàn)錯(cuò)誤時(shí)，分析器每次拋棄一個(gè)輸入

記號，一直向前搜索，直到輸入記號屬于某個(gè)指定的合法記號(稱為同步記號)集合為止。同步記號一般是定界符，如分號或end等，它們在源程序中的作用很清楚。當(dāng)然，設(shè)計(jì)編譯器時(shí)必須選擇適當(dāng)?shù)耐接浱?。這種處理方法最簡單，但是也最容易造成錯(cuò)報(bào)，特別是漏報(bào)和多報(bào)語法錯(cuò)誤的現(xiàn)象。第3章80x86微處理器(2)短語級恢復(fù)(Phrase-level

recovery)：發(fā)現(xiàn)錯(cuò)誤時(shí)，分析器采用串替換的方式對剩余輸入進(jìn)行局部糾正，它用可以使分析器繼續(xù)的輸入串來代替剩余輸入的前綴。典型的局部糾正是用分號代替逗號，刪除多余的分號，或插入遺漏的分號等。設(shè)計(jì)編譯器時(shí)必須仔細(xì)選擇替換的串，以免引起死循環(huán)，例如，若總是在當(dāng)前輸入符號的前面插入一些東西就會造成死循環(huán)。這種方式建立在產(chǎn)生式(用于規(guī)定上下文無關(guān)文法的一種形式化描述)的基礎(chǔ)之上，以短語為基本分析單元，同時(shí)也便于進(jìn)行語法制導(dǎo)翻譯，恢復(fù)得比緊急方式要精確，因此被認(rèn)為是一種較為理想的恢復(fù)方式。第3章80x86微處理器出錯(cuò)產(chǎn)生式(Error-productions)：預(yù)測被分析語言可能出現(xiàn)的錯(cuò)誤，用出錯(cuò)產(chǎn)生式捕捉錯(cuò)誤。這是語法分析器生成器YACC采用的方式，它基本上可以被認(rèn)為是一種預(yù)置型的短語級恢復(fù)方式。全局糾正(Global

correction)：對有語法錯(cuò)誤的輸入序列x，根據(jù)文法G構(gòu)造相近序列y的語法樹，使得x變換成y所需的修改、插入、刪除次數(shù)最少。由于這種方法的代價(jià)太大，因此目前只具有理論價(jià)值。第3章80x86微處理器例3.1下述兩條是有語法錯(cuò)誤的語句，其中第一條賦值句結(jié)束時(shí)忘記加分號，采用緊急恢復(fù)方式和短語級恢復(fù)方式的可能結(jié)果分別如下所示。x

:=

a

+

by

:=

c

+

d;緊急方式：x:=a+b+d;--丟棄b之后的若干記號，直到遇到同步記號+短語級恢復(fù)：x

:=

a

+

b;

--

加入分號，使之成為一個(gè)賦值句y

:=

c

+

d;第3章80x86微處理器3.2上下文無關(guān)文法(Context

Free

Grammar,CFG)3.2.1

CFG的定義與表示定義3.1上下文無關(guān)文法是一個(gè)四元組G

=(N，T，P，S)，其中①N是非終結(jié)符的有限集合(Nonterminals)；②T是終結(jié)符的有限集合(Terminals)，且N∩T=Φ；③P是產(chǎn)生式的有限集合(Productions)，每個(gè)產(chǎn)生式形如:A→α其中A∈N，被稱為產(chǎn)生式的左部，α∈(N∪T)*，被稱為產(chǎn)生式的右部，若α=ε，則稱A→ε為空產(chǎn)生式(也可以記為A→)；④S是非終結(jié)符，被稱為文法的開始符號(Start

symbol)。第3章80x86微處理器例3.2定義簡單算術(shù)表達(dá)式的上下文無關(guān)文法G3.1=(N,T,P,S)如下所示。N={E}

T={+,*,(,),–,id}

S=EP:

E

→

E

+

E

(1)E

→

E

*

E

(2)E

→

(E)

(3)E

→

–E

(4)E

→

id

(5)第3章80x86微處理器1．由產(chǎn)生式集表示CFG由于每個(gè)產(chǎn)生式中均有A∈N且α∈(N∪T)*，所以，對于一個(gè)沒有錯(cuò)誤的CFG，可以這樣區(qū)分N和T集合：N是僅出現(xiàn)在產(chǎn)生式左邊符號的集合，T是詞法分析器返回的記號的集合(某些約定的特殊終結(jié)符除外)，根據(jù)N∩T=Φ可以推斷出T是所有不出現(xiàn)在產(chǎn)生式左邊符號的集合。如果再約定S是第一個(gè)產(chǎn)生式的左部，則文法可以由其產(chǎn)生式集P代替，即不寫四元組，而僅給出P。CFG的產(chǎn)生式表示也被稱為巴克斯范式(Backus-Naur

Form，BNF)，值得注意的是，規(guī)范的BNF中，“→”用“::=”表示。第3章80x86微處理器2．產(chǎn)生式的一般讀法一般情況下，可以將產(chǎn)生式中的記號“→”讀作“定義為”或者“可導(dǎo)出”。例如，E→E+E可讀作“E定義為E+E”，或者“E可導(dǎo)出E+E”。更一般的，可用自然語言表述為“算術(shù)表達(dá)式定義為兩個(gè)算術(shù)表達(dá)式相加”，或者“一個(gè)算術(shù)表達(dá)式加上另一個(gè)算術(shù)表達(dá)式，仍然是一個(gè)算術(shù)表達(dá)式”。第3章80x86微處理器3．終結(jié)符與非終結(jié)符書寫上的區(qū)分對于一個(gè)僅有幾個(gè)產(chǎn)生式的簡單文法，其中的終結(jié)符和非終結(jié)符很容易區(qū)分，沒有必要在書寫上明確區(qū)分終結(jié)符和非終結(jié)符。但是對于一個(gè)實(shí)用的文法，產(chǎn)生式可能有幾百個(gè)或者更多，這時(shí)如果終結(jié)符和非終結(jié)符之間在書寫上沒有明確區(qū)分，則很難辨別它們，給理解產(chǎn)生式造成困難。區(qū)分終結(jié)符和非終結(jié)符的方法有很多，原則是容易辨別即可，例如，①

用大小寫區(qū)分： E

→

id②

用"

"區(qū)分： E

→

"id" E

→

E

"+"

E③

用<

>區(qū)分：

<E>

→

<E>

+

<E>第3章80x86微處理器本教材默認(rèn)采用區(qū)分大小寫的方法來區(qū)分終結(jié)符與非終結(jié)符，若不作特殊說明，一般用大寫英文字母A、B、C表示非終結(jié)符，小寫英文字母a、b、c表示終結(jié)符，小寫希臘字母α、β、δ表示任意的文法符號序列，即大小寫混合的英文字母串。第3章80x86微處理器4．產(chǎn)生式的縮寫形式考察文法G3.1，多個(gè)產(chǎn)生式左部的非終結(jié)符均是E。對于這種情況，可以把左部非終結(jié)符相同的產(chǎn)生式合并成一個(gè)產(chǎn)生式，并以此非終結(jié)符為該產(chǎn)生式命名，而所有的產(chǎn)生式右部由或符號(|)連接，每個(gè)右部現(xiàn)在被稱為該產(chǎn)生式的一個(gè)候選項(xiàng)，各候選項(xiàng)具有平等的權(quán)利。第3章80x86微處理器例3.3

G3.1可以重寫為如下形式：E

→

E

+

E|

E

*

E|(E)|

–E|

id(1)(2)(3)(4)(5)該產(chǎn)生式被稱為E產(chǎn)生式，它一共有5個(gè)候選項(xiàng)，分別表示：兩個(gè)算術(shù)表達(dá)式相加結(jié)果是一個(gè)算術(shù)表達(dá)式，兩個(gè)算術(shù)表達(dá)式相乘結(jié)果是一個(gè)算術(shù)表達(dá)式，加上括弧的算術(shù)表達(dá)式還是一個(gè)算術(shù)表達(dá)式，對算術(shù)表達(dá)式取負(fù)的結(jié)果是一個(gè)算術(shù)表達(dá)式，標(biāo)識符是一個(gè)算術(shù)表達(dá)式。第3章80x86微處理器3.2.2

CFG產(chǎn)生語言的基本方法——推導(dǎo)可以通過推導(dǎo)的方法產(chǎn)生CFG所描述的語言。非正式地講，推導(dǎo)就是從文法的開始符號S開始，反復(fù)使用產(chǎn)生式，將產(chǎn)生式左部的非終結(jié)符替換為右部的文法符號序列(展開產(chǎn)生式，用標(biāo)記=>表示)，直到得到一個(gè)終結(jié)符序列。例3.4終結(jié)符序列–(id+id)可以由文法G3.2產(chǎn)生，因此它是文法G3.2所產(chǎn)生的語言中的一個(gè)元素。標(biāo)記=>上方的序號指出每次使用的產(chǎn)生式序號。(4)

(3)

(1)

(5)

(5)E

=>

–E

=>

–(E)

=>

–(E+E)

=>

–(id+E)

=>

–(id+id)第3章80x86微處理器定義3.2將產(chǎn)生式A→γ的右部代替文法符號序列αAβ中的A得到αγβ的過程，稱為αAβ直接推導(dǎo)出αγβ，記作：αAβ=>αγβ。若對于任意文法符號序列α1，α2，...，αn有α1=>α2=>...=>αn則稱此過程為零步或多步推導(dǎo)，記為：α1=>αn，其中α1=αn的情況為零步推導(dǎo)。若α1≠αn，即推導(dǎo)過程中至少使用一次產(chǎn)生式，則稱此過程為至少一步推導(dǎo)，記為：α1=>αn。**第3章80x86微處理器定義3.2強(qiáng)調(diào)了兩點(diǎn)：①對于任何α，有α=>α，*即任何文法符號序列可以推導(dǎo)出它自身；②若α

=>*β，β

=>γ，*

則α*

=>γ，即*

推導(dǎo)具有傳遞性。第3章80x86微處理器定義3.3由CFG

G所產(chǎn)生的語言L(G)被定義為:L(G)

=

{

ω|S

ω+=>and

ω∈T*

}，L(G)稱為上下文無關(guān)語言(Context

Free

Language,CFL)，ω稱為句子。若Sα，=*>α∈(N∪T)*，則稱α為G的一個(gè)句型。第3章80x86微處理器定義3.4在推導(dǎo)過程中，若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符，則稱為最左推導(dǎo)，由最左推導(dǎo)產(chǎn)生的句型被稱為左句型。類似地，可以定義最右推導(dǎo)與右句型，最右推導(dǎo)也被稱為規(guī)范推導(dǎo)。再考察例3.4的推導(dǎo)過程，α1=E，α2=–E，α3=–(E)，α4=–

(E+E)，α5=–(id+E)，α6=–(id+id)。其中，α1是文法開始符號，

α6是句子，其他αi(i=2,3,4,5)均是句型。由于從α4到α5替換的是最左邊的非終結(jié)符，所以此推導(dǎo)是一個(gè)最左推導(dǎo)，所有的句型是左句型。句型是一個(gè)相當(dāng)廣泛的概念，根據(jù)定義3.3可知，α1和α6同樣也是句型。第3章80x86微處理器3.2.3推導(dǎo)、分析樹與語法樹定義3.5對CFG

G的句型，分析樹被定義為具有下述性質(zhì)的一棵樹。①根由開始符號所標(biāo)記；②每個(gè)葉子由一個(gè)終結(jié)符、非終結(jié)符或ε標(biāo)記；③每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記；④若A→X1X2...Xn是一個(gè)產(chǎn)生式，則X1，X2，...，Xn是標(biāo)記為A的內(nèi)部結(jié)點(diǎn)從左到右所有孩子的標(biāo)記。若A→ε，則標(biāo)記為A

的結(jié)點(diǎn)可以僅有一個(gè)標(biāo)記為ε的孩子。第3章80x86微處理器分析樹與文法和語言存在下述關(guān)系：①每一直接推導(dǎo)(或者每個(gè)產(chǎn)生式)，對應(yīng)一棵僅有父子關(guān)系的子樹，即產(chǎn)生式左部非終結(jié)符“長出”右部的孩子；②分析樹的葉子從左到右，構(gòu)成G的一個(gè)句型。若葉子僅由終結(jié)符標(biāo)記，則構(gòu)成一個(gè)句子。第3章80x86微處理器例3.5考慮例3.4的最左推導(dǎo)E=>–E=>–(E)=>–(E+E)=>–

(id+E)=>–(id+id)，和最右推導(dǎo)E=>–E=>–(E)=>–(E+E)=>(E+id)=>–(id+id)，它們所對應(yīng)的分析樹序列分別如圖3.2(a)、(所示。可以看出，最左推導(dǎo)和最右推導(dǎo)的中間過程對應(yīng)的分析樹可能不同(因?yàn)榫湫筒煌?，但是最終的分析樹相同，因?yàn)樽罱K是同一個(gè)句子。更多的情況下，往往僅希望用樹來反映句型的結(jié)構(gòu)實(shí)質(zhì)，而忽略句型的推導(dǎo)過程，從而引出語法樹的概念。語法樹是表示表達(dá)式結(jié)構(gòu)的最好形式。第3章80x86微處理器定義3.6對CFG

G的句型，表達(dá)式的語法樹被定義為具有下述性質(zhì)的一棵樹:①根與內(nèi)部節(jié)點(diǎn)由表達(dá)式中的操作符標(biāo)記；②葉子由表達(dá)式中的操作數(shù)標(biāo)記；③用于改變運(yùn)算優(yōu)先級和結(jié)合性的括弧，被隱含在語法樹的結(jié)構(gòu)中。第3章80x86微處理器例3.6根據(jù)定義3.6，例3.5最終的分析樹所對應(yīng)的語法樹如圖3.3(a)所示。定義3.6是針對表達(dá)式的，若將一般句子的結(jié)構(gòu)看作是操作符與操作數(shù)的組合，則可以利用定義3.6得到對應(yīng)的語法樹。例如條件語句if

condition

then

s1

else

s2，可以看作是操作符if-thenelse作用于三個(gè)操作數(shù)condition、s1、s2，則此條件語句的語法樹如圖3.3(b)所示。第3章80x86微處理器圖3.2句子–(id+id)的分析樹(a)最左推導(dǎo)的分析樹；(b)最右推導(dǎo)的分析樹第3章80x86微處理器圖3.3句子的語法樹與分析樹相比，語法樹僅反映句型的結(jié)構(gòu)，而忽略了推導(dǎo)句型的過程，因此有些教材也將分析樹和語法樹分別稱為具體語法樹和抽象語法樹。第3章80x86微處理器二義性與二義性的消除二義性(Ambiguity)在例3.4中，對句子–(id+id)無論采用最左推導(dǎo)還是最右推導(dǎo)得到的是同一棵分析樹。是否對于任何一個(gè)句子都僅對應(yīng)一棵分析樹？也就是說，根據(jù)文法產(chǎn)生的任何一個(gè)句子都有唯一的結(jié)構(gòu)？事實(shí)并非如此。第3章80x86微處理器例3.7用文法G3.2采用最左推導(dǎo)產(chǎn)生句子id+id*id，可得到兩棵分析樹，如圖3.4(a)、(b)所示。用文法G3.2采用最左推導(dǎo)產(chǎn)生句子id+id+id，也可得到兩棵分析樹，如圖3.4(c)、(d)所示。其中圖3.4(a)、(b)所對應(yīng)的最左推導(dǎo)分別如下：(a)

E=>

E

*

E(b)E

=>

E

+

E=>

id

+

E=>

id

+

E

*

E=>

id

+

id

*

E=>

id

+

id

*

id=>

E

+

E

*

E=>

id

+

E

*

E=>

id

+

id

*

E=>

id

+

id

*

id第3章80x86微處理器圖3.4一個(gè)句子兩棵分析樹(a)先進(jìn)行+運(yùn)算；(b)先進(jìn)行*運(yùn)算；(c)+左結(jié)合；(d)+右結(jié)合第3章80x86微處理器定義3.7若文法G對同一個(gè)句子產(chǎn)生不止一棵分析樹，則稱G是二義的。文法二義的本質(zhì)是，在產(chǎn)生句子的過程中某些直接推導(dǎo)有多于一種選擇，從而使得下一步分析不確定，如上例對句子id+id*id的推導(dǎo)中，第一步直接推導(dǎo)既可以選用產(chǎn)生式E→E+E，也可以選用產(chǎn)生式E→E*E，從而造成一個(gè)句子有兩種以上的結(jié)構(gòu)。不同的結(jié)構(gòu)反映不同的意義，從運(yùn)算的角度看，圖3.4(a)分析樹代表的句子id+id*id的運(yùn)算次序是(id+id)*id，加法具有較高的優(yōu)先級；而圖3.4(b)分析樹的運(yùn)算次序是id+(id*id)，乘法具有較高的優(yōu)先級。圖3.4(c)分析樹代表的句子id+id+id的運(yùn)算次序是(id+id)+id，加法具有左結(jié)合性；而圖3.4(d)分析樹的運(yùn)算次序是id+(id+id)，加法具有右結(jié)合性。第3章80x86微處理器將圖3.2與圖3.4進(jìn)行比較，可以得出兩個(gè)結(jié)論：①一個(gè)句型有多于一棵分析樹，僅與文法和句型有關(guān)，與采用的推導(dǎo)方法無關(guān)；②造成二義性的原因，是文法中缺少對文法符號優(yōu)先級和結(jié)合性的規(guī)定。為了進(jìn)一步理解文法的二義性，考察另一個(gè)二義文法的典型例子“懸空(dangling)else”問題。描述if-then-else語言結(jié)構(gòu)二義文法如下所示，用文法G3.3產(chǎn)生同時(shí)含有if-then-else和if-then結(jié)構(gòu)的句子時(shí)，else與哪個(gè)then匹配不確定。第3章80x86微處理器S

→

if

C

then

S(1)|

if

C

then

S

else

S(2)|

id

:=

EC

→

E

=

E

|

E

<

E

|

E

>

E(3)(4)

…

(6)E

→

E

+

E

|

–

E

|

id

|

n(7)

…

(10)第3章80x86微處理器例3.8條件語句if

x<3

then

if

x>0

then

x:=5

else

x:=–5中，兩個(gè)then和一個(gè)else，用G3.3產(chǎn)生此語句時(shí)，G3.3無法判斷else應(yīng)該與哪一個(gè)then匹配，因?yàn)楹蜻x項(xiàng)(1)和(2)均可以用來進(jìn)行第一步直接推導(dǎo)，因此得到兩棵分析樹如圖3.5所示(圖中三角形代表簡化了的推導(dǎo)過程)。圖3.5(a)所對應(yīng)的推導(dǎo)過程為:S=>if

C

then

S

else

S

(else與遠(yuǎn)離它的then結(jié)合，采用候選項(xiàng)(2)=>

*if

x<3

then

S

else

S=>

if

x<3

then

if

C

then

S

else

S=*>

if

x<3

then

if

x>0

then

x:=5

else

x:=

–5第3章80x86微處理器圖3.5(b)所對應(yīng)的推導(dǎo)過程為:S=>if

C

then

S

(else與接近它的then結(jié)合，采用候選項(xiàng)(1))=>

*if

x<3

then

S=>

if

x<3

then

if

C

then

S

else

S=*>

if

x<3

then

if

x>0

then

x:=5

else

x:=

–5第3章80x86微處理器圖3.5“懸空else”語句的兩棵分析樹(a)else與離它遠(yuǎn)的then匹配；(b)else與接近它的then匹配第3章80x86微處理器在任何一個(gè)程序設(shè)計(jì)語言中，如果出現(xiàn)了二義性，則表示

同一段程序在確定的、相同的環(huán)境下反復(fù)執(zhí)行，會得到不同的結(jié)果，而這種情況在程序設(shè)計(jì)中是不允許的。也就是說，任何一個(gè)程序設(shè)計(jì)語言不應(yīng)該有二義性。以Pascal為例，算術(shù)表達(dá)式中乘法的優(yōu)先級高于加法的優(yōu)先級，加法和乘法均具有左結(jié)合性質(zhì)，圖3.4中的四棵分析樹，僅有(b)和(c)是合法的。if-then-else語句中，總是要求else與最接近它的then匹配，圖3.5中的兩棵分析樹，僅有(b)是正確的。第3章80x86微處理器3.2.4.2二義性的消除二義文法不是CFG，這意味著自上而下和自下而上分析均無法正確處理二義文法所產(chǎn)生的語言。但是一個(gè)文法是二義的，并不意味它所產(chǎn)生的語言一定是二義的，只有當(dāng)產(chǎn)生一個(gè)語言的所有文法都是二義的，這個(gè)語言才被認(rèn)為是二義的。程序設(shè)計(jì)語言是非二義的，任何時(shí)刻一個(gè)句子只對應(yīng)一個(gè)結(jié)構(gòu)。因此要求想辦法解決文法產(chǎn)生二義性的問題，即為文法的符號規(guī)定適當(dāng)?shù)膬?yōu)先級和結(jié)合性?；谶@一思想，可以有兩種方法解決二義性問題：①改寫二義文法為非二義文法；②對二義文法施加限制，具體就是為文法符號規(guī)定優(yōu)先級和結(jié)合性，使得分析過程中僅能產(chǎn)生一棵分析樹。第3章80x86微處理器1．改寫二義文法為非二義文法改寫二義文法的基本思想是通過引入新的非終結(jié)符，使原來分辨不清的結(jié)構(gòu)受到約束，從而使得對任何一個(gè)句子，僅能構(gòu)造一棵分析樹。下面首先通過例子介紹如何引入新的非終結(jié)符來解決分析的不確定性，然后給出引入非終結(jié)符的一般原則。第3章80x86微處理器例3.9改寫二義文法G3.2為非二義文法G3.4。E

→

E

+

T|

TT

→

T

*

F|

FF

→

(E)|–F|

id用G3.4對id+id*id重新推導(dǎo)。最左推導(dǎo)：E

=>

E

+

T

=>

T

+

T

=>

F

+

T

=>

id

+

T=>

id

+

T

*

F

=>

id

+

F

*

F

=>

id

+

id

*

F

=>

id

+

id

*

id第3章80x86微處理器最右推導(dǎo):E

=>

E

+

T

=>

E

+

T

*

F

=>

E

+

T

*

id

=>

E

+

F

*

id=>

E

+

id

*

id

=>

T

+

id

*

id

=>

F

+

id

*

id

=>

id

+

id

*

id上述兩個(gè)推導(dǎo)的中間過程雖不同，但最終生成的分析樹是一棵，如圖3.6(a)所示。同理，用文法G3.4對id+id+id進(jìn)行推導(dǎo)，得到的最終分析樹如圖3.6(b)所示。第3章80x86微處理器圖3.6句子id+id*id和id+id+id的分析樹(a)id+id*id的分析樹；(b)id+id+id的分析樹第3章80x86微處理器認(rèn)真分析圖3.6的分析樹，并與圖3.2(b)的分析樹進(jìn)行比較，可以得出以下印象或結(jié)論：由于新引入的非終結(jié)符限制每一步直接推導(dǎo)均有唯一選擇，使得同一個(gè)句子僅有一棵分析樹。最終產(chǎn)生的分析樹與推導(dǎo)方法無關(guān)，而僅與文法的描述有關(guān)。用通俗的話講，推導(dǎo)僅改變分析樹節(jié)點(diǎn)生孩子的先后，文法才決定生什么樣的孩子。引入新的非終結(jié)符，使得直接推導(dǎo)的步驟數(shù)增加，分析樹的高度增高，從而分析效率降低。第3章80x86微處理器在下邊(4)與(5)中，設(shè)α和β是任意的文法符號序列，且從α和β可以推導(dǎo)出ε，a∈α∪β是A產(chǎn)生式中的終結(jié)符，S是文法的開始符號。若SαAβ所需的直接推導(dǎo)步驟越少，則稱A越接近S。(4)越接近S的A與a，優(yōu)先級越低。例如從產(chǎn)生式E→T+E和T→T*F可以看出，E比T接近文法開始符號E，因此E(或+)比T(或*)優(yōu)先級低。同理T比F優(yōu)先級低。第3章80x86微處理器(5)對具有遞歸定義性質(zhì)的A產(chǎn)生式A→αAβ，若a∈β(A在a的左邊)，則a具有左結(jié)合性質(zhì)，若a∈α(A在a的右邊)，則a具有右結(jié)合性質(zhì)。例如E→E+T中E在+的左邊，則+具有左結(jié)合性質(zhì)，若

產(chǎn)生式形如E→T+E，則+具有右結(jié)合性質(zhì)。根據(jù)上述(4)與(5)，可以將書寫非二義文法的關(guān)鍵步驟歸納為下述兩點(diǎn)：①引入一個(gè)新的非終結(jié)符，增加一個(gè)子結(jié)構(gòu)并提高一級優(yōu)先級；②遞歸非終結(jié)符在產(chǎn)生式中的位置，反映文法符號的結(jié)合性。第3章80x86微處理器根據(jù)上述結(jié)論，簡單考察文法G3.2所描述表達(dá)式結(jié)構(gòu)的非二義文法G3.4是如何構(gòu)造的。首先，文法G3.2所描述的表達(dá)式中，可能有三種優(yōu)先級別的子表達(dá)式：+運(yùn)算優(yōu)先級最低，其次是*，而()、–(單目減)和id優(yōu)先級最高。因此需要引入三個(gè)非終結(jié)符E、T和F，分別對應(yīng)三個(gè)優(yōu)先級的子表達(dá)式，+運(yùn)算構(gòu)成的子表達(dá)式由E產(chǎn)生式描述，*運(yùn)算構(gòu)成的子表達(dá)式由T產(chǎn)生式描述，其他子表達(dá)式由F產(chǎn)生式描述。其次，確定運(yùn)算的結(jié)合性：+和*具有左結(jié)合性質(zhì)，–具有右結(jié)合性質(zhì)。因此E和T分別在+和*的左邊出現(xiàn)，而F在–的右邊出現(xiàn)。從而得到E產(chǎn)生式：E→E+T|T。第一個(gè)候選項(xiàng)產(chǎn)生含有+運(yùn)算的子表達(dá)式，第二個(gè)候選項(xiàng)產(chǎn)生含有*運(yùn)算的子表達(dá)式。由此可以看出，對于一個(gè)*運(yùn)算的子表達(dá)式，至少需要增加一次E到T的推導(dǎo)。依此類推，可以構(gòu)造T產(chǎn)生式和F產(chǎn)生式，最終得到文法G3.4。第3章80x86微處理器對于“懸空else”問題，它的實(shí)質(zhì)是if語句可以是完整的結(jié)構(gòu)(if-then-else)，也可以是不完整的結(jié)構(gòu)(if-then)。因此，在一復(fù)合的if語句中，可能then結(jié)構(gòu)多于else結(jié)構(gòu)，從而使得else不知與哪個(gè)then匹配。根據(jù)一般程序設(shè)計(jì)語言的規(guī)定，else總是與最

接近它的then匹配，這實(shí)質(zhì)上是與最右邊的then匹配，因此，解

決“懸空else”的問題變成為規(guī)定else具有右結(jié)合性質(zhì)。第3章80x86微處理器例3.10文法G3.3的非二義文法G3.5如下所示。解決二義文法G3.3的關(guān)鍵是將語句S分為完全匹配(MS)和不完全匹配(UMS)兩類，并且在不完全匹配的語句中確定else是右結(jié)合的。如產(chǎn)生式(6)所示，UMS在else右邊出現(xiàn)，從而使得用G3.5產(chǎn)生例3.7的條件語句if

x<3

then

if

x>0

then

x:=5

else

x:=–5時(shí)，每一步直接推導(dǎo)均是確定的，得到的分析樹如圖3.7所示。第3章80x86微處理器S

→

MS(1)|

UMS(2)MS

→

if

C

then

MS

else

MS(3)|

id

:=

E(4)UMS→

if

C

then

S(5)|

if

C

then

MS

else

UMS(6)C

→

E

=

E

|

E

<

E

|

E

>

E(7)

…

(9)E

→

E

+

T

|

T(10)

…

(11)T

→

T

*

F

|

F(12)

…

(13)F

→

(E)

|

–F

|

id

|

n(14)

…

(17)第3章80x86微處理器圖3.7“懸空else”解決后的分析樹第3章80x86微處理器2．為文法符號規(guī)定優(yōu)先級和結(jié)合性改寫文法可以解決二義性問題，但不是唯一的解決方法。比較上述討論過的二義文法和非二義文法，發(fā)現(xiàn)二義文法至少有兩個(gè)優(yōu)點(diǎn)：①比非二義文法容易理解；②分析效率高(分析樹低，直接推導(dǎo)步驟少)。第3章80x86微處理器由于二義性的問題實(shí)質(zhì)上是文法符號(包括終結(jié)符和非終結(jié)符)的優(yōu)先級和結(jié)合性問題，因此，另一種解決方案是，保留原來的二義文法，而對文法中有二義的文法符號規(guī)定適當(dāng)?shù)膬?yōu)先級與結(jié)合性，使得在產(chǎn)生語言的過程中，限制不確定的選項(xiàng)到唯一選擇。例如，在二義文法G3.2中，只要分別為+、*和–規(guī)定正確的優(yōu)先級和結(jié)合性，就會使得分析任何一個(gè)句子時(shí)僅能得到一棵分析樹。這種解決方案的典型例子是語法分析器生成器YACC。YACC構(gòu)造的是基于LALR(1)文法的語法分析器，但是通過規(guī)定文法符號的優(yōu)先級與結(jié)合性，使得YACC構(gòu)造的語法分析器可以對二義文法所描述的語言進(jìn)行確定地分析。第3章80x86微處理器3.3

語言與文法簡介到目前為止，我們在兩個(gè)層面上討論了程序設(shè)計(jì)語言的結(jié)構(gòu)：從詞法分析的層面上看，語言是由字母組成的記號的集合；從

語法分析的層面上看，語言是由記號組成的句子的集合。記號可以用正規(guī)式描述，句子可以用CFG描述。程序設(shè)計(jì)語言的結(jié)構(gòu)均可以用文法來描述。文法無論對程序設(shè)計(jì)語言的設(shè)計(jì)還是對編譯器的編寫，至少在以下三個(gè)方面起著重要作用：第3章80x86微處理器①文法給出了精確的、易于理解的語言結(jié)構(gòu)的說明；②以文法為基礎(chǔ)的語言，便于加入新的或修改、刪除舊的語言結(jié)構(gòu)；③有些類別的文法，可以自動生成高效的分析器。本節(jié)從理論的角度對文法進(jìn)行簡單的討論。討論建立在形式語言與自動機(jī)的理論之上，且僅引用結(jié)論而忽略數(shù)學(xué)的證明，有興趣的讀者可以參閱相關(guān)文獻(xiàn)。希望通過本節(jié)的討論，能使讀者對文法的分類和它們在編譯器構(gòu)造中的作用有一定的了解。第3章80x86微處理器3.3.1正規(guī)式與上下文無關(guān)文法1．正規(guī)式到CFG的轉(zhuǎn)換推論3.1正規(guī)式所描述的語言結(jié)構(gòu)均可以用CFG描述，反之不一定。我們通過引入從正規(guī)式構(gòu)造CFG的一種方法來說明上述推論成立。此方法分如下幾個(gè)步驟：①構(gòu)造正規(guī)式的NFA；②若0為初態(tài)，則A0為開始符號；③對于move(i,a)=j，引入產(chǎn)生式Ai→aAj；④對于move(i,ε)=j，引入產(chǎn)生式Ai→Aj；⑤若i是終態(tài)，則引入產(chǎn)生式Ai→ε。第3章80x86微處理器例3.11利用上述方法，正規(guī)式r=(a|b)*abb的CFG描述如下。其中識別r的NFA如圖3.8(a)所示。A0

→

aA0|bA0|aA1A1

→

bA2A2

→

bA3A3

→ε第3章80x86微處理器圖3.8正規(guī)式與CFG(a)(a|b)*abb的NFA；(b)G3.6產(chǎn)生abb的分析樹；(c)G3.7產(chǎn)生abb的分析樹第3章80x86微處理器事實(shí)上，從正規(guī)式構(gòu)造CFG，往往并不使用上述方法，而是通過分析正規(guī)式的特性，憑經(jīng)驗(yàn)直接構(gòu)造。例如，可以把r=(a|b)*abb看作首尾兩個(gè)部分，首部是0個(gè)或若干個(gè)a和b組成的串，尾部是固定字符串a(chǎn)bb。則得到G3.7如下：A

→

HT

(1)H

→ε|

aH

|

bH(2),(3),

(4)T

→

abb

(5)不難驗(yàn)證，文法G3.6和文法G3.7描述同一集合，因此它們是等價(jià)的。圖3.8(b)和(c)分別以分析樹的形式記錄了G3.6和G3.7產(chǎn)生句子abb的過程。第3章80x86微處理器2．為什么用正規(guī)式而不用CFG描述程序設(shè)計(jì)語言的詞法根據(jù)推論3.1，CFG既描述程序設(shè)計(jì)語言的語法又描述詞法，而基于下述幾個(gè)原因，往往采用正規(guī)式而不是CFG描述詞法：①詞法規(guī)則簡單，用正規(guī)式描述已足夠；②正規(guī)式的表示比CFG更直觀、簡潔、易于理解；③有限自動機(jī)的構(gòu)造比下推自動機(jī)簡單，且分析效率高；④區(qū)分詞法和語法，為編譯器前端的模塊劃分提供方便。第3章80x86微處理器有一個(gè)貫穿詞法分析和語法分析始終的思想是，語言的描述和語言的識別是表示一個(gè)語言的兩個(gè)不同側(cè)面，二者缺一不

可。用正規(guī)式和CFG描述的語言，對應(yīng)的識別方法(自動機(jī))不同。一般情況下，正規(guī)式適合描述線性結(jié)構(gòu)，如標(biāo)識符、關(guān)鍵字、

注釋等。而CFG適合描述具有嵌套(層次)性質(zhì)的非線性結(jié)構(gòu)，如

不同結(jié)構(gòu)的句子if-then-else、begin-end等。第3章80x86微處理器3.3.2上下文有關(guān)語言(Context

Sensitive

Language,CSL)程序設(shè)計(jì)語言中除了CFG可以描述的結(jié)構(gòu)之外，還有一些是CFG無法描述的所謂上下文有關(guān)的結(jié)構(gòu)。典型的這類語言結(jié)構(gòu)包括：變量的聲明與引用、過程調(diào)用時(shí)形參與實(shí)參的一致性檢查等。描述它們的文法被稱為上下文有關(guān)文法(ContextSensitive

Grammar,CSG)。第3章80x86微處理器例3.12標(biāo)識符聲明與引用問題的抽象可以用L1表示，其中第一個(gè)ω表示聲明，第二個(gè)ω表示引用，聲明與引用之間可以有任意長度的序列c。過程定義與調(diào)用中形參與實(shí)參一致性問題的抽象可以用L2表示，其中anbm是形參表，cndm是實(shí)參表，L1和L2均不是CFL，因?yàn)樵O(shè)計(jì)不出CFG來描述它們。這意味著許多程序設(shè)計(jì)語言，如Pascal、Ada、C++等均不是CFL，因?yàn)樗鼈円髽?biāo)識符先聲明后引用，并且要求形參與實(shí)參一致。L1={ωcω|ω∈(a|b)*}L2={anbmcndm|n≥1和m≥1}L3={anbncn|n≥1}第3章80x86微處理器另一個(gè)不是CFL的例子是英文排版中加底線問題的抽象，它可以用L3表示。其中anbncn分別表示輸入n個(gè)字符、回退n個(gè)字符和加n個(gè)底線。這是一個(gè)所謂的計(jì)數(shù)問題，即a、b、c三部分要保持個(gè)數(shù)相同，或者說保持三部分相關(guān)?！鰭侀_上述語言的實(shí)際含義，僅考慮它們的抽象表示，則對上述語言稍加修改，就可得到CFL。第3章80x86微處理器例3.13

L1"={ωcωr|ω∈(a|b)*}是上下文無關(guān)的，其中ωr是ω的逆對應(yīng)文法為:S

→

aSa

|

bSb

|

cL2"={anbmcmdn

|

n≥1和m≥1}是上下文無關(guān)的，對應(yīng)文法為：S→aSd

|

aAdA

→

bAc

|

bc第3章80x86微處理器L2""={anbncmdm

|

n≥1和m≥1}是上下文無關(guān)的，對應(yīng)文法為：S→ABA

→

aAb

|

abB

→

cBd

|

cdL3"={ambmcn|m，n≥1}是上下文無關(guān)的，對應(yīng)文法為：A→ACA

→

aAb

|

abC

→

cC

|

c第3章80x86微處理器L3‘與L3的區(qū)別在于，L3要求a、b、c三部分保持相關(guān)，而

L3’僅要求a、b兩部分保持相關(guān)，c與前邊無關(guān)。似乎降低了要求，L3‘就成為CFL，但是，L3’不是正規(guī)集，因?yàn)闃?gòu)造不出可以識別L3‘的DFA。我們可以用反證的方法來說明這一點(diǎn)。假設(shè)L3"是一個(gè)正規(guī)集，則可以構(gòu)造一個(gè)DFA

D，它接受L3"。設(shè)D有n個(gè)狀態(tài)(n是一個(gè)有限數(shù)字)，考察D讀完ε，a，aa，...，an，分別到達(dá)狀態(tài)S0，S1，...，Sn，共有n+1個(gè)狀態(tài)。根據(jù)鴿巢原理，在序列S0，S1，...，Sn中至少有兩個(gè)狀態(tài)相同，不妨設(shè)Si=Sj(j>i)因?yàn)閍ibick

屬于L3"，所以D可以從狀態(tài)Si再讀進(jìn)i個(gè)b和k個(gè)c到達(dá)終態(tài)f，如圖3.9所示。但是，D中也存在從初態(tài)S0到Si，再從Si到Sj標(biāo)記為aj的路徑，由于Si=Sj，D也接受不在L3"范圍內(nèi)的ajbick。所以假設(shè)不成立，L3"不是正規(guī)集。若再降低要求，a、b、c三部分均可無關(guān)，則可得到正規(guī)集。第3章80x86微處理器圖3.9既接受aibick也接受ajbick的DFA第3章80x86微處理器例3.14L3""={akbmcn

|

k，m，n≥1}是正規(guī)集，其對應(yīng)的正規(guī)式為：a+b+c+。同時(shí)也可由如下CFG產(chǎn)生：S

→

ABCA

→

a

|

aAB

→

b

|

bBC

→

c

|

cC第3章80x86微處理器3.3.3形式語言與自動機(jī)簡介喬姆斯基(Chomsky)把文法分為四種類型:0型、1型、2型和3型。文法之間的差異在于對產(chǎn)生式施加不同的限制。定義3.8若文法G=(N，T，P，S)的每個(gè)產(chǎn)生式α→β中，均有α∈(N∪T)*，且至少含有一個(gè)非終結(jié)符，β∈(N∪T)*，則稱G為0型文法。對0型文法施加以下第i條限制，即可得到i型文法。第3章80x86微處理器G的任何產(chǎn)生式α→β(S→ε除外)均滿足|α|≤|β|(|x|表示x中法符號的個(gè)數(shù))；G的任何產(chǎn)生式形如A→β，其中A∈N，β∈(N∪T)*；G的任何產(chǎn)生式形如A→a或者A→aB(或者A→Ba)，其中

A，B∈N，a∈T?！?型文法也被稱為短語文法，任何0型語言都是遞歸可枚舉的，反之，遞歸可枚舉集也必定是一個(gè)0型語言。第3章80x86微處理器1型文法就是上下文有關(guān)文法，這種文法意味著對非終結(jié)符的替換必須考慮上下文，并且一般不允許換成ε串。例如，若αAβ→αγβ是1型文法的產(chǎn)生式，α和β不全為空，則非終結(jié)符A只有在左邊是α，右邊是β這樣的上下文中才可能替換成γ。2型文法就是上下文無關(guān)文法，非終結(jié)符的替換無需考慮上下文。3型文法等價(jià)于正規(guī)式，因而也被稱為正規(guī)文法或線性文法。四種類型的文法和它們所描述的語言，以及識別對應(yīng)語言的自動機(jī)分別列舉在表3.1中。第3章80x86微處理器表3.1文法、語言與自動機(jī)文法產(chǎn)生式語

言自動機(jī)0型(短語)文法α→β0型語言(短語結(jié)構(gòu)語言，遞歸可枚舉集)圖靈機(jī)1型文法(CSG)限制11型語言(CSL)線性界線自動機(jī)2型文法(CFG)限制22型語言(CFL)下推自動機(jī)3型(正規(guī))文法限制33型語言(正規(guī)語言，正規(guī)集)有限自動機(jī)第3章80x86微處理器例3.15再考慮上下文有關(guān)語言L3={anbncn|n≥1}，可以用下述CSG產(chǎn)生。S→aSBC(1)bB→bb(5)S→aBC(2)bC→bc(6)CB→BC(3)cC→cc(7)aB→ab(4)第3章80x86微處理器對句子akbkck

的推導(dǎo)過程如下：S

=>...=>

ak–1S(BC)k–1k–1次S→aSBC的直接推=>

ak(BC)kS→aBC一次直接推導(dǎo)=>...=>

akBkCk若干次CB→BC的直接推導(dǎo)=>

akbBk–1CkaB→ab一次直接推導(dǎo)=>...=>

akbkCkk–1次bB→bb的直接推導(dǎo)=>

akbkcCk–1bC→bc一次直接推導(dǎo)=>...=>

akbkckk–1次cC→cc的直接推導(dǎo)第3章80x86微處理器對比L3、L3"、L3""，它們之間的關(guān)系可如圖3.10所示。圖3.10

L3、L3"、L3""的關(guān)系第3章80x86微處理器對比L3、L3"、L3""，它們之間的關(guān)系可如圖3.10所示。其中：A={aibjck

|

i,j,k≥1}B

=

{

aibick

|

i,k≥1

}C={aibici

|

i≥1}

L3=C(僅CSG可產(chǎn)生)L3"=B

(CSG、CFG均可產(chǎn)生）L3""=A

(CSG、CFG、正規(guī)式均可產(chǎn)生）第3章80x86微處理器L3、L3"和L3""說明一個(gè)問題：如果說正規(guī)式描述的語言僅計(jì)一個(gè)數(shù)(僅對一個(gè)部分計(jì)數(shù)，或者說各部分互不相關(guān))，則CFG可以計(jì)兩個(gè)數(shù)，CSG可以計(jì)三個(gè)數(shù)。打個(gè)形象的比喻：正規(guī)式不管是桃子還是梨統(tǒng)統(tǒng)挑出來；CFG則可以把桃子挑選出來；CSG則可以進(jìn)一步把好桃子挑選出來。通過上述討論，可以得出這樣一個(gè)印象：i型文法比i＋1型文法能力強(qiáng)。理論上的結(jié)論是：就描述與識別能力來講，0型文法和圖靈機(jī)最強(qiáng)，3型文法和有限自動機(jī)最弱。但是文法的設(shè)計(jì)與自動機(jī)構(gòu)造的難易程度，卻與它們的能力成反比。到目前為止，真正實(shí)

用的識別器均基于CFG(包括正規(guī)文法)。而對于語言結(jié)構(gòu)中超出

CFG能力的部分，采用語義分析的方法處理。在以后的討論中，除非特別說明，文法均指CFG。第3章80x86微處理器3.4

自上而下語法分析3.4.1自上而下分析的一般方法自上而下分析的基本思想是：對于任何一個(gè)輸入序列，從文法的開始符號開始，進(jìn)行最左推導(dǎo)，直到得到一個(gè)合法句子或者發(fā)現(xiàn)一個(gè)非法結(jié)構(gòu)。在推導(dǎo)的過程中試圖用一切可能的方法，自上而下、從左到右為輸入序列建立分析樹。整個(gè)分析是一種試探的過程，是反復(fù)使用不同產(chǎn)生式謀求與輸入序列匹配的過程。第3章80x86微處理器例3.16對于下述所給文法和輸入序列ω=cad，自上而下試探建立分析樹的過程如圖3.11所示。一開始根據(jù)當(dāng)前輸入的第一個(gè)記號c展開產(chǎn)生式S→cAd，得到句型cAd，匹配c后暴露出a。由于A產(chǎn)生式有兩個(gè)以a開始的候選項(xiàng)，選擇任何一個(gè)產(chǎn)生式展開均可，第一次選擇A→ab得到句型cabd，與輸入序列cad匹配到第三個(gè)記號時(shí)失敗，如圖3.11(a)，于是回退一步，選擇A→a再得到句型cad，與輸入序列cad匹配成功，如圖3.11(b)。S

→

cAdA

→

ab

|

a第3章80x86微處理器圖3.11試探性質(zhì)的自上而下分析(a)匹配失敗，回溯；(b)匹配成功，接收第3章80x86微處理器若存在形如A→αβ1|αβ2的產(chǎn)生式，即A產(chǎn)生式中有多于一個(gè)候選項(xiàng)的前綴相同(稱為公共左因子，或簡稱左因子)，則可能會造成虛假匹配，使得在分析過程中可能需要進(jìn)行大量回溯，

從而造成分析效率低、語義動作難以恢復(fù)以及出錯(cuò)位置的報(bào)告

不確切等。若存在形如A→Aα的產(chǎn)生式，則分析過程中一旦采用了該產(chǎn)生式去替換，就會陷入死循環(huán)而使分析無法進(jìn)行下去。產(chǎn)生式的這種形式被稱為左遞歸。為了避免上述弱點(diǎn)，需要對文法進(jìn)行重寫。消除左遞歸，以避免陷入死循環(huán)；提取左因子，以避免回溯。第3章80x86微處理器3.4.2消除左遞歸定義3.9若文法G中的非終結(jié)符A，對某個(gè)文法符號序列α存在推導(dǎo)AAα，則稱文法G是左遞歸的。若文法G中有形如A→Aα的產(chǎn)生式，則稱該產(chǎn)生式對A直接左遞歸。第3章80x86微處理器1．消除文法的直接左遞歸首先考慮僅有兩個(gè)候選項(xiàng)的直接左遞歸的產(chǎn)生式A→Aα|β。該產(chǎn)生式僅有兩個(gè)候選項(xiàng)，其中一個(gè)是直接左遞歸的，另一個(gè)不含直接左遞歸，可以用非左遞歸的A→βA"和A"→αA"|

ε取代。首先看第一組產(chǎn)生式A→Aα|β，使用A→Aα進(jìn)行若干次直接推導(dǎo)得到

Aα*，再使用A→β進(jìn)行一次直接推導(dǎo)得到βα*，它產(chǎn)生的集合是β后邊跟隨若干個(gè)α(可以是0個(gè))。再看第二組產(chǎn)生式A→βA"和A"→

αA"|

ε，使用A→βA"進(jìn)行一次直接推導(dǎo)得到βA"，再使用A"→αA"進(jìn)行若干次直接推導(dǎo)得到βα*A"，最后使用A"→ε進(jìn)行一次直接推導(dǎo)得到βα*。顯然兩組產(chǎn)生式產(chǎn)生的是同一個(gè)集合。第3章80x86微處理器算法3.1消除直接左遞歸輸入文法G中所有的A產(chǎn)生式輸出等價(jià)的不含直接左遞歸的文法G"方法首先，整理A產(chǎn)生式為如下形式：A→

Aα1

|

Aα2

|

...

|

Aαm

|β1

|β2

|

...|βn其中，αi非空，βj均不以A開始。然后用下述產(chǎn)生式代替A產(chǎn)生式：A→

β1

A"

|β2

A"

|

...|βn

A"A"→

α1

A"

|

α2

A"

|

...

|

αm

A"

|ε第3章80x86微處理器圖3.12文法G3.4"產(chǎn)生的id+id*id的分析樹第3章80x86微處理器例3.17考慮簡單的算術(shù)表達(dá)式文法G3.4，其中的E和T均是左遞歸的產(chǎn)生式。運(yùn)用算法3.1消除直接左遞歸，得到文法G3.4"如下。用文法G3.4"分析id+id*id，得到分析樹如圖3.12所示。與圖

3.6(a)中的分析樹比較，兩棵分析樹反映的語言結(jié)構(gòu)是相同的，均是先進(jìn)行乘法運(yùn)算再進(jìn)行加法運(yùn)算。E

→

TE"E"

→

+TE"

|

εT

→

FT"T"

→

*FT"

|

εF

→

(E)

|

–F

|

id第3章80x86微處理器2．消除文法的左遞歸有些左遞歸并不是直接的，如下述文法G3.8中的S不是直接左遞歸，但也是左遞歸的，因?yàn)榇嬖谕茖?dǎo)S=>Aa=>Sda。對于文法中的左遞歸，可以用算法3.2系統(tǒng)地消除。S→Aa

|

bA→Ac

|

Sd

|ε第3章80x86微處理器算法3.2消除左遞歸輸入無回路文法G輸出無左遞歸的等價(jià)文法G"方法將非終結(jié)符合理排序：A1，A2，...，An，然后運(yùn)用下述過程：for

i

in

2..nloop

for

j

in

1..i–1loop用Aj→δ1|δ2|...|δk的右部替換每個(gè)形如Ai→Ajγ產(chǎn)式中的Aj,得到新產(chǎn)生式：Ai→δ1γ|δ2γ|...|δkγ;消除Ai產(chǎn)生式中的直接左遞歸;end

loop;end

loop;第3章80x86微處理器算法3.2并不能消除所有文法中的左遞歸，若文法G產(chǎn)生句子的過程中會出現(xiàn)AA的推導(dǎo)，則無法消除左遞歸。例3.18將算法3.2用于文法G3.8，按下述步驟消除G3.8中的左遞歸。①將S和A排序，S在先A在后；②用S右部替換A→Sd中的S，得到新產(chǎn)生式A→Ac

|

Aad

|

bd

|ε第3章80x86微處理器消除新產(chǎn)生式中的直接左遞歸，最后得到等價(jià)的文法G3.8"如下。S→

Aa

|

bA→

bdA"

|

A"A"→

cA"

|

adA"

|

ε第3章80x86微處理器例3.19算術(shù)表達(dá)式組成的語句序列，文法G3.9如下:L→E；L

|

εE

→

E

+

T

|

E

–

T

|

TT

→

T

*

F

|

T

/

F

|

T

mod

F

|

FF

→

(

E

)

|

id

|

num消除左遞歸后的等價(jià)文法G3.9":L→E；L

|

εE

→

T

E"E"

→

+

T

E"

|

–

T

E"

|

εT

→

F

T"T"

→

*

F

T"

|

/

F

T"

|

mod

F

T"

|

εF

→

(

E

)|

id

|

num(G3.9)(G3.9")第3章80x86微處理器3.4.3提取左因子對于有左因子的文法，推導(dǎo)過程中會出現(xiàn)無法確定用A產(chǎn)生式的哪個(gè)候選項(xiàng)替換A的情況，這時(shí)，可以重寫A產(chǎn)生式來推遲這種決定，直到看見足夠的輸入，能正確決定所需選擇為止。這一過程類似于有限自動機(jī)的確定化，被稱為提取左因子。算法3.3提取文法的左因子輸入文法G輸出等價(jià)的無左因子文法G"第3章80x86微處理器方法為每個(gè)產(chǎn)生式A，找出其候選項(xiàng)中最長公共前綴α，重排A產(chǎn)生式如下，其中γ是不以α為前綴的其他候選項(xiàng)。A→αβ1|αβ2|

...|αβn|γ并用下述產(chǎn)生式替代之。A→

αA"|γ

A"→

β1|β2|

...|βn重復(fù)此過程，直到所有A產(chǎn)生式的候選項(xiàng)中均不再有公共前綴。第3章80x86微處理器例3.20考察懸空else文法G3.10：S

→

iCtS

|

iCtSeS

|

aC

→

bS的前兩個(gè)候選項(xiàng)中含有左因子iCtS，按算法3.3提取左因子之后，等價(jià)文法G3.10‘如下。S

→

iCtSS"

|

aS"

→

eS

|εC

→

bG3.10G3.10第3章80x86微處理器當(dāng)一個(gè)文法中既有左遞歸又含左因子時(shí)，一般的做法是先消除左遞歸。因?yàn)樽筮f歸也是左因子的一種形式，當(dāng)左遞歸消除后，同時(shí)也消除了部分左因子。如例3.19中的文法G3.9，由于除了E和T產(chǎn)生式之外，沒有其他形式的左因子，所以左遞歸消除后，成為既無左遞歸又無左因子的文法G3.9"。第3章80x86微處理器3.4.4遞歸下降分析遞歸下降分析是直接以程序的方式模擬產(chǎn)生式產(chǎn)生語言的過程。它的基本思想是：為每一個(gè)非終結(jié)符構(gòu)造一個(gè)子程序，每一個(gè)子程序的過程體中按該產(chǎn)生式的候選項(xiàng)分情況展開，遇到終結(jié)符直接匹配，而遇到非終結(jié)符就調(diào)用相應(yīng)非終結(jié)符的子程序。該分析從調(diào)用文法開始符號的子程序開始，直到所有非終結(jié)符都展開為終結(jié)符并得到匹配為止。若分析過程中達(dá)到這一步則表明分析成功，否則表明輸入中有語法錯(cuò)誤。遞歸下降分析對文法的限制是不能有公共左因子和左遞歸。由于文法是遞歸定義的，因此子程序也是遞歸的，被稱為遞歸下降子程序。第3章80x86微處理器對于規(guī)模比較小的語言，遞歸下降子程序方法是很有效的方法，它簡單靈活，容易構(gòu)造，其缺點(diǎn)是程序與文法直接相關(guān)，對文法的任何改變均需對程序進(jìn)行相應(yīng)的修改。遞歸下降子程序方法是一種非形式化的方法，只要能夠?qū)懗雒總€(gè)非終結(jié)符的子程序，采用什么樣的方法和步驟均可。從初學(xué)者的角度出發(fā)，我們分三個(gè)步驟構(gòu)造遞歸下降子程序，并且以文法G3.9"為例，詳細(xì)討論各步驟的具體過程。①構(gòu)造文法的狀態(tài)轉(zhuǎn)換圖并且化簡；②將轉(zhuǎn)換圖轉(zhuǎn)化為EBNF表示；③從EBNF構(gòu)造子程序。第3章80x86微處理器1．文法的狀態(tài)轉(zhuǎn)換圖文法的狀態(tài)轉(zhuǎn)換圖是針對非終結(jié)符而言的，每個(gè)非終結(jié)符對應(yīng)一個(gè)狀態(tài)轉(zhuǎn)換圖。它與FA的狀態(tài)轉(zhuǎn)換圖相似，唯一的區(qū)別是表示狀態(tài)轉(zhuǎn)移的邊上標(biāo)記的不是字母，而是文法符號(終結(jié)符或非終結(jié)符)。文法狀態(tài)轉(zhuǎn)換圖的構(gòu)造方法如下：①為每個(gè)非終結(jié)符A建立一個(gè)初態(tài)和一個(gè)終態(tài)；②為每個(gè)產(chǎn)生式A→X1X2...Xn構(gòu)造從初態(tài)到終態(tài)的路徑，邊分別標(biāo)記為X1，X2，...，Xn。③根據(jù)識別同一集合的原則，化簡轉(zhuǎn)換圖。第3章80x86微處理器圖3.13文法G3.9"的狀態(tài)轉(zhuǎn)換圖第3章80x86微處理器對于圖3.13的狀態(tài)轉(zhuǎn)換圖，可以根據(jù)識別同一集合的原則，對它們進(jìn)行化簡：①在狀態(tài)轉(zhuǎn)換圖中，對非終結(jié)符A的一次匹配，等價(jià)于對A遞歸子程序的一次調(diào)用，因此轉(zhuǎn)換圖中標(biāo)記為A的邊可等價(jià)為標(biāo)記ε的邊轉(zhuǎn)向A轉(zhuǎn)換圖的初態(tài)；②標(biāo)記為ε的邊所連接的兩個(gè)狀態(tài)可以合并；③標(biāo)記相同的路徑可以合并；④不可區(qū)分的狀態(tài)可以合并。第3章80x86微處理器以E和E"的轉(zhuǎn)換圖為例，對它們進(jìn)行下述化簡：①首先考察E"的轉(zhuǎn)換圖，合并E"轉(zhuǎn)換圖中+TE"和–TE"兩條路徑見圖3.14(a)；②對E"的匹配改為指向E"的初態(tài)且標(biāo)記為ε的邊，見圖3.14(b)；③從狀態(tài)8出發(fā)，經(jīng)T可到達(dá)的狀態(tài)的全體7、9、10可以合并為一個(gè)狀態(tài)，由于10是終態(tài)，合并后的狀態(tài)也應(yīng)是終態(tài)，取10為代表，見圖3.14(c)；④再考察E的轉(zhuǎn)換圖，對E"的匹配改為指向E"的初態(tài)且標(biāo)記為ε的邊，見圖3.14(d)；第3章80x86微處理器⑤由于從4、8狀態(tài)經(jīng)T的下一狀態(tài)轉(zhuǎn)移均可到達(dá)狀態(tài)10，且5狀態(tài)經(jīng)ε到達(dá)狀態(tài)10，所以4、5、8是不可區(qū)分的，可以合并為一個(gè)狀態(tài)并取4為代表，最后得到E的轉(zhuǎn)換圖，見圖3.14(e)。第3章80x86微處理器圖3.14狀態(tài)轉(zhuǎn)換圖的化簡第3章80x86微處理器T和T"的化簡與E和E"的化簡完全相同，另外讀者可以參考上述討論，對L的轉(zhuǎn)換圖進(jìn)行化簡。最終化簡后的文法G3.9"的狀態(tài)轉(zhuǎn)換圖如圖3.15所示。從狀態(tài)轉(zhuǎn)換圖中可以看出各非終結(jié)符所表示的產(chǎn)生式的結(jié)構(gòu)：L是由0個(gè)或若干個(gè)E組成的序列，E是至少由一個(gè)T組成的算術(shù)表達(dá)式或者由加減運(yùn)算與T組成的算術(shù)表達(dá)式；T是至少由一個(gè)F組成的算術(shù)表達(dá)式或者由乘、除和取模運(yùn)算與F組成的算術(shù)表達(dá)式；F是由標(biāo)識符、整型數(shù)或者加括弧的算術(shù)表達(dá)式組成的算術(shù)表達(dá)式。第3章80x86微處理器圖3.15

G3.9"化簡后的狀態(tài)轉(zhuǎn)換圖第3章80x86微處理器2．文法的擴(kuò)展BNF(EBNF)表示與正規(guī)式的簡化表示類似，為了書寫和表達(dá)的簡潔方便，可以對產(chǎn)生式集進(jìn)行擴(kuò)充，稱為文法的擴(kuò)展BNF表示(Extended

BNF，EBNF)。具體可以在產(chǎn)生式的右部引入下述符號進(jìn)行擴(kuò)充，每種擴(kuò)充形式均可以與程序的某種語句結(jié)構(gòu)直接對應(yīng)。①{}：被括在{}中的內(nèi)容可以重復(fù)0或若干次；“{}”可以用來表示轉(zhuǎn)換圖中的環(huán)，并且可以在遞歸下降子程序中用while結(jié)構(gòu)來實(shí)現(xiàn)；②[]：被括在[]中的內(nèi)容是可選擇的；“[]”可以用來表示轉(zhuǎn)換圖中可以被繞過的路徑，并且可以用if或while結(jié)構(gòu)實(shí)現(xiàn)；第3章80x86微處理器③|：“|”在BNF表示中代表產(chǎn)生式中各候選項(xiàng)的或關(guān)系，而在EBNF中，“|”還可以出現(xiàn)在括弧“()”之內(nèi)，表示括弧中各部分之間的或關(guān)系；它一般表示轉(zhuǎn)換圖中的并列路徑，并且可以用case結(jié)構(gòu)實(shí)現(xiàn)；④()：利用()可以改變運(yùn)算的優(yōu)先級和結(jié)合性。第3章80x86微處理器化簡后的狀態(tài)轉(zhuǎn)換圖與EBNF之間，特別是EBNF與程序結(jié)構(gòu)之間的對應(yīng)關(guān)系，使得EBNF成為初學(xué)者構(gòu)造遞歸下降子程序的有力幫手。根據(jù)轉(zhuǎn)換圖與EBNF對應(yīng)關(guān)系，構(gòu)造文法G3.9"的

EBNF文法G3.9""如下。L

→

{

E;

}E

→

T

{

(+|–)

T

}T

→

F

{

(*|/|mod)

F

}F

→

(

E

)

|

id

|

num(G3.9"")第3章80x86微處理器3．遞歸下降子程序事實(shí)上，EBNF表示的產(chǎn)生式已經(jīng)可以被看作是程序的抽象。用某種程序設(shè)計(jì)語言表示出來，并且加上適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)與基本函數(shù)，就形成了非終結(jié)符的遞歸下降子程序。G3.9""的遞歸下降子程序如下。首先設(shè)計(jì)兩個(gè)變量lookahead和eof,lookahead是當(dāng)前的下一輸入終結(jié)符，eof是輸入的結(jié)束標(biāo)志。另外設(shè)計(jì)一個(gè)函數(shù)match(t)，它的作用是進(jìn)行終結(jié)符的匹配，首先將lookahead與t比較，若相同則取下一終結(jié)符，否則報(bào)錯(cuò)。第3章80x86微處理器procedure

match(t)isbegin

if

t=lookaheadthen

lookahead:=lexan；--調(diào)用詞法分析器，返回一個(gè)終結(jié)符else

error("syntax

error1")；end

if；end

match；procedure

L

is

--展開非終結(jié)符Lbeginlookahead:=lexan；

--