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

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

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

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

注意:

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

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

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

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

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

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

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

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

例如,設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)當語言為有窮集合時,用枚舉方法來表示語言。例如,設有字母表A={a,b,c},則L1={a,b,c}L2={a,aa,ab,ac}L3={c,cc}均表示字母表A上的一個形式語言。例如,設字母表∑={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)生式,它是一個符號與一個符號串的有序對(A,β)通常寫做A→β(或A::=β)A是規(guī)則左部它是一個符號,β規(guī)則右部它是一個符號串;“→',和“::=',表示“定義為',或“生成",一組規(guī)則規(guī)定了一個語言的語法結構編譯原理第二章文法和語言的基本知識符號分為兩類,一類是終結符號,另一類是非終結符號。非終結符號是出現(xiàn)在規(guī)則左部能派生出符號或符號串的那些符號,即每個非終結符號表示一定符號串的集合,用大寫字母表示或用尖括號把非終結符號括起來。上例中A終結符號是不屬于非終結符號的那些符號,它是組成語言的基本符號,是一個語言的不可再分的基本符號,通常用小寫字母表示。上例中0,1編譯原理第二章文法和語言的基本知識2)文法文法是對語言結構的定義和描述,是規(guī)則的非空有窮集合,通常表示成四元組G=(VN,VT,P,S)。

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

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

稱為文法G的字匯表。

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

S是一個非終結符號,稱為文法的開始符號或文法的識別符號(至少在一條規(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ī)則”的方法來構造語言的文法（1）找出語言的若干典型句子（2）分析句子的特點（3）根據(jù)句子的特點湊規(guī)則（4）得到文法（5）檢查文法。文法應滿足如下兩點要求：

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

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

當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還可以設計文法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編譯原理第二章文法和語言的基本知識試設計一個表示所有標識符的文法。I代表標識符,L代表字母,D代表數(shù)字,則定義標識符的文法為,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ù)字標識符例2：字母或以字母開頭的字母數(shù)字串現(xiàn)若將定義標識符的文法設計成G’

=(VN,VT,P,S),P={I→LlIDL→a|b|c|...|x|y|zD→0|1|2|3|...|9}X編譯原理第二章文法和語言的基本知識1）直接推導3、語言的形式定義G是一文法,我們從xAy直接推出xay,即xAyxay,僅A→a是G的一個規(guī)則且x,y?(VNUVT)*.例如,設有文法G[S]=({S},{0,1},P,S)其中,P為S→01|0S1有如下直接推導: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)、推導

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

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

對i+i*i有如下直接推導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).廣義推導a0

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

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

x,x?VT*,則稱x是文法G[S]的句子。例設有文法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)當文法給定,語言也就確定。(2)L(G)是VT*的子集。即屬于VT*的符號串x不一定屬于L(G)。例：設有文法G[S]:S→0S|1S|ε

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

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