本文格式為Word版，下載可任意編輯——編譯原理第2講(第三章)

編譯原理

第三章文法和語言為語言的語法描述尋求工具

工具要對程序設計語言給出確切無二義的語法描述。(嚴謹、簡單、易讀)形式工具--“形式〞是指這樣的事實：語言的所有規(guī)則只以什麼符號串能出現(xiàn)的方式來陳述1

編譯原理

本章內(nèi)容1.符號和符號串2.文法和語言的形式定義3.文法的類型4.上下文無關文法及其語法樹5.上下文無關文法的句型分析6.有關文法實用中的一些說明

編譯原理

語言漫談自然語言：英語，漢語，法語。。。形式語言：C,Pascal,Fortran等(簡單說，文法嚴格的語言)自然語言比形式語言繁雜。為什么？想想翻譯軟件的質(zhì)量。俄文的“心靈樂意，但肉身衰弱〞(對應中文：心有余而力不足；對應英文：Thespiritiswilling,butthefleshisweak),以機器翻譯為英文時就變?yōu)椤胺丶泳坪懿诲e，但肉已腐敗〞(Thevodkaisgood,butthemeatisrotten)。3

編譯原理

語言漫談程序設計語言(形式語言):是一個記號系統(tǒng)，完整的定義應包括的語法和語義2個方面。語法：是指一組規(guī)則，用它可以形成和產(chǎn)生一個適合的程序。(定義什么樣的符號序列是合法的)語義：自然語言中詞語的意義，規(guī)律形式系統(tǒng)中符號的解釋。(定義什么樣的符號序列是有含義的)文法：是說明語法的一個工具。這是形式語言理論的基本概念之一。??:是說明語義的工具。這是很困難的。

編譯原理

符號和符號串先了解一些基本概念

編譯原理

基本概念符號：可以相互區(qū)別的記號(元素)。字母表：符號(元素)的非空有窮集合。符號串：由字母表中的符號組成的任何有窮序列稱為該字母表上的符號串。

例：(1)符號“a〞組成的字母表記作{a}(2)符號“a〞和“b〞組成的字母表記作{a,b}a,b,aa,bb,ab,abb,aab,…都是字母表{a,b}上的符號串。

編譯原理

基本概念符號串的長度：符號串中符號的個數(shù)。假使符號串x中有m個符號，則長度表示|x|=m空串:長度為0的符號串，它不同于Ф(表示空集)。

連接：連接符號串x、y,是把y的符號串寫在x的符號串之后得到的符號串；即x、y的連接為xy。方冪：符號串自身連接n次得到的符號串；如：x的n次連接為xx…x(n個x),也記作xn

編譯原理

基本概念頭、尾、固有頭、固有尾；例：符號串x=abc的頭：,a,b,abc;尾：,c,bc,abc;固有頭：,a,b;固有尾：,c,bc;符號串集合：若集合中所有元素都是某字母表上的符號串，則稱之為該字母表上的符號串集合。

符號串集合乘積例：符號串集合A={ab,aa},B={ba,bb}乘積AB={abba,abbb,aaba,aabb}AB={xy|x∈A,y∈B}8

編譯原理

基本概念語言(language)某字母表Σ上的串的集

合，是Σ*的一個子集。

例如：Σ={a,b}

{a,aa,aaa,…}或記作：{w|w∈Σ*且w=an,n≥1}{ab,aabb,aaabbb,…,anbn,…}或記作：{w|w∈Σ*且w=anbn,n≥1}都可稱為一種語言9

編譯原理

基本概念閉包：Σ*稱為Σ的閉包，若Σ*表示為Σ上的所有有窮長的串的集合，可表示為：Σ*={}Σ1∪Σ2∪Σ3∪…正閉包：Σ+稱為Σ的閉包，可表示為：Σ+=Σ*-{}=ΣΣ*=Σ1∪Σ2∪Σ3∪…(其中用∪代表規(guī)律“或〞運算)

例：Σ={a,b}Σ*={,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}

編譯原理

基本概念Σ={字母，數(shù)字，空格，標點符號[‘@,.等]}Σ*就是所有可能的符號串的集合。譬如：r5*e3!dfd

thisisadog.英語：所謂英語就是那些符合詞法(字典，構詞法)和語法，語義規(guī)則的在字母表Σ上的符號串集合。

編譯原理

文法和語言的形式定義如何來描述一種語言？假使語言是有窮的(只含有有窮多個句子),可以將句子逐一列出來表示假使語言是無窮的，找出語言的有窮表示。語言的有窮表示有兩個途經(jīng)：生成方式(文法):語言中的每個句子可以用嚴格定義的規(guī)則來構造。識別方式(自動機):用一個過程，當輸入的一任意串屬于語言時，該過程經(jīng)有限次計算后就會停止并回復“是〞,若不屬于，要么能中止并回復“不是〞,要么永遠繼續(xù)下去。

編譯原理

文法與語言的關系

文法即是生成方式描述語言的

語言中的每個句子可以用嚴格定義的規(guī)則來構造

編譯原理

文法的定義

用大寫字母表示A

用小寫字母表示a

文法G定義為四元組(VN,VT,P,S),其中VN:非終結(jié)符號(或語法實體，或變量)集；VT:終結(jié)符號集；N:Nonterminal;P:規(guī)則的集合；T:terminalVN,VT和P是非空有窮集。S:稱作識別符號或開始符號的一個非終結(jié)符，它至少要在一條產(chǎn)生式中作為左部出現(xiàn)。VN和VT不含公共的元素，即VN∩VT=φ用V表示VN∪VT,稱為文法G的字母表或字匯表。規(guī)則，也稱重寫規(guī)則、產(chǎn)生式或生成式，是形如→或∷=的(,)有序?qū)Γ渲惺亲帜副鞻的正閉包V+中的一個符號，是V*中的一個符號。稱為規(guī)則的左部，稱作規(guī)則的右部。14

編譯原理

文法的例子(1)例3.1文法G=(VN,VT,P,S)VN={S},VT={0,1}P={S→0S1,S→01}S為開始符號

編譯原理

文法的例子(2)例3.2文法G=(VN,VT,P,S)VN={標識符，字母，數(shù)字}VT={a,b,c,…x,y,z,0,1,…,9}P={標識符→字母標識符→標識符字母標識符→標識符數(shù)字字母→a…字母→z數(shù)字→0…數(shù)字→9}S=標識符16

編譯原理

文法的寫法元符號:→∷=|習慣大寫字母表示非終結(jié)符小寫字母表示終結(jié)符

(1)G:S→aAbA→abA→aAbA→ε

(2)G[S]:A→abA→aAbA→εS→aSb(3)G[S]:A→ab|aAb|εS→aSb17

編譯原理

推導的定義(1)直接推導“〞α→β是文法G的產(chǎn)生式，若有v,w滿足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*則稱v直接推導到w,記作vw.也稱w直接歸約到v例：G:S→0S1,S→010S100S1100S11000S111000S11100001111S0S118

編譯原理

推導例子程序分程序.(程序分程序.)分程序.變量說明部分語句.(分程序變量說明部分語句)VAR標識符;BEGINREAD(標識符)END.VARA;BEGINREAD(標識符)END.(標識符A)VARA;BEGINREAD(標識符)END.VARA;BEGINREAD(A)END.(標識符A)

編譯原理

推導的定義(2)若存在v=w0w1...wn=w,(n0)則記為v=+w,稱作v推導出w,或w歸約到v若有v=+w