編譯方法、技術(shù)與實(shí)踐 課件全套 許暢 第1-6章 概述、詞法分析與語法分析 -中間代碼優(yōu)化

第一章

概述2課程簡(jiǎn)介教材主要教材：《編譯方法、技術(shù)與實(shí)踐》，許暢，馮洋，機(jī)械工業(yè)出版社參考教材：《編譯原理》第二版--

機(jī)械工業(yè)出版社Aho,AlfredV.,MonicaS.Lam,RaviSethi,andJeffreyD.Ullman.

Compilers:principles,techniquesandtools.

2020.《現(xiàn)代編譯原理

（C語言描述）》--人民郵電出版社Appel,AndrewW.ModerncompilerimplementationinC.

Cambridgeuniversitypress,

2004.3課程簡(jiǎn)介語法分析樹源代 詞法分碼 析器詞法單元流第三版實(shí)驗(yàn)：2022

年秋季學(xué)期

~第二版實(shí)驗(yàn)：2012

年春季學(xué)期

至

2022

年春季學(xué)期實(shí)驗(yàn)一詞法分析 語法分析語法分析器實(shí)驗(yàn)二語義分析語義分析器注釋語法樹實(shí)驗(yàn)四目標(biāo)代碼生成代碼生成器目標(biāo)代碼實(shí)驗(yàn)三中間代碼生成翻譯器中間代碼實(shí)驗(yàn)五中間代碼優(yōu)化優(yōu)化管道優(yōu)化后中間代碼4提綱編譯器的結(jié)構(gòu)編譯過程語言特征5什么是編譯器一個(gè)編譯器就是一個(gè)程序，讀入以某一種語言（源語言）編寫的程序，并把該程序翻譯成為一個(gè)等價(jià)的、用另一種語言（目標(biāo)語言）編寫的程序。如果翻譯過程發(fā)現(xiàn)源程序有錯(cuò)，則報(bào)錯(cuò)狹義：程序設(shè)計(jì)語言

→機(jī)器代碼廣義：程序變換

C++→C

→匯編

Pascal

→C編譯器源程序目標(biāo)程序6編譯器簡(jiǎn)介編譯器

vs.

解釋器編譯器的結(jié)構(gòu)編譯的構(gòu)造工具編譯器源程序目標(biāo)程序7編譯器簡(jiǎn)介8編譯器效率高，一次編譯，多次運(yùn)行。通常目標(biāo)程序是可執(zhí)行的。程序輸出編譯器源程序程序輸入目標(biāo)程序程序輸出程序輸入9解釋器直接利用用戶提供的輸入，執(zhí)行源程序中指定的操作。不生成目標(biāo)程序，而是根據(jù)源程序的語義直接運(yùn)行。邊解釋，邊執(zhí)行，錯(cuò)誤診斷效果好。解釋器源程序程序輸入程序輸出10編譯器

vs.

解釋器Java結(jié)合了兩者：

先編譯成字節(jié)碼，再由Java虛擬機(jī)解釋執(zhí)行

即時(shí)編譯（Just-in-time

compiling）11典型語言（如C）的編譯預(yù)處理器編譯器匯編器鏈接器加載器12編譯器簡(jiǎn)介編譯器

vs.

解釋器編譯器的結(jié)構(gòu)編譯的構(gòu)造工具13編譯器的結(jié)構(gòu)分析部分（Analysis）

源程序

- 語法結(jié)構(gòu)

- 中間表示

搜集源程序中的相關(guān)信息，放入符號(hào)表

分析、定位程序中可能存在的錯(cuò)誤信息（語法、語義錯(cuò)誤）

又稱編譯器的前端（front

end），是與機(jī)器無關(guān)的部分綜合部分（Synthesis）

根據(jù)符號(hào)表和中間表示構(gòu)造目標(biāo)程序

又稱編譯器的后端（back

end），是與機(jī)器相關(guān)的部分14編譯器中的若干步驟每個(gè)步驟把源程序的一種表示方式轉(zhuǎn)換成另一種表示方式。實(shí)踐中，某些中間表示不需要明確的構(gòu)造出來。符號(hào)表可由各個(gè)步驟使用15符號(hào)表管理記錄源程序中使用的變量的名字，收集各種屬性

名字的存儲(chǔ)分配

類型

作用域

過程名字的參數(shù)數(shù)量、參數(shù)類型等等符號(hào)表可由編譯器的各個(gè)步驟使用16類比：英語的分析理解過程詞法分析：Thisline

is

a

longer

sentence.語法分析：語義分析Thislineisalonger

sentence.17詞法分析詞法分析/掃描（lexical

analysis,

scanning）

讀入源程序的字符流，輸出有意義的詞素(lexeme)

基于詞素，產(chǎn)生詞法單元：<token-name,

attribute-value>

token-name由語法分析步驟使用

attribute-value指向相應(yīng)的符號(hào)表?xiàng)l目，由語義分析/代碼生成步驟使用例子

position=initial+rate*

60

<id,1>

<=,

>

<id,

2>

<+,

>

<id,3>

<*,

>

<number,

4>18語法分析詞法分析后，需要得到詞素序列的語法結(jié)構(gòu)語法分析/解析（syntax

analysis/parsing）

根據(jù)各個(gè)詞法單元的第一個(gè)分量來創(chuàng)建樹形中間表示形式。通常是語法樹（syntax

tree）。

指出了詞法單元流的語法結(jié)構(gòu)。19語義分析得到語義(meaning)，對(duì)于編譯器來說比較難語義分析（semanticanalysis）

使用語法樹和符號(hào)表中的信息，檢查源程序是否滿足語言定義的語義約束。

同時(shí)收集類型信息，用于代碼生成。

類型檢查，類型轉(zhuǎn)換。20中間代碼生成根據(jù)語義分析的輸出，生成類機(jī)器語言的中間表示三地址代碼：

每個(gè)指令最多包含三個(gè)運(yùn)算分量

t1=inttofloat(60)；t2=id3*t1;t3=id2+

t2;21代碼優(yōu)化通過對(duì)中間代碼的分析，改進(jìn)中間代碼，得到更好的目標(biāo)代碼

快、短、能耗低優(yōu)化有具體的設(shè)計(jì)目標(biāo)22代碼生成把中間表示形式映射到目標(biāo)語言

寄存器的分配

指令選擇

內(nèi)存分配23編譯器的趟（Pass）趟：以文件為輸入輸出單位的編譯過程的個(gè)數(shù)，每趟可由一個(gè)或若干個(gè)步驟構(gòu)成“步驟”是邏輯組織方式“趟”和具體的實(shí)現(xiàn)相關(guān)

參考LLVM實(shí)現(xiàn)中的Pass24編譯器簡(jiǎn)介編譯器

vs.

解釋器編譯器的結(jié)構(gòu)編譯的構(gòu)造工具25編譯器的構(gòu)造工具語法分析器的生成器：

yacc/bison

根據(jù)一個(gè)程序設(shè)計(jì)語言的語法描述自動(dòng)生成語法分析器掃描器的生成器:

lex/flex

根據(jù)一個(gè)語言的詞法單元的正則表達(dá)式描述生成詞法分析器語法制導(dǎo)的翻譯引擎

生成一組用于遍歷分析樹并生成中間代碼的程序代碼生成器的生成器

把中間語言的每個(gè)運(yùn)算翻譯成目標(biāo)機(jī)上機(jī)器語言的規(guī)則，生成代碼生成器數(shù)據(jù)流分析引擎

收集數(shù)據(jù)流信息，用于優(yōu)化編譯器構(gòu)造工具集26編譯技術(shù)的應(yīng)用高級(jí)程序設(shè)計(jì)語言的實(shí)現(xiàn)

高級(jí)程序設(shè)計(jì)語言的抽象層次的提高有利于編程，但是直接生成的代碼卻相對(duì)低效率

聚合類型/高級(jí)控制流/面向?qū)ο?垃圾自動(dòng)收集機(jī)制針對(duì)計(jì)算機(jī)體系結(jié)構(gòu)的優(yōu)化

并行性：指令級(jí)并行，處理器層次并行

內(nèi)存層次結(jié)構(gòu)新體系結(jié)構(gòu)的設(shè)計(jì)

RISC

專用體系結(jié)構(gòu)

一個(gè)新的體系結(jié)構(gòu)特征能否被充分利用，取決于編譯技術(shù)27編譯技術(shù)的應(yīng)用程序翻譯

二進(jìn)制翻譯/硬件合成/數(shù)據(jù)查詢解釋器/編譯后模擬軟件生產(chǎn)率工具

類型檢查

邊界檢查

內(nèi)存管理工具28編譯器的處理對(duì)象-程序語言編譯器源程序目標(biāo)程序29程序設(shè)計(jì)語言語言的代分類

第一代語言：機(jī)器語言

第二代語言：匯編語言

第三代語言：高級(jí)程序設(shè)計(jì)語言Fortran,Pascal,Lisp,Modula,

C

第四代：特定應(yīng)用語言：NOMAD,

SQL,

Postscript

第五代：基于邏輯和約束的語言，Prolog、OPS5命令式語言/聲明式語言

前者指明如何完成，后者指明要完成哪些計(jì)算馮.諾依曼語言/面向?qū)ο蟮恼Z言/腳本語言面向?qū)ο笳Z言

Simula,Smalltalk,Modula3,C++,ObjectPascal,Java,

C#

數(shù)據(jù)抽象、繼承30程序設(shè)計(jì)語言和編譯器之間的關(guān)系程序設(shè)計(jì)語言的新發(fā)展向編譯器設(shè)計(jì)者提出新要求

設(shè)計(jì)相應(yīng)的算法和表示方法來翻譯和支持新的語言特征通過降低高級(jí)語言的執(zhí)行開銷，推動(dòng)這些高級(jí)語言的使用編譯器設(shè)計(jì)者還需要更好地利用新硬件的能力31程序設(shè)計(jì)語言的基礎(chǔ)概念靜態(tài)/動(dòng)態(tài)

靜態(tài)：語言策略支持編譯器靜態(tài)決定某個(gè)問題

動(dòng)態(tài)：只允許在程序運(yùn)行時(shí)刻作出決定

Java類聲明中的static指明了變量的存放位置可靜態(tài)確定作用域

x的一個(gè)聲明的作用域是指程序中的一個(gè)區(qū)域，其中對(duì)x的使用都指向這個(gè)聲明

靜態(tài)作用域：通過靜態(tài)閱讀程序決定作用域

動(dòng)態(tài)作用域32程序設(shè)計(jì)語言的基礎(chǔ)概念環(huán)境與狀態(tài)

環(huán)境：是從名字到存儲(chǔ)位置的映射

狀態(tài)：從內(nèi)存位置到它們的值的映射環(huán)境的改變需要遵守語言的作用于規(guī)則33程序設(shè)計(jì)語言的基礎(chǔ)概念靜態(tài)作用域和塊結(jié)構(gòu)

C族語言使用靜態(tài)作用域。C語言程序由頂層的變量、函數(shù)聲明組成函數(shù)內(nèi)部可以聲明變量（局部變量/參數(shù)），這些聲明的作用域在它出現(xiàn)的函數(shù)內(nèi)一個(gè)頂層聲明的作用域包括其后的所有程序。除去那些具有同樣名字的變量聲明的函數(shù)體。

作用域規(guī)則基于程序結(jié)構(gòu)，聲明的作用域由它在程序中的位置隱含決定。

也通過public、private、protected進(jìn)行明確控制34程序設(shè)計(jì)語言的基礎(chǔ)概念塊作用域?qū)嵗?5程序設(shè)計(jì)語言的基礎(chǔ)概念動(dòng)態(tài)作用域

對(duì)一個(gè)名字x的使用指向的是最近被調(diào)用但還沒有終止且聲明了x的過程中的這個(gè)聲明。#include<stdio.h>#definea

(x+1)intx=

2;voidc(){printf("%d\n",a);}voidb(){intx=1;

printf("%d\n",a);}int

main(){b();c();}#include<stdio.h>#definea

(x+1)intx=

2;voidc(){printf("%d\n",a);}voidb(){intx=1;printf("%d\n",a);c();}int

main(){b();}第二章

詞法分析和語法分析（一）提綱詞法分析概要正則表達(dá)式有限狀態(tài)自動(dòng)機(jī)從NFA到DFA的轉(zhuǎn)換狀態(tài)最小化算法一個(gè)實(shí)例詞法分析<id,3>

<*,>

<number,

position=initial+rate*

60<id,1>

<=,

>

<id,

2>

<+,

>4>詞法分析器作用詞法分析是讀入源程序的輸入字符、將它們組成詞素，生成并輸出一個(gè)詞法單元序列，每個(gè)詞法單元對(duì)應(yīng)于一個(gè)詞素常見的做法

由語法分析器調(diào)用，需要的時(shí)候不斷讀取、生成詞法單元

可以避免額外的輸入輸出在識(shí)別出詞法單元之外，還會(huì)完成一些不需要生成詞法單元的簡(jiǎn)單處理，比如刪除注釋、將多個(gè)連續(xù)的空白字符壓縮成一個(gè)字符等詞法分析相關(guān)概念詞素（Lexeme）

源程序中的字符序列，它和某類詞法單元的模式匹配，被詞法分析器識(shí)別為該詞法單元的實(shí)例。詞法單元（Token）：

包含單元名（Token-name）和可選的屬性值(attribute-value)

單元名是表示某種詞法單位抽象符號(hào)。語法分析器通過單元名即可確定詞法單元序列的結(jié)構(gòu)。詞法單元示例詞法單元的屬性一個(gè)模式匹配多個(gè)詞素時(shí)，必須通過屬性來傳遞附加的信息。屬性值將被用于語義分析、代碼生成等階段。不同的目的需要不同的屬性。因此，屬性值通常是一個(gè)結(jié)構(gòu)化數(shù)據(jù)。詞法單元id的屬性

詞素、類型、第一次出現(xiàn)的位置、…詞法單元示例（名和屬性值）第一步：如何描述詞素？模式（Pattern）詞法單元對(duì)應(yīng)的詞素可能具有的形式可以用正則表達(dá)式來表示詞素詞法單元Specification提綱詞法分析概要正則表達(dá)式有限狀態(tài)自動(dòng)機(jī)從NFA到DFA的轉(zhuǎn)換狀態(tài)最小化算法相關(guān)概念字母表：一個(gè)有限的符號(hào)集合

二進(jìn)制{0，1}

ASCII

Unicode

典型的字母表包括字母、數(shù)位和標(biāo)點(diǎn)符號(hào)串：字母表中符號(hào)組成的一個(gè)有窮序列

串s的長(zhǎng)度

|s|

空串ε，長(zhǎng)度為0的串語言：給定字母表上一個(gè)任意的可數(shù)的串的集合

語法正確的C程序的集合，英語，漢語相關(guān)概念和串有關(guān)的術(shù)語（banana）

前綴：從串的尾部刪除0個(gè)或多個(gè)符號(hào)后得到的串（ban、banana、

ε）

后綴：從串的開始處刪除0個(gè)或多個(gè)符號(hào)后得到的串（nana、banana、ε）

子串：刪除串的某個(gè)前綴和某個(gè)后綴得到的串（banana、nan、

ε）

真前綴、真后綴、真子串：既不等于原串，也不等于空串的前綴、后綴、子串

子序列：從原串中刪除0個(gè)或者多個(gè)符號(hào)后得到的串（baan）相關(guān)概念串的運(yùn)算

連接(concatenation)：x和y的連接時(shí)把y附加到x的后面形成的串，記作xy。x=dog，y=house，xy=doghouse

指數(shù)運(yùn)算（冪運(yùn)算）：s0=ε，s1=s，si=si-1s；x=dog，x0=ε，x1=dog，x3=dogdogdog相關(guān)概念語言上的運(yùn)算語言：串的集合

i

1LiL

語言的一些實(shí)例L=

{A,B,……,Z,a,b,……,z}D=

{0,1,……,9}LUD:

{A,B,……,Z,a,b,……,z,0,1,……,9}LD

：520個(gè)長(zhǎng)度為2的串的集合L4

：所有由四個(gè)字母構(gòu)成的串的集合L*

：所有字母構(gòu)成的集合，包括ε。L(LUD)*

:D+:正則表達(dá)式正則表達(dá)式

一種描述詞素模式的重要表示方法正則表達(dá)式可以高效、簡(jiǎn)潔地描述處理詞法單元時(shí)用到的模式類型可以描述所有通過對(duì)某個(gè)字母表上的符號(hào)應(yīng)用運(yùn)算符而得到的語言。其定義的集合叫做正則集合(regular

set)每個(gè)正則表達(dá)式r可以描述一個(gè)語言L(r)，也即其定義的正則集合例如，C語言標(biāo)識(shí)符的語言，可以用如下正則表達(dá)式來表示：letter_(letter_|digit)*重要正則表達(dá)式正則表達(dá)式可以由較小的正則表達(dá)式遞歸構(gòu)建（字母表Σ上的正則表達(dá)式的定義）

基本部分ε

是一個(gè)正則表達(dá)式，L(ε)={ε}如果a是Σ上的一個(gè)符號(hào)，那么a是正則表達(dá)式，L(a)={a}

歸納步驟：選擇：(r)

|(s)，L((r)

|(s))=L(r)

UL(s)；連接：(r)(s)，L((r)(s))=L(r)L(s)

；閉包：(r)*，L((r)*)=(L(r))*；括號(hào)：(r)，L((r))=L(r)運(yùn)算的優(yōu)先級(jí)：* > 連接符

> |(a)|((b)*(c))可以改寫為

a|b*c正則表達(dá)式實(shí)例Σ={a,b}L(a|b)=

{a,b}L((a|b)(a|b))=

{aa,ab,ba,bb}L(a*)=

{ε,a,aa,aaa,aaaa,……}L((a|b)*)={ε,a,b,aa,ab,ba,bb,

aaa,aab,……}L(a|a*b)=

{a,b,ab,aab,aaab,…}P76,

練習(xí)3.2.2

((ε|a)b*)*正則表達(dá)式的性質(zhì)等價(jià)性

如果兩個(gè)正則表達(dá)式r和s表示同樣的語言，則r=s■ 代數(shù)定律正則定義對(duì)正則表達(dá)式命名，使表示簡(jiǎn)潔d1

r1d2

r2..

.dn

rn各個(gè)di不在字母表

中，且名字都不同每個(gè)ri都是

{d1,

d2,

…,

di-1

}上的正則表達(dá)式正則定義各個(gè)di在Σ上的正則表達(dá)式如下：

d1的正則表達(dá)式即r1

將r2中的d1替換為r1，得到d2的正則表達(dá)式

………

…

將ri中的d1,d2,…,di-1替換為各自的正則表達(dá)式，得到di的正則表達(dá)式注意：替換的時(shí)候不能破壞替換進(jìn)去的di的完整性正則定義實(shí)例C語言的標(biāo)識(shí)符集合letter

A|B|…|Z|a|b|…|z|

_digit

0|1|…|

9id

letter(letter|digit)*正則定義實(shí)例Pascal無符號(hào)數(shù)集合，例如：1946,

11.28,63.6E8,

1.99E

6digit

0|1|…|

9digits

digit digit*optional_fraction

.digits|

optional_exponent

(E(+|

|

)digits)|

num

digits

optional_fraction

optional_exponent正則表達(dá)式的擴(kuò)展基本運(yùn)算符：并

連接

閉包擴(kuò)展運(yùn)算符

一個(gè)或多個(gè)：r+

,

等價(jià)于rr*

零個(gè)或一個(gè)：

r?，等價(jià)于ε

|r

字符類

[abc]等價(jià)于a|b|c,

[a-z]等價(jià)于a|b|…|z前面兩個(gè)例子的簡(jiǎn)化表示練習(xí)字母表{a,b}上以aa結(jié)尾的所有字符串。能被4整除的所有二進(jìn)制數(shù)。附注正則表達(dá)式是一種描述手段，通常用來描述程序語言的詞法符號(hào)。很多編輯器支持正則表達(dá)式工具GREP有關(guān)實(shí)驗(yàn)如何定義你的語言？正則表達(dá)式可以由較小的正則表達(dá)式遞歸構(gòu)建第二步：如何識(shí)別詞法單元？詞素詞法單元狀態(tài)轉(zhuǎn)換圖、有限自動(dòng)機(jī)識(shí)別一個(gè)串是否屬于某個(gè)正則集Implementation提綱詞法分析概要正則表達(dá)式有限狀態(tài)自動(dòng)機(jī)從NFA到DFA的轉(zhuǎn)換狀態(tài)最小化算法詞法單元的識(shí)別詞法分析器要求能夠檢查輸入字符串，在前綴中找出和某個(gè)模式匹配的詞素

首先通過正則定義來描述各種詞法單元的模式

定義ws→(blank

|

tab|

newline)+來消除空白詞法分析器識(shí)別到這個(gè)模式時(shí)，不返回詞法單元，繼續(xù)識(shí)別其它模式狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖是詞法分析器的重要組件之一可以將正則表達(dá)式轉(zhuǎn)換成狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖(transition

diagram)

狀態(tài)(state)：表示在識(shí)別詞素的過程中可能出現(xiàn)的情況狀態(tài)看作是已處理部分的總結(jié)某些狀態(tài)為接受狀態(tài)或最終狀態(tài)，表明已經(jīng)找到詞素加上*的接受狀態(tài)表示最后讀入的符號(hào)不在詞素中開始狀態(tài)（初始狀態(tài)）：用start邊表示

邊(edge)：從一個(gè)狀態(tài)指向另一個(gè)狀態(tài)；邊的標(biāo)號(hào)是一個(gè)或者多個(gè)符號(hào)如果當(dāng)前符號(hào)為s，下一個(gè)輸入符號(hào)為a，就沿著從s離開，標(biāo)號(hào)為a的邊到達(dá)下一個(gè)狀態(tài)狀態(tài)轉(zhuǎn)換圖的例子保留字和標(biāo)識(shí)符的識(shí)別在很多程序設(shè)計(jì)語言中，保留字也符合標(biāo)識(shí)符的模式，識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖也會(huì)識(shí)別保留字解決方法

在符號(hào)表中預(yù)先填寫保留字，并指明它們不是普通標(biāo)識(shí)符

為關(guān)鍵字/保留字建立單獨(dú)的狀態(tài)轉(zhuǎn)換圖。并設(shè)定保留字的優(yōu)先級(jí)高于標(biāo)識(shí)符其它的狀態(tài)轉(zhuǎn)換圖其它的狀態(tài)轉(zhuǎn)換圖Finite-state

machinesFinite-state

machines

can

model

alargeamong

whicharenumber

ofelectronicproblems,designautomation,communicationprotocoldesign,parsingand other engineeringapplications.

Inbiology and artificial intelligence research,state machines or hierarchiesof statemachinesaresometimesusedtodescribeneurologicalsystems,andin

linguisticstheycanbeusedtodescribethegrammarsofnatural

languages.有窮自動(dòng)機(jī)本質(zhì)上等價(jià)于狀態(tài)轉(zhuǎn)換圖區(qū)別在于：

自動(dòng)機(jī)是識(shí)別器，對(duì)每個(gè)輸入串回答yes

or

no分為兩類

不確定的有窮自動(dòng)機(jī)（Nondeterministic

FiniteAutomaton，NFA）

確定的有窮狀態(tài)自動(dòng)機(jī)（Deterministic

FiniteAutomaton，DFA）重要不確定

vs.

確定不同：

NFA:

一個(gè)符號(hào)標(biāo)記離開同一狀態(tài)的多條邊

DFA:

對(duì)于每個(gè)狀態(tài)和字母表中的每個(gè)字符，有且僅有一條離開該狀態(tài)、以該符合為標(biāo)號(hào)的邊

NFA:

可以有邊的標(biāo)號(hào)是ε

DFA:

沒有標(biāo)記為ε的邊相同：都可以識(shí)別正則語言，兩者之間存在等價(jià)性不確定的有窮自動(dòng)機(jī)

(NFA)NFA由以下幾部分組成

一個(gè)有窮的狀態(tài)集合S

一個(gè)輸入符號(hào)集合Σ（input

alphabet）

轉(zhuǎn)換函數(shù)（transition

function）對(duì)于每個(gè)狀態(tài)和Σ

∪

{ε}中的符號(hào)，給出相應(yīng)的后繼狀態(tài)集合

一個(gè)狀態(tài)S0被指定為開始狀態(tài)/初始狀態(tài)

S的一個(gè)子集F被指定為接受狀態(tài)NFA的例子狀態(tài)集合S={0,1,2,3}開始狀態(tài)0接受狀態(tài)集合{3}轉(zhuǎn)換函數(shù)：

(0,a)→{0,1} (0,b)→{0}(1,b)→2(2,b)→3轉(zhuǎn)換表NFA可以表示為一個(gè)轉(zhuǎn)換表

表的各行對(duì)應(yīng)于狀態(tài)

各列對(duì)應(yīng)于輸入符號(hào)和ε

表中的元素表示給定狀態(tài)在給定輸入下的后繼狀態(tài)自動(dòng)機(jī)對(duì)輸入字符串的接受一個(gè)NFA接受輸入字符串x，當(dāng)且僅當(dāng)對(duì)應(yīng)的轉(zhuǎn)換圖中存在一條從開始狀態(tài)到某個(gè)接受狀態(tài)的路徑，使得該路徑中各條邊上的標(biāo)號(hào)組成符號(hào)串x（路徑中可能包含ε

邊）下圖對(duì)應(yīng)的NFA能夠接受aabb注意：只要存在從開始狀態(tài)到接受狀態(tài)的路徑，符號(hào)串就認(rèn)為被NFA接受自動(dòng)機(jī)與語言由一個(gè)NFA

A定義（接受）的語言是從開始狀態(tài)到某個(gè)接受狀態(tài)的所有路徑上的符號(hào)串集合，稱為L(zhǎng)(A)相應(yīng)的語言：L(aa*|bb*)確定有窮自動(dòng)機(jī)

(DFA)一個(gè)NFA被稱為DFA，如果

沒有ε之上的轉(zhuǎn)換動(dòng)作

對(duì)于每個(gè)狀態(tài)s和每個(gè)輸入符號(hào)a，有且只有一條標(biāo)號(hào)為a的邊可以高效判斷一個(gè)串能否被一個(gè)DFA接受每個(gè)NFA都有一個(gè)等價(jià)的DFA，即它們接受同樣的語言DFA的模擬假設(shè)輸入符號(hào)就是字符串中的符號(hào)；Nextchar讀入下一個(gè)字符（符號(hào)）move給出了離開s，標(biāo)號(hào)為c的邊的目標(biāo)狀態(tài)如何模擬NFADFA的例子假設(shè)輸入為ababb，那么進(jìn)入的狀態(tài)序列為 0,1,2,1,2,3，返回yes我們已有的工具：1.RE2.DFA3.NFA詞素詞法單元正則表達(dá)式到自動(dòng)機(jī)正則表達(dá)式可以簡(jiǎn)潔、精確地描述詞法單元的模式進(jìn)行模式匹配時(shí)，模擬DFA的執(zhí)行比模擬NFA更為簡(jiǎn)單有效

ε的模擬，難

不確定性的模擬，難因此，需要將正則表達(dá)式轉(zhuǎn)換為DFA步驟：

正則表達(dá)式到NFA

NFA到DFA提綱詞法分析概要正則表達(dá)式有限狀態(tài)自動(dòng)機(jī)從NFA到DFA的轉(zhuǎn)換狀態(tài)最小化算法NFA轉(zhuǎn)換成DFA

-

子集構(gòu)造法對(duì)NFA的模擬往往不如對(duì)DFA的模擬直接，除非轉(zhuǎn)換花費(fèi)更多的時(shí)間基本思想：

DFA每個(gè)狀態(tài)

→

NFA一個(gè)狀態(tài)集

“并行地模擬”

NFA在遇到一個(gè)給定輸入串時(shí)可能執(zhí)行的所有動(dòng)作

構(gòu)造得到的DFA的每個(gè)狀態(tài)和NFA的狀態(tài)子集對(duì)應(yīng)

DFA讀入a1,a2,…,an后到達(dá)的狀態(tài)對(duì)應(yīng)于從NFA開始狀態(tài)出發(fā)沿著a1,a2,…,an可能到達(dá)的狀態(tài)集合理論上，最壞情況下DFA的狀態(tài)個(gè)數(shù)會(huì)是NFA狀態(tài)個(gè)數(shù)的指數(shù)多個(gè)。但是對(duì)于大部分應(yīng)用，NFA和相應(yīng)的DFA的狀態(tài)數(shù)量大致相同NFA轉(zhuǎn)換成DFA

-

子集構(gòu)造法輸入：一個(gè)NFA

N輸出：一個(gè)接受相同語言的DFA

Ds表示N中的單個(gè)狀態(tài)，T代表N的一個(gè)狀態(tài)集NFA轉(zhuǎn)換成DFA

-

子集構(gòu)造法D的開始狀態(tài)是ε-closure(s0)，D的接受狀態(tài)是所有至少包含了N的一個(gè)接受狀態(tài)的狀態(tài)集合。NFA轉(zhuǎn)換成DFA

-

子集構(gòu)造法對(duì)NFA的任何狀態(tài)集合ε-closure(T)的計(jì)算一個(gè)圖搜索過程N(yùn)FA到DFA轉(zhuǎn)換的示例A：=ε-closure(0)={0,1,2,4,7}B：Dtran[A,a]=ε-closure(move(A,a))=ε-

closure({3,8})={1,2,3,4,6,7,8}C：Dtran[A,b]=ε-closure(move(A,b))=ε

-closure({5})={1,2,4,5,6,7}D：Dtran[B,b]=ε-closure(move(B,b))=

{1,2,4,5,6,7,9}……E: Dtran[D,b]=ε-closure(move(B,b))=

{1,2,4,5,6,7,10}NFA到DFA轉(zhuǎn)換的示例開始狀態(tài)：A接受狀態(tài)：E對(duì)NFA的運(yùn)行進(jìn)行模擬:子集構(gòu)造法輸入：一個(gè)以文件結(jié)束符eof結(jié)尾的輸入串x，一個(gè)NFA

N，其開始狀態(tài)是S0，接受狀態(tài)集為F，轉(zhuǎn)換函數(shù)為move輸出：如果N接受x，返回yes，否則返回no正則表達(dá)式到NFA輸入：字母表Σ上的一個(gè)正則表達(dá)式r輸出：一個(gè)接受L(r)的NFA

N基本思想

根據(jù)正則表達(dá)式的遞歸定義，按照正則表達(dá)式的結(jié)構(gòu)遞歸地構(gòu)造出相應(yīng)的NFA

算法分成兩個(gè)部分：基本規(guī)則處理ε和單符號(hào)的情況對(duì)于每個(gè)正則表達(dá)式的運(yùn)算，建立構(gòu)造相應(yīng)NFA的方法轉(zhuǎn)換算法(1)基本規(guī)則：

表達(dá)式ε，

表達(dá)式a，轉(zhuǎn)換算法(2)歸納規(guī)則

正則表達(dá)式s和t的NFA分別是

N(s)和N(t)

r=s|r，

r的NFA

N(r)轉(zhuǎn)換算法(2)歸納規(guī)則

正則表達(dá)式r=st，

N(r)轉(zhuǎn)換算法(3)歸納規(guī)則

正則表達(dá)式

r=s*,

N(r)

r=(s),

N(r)=N(s)正則表達(dá)式到NFA的例子（1）正則表達(dá)式(a|b)*abb第一個(gè)a對(duì)應(yīng)的NFA第一個(gè)b對(duì)應(yīng)的NFA正則表達(dá)式到NFA的例子（2）(a|b)的NFA第二個(gè)a的NFA正則表達(dá)式到NFA的例子（3）(a|b)*的NFA練習(xí)字母表{x,y}上以x開頭和結(jié)尾的任意串。用正則表達(dá)式表示字母表{a,

b}上由a、b組成，且不連續(xù)出現(xiàn)兩個(gè)a的所有句子的集合，并給出接受該語言的DFA。提綱詞法分析概要正則表達(dá)式有限狀態(tài)自動(dòng)機(jī)從NFA到DFA的轉(zhuǎn)換狀態(tài)最小化算法基于DFA的模式匹配器的優(yōu)化DFA化簡(jiǎn)：狀態(tài)數(shù)最小化等價(jià)的DFA可能具有不同的狀態(tài)個(gè)數(shù)任何正則語言都有一個(gè)唯一的（不計(jì)同構(gòu)）狀態(tài)數(shù)目最少的DFADFA狀態(tài)最小化原理：將一個(gè)DFA的狀態(tài)集合分劃成多個(gè)組，每個(gè)組中的各狀態(tài)之間相互不可區(qū)分，然后將每個(gè)組中的狀態(tài)合并成狀態(tài)最少DFA的一個(gè)狀態(tài)可區(qū)分的定義：

如果分別從狀態(tài)s和狀態(tài)t出發(fā)，沿著標(biāo)號(hào)為x的路徑到達(dá)的兩個(gè)狀態(tài)只有一個(gè)是接受狀態(tài)，稱為x區(qū)分狀態(tài)s和t

如果存在能夠區(qū)分s和t的串，那么它們就是可區(qū)分的空串區(qū)分了E和其它狀態(tài)bb區(qū)分了A和BA和C是可區(qū)分的嗎？最小化算法（分劃部分）設(shè)置初始分劃П={S-F,F}迭代，不斷分劃：for(П中的每個(gè)元素G){細(xì)分G，使得G中的s、t仍然在同一組中

iff對(duì)任意a，s,t都到達(dá)П中的同一組；Пnew=將П中的G替換為細(xì)分得到的小組；}如果Пnew==П，令Пfinal==П，轉(zhuǎn)步驟4；否則П==Пnew，轉(zhuǎn)步驟2；最小化算法（構(gòu)造部分）在Пfinal的每個(gè)組中選擇一個(gè)狀態(tài)作代表，作為最小DFA的狀態(tài)

開始狀態(tài)就是中包含原開始狀態(tài)的組的代表

接受狀態(tài)就是包含了原接受狀態(tài)的組的代表

轉(zhuǎn)化關(guān)系構(gòu)造如下：如果s是中G的代表，而s在a上的轉(zhuǎn)換到達(dá)t，而t所在組的代表為r，那么最小DFA中有從s到r的、在a上的轉(zhuǎn)換DFA最小化的正確性證明位于Пfinal的同一組中的狀態(tài)不可能被任意串區(qū)分Пfinal的不同組的狀態(tài)之間是可區(qū)分的DFA最小化的例子初始分劃：{A,B,C,D} {E}處理{A,B,C,D}，b把它細(xì)分為{A,B,C}

{D}處理{A,B,C}，b把它細(xì)分為{A,C}{B}分劃完畢。選取A,B,D和E作為代表，構(gòu)造得到最小DFA第二章

詞法分析與語法分析（二）提綱語法分析概要上下文無關(guān)文法自頂向下的語法分析算法自底向上的語法分析算法詞法分析和語法分析的實(shí)踐技術(shù)描述分析引言程序設(shè)計(jì)語言源程序的構(gòu)成：語法結(jié)構(gòu)一個(gè)實(shí)例語法分析

position=initial+rate*

60<id,1>

<=,

>

<id,

2>

<+,

><id,3>

<*,

>

<number,

4>引言文法：一種用于描述程序設(shè)計(jì)語言語法的表示方法，能夠自然地描述程序設(shè)計(jì)語言構(gòu)造的層次化語法結(jié)構(gòu)

文法給出了一個(gè)程序設(shè)計(jì)語言的精確易懂的語法規(guī)約

可以基于文法構(gòu)造語法分析器，幫助確定源程序的語法結(jié)構(gòu)

語法結(jié)構(gòu)有助于把源程序翻譯為正確的目標(biāo)代碼

文法的擴(kuò)展性，有助于迭代的語言演化語法分析器輸入：詞法分析器輸出的詞法單元序列輸出：語法樹表示語法分析器功能：

驗(yàn)證輸入源程序的合法性，輸出良構(gòu)程序的語法結(jié)構(gòu)

對(duì)于病構(gòu)的程序，能夠報(bào)告語法錯(cuò)誤，進(jìn)行錯(cuò)誤恢復(fù)語法分析器的類型：

通用型

自頂向下：通常處理LL文法

自底向上：通常處理LR文法從左到右掃描字符類型檢查，語義分析，翻譯生成中間代碼等往往和語法分析過程交錯(cuò)完成，實(shí)踐中往往和語法分析放入一個(gè)模塊，圖上用“前端的其余部分”表示上述活動(dòng)語法分析器語法錯(cuò)誤的處理錯(cuò)誤難以避免編譯器需要具有處理錯(cuò)誤的能力程序中可能存在不同層次的錯(cuò)誤

詞法錯(cuò)誤

語法錯(cuò)誤

語義錯(cuò)誤

邏輯錯(cuò)誤語法錯(cuò)誤相對(duì)容易發(fā)現(xiàn)，語義和邏輯錯(cuò)誤較難精確的檢測(cè)到語法分析器中錯(cuò)誤處理程序的設(shè)計(jì)目標(biāo)

清晰準(zhǔn)確地報(bào)告出現(xiàn)錯(cuò)誤，并指出錯(cuò)誤的位置

能從當(dāng)前錯(cuò)誤中恢復(fù)，以繼續(xù)檢測(cè)后面的錯(cuò)誤

盡可能減少處理正確程序的開銷預(yù)測(cè)分析中的錯(cuò)誤恢復(fù)錯(cuò)誤恢復(fù)

當(dāng)預(yù)測(cè)分析器報(bào)錯(cuò)時(shí)，表示輸入的串不是句子

對(duì)于使用者而言，希望預(yù)測(cè)分析器能夠進(jìn)行恢復(fù)處理后繼續(xù)語法分析過程，以便在一次分析中找到更多的語法錯(cuò)誤

但是有可能恢復(fù)得并不成功，之后找到的語法錯(cuò)誤有可能是假的

進(jìn)行錯(cuò)誤恢復(fù)時(shí)可用的信息：棧里面的符號(hào)，待分析的符號(hào)兩類錯(cuò)誤恢復(fù)方法

恐慌模式

短語層次的恢復(fù)恐慌模式基本思想

語法分析器忽略輸入中的一些符號(hào)，直到出現(xiàn)由設(shè)計(jì)者選定的某個(gè)同步詞法單元

解釋語法分析過程總是試圖在輸入的前綴中找到和某個(gè)非終結(jié)符號(hào)對(duì)應(yīng)的串；出現(xiàn)錯(cuò)誤表明現(xiàn)在已經(jīng)不可能找到這個(gè)非終結(jié)符號(hào)（程序結(jié)構(gòu)）的串如果編程錯(cuò)誤僅僅局限于這個(gè)程序結(jié)構(gòu)，那么我們可以考慮跳過這個(gè)程序結(jié)構(gòu)，假裝已經(jīng)找到了這個(gè)結(jié)構(gòu)；然后繼續(xù)進(jìn)行語法分析處理

同步詞法單元就是這個(gè)程序結(jié)構(gòu)結(jié)束的標(biāo)志短語層次的恢復(fù)在預(yù)測(cè)語法分析表的空白條目中插入錯(cuò)誤處理例程的函數(shù)指針例程可以改變、插入或刪除輸入中的符號(hào)；發(fā)出適當(dāng)?shù)腻e(cuò)誤消息代表性文法LR文法類自底向上分析LL類文法（無左遞歸）自頂向下分析提綱語法分析概要上下文無關(guān)文法自頂向下的語法分析算法自底向上的語法分析算法詞法分析和語法分析的實(shí)踐技術(shù)上下文無關(guān)文法上下文無關(guān)文法

（Context

Free

Grammar,CFG）上下文無關(guān)文法是一種能夠很好描述程序設(shè)計(jì)語言的表示方法stmt→if(expr)stmtelse

stmtexpr→

……stmt→

……上下文無關(guān)文法的定義一個(gè)CFG由以下幾個(gè)部分構(gòu)成

終結(jié)符號(hào)組成串的基本符號(hào)，與“詞法單元名字”同義

非終結(jié)符號(hào)語法變量，表示特定串的集合給出了語言的層次結(jié)構(gòu)，這種層次結(jié)構(gòu)是語法分析和翻譯的關(guān)鍵

一個(gè)開始符號(hào)某個(gè)特定的非終結(jié)符號(hào)，其表示的串集合是這個(gè)文法生成的語言

一組產(chǎn)生式描述將終結(jié)符號(hào)和非終結(jié)符號(hào)組合成串的方法產(chǎn)生式左部（頭）是一個(gè)非終結(jié)符號(hào)符號(hào)

“→”一個(gè)由零個(gè)或多個(gè)終結(jié)符號(hào)與非終結(jié)符號(hào)組成的產(chǎn)生式右部（體）上下文有關(guān)文法與上下文無關(guān)文法什么是上下文？

在應(yīng)用一個(gè)產(chǎn)生式進(jìn)行推導(dǎo)時(shí)，前后已經(jīng)推導(dǎo)出的部分結(jié)果就是上下文；

上下文無關(guān)的意思的，只要文法的定義里有某個(gè)產(chǎn)生式，不管一個(gè)非終結(jié)符前后的串是什么，就可以應(yīng)用相應(yīng)的產(chǎn)生式進(jìn)行推導(dǎo)文法的分類：

上下文有關(guān)文法

上下文無關(guān)文法上下文有關(guān)文法與上下文無關(guān)文法一個(gè)簡(jiǎn)單的上下文無關(guān)文法例子

Sent->SV

O

S->人

|天

V->吃

|下

O

->雨

|

雪

|

飯

|

肉其中英文字母都是非終結(jié)符（SVO

分別表示主謂賓），漢字都是終結(jié)符。上下文有關(guān)文法與上下文無關(guān)文法一個(gè)簡(jiǎn)單的上下文無關(guān)文法例子

Sent->SV

O

S->人

|天

V->吃

|下

O

->雨

|

雪

|

飯

|

肉這個(gè)文法可以生成多少個(gè)句子？上下文有關(guān)文法與上下文無關(guān)文法一個(gè)簡(jiǎn)單的上下文無關(guān)文法例子

Sent->SV

O

S->人

|天

V->吃

|下

O

->雨

|

雪

|

飯

|

肉“天吃肉”。其（最左）推導(dǎo)過程為：Sent

->

SVO

->

天VO

->

天吃O(shè)

->

天吃肉上下文有關(guān)文法與上下文無關(guān)文法一個(gè)簡(jiǎn)單的上下文有關(guān)文法例子

Sent->SV

O

S->人

|天

人V

->

人吃

天V

->

天下

下O

->

下雨

|

下雪

吃O(shè)

->

吃飯

|

吃肉其中英文字母都是非終結(jié)符（SVO

分別表示主謂賓），漢字都是終結(jié)符。上下文有關(guān)文法與上下文無關(guān)文法一個(gè)簡(jiǎn)單的上下文有關(guān)文法例子

Sent->SV

O

S->人

|天

人V

->

人吃

天V

->

天下

下O

->

下雨

|

下雪

吃O(shè)

->

吃飯

|

吃肉這個(gè)文法可以生成多少個(gè)句子？上下文有關(guān)文法與上下文無關(guān)文法一個(gè)簡(jiǎn)單的上下文有關(guān)文法例子

Sent->SV

O

S->人

|天

人V

->

人吃

天V

->

天下

下O

->

下雨

|

下雪

吃O(shè)

->

吃飯

|

吃肉Sent

->

SVO

->人VO

->人吃O(shè)

->

人吃飯其中第三步推導(dǎo)是這樣的：非終結(jié)符

V

的上文是“人”，因此可以應(yīng)用“人V

->

人吃”這條產(chǎn)生式，得到“人VO

->

人吃O(shè)”。第四步也類似。用于描述算術(shù)表達(dá)式的文法定義符號(hào)表示約定終結(jié)符號(hào)：a

b

+

3

id…非終結(jié)符號(hào):

A

B

C…,

S,

stmt文法符號(hào):

X

Y

…終結(jié)符號(hào)串:u

vw…文法符號(hào)串:α

β…不同可選體:

α1

α2

α3…開始符號(hào):

S推導(dǎo)產(chǎn)生式又可稱為重寫規(guī)則（Rewriting

rule）推導(dǎo)

將待處理的串中的某個(gè)非終結(jié)符號(hào)替換為這個(gè)非終結(jié)符號(hào)的某個(gè)產(chǎn)生式的體

從開始符號(hào)出發(fā)，不斷進(jìn)行上面的替換，就可以得到文法的不同句型推導(dǎo)的實(shí)例

文法:E→ -E|E+E|E*E|(E)| id

從E到-(id)的推導(dǎo)序列：E

=>-E

=>

-(E)

=>-(id)：推導(dǎo)推導(dǎo)的一般性定義

如果A→γ是一個(gè)產(chǎn)生式，那么αAβ

αγβ經(jīng)過零步或者多步推導(dǎo)出：

對(duì)于任何串α,

α α

如果α β且β

γ，那么α γ經(jīng)過一步或者多步推導(dǎo)出

α β且α不等于β等價(jià)于α β最左(右)推導(dǎo)符號(hào)：文法實(shí)例E→E+E|E*E|-E|(E)|

id從上述文法推導(dǎo)出串

–(id+id)推導(dǎo)的例子句型/句子/語言句型（sentential

form）：

如果S α，那么α就是文法的一個(gè)句型

可能既包含非終結(jié)符，又包含終結(jié)符號(hào)；可以是空串句子（sentence）

文法的句子就是不包含非終結(jié)符號(hào)的句型語言

文法G的語言就是G的句子的集合，記為L(zhǎng)(G)

ω在L(G)中當(dāng)且僅當(dāng)ω是G的句子，即S ω推導(dǎo)的問題從推導(dǎo)的角度看，語法分析的任務(wù)是：接受一個(gè)終結(jié)符號(hào)串作為輸入，找出從文法的開始符號(hào)推導(dǎo)出這個(gè)串的方法E→E+E|E*E|-E|(E)|

id推導(dǎo)出串

–(id+id*id)推導(dǎo)的問題推導(dǎo)中可能遇到的兩個(gè)問題

每一步替換哪個(gè)非終結(jié)符號(hào)？

若以這個(gè)非終結(jié)符號(hào)為頭的產(chǎn)生式有多個(gè)，用哪個(gè)產(chǎn)生式的右部替換？E→E+E|E*E|-E|(E)|

id推導(dǎo)出串

–(id+id*id)，

,通常使用兩種方式進(jìn)行推導(dǎo)

最左推導(dǎo)：總是選擇每個(gè)句型的最左非終結(jié)符號(hào)。記作

最右推導(dǎo)：總是選擇最右邊的非終結(jié)符號(hào)。記作每個(gè)最左推導(dǎo)步驟可以寫成應(yīng)用產(chǎn)生式:如果

經(jīng)過最左推導(dǎo)得到

，記作，則

是最左句型：S是文法G的識(shí)別符號(hào)，如果G的最左句型非終結(jié)符號(hào)的替換順序語法分析樹推導(dǎo)的圖形表示形式

根結(jié)點(diǎn)的標(biāo)號(hào)是文法的開始符號(hào)

每個(gè)葉子結(jié)點(diǎn)的標(biāo)號(hào)是非終結(jié)符號(hào)、終結(jié)符號(hào)或ε

每個(gè)內(nèi)部節(jié)點(diǎn)的標(biāo)號(hào)是非終結(jié)符號(hào)

每個(gè)內(nèi)部結(jié)點(diǎn)表示某個(gè)產(chǎn)生式的一次應(yīng)用內(nèi)部結(jié)點(diǎn)的標(biāo)號(hào)為產(chǎn)生式頭，結(jié)點(diǎn)的子結(jié)點(diǎn)從左到右是產(chǎn)生式的體有時(shí)允許樹的根不是開始符號(hào)（對(duì)應(yīng)于某個(gè)短語）樹的葉子組成的序列是根的文法符號(hào)的句型一棵分析樹可對(duì)應(yīng)多個(gè)推導(dǎo)序列，但是分析樹和最左（右）推導(dǎo)序列之間具有一一對(duì)應(yīng)關(guān)系語法分析樹推導(dǎo)的圖形表示形式，樹上看不出來推導(dǎo)的順序能夠反映串的語法層次結(jié)構(gòu)語法分析樹

內(nèi)部節(jié)點(diǎn)：對(duì)應(yīng)于一個(gè)非終結(jié)符號(hào)

子節(jié)點(diǎn)：對(duì)應(yīng)于其父節(jié)點(diǎn)為頭的產(chǎn)生式體

葉子節(jié)點(diǎn)：可以是終結(jié)符號(hào)或非終結(jié)符號(hào)，從左到右排列可以得到一個(gè)句型，稱為這棵樹的結(jié)果推導(dǎo)和語法樹對(duì)于推導(dǎo)中的每個(gè)句型

i

，我們都可以構(gòu)造出一個(gè)結(jié)果為

i

的語法樹

構(gòu)造過程是對(duì)i的一次歸納過程

假設(shè)已經(jīng)構(gòu)造出

在推導(dǎo)的第i步，對(duì)

i

應(yīng)用規(guī)則從推導(dǎo)序列構(gòu)造分析樹假設(shè)有推導(dǎo)序列：

A

=>

α1=>α2 =>…=>

αn算法：

初始化：α1的分析樹是標(biāo)號(hào)為A的單個(gè)結(jié)點(diǎn)

假設(shè)已經(jīng)構(gòu)造出αi-1=X1X2…Xk的分析樹，且αi-1到αi的推導(dǎo)是將Xj替換為β，那么在當(dāng)前分析樹中找出第j個(gè)非ε結(jié)點(diǎn)，向這個(gè)結(jié)點(diǎn)增加構(gòu)成β的子結(jié)點(diǎn)。（如果β=ε，則增加一個(gè)標(biāo)號(hào)為ε的子結(jié)點(diǎn)）推導(dǎo)與語法樹的例子二義性文法如果一個(gè)文法可以為一個(gè)句子生成多棵不同的語法分析樹，則該文法為二義性文法通常情況下，我們需要無二義性的文法二義性程序設(shè)計(jì)語言的文法通常都應(yīng)該是無二義性的

否則就會(huì)導(dǎo)致一個(gè)程序有多種“正確”的解釋。

比如文法：E→ -E

|

E+E

|

E*E

|

(E)

|

id

的句子 a+b*c但有些二義性的情況可以方便文法或語法分析器的設(shè)計(jì)

需要消二義性規(guī)則來剔除不要的語法分析樹

比如：先乘除后加減文法的二義性例子：stmt

→if expr thenstmt|if expr thenstmt else stmt|otherif E1 then if E2 then

S1 else S2 的兩棵語法樹這個(gè)文法是可以被改造成等價(jià)的無二義性的文法文法及其生成的語言語言是由文法的開始符號(hào)出發(fā)，能夠推導(dǎo)得到的所有句子的集合文法G: S

→

aS|a|b, L(G)={ai(a|b),

i>=0}文法G：S

→

aSb|abL(G)={anbn,

n>=1}文法G：S

→(S)S|εL(G)={所有具有對(duì)稱括號(hào)對(duì)的串}驗(yàn)證文法生成的語言驗(yàn)證文法G生成語言L可以幫助我們了解文法可以生成什么樣的語言基本步驟：

首先證明L(G)

L：G生成的每個(gè)串都在L中

然后證明L

L(G)：L的每個(gè)串都能由G生成

一般使用數(shù)學(xué)歸納法證明L(G)

L：按照推導(dǎo)序列長(zhǎng)度進(jìn)行數(shù)學(xué)歸納證明L

L(G)：按照符號(hào)串的長(zhǎng)度來構(gòu)造推導(dǎo)序列實(shí)例：文法G：S

→

(S)S|ε,L(G)={所有具有對(duì)稱括號(hào)對(duì)的串}文法的設(shè)計(jì)程序設(shè)計(jì)語言所需要的文法

上下文無關(guān)文法足夠用來描述語法嗎？標(biāo)識(shí)符必須先聲明后使用

語法分析器能夠完全按照上下文無關(guān)文法來構(gòu)造嗎？二義性、左遞歸的文法可能給語法分析器造成很大麻煩可以怎么做？

改造語法分析器，添加語義規(guī)則，使它可以做得更多

改造上下文無關(guān)文法，消除二義性和左遞歸在進(jìn)行高效的語法分析之前，需要對(duì)文法做以下處理

消除二義性文法的二義性：文法可以為一個(gè)句子生成多顆不同的樹

消除左遞歸左遞歸：文法中一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串α，存在一個(gè)推導(dǎo) ，則稱這個(gè)文法是左遞歸的

提取左公因子文法的設(shè)計(jì)很重要消除文法的二義性一些二義性文法可以被改成等價(jià)的無二義性的文法例子：stmt

→if expr then stmt| if expr then

stmt

else stmt| otherif E1 then if E2 then S1 else S2 的兩棵語法樹消除文法的二義性（續(xù)）改寫文法，基本思想:

在一個(gè)then和一個(gè)else之間出現(xiàn)的語句必須是“已匹配的”。也就是說then和else中間的語句不能以一個(gè)尚未匹配的then結(jié)尾解決方案：引入新的非終結(jié)符號(hào)matched_stmt，用來區(qū)分是否是成對(duì)的then/else消除文法的二義性（續(xù)）二義性的消除方法沒有規(guī)律可循通常并不是通過改變文法來消除二義性消除左遞歸左遞歸的定義

文法中一個(gè)非終結(jié)符號(hào)A使得對(duì)某個(gè)串α，存在一個(gè)推導(dǎo) ，則稱這個(gè)文法是左遞歸的立即左遞歸

如果存在A→

Aα,則稱為立即左遞歸為什么要消除左遞歸？

自頂向下的語法分析技術(shù)不能處理左遞歸的文法立即左遞歸的消除實(shí)例：A→Aα|

βA

→ β

A’A’→αA’|

ε立即左遞歸的消除：假設(shè)非終結(jié)符號(hào)A存在立即左遞歸的情形，假設(shè)以A為左部的規(guī)則有首先對(duì)A產(chǎn)生式分組(所有αi不等于ε，βi不以A開頭)可以替換為由A生成的串總是以某個(gè)βi開頭，然后跟上零個(gè)或者多個(gè)αi的重復(fù)消除立即左遞歸| β1

| β2

| …

| βnA→

Aα1

| Aα2|…|

Aαm分組A

→|Aα1

| Aα2|…|

Aαmβ1

| β2| …| βn替換A

→ β1

A’

| β2

A’

| …

| βn

A’A’

→ α1

A’

| α2A’|…|

αm

A’ |

ε立即左遞歸消除示例消除多步左遞歸消除立即左遞歸的方法并不能消除因?yàn)閮刹交蚨嗖酵茖?dǎo)而產(chǎn)生的左遞歸文法：S

→Aa

|

b, A→Ac|Sd

|ε?S=> Aa=>

Sda如何消除？消除算法輸入：沒有環(huán)Ai Ai和

A→ε輸出：一個(gè)等價(jià)的無左遞歸的文法算法原理：

給非終結(jié)符號(hào)排序，A1, A2, …, An

如果只有Ai

Aj

(i<j)，則不會(huì)有左遞歸

如果發(fā)現(xiàn)Ai

Aj

(i>j)

，代入

Aj

的當(dāng)前產(chǎn)生式，若替換后有

Ai

的直接左遞歸，再消除通用的左遞歸消除方法輸入：沒有環(huán)和ε產(chǎn)生式的文法G輸出：等價(jià)的無左遞歸的文法步驟：將文法的非終結(jié)符號(hào)任意排序?yàn)锳1,A2,…,Anfori=1tondo

{forj=1toi-1

do{將形如Ai→

Ajγ的產(chǎn)生式替換為Ai→δ1γ|δ2γ

|

…|δkγ，其中Aj→

δ1|δ2|…|

δk是以Aj為左部的所有產(chǎn)生式；}消除Ai的立即左遞歸；}通用的左遞歸消除方法（續(xù)）內(nèi)層循環(huán)的每一次迭代保證了Ai的產(chǎn)生式的右部首符號(hào)都比Aj更加靠后當(dāng)內(nèi)層循環(huán)結(jié)束時(shí)，Ai的產(chǎn)生式的右部首符號(hào)不先于Ai消除立即左遞歸就保證了Ai的產(chǎn)生式的右部首符號(hào)必然比Ai后。（不能有環(huán)和ε產(chǎn)生式）當(dāng)外層循環(huán)結(jié)束時(shí)，所有的產(chǎn)生式都是如此。使用這些產(chǎn)生式當(dāng)然不會(huì)產(chǎn)生左遞歸的情形消除算法（示例）S→Aa|

b,A→Ac|Sd

|ε排序：S A替換：

i=1，沒有處理

i=2,

替換

A→Sd

中的

S，得到

A

→

Ac|

Aad

|

bd|ε消除立即左遞歸提取左公因子在推導(dǎo)的時(shí)候，不知道該如何選擇（自頂向下算法會(huì)詳細(xì)描述）A→αβ1|

αβ2A

→ αA’A’→β1|

β2提取左公因子算法輸入：文法G輸出：一個(gè)等價(jià)的提取了左公因子的文法方法：對(duì)于每個(gè)非終結(jié)符號(hào)A，找出它的兩個(gè)或多個(gè)可選項(xiàng)之間的最長(zhǎng)公共前綴α，且α≠ε，那么將A所有的產(chǎn)生式A→αβ1|αβ2|...|αβn|

γ替換為A→αA’|γA’→β1|β2|...|

βn提取左公因子對(duì)于S而言，最長(zhǎng)的前綴是i

E

tS，因此：非上下文無關(guān)語言的構(gòu)造抽象語言

L1={wcw

|

w在(a|b)*中}這個(gè)語言不是上下文無關(guān)的語言它抽象地表示了C或者Java中“標(biāo)識(shí)符先聲明后使用”的規(guī)則

說明了C/Java這些語言不是上下文無關(guān)語言，不能使用上下文無關(guān)文法描述。

通常用上下文無關(guān)文法描述其基本結(jié)構(gòu)，不能用文法描述的特性在語義分析階段完成。原因是上下文無關(guān)文法具有高效的處理算法。提綱語法分析概要上下文無關(guān)文法自頂向下的語法分析算法自底向上的語法分析算法詞法分析和語法分析的實(shí)踐技術(shù)自頂向下分析技術(shù)自頂向下分析可以被看作是為輸入串構(gòu)造語法分析樹的問題，也可以看作一個(gè)尋找輸入串的最左推導(dǎo)的過程問題

在推導(dǎo)的每一步，對(duì)非終結(jié)符號(hào)A，應(yīng)用哪個(gè)產(chǎn)生式，以可能產(chǎn)生于輸入串相匹配的終結(jié)符號(hào)串id+id*id的自頂向下分析自頂向下語法分析問題：對(duì)于非終結(jié)符號(hào)A，選擇哪一個(gè)產(chǎn)生式一種通用的遞歸下降分析框架

由一組過程組成，每個(gè)非終結(jié)符號(hào)對(duì)應(yīng)一個(gè)過程

程序的執(zhí)行從開始符號(hào)對(duì)應(yīng)的過程開始

每個(gè)過程的功能是：選擇一個(gè)產(chǎn)生式體，掃描相應(yīng)的句子。若遇到非終結(jié)符號(hào)，調(diào)用該符號(hào)對(duì)應(yīng)的過程遞歸下降分析過程示例輸入串w

=

c

a

d文法：

S→

cAd

A→ab|

a遞歸下降分析過程示例輸入串w

=

c

a

d文法：

S→

cAd

A→ab|

a遞歸下降分析過程示例輸入串w

=

c

a

d文法：

S→

cAd

A→ab|

a遞歸下降分析過程示例輸入串w

=

c

a

d文法：

S→

cAd

A→ab|

a匹配成功！遞歸下降過程示例(續(xù))可能需要回溯，或者說，可能需要重復(fù)掃描輸入“在回到A時(shí)，我們必須把輸入指針重新設(shè)置到位置2，即我們第一次嘗試展開A時(shí)該指針指向的位置。這意味著A的過程必須將輸入指針存放在一個(gè)局部變量中?！比绻姆ㄖ写嬖谧筮f歸……回溯（窮試

?）顯然是笨辦法預(yù)測(cè)分析法簡(jiǎn)介試圖從開始符號(hào)推導(dǎo)出輸入符號(hào)串以開始符號(hào)作為初始的當(dāng)前句型每次為最左邊的非終結(jié)符號(hào)選擇適當(dāng)?shù)漠a(chǎn)生式

通過查看下一個(gè)輸入符號(hào)來選擇這個(gè)產(chǎn)生式

有多個(gè)可能的產(chǎn)生式時(shí)預(yù)測(cè)分析法無能為力比如文法：E→

+EE

|

-EE

|

id；輸入為+

id

-id

id當(dāng)兩個(gè)產(chǎn)生式具有相同的前綴時(shí)無法預(yù)測(cè)

文法：stmt

→

if

expr

then

stmtelsestmt|if

expr

then

stmt

輸入：if

a

then

…

新文法：stmt

→

if

expr

then

stmt

elsePart

elsePart→elsestmt|

ε需要提取公因子預(yù)測(cè)分析技術(shù)一種確定性的、無回溯的分析技術(shù)在每一步選擇正確的產(chǎn)生式例1：文法G(S)：S→pAS→qBA→cAdA→a輸入串

W=pccadd消除二義性消除左遞歸提取左公因子預(yù)測(cè)分析技術(shù)（續(xù)）例2：文法G(S)為：S

→ApS→BqA

→a∣cAB→b∣dB輸入W=ccap預(yù)測(cè)分析技術(shù)（續(xù)）通過在輸入中向前看固定多個(gè)符號(hào)來選擇正確的產(chǎn)生式通常情況下，我們只需要向前看一個(gè)符號(hào)

遞歸下降分析一般只適合于每個(gè)子表達(dá)式的第一個(gè)終結(jié)符能夠?yàn)楫a(chǎn)生式選擇提供足夠信息的那些文法給出兩個(gè)與文法相關(guān)的兩個(gè)函數(shù)

FIRST

FOLLOW基于上述兩個(gè)函數(shù)，可以根據(jù)下一個(gè)輸入符號(hào)來選擇應(yīng)用哪個(gè)產(chǎn)生式FIRST和FOLLOW（1）在自頂向下的分析技術(shù)中，通常使用向前看幾個(gè)符號(hào)來唯一地確定產(chǎn)生式（這里假定只看一個(gè)符號(hào)）當(dāng)前句型是xAβ，而輸入是xa…。那么選擇產(chǎn)生式A→α的必要條件是下列之一：

Α ε，且β以a開頭；也就是說在某個(gè)句型中a跟在A之后；

Α a…；

如果按照這兩個(gè)條件選擇時(shí)能夠保證唯一性，那么我們就可以避免回溯。因此，我們定義FIRST和FOLLOW很重要FIRST和FOLLOW（2）FIRST(α)：

可以從α推導(dǎo)得到的串的首符號(hào)的集合；

如果α ε，那么ε也在FIRST(α)中；FOLLOW(A)：

可能在某些句型中緊跟在A右邊的終結(jié)符號(hào)的集合。FIRST(α)定義：可從α推導(dǎo)得到的串的首符號(hào)的集合，其中α是任意的文法符號(hào)串。如果α ε，那么ε也在FIRST(α)中FIRST函數(shù)的意義

如果兩個(gè)A產(chǎn)生式

A→

α|

β，其中First(α)和First(β)是不相交的集合。下一個(gè)輸入符號(hào)是a，若a∈

First(α)，則選擇A

→α

，若a∈

First(β)，則選擇A

→

β

用于預(yù)測(cè)產(chǎn)生式的選擇First的計(jì)算對(duì)于文法符號(hào)X的FIRST(X)，通過不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符號(hào)或者ε可以加入到任何FIRST集合為止

如果X是終結(jié)符號(hào)，那么FIRST(X)={X}

如果X是非終結(jié)符號(hào)，且有規(guī)則X

→

a…,那么將a添加到FIRST(X)中;

如果X

→

，那么

也在FIRST(X)中

對(duì)于規(guī)則X

→

Y1Y2…Yn，把FIRST(Y1)中的非

符號(hào)添加到FIRST(X)中。如果

在FIRST(Y1)中，把FIRST(Y2)中的非

符號(hào)添加到FIRST(X)中…；如果

在FIRST(Yn)中，把

添加到FIRST(X)中First的計(jì)算（續(xù)）對(duì)于文法符號(hào)串X1X2…Xn的First集合

向First(X1X2…Xn)加入First(X1)中所有的非ε符號(hào)。

如果ε在First(X1)中，再加入First(X2)中的所有非ε符號(hào)。如果ε在First(X1)和First(X2)中，再加入First(X3)中的所有非ε符號(hào)。依次類推。

如果對(duì)所有的i（1到n），ε都在First(Xi)中，則ε加入First(X1X2…Xn)中。First的計(jì)算示例First(F)=First(T)=First(E)={(,id}First(E’)={+,

ε}First(T’)={*,

ε}First(TE’)=First(T)={(,id}First(+TE’)={+}……一個(gè)實(shí)例

S→AB|

CD

A→aD

| ε

C

→cD

B

→bC

D

→d文法G[S],

輸入bcdFirst(S)={a,b,

c}First(A)={a,ε

}First(B)=

First(C)=

{c}First(D)=

1661611FOLLOW函數(shù)文法G[S],

輸入bcdS→

AB|CDA→aD|

εC→cDB

→bCD

→d對(duì)于非終結(jié)符號(hào)A，F(xiàn)OLLOW(A)定義為可能在某些句型中緊跟在A右邊的終結(jié)符號(hào)的集合

例如S αAaβ，終結(jié)符號(hào)a∈Follow(A)如果A是某些句型的最右符號(hào)，那么$ ∈Follow(A)。

$是特殊的輸入串“結(jié)束標(biāo)記”FOLLOW函數(shù)的意義：

如果A→α，當(dāng)α→

或α

時(shí)，F(xiàn)OLLOW(A)可以幫助我們做出選擇恰當(dāng)?shù)漠a(chǎn)生式

例如：如果A→

α,

b屬于FOLLOW(A)，如果α

，則若當(dāng)前輸入符號(hào)是b，可以選擇A

→

α，因?yàn)锳最終到達(dá)了

，而且后面跟著bFOLLOW計(jì)算計(jì)算各個(gè)非終結(jié)符號(hào)A的FOLLOW(A)集合，不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符號(hào)可以被加入到任意FOLLOW集合中

將$放入FOLLOW(S)，S是開始符號(hào)，而$是輸入串的結(jié)束標(biāo)記

如果存在產(chǎn)生式A

→

αBβ，那么First(β)中除ε之外的所有符號(hào)都在Follow(B)中

如果存在一個(gè)產(chǎn)生式A

→

αB，或存在產(chǎn)生式A→

αBβ且First(β)包含ε，那么Follow(A)中的所有符號(hào)都在Follow(B)中Follow的計(jì)算示例T

→ F

T’□ 文法E → T

E’T’

→ *FT’|

E’→+TE’|

F → (

E

) |

i□ FOLLOW(E)={)，

$}□ FOLLOW(E’)={)，

$}□ FOLLOW(T)={+，)，$}□ FOLLOW(T’)={+，)，$}□ FOLLOW(F)=(*，+，)，$)←FIRST())U

{$}←

FOLLOW(E)←FIRST(E’)U

FOLLOW(E’)←

FOLLOW(T)←FIRST(T’)U

FOLLOW(T)將$放入FOLLOW(S)，S是開始符號(hào)，而$是輸入串的結(jié)束標(biāo)記如果存在產(chǎn)生式A

→

αBβ，那么First(β)中除ε之外的所有符號(hào)都在Follow(B)中如果存在一個(gè)產(chǎn)生式A

→

αB，或存在產(chǎn)生式A

→

αBβ且First