第2章文法和語言的基本知識2.1-2.4

復(fù)習(xí)補(bǔ)充第一章37用戶名/密碼:compiler教材編譯原理(第3版).劉銘,徐蘭芳,駱婷編著.電子工業(yè)出版社.1.3編譯程序的實現(xiàn)方法設(shè)計目標(biāo)目標(biāo)程序小，執(zhí)行速度快。編譯程序小，執(zhí)行速度快。診斷能力強(qiáng)，可靠性強(qiáng)?？梢浦残?，可擴(kuò)充性。如何實現(xiàn)編譯器？直接用可運行的代碼編制——太費力！問題一：A機(jī)上有一個C語言編譯器，是否可利用此編譯器實現(xiàn)B機(jī)上的C語言編譯器？解決：移植方法用C語言寫一個B機(jī)上的C編譯程序(P0:C→B)用A機(jī)上的C編譯程序(P1:C→A)編譯它(P0)，得到可在A機(jī)上運行的“B機(jī)上的C編譯程序”(P2:C→B)在A機(jī)上用P2再編譯P0，得到可在B機(jī)上運行的“B機(jī)上的C編譯程序”(P3:C→B)Ｔ形圖表示語言翻譯的Ｔ形圖源語言書寫語言目標(biāo)語言編譯程序P1）交叉編譯(CrossCompiling)條件：Ａ機(jī)有Ｃ語言的編譯程序目的：實現(xiàn)Ｂ機(jī)的Ｃ語言的編譯Ｃ語言Ｃ語言Ｂ機(jī)器Ｃ語言Ａ機(jī)器A機(jī)器Ｃ語言A機(jī)器Ｂ機(jī)器1.(人)用Ｃ語言編制B機(jī)的Ｃ編譯程序P0(C→B)(Ａ機(jī)的C編譯程序P1)編譯P0，得到在A機(jī)上可運行的P2(C→B)P0P1P2交叉編譯Ｃ語言Ｃ語言Ｂ機(jī)器Ｃ語言Ａ機(jī)器Ｂ機(jī)器Ｃ語言Ｂ機(jī)器Ｂ機(jī)器3.(Ａ機(jī)的P2)編譯P0，得到在B機(jī)上可運行的P3(C→B)P0P2P3問題二：A機(jī)上有一個C語言編譯器，現(xiàn)要實現(xiàn)一個新語言NEW的編譯器？能利用交叉編譯技術(shù)么？問題三：直接在一個機(jī)上實現(xiàn)C語言編譯器，還有別的技術(shù)么？解決：用匯編語言實現(xiàn)一個Ｃ子集的編譯程序(P0—人)用匯編程序處理該程序,得到(P2:可直接運行)用Ｃ子集編制Ｃ語言的編譯程序(P3—人)用P2編譯P3，得到P42)編譯程序的自展技術(shù)Ｃ子集匯編語言機(jī)器語言匯編語言機(jī)器語言機(jī)器語言Ｃ子集機(jī)器語言機(jī)器語言1.用匯編語言實現(xiàn)一個Ｃ子集的編譯程序(P0—人)2.用匯編程序(P1)處理該程序,得到(P2:可直接運行)P0P1P2編譯程序的自展技術(shù)Ｃ語言Ｃ子集機(jī)器語言Ｃ子集機(jī)器語言機(jī)器語言Ｃ語言機(jī)器語言機(jī)器語言3.用Ｃ子集編制Ｃ語言的編譯程序(P3—人)4.用P2編譯P3，得到P4P3P2P43)利用編譯程序自動生成器詞法分析器的自動生成程序LEX詞法規(guī)則說明詞法分析程序(C程序)輸入： 詞法（正規(guī)表達(dá)式） 識別動作（Ｃ程序段）輸出：

yylex()函數(shù)語法分析器的自動生成程序ＹＡＣＣ語法規(guī)則說明語法分析程序(C程序)輸入： 語法規(guī)則（產(chǎn)生式） 語義動作（Ｃ程序段）輸出：

yyparse()函數(shù)編譯原理第二章文法和語言的基本知識第2章文法和語言的基本知識2.1.概述2.2.字母表和符號串的基本概念2.3.文法和語言的形式定義2.4.短語、直接短語和句柄2.5.語法樹與文法的二義性2.6.文法和語言的分類編譯原理第二章文法和語言的基本知識2.1概述語法是對語言結(jié)構(gòu)的定義;語義是描述了語言的含義;語用是從使用的角度去描述語言。例：s=2*3.1416*r*(r+h)的非形式化的描述如下:語法一賦值語句由一個變量、一個后隨賦值號“=”、及其后跟一個表達(dá)式構(gòu)成。語義一首先計算語句右部表達(dá)式的值,然后把所得結(jié)果送入左部變量中。語用一賦值語句可用來計算和保存表達(dá)式的值。第二章文法和語言的基本知識編譯原理第二章文法和語言的基本知識2.2字母表和符號串的基本概念1、字母表和符號串1)字母表是元素的非空有窮集合。例如:∑={a,b,c}

注意:

字母表中至少包含一個元素;字母表中的元素,可以是字母、數(shù)字或其他符號2)符號(字符)

字母表中的元素稱為符號,或稱為字符。3)符號串(字)

符號的有窮序列稱為符號串。例如:上述字母表,則有符號串a(chǎn),b,ab,ba,cba,abc...

不包含任何符號的符號串,稱為空符號串,用ε表示,即空符號串由0個符號組成,其長度|ε|=0編譯原理第二章文法和語言的基本知識2、符號串的運算1)符號串的連結(jié)例如,設(shè)x=abc,y=10a,則xy=abc10ayx=10aabc。注意:對任意一個符號串x,有εx=xε=x2)集合的乘積設(shè)A和B是符號串的集合,則A和B的乘積定義為:AB={xy|x?A,y?B}例如,設(shè)A={a,b},B={c,d},則AB={ac,ad,bc,bd}。對任意集合A,有{ε}A=A{ε}=A,注意ε是符號串,不是集合,而{ε}表示由空符號串ε所組成的集合,但這樣的集合不是空集合?={}編譯原理第二章文法和語言的基本知識3.符號串的冪運算設(shè)x是符號串,則x的幕運算定義為

x0=ε,x1=x,x2=xx...xn=xx…x=xxn-1(n>0)4.集合的冪運算設(shè)A是符號串的集合,則集合A的冪運算定義為:

A自身的n次（連接）積記為：An=AA…A(n個A)5.集合A的正閉包A+與閉包A*

設(shè)A是符號串的集合,則A的正閉包A+和A的閉包A*定義

A+=A1UA2U...UAn...A*=A0UA1UA2U...UAn...={ε}UA+

例如,設(shè)A={a,b}則A+={a,b,aa,ab,ba,bb,aaa,aab,...}A*={ε,a,b,aa,ab,ba,bb,aaa,aab,...}編譯原理第二章文法和語言的基本知識2.3文法和語言的形式定義1、形式語言序列的集合稱為形式語言。（對每個具體語言,都有語法和語義兩個方面,形式語言是指不考慮語言的具體意義,即不考慮語義）2形式語言的描述1)當(dāng)語言為有窮集合時,用枚舉方法來表示語言。例如,設(shè)有字母表A={a,b,c},則L1={a,b,c}L2={a,aa,ab,ac}L3={c,cc}均表示字母表A上的一個形式語言。例如,設(shè)字母表∑={0,1},∑+=∑1U∑2U∑3U…...={0,1,00,10,01,11,000,100…..}無窮集合2)文法來描述無窮集合的語言。用A表示∑+,用式子A→0表示符號串0?A或A生成符號串0,符號“→”,讀做“生成”,或“由......組成“.則集合A可表示成A→0,A→1,A→A0,A→A12、文法的形式定義(Grammar)1)規(guī)則（Production）規(guī)則也稱產(chǎn)生式,它是一個符號與一個符號串的有序?qū)?A,β)通常寫做A→β(或A::=β)A是規(guī)則左部它是一個符號,β規(guī)則右部它是一個符號串;“→',和“::=',表示“定義為',或“生成",一組規(guī)則規(guī)定了一個語言的語法結(jié)構(gòu)編譯原理第二章文法和語言的基本知識符號分為兩類,一類是終結(jié)符號,另一類是非終結(jié)符號。非終結(jié)符號是出現(xiàn)在規(guī)則左部能派生出符號或符號串的那些符號,即每個非終結(jié)符號表示一定符號串的集合,用大寫字母表示或用尖括號把非終結(jié)符號括起來。上例中A終結(jié)符號是不屬于非終結(jié)符號的那些符號,它是組成語言的基本符號,是一個語言的不可再分的基本符號,通常用小寫字母表示。上例中0,1編譯原理第二章文法和語言的基本知識2)文法文法是對語言結(jié)構(gòu)的定義和描述,是規(guī)則的非空有窮集合,通常表示成四元組G=(VN,VT,P,S)。

VN是規(guī)則中非終結(jié)符號的集合。

VT是規(guī)則中終結(jié)符號的集合。VNnVT=?VNUVT

稱為文法G的字匯表。

P是文法規(guī)則的集合。(關(guān)鍵)

S是一個非終結(jié)符號,稱為文法的開始符號或文法的識別符號(至少在一條規(guī)則的左部出現(xiàn)).上例描述的語言序列只可能是由0和1組成的符號串,可用G[A]=({A},{0,1},{A→0,A→1,A→A0,A→A1},A)表示對于若干個左部相同的規(guī)則,如A→a1A→a2

………A→an將它們縮寫為A→a1|a2|...|an約定:1.對文法G不用四元組顯式表示,而只將規(guī)則寫出.2.第一條規(guī)則的左部是文法的開始符號.例:G:A→0|1|A0|A1關(guān)于語言文法的構(gòu)造：一般采用“湊規(guī)則”的方法來構(gòu)造語言的文法（1）找出語言的若干典型句子（2）分析句子的特點（3）根據(jù)句子的特點湊規(guī)則（4）得到文法（5）檢查文法。文法應(yīng)滿足如下兩點要求：

a.語言的所有句子都能由文法的開始符號推導(dǎo)得到

b.由文法開始符號推導(dǎo)出的所有終結(jié)符號串都是語言的句子編譯原理第二章文法和語言的基本知識設(shè)字母表∑={a,b};試設(shè)計一個文法,描述語言L={a2n,b2n|n>=1}分析：當(dāng)n=1L={aa,bb}

當(dāng)n=2L={aaaa,bbbb}

…………..L={aa,bb,aaaa,bbbb,……}定義語言L的文法G=(VN,VT,P,S)VN={A,B,D},VT={a,b}P={A→aa|aaB|bb|bbDB→aa|aaBD→bb|bbD}S=A還可以設(shè)計文法G’

=（{A,B,D},{a,b}，P，A）P={A→B|DB→aa|aBaD→bb|bDb}G和G’是等價文法例1：文法G’’

=（{A},{a,b},P,A）P={A→aa|aaA|bb|bbA}X編譯原理第二章文法和語言的基本知識試設(shè)計一個表示所有標(biāo)識符的文法。I代表標(biāo)識符,L代表字母,D代表數(shù)字,則定義標(biāo)識符的文法為,G=(VN,VT,P,S)其中VN={I,L,D}VT={a,b,c,...,x,y,z,0,1,2,...,9}P={I→L|IL|IDL→a|b|c|...|x|y|zD→0|1|2|3|...|9}S=I字母字母數(shù)字標(biāo)識符例2：字母或以字母開頭的字母數(shù)字串現(xiàn)若將定義標(biāo)識符的文法設(shè)計成G’

=(VN,VT,P,S),P={I→LlIDL→a|b|c|...|x|y|zD→0|1|2|3|...|9}X編譯原理第二章文法和語言的基本知識1）直接推導(dǎo)3、語言的形式定義G是一文法,我們從xAy直接推出xay,即xAyxay,僅A→a是G的一個規(guī)則且x,y?(VNUVT)*.例如,設(shè)有文法G[S]=({S},{0,1},P,S)其中,P為S→01|0S1有如下直接推導(dǎo):S01使用規(guī)則S→01,此時x=ε,y=εS0S1,使用規(guī)則S→0S1此時x=ε,y=ε0S10011使用規(guī)則S→01,此時x=0,y=100S11000S111使用規(guī)則S→0S1,此時x=00,y=11編譯原理第二章文法和語言的基本知識2)、推導(dǎo)

如果存在一個直接推導(dǎo)序列:ao=〉a1=〉a2=〉..·=〉an則稱這個序列是一個從aO至an的長度為n的推導(dǎo),記為ao

an。表示從ao出發(fā),經(jīng)一步或若干步或使用若干次規(guī)則可推導(dǎo)出an。例如,設(shè)有文法G[E]=({E,T,F},{i,+,*,(,)},P,E)其中,P為E→E+T|TT→T*F|FF→(E)|i

對i+i*i有如下直接推導(dǎo)E=〉E+T=〉T+T=〉F+T=〉i+T=〉i+T*F=〉i+F*F=〉i+i*F=〉i+i*i記為Ei+i*i++編譯原理第二章文法和語言的基本知識3).廣義推導(dǎo)a0

an表示從ao出發(fā),經(jīng)0步或若干步,可推導(dǎo)出an。對上例,有EEEi+i*i顯然,直接推導(dǎo)的長度為1,推導(dǎo)的長度大于等于1,而廣義推導(dǎo)的長度大于等于0.4)、句型和句子設(shè)有文法G[S]，如果S

x,x?(VNUVT)*,則稱符號串x為文法G[S]的句型。S

x,x?VT*,則稱x是文法G[S]的句子。例設(shè)有文法G[S]:S→01|0S1S

01,s

0S1,S

00S11,s

000111顯然,符號串01,0S1,00S11和000111都是文法G[S]的句型,而01和000111又是文法G[S]的句子。*********編譯原理第二章文法和語言的基本知識5).語言G[S]產(chǎn)生的所有句子的集合稱為文法G所定義的語言,記為L(G[S]):L(G[S])={x|S

x且x?VT*}由語言定義可知:(1)當(dāng)文法給定,語言也就確定。(2)L(G)是VT*的子集。即屬于VT*的符號串x不一定屬于L(G)。例：設(shè)有文法G[S]:S→0S|1S|ε

求該文法所定義的語言求該文法所確定的語言為L(G[S])={ε

，0,1，00，01，10，11,……}={x|x?{0,1}*}+編譯原理第二章文法和語言的基本知識從已知文法確定語言的中心思想：從文法的開始符號出發(fā)，反復(fù)連續(xù)地使用規(guī)則，對非終結(jié)符施行替換和展開，找出句子的規(guī)律，用式子或自然語言描述出來。形式語言理論可以證明如下兩點：(1)給定一個文法，就能從結(jié)構(gòu)上唯一確定其語言，即G→L(G)(2)給定一種語言，能確定其文法，但不是唯一的，即L→G1或G2或…或Gn編譯原理第二章文法和語言的基本知識4.規(guī)范推導(dǎo)和規(guī)范歸約例如,設(shè)有文法G[N1]:N1→NN→ND|DD→0|1|2符號串12是該文法的一個句子,