編譯原理—第3章文法和語法

1、第第3 3章章文法和語言文法和語言教學要求：本章是編譯原理課程的理論基教學要求：本章是編譯原理課程的理論基礎(chǔ)，要求理解文法、語言、規(guī)范推導、規(guī)礎(chǔ)，要求理解文法、語言、規(guī)范推導、規(guī)范歸約和短語、簡單短語、句柄的基本概范歸約和短語、簡單短語、句柄的基本概念；掌握語言的求解方法、文法的二義性念；掌握語言的求解方法、文法的二義性的判斷方法及句型的分析方法。的判斷方法及句型的分析方法。教學重點：上下文無關(guān)文法，語言定義教學重點：上下文無關(guān)文法，語言定義 一、語言一、語言 語言是由句子組成的集合，是由一組記號語言是由句子組成的集合，是由一組記號所構(gòu)成的集合。所構(gòu)成的集合。漢語漢語-所有符合漢語語法的句子的

2、全體所有符合漢語語法的句子的全體英語英語-所有符合英語語法的句子的全體所有符合英語語法的句子的全體程序設計語言程序設計語言-所有該語言的程序的全體所有該語言的程序的全體“我是大學生我是大學生”是否是該語言的句子？是否是該語言的句子？句子句子:=:=主語謂語主語謂語主語主語:=:=代詞代詞| |名詞名詞代詞代詞:= := 你你 | | 我我 | | 他他名詞名詞:= := 王明王明 | | 大學生大學生 | | 工人工人 | | 英語英語謂語謂語:=:=動詞直接賓語動詞直接賓語動詞動詞:= := 是是 | | 學習學習直接賓語直接賓語:=:=代詞代詞| |名詞名詞二、文法二、文法“:=”與與“”

3、等價，表示為等價，表示為“由由什么組成什么組成”或或“定義為定義為”句子句子 主語謂語主語謂語 代詞謂語代詞謂語 我謂語我謂語 我動詞直接賓語我動詞直接賓語 我是直接賓語我是直接賓語 我是名詞我是名詞 我是大學生我是大學生句子句子:=:=主語謂語主語謂語主語主語:=:=代詞代詞| |名詞名詞代詞代詞:= := 你你 | | 我我 | | 他他名詞名詞:= := 王明王明 | | 大學生大學生 | | 工人工人 | | 英語英語謂語謂語:=:=動詞直接賓語動詞直接賓語動詞動詞:= := 是是 | | 學習學習直接賓語直接賓語:=:=代詞代詞| |名詞名詞語法變量（在形式語法變量（在形式語言中又稱

4、語言中又稱“非終非終結(jié)符結(jié)符”）單詞符號（在形單詞符號（在形式語言中又稱式語言中又稱“終結(jié)符號終結(jié)符號”)三、符號和符號串三、符號和符號串1 1、字母表和符號串、字母表和符號串字母表：符號的非空有限集字母表：符號的非空有限集 例：例： = = a a，b b，cc符號：字母表中的元素符號：字母表中的元素 例：例： a a，b b，c c符號串：符號的有窮序列符號串：符號的有窮序列 例：例：a, aa, ac, abca, aa, ac, abc，.空符號串：無任何符號的符號串空符號串：無任何符號的符號串( ()符號串集合：由符號串構(gòu)成的集合。符號串集合：由符號串構(gòu)成的集合。2 2、符號串的運算

5、、符號串的運算符號串的長度符號串的長度：符號串中符號的個數(shù)：符號串中符號的個數(shù). .符號串符號串s s的長度的長度記為記為| |s|s|。 的長度為的長度為0 0符號串的連接符號串的連接：符號串：符號串x x、y y的連接的連接, ,是把是把y y的符號寫在的符號寫在x x的符號之后得到的符號串的符號之后得到的符號串xyxy例例 x=ST,y=abu x=ST,y=abu 則則 xy=STabuxy=STabu |x|=2,|y|=3,|xy|=5 |x|=2,|y|=3,|xy|=5 x = x= x x = x= x方冪方冪：符號串：符號串x x自身連接自身連接n n次得到的符號串次得到的

6、符號串 xxxx(nxxxx(n個個x)x)定義為定義為 x xn n x x0 0=, x=, x1 1=x, x=x, x2 2=xx, x=xx, x3 3=xxx=xxxx=AB, x=AB, 則則 x x0 0=, x=, x1 1=AB, x=AB, x2 2=ABAB, x=ABAB, x3 3=ABABAB=ABABAB對于對于 n0, xn0, xn n = xx= xxn-1 n-1 = x= xn-1n-1x x 3 3、符號串集合、符號串集合 若集合若集合A A中一切元素都是某字母表中一切元素都是某字母表 上的符號串，上的符號串，則稱則稱A A為字母表為字母表 上的符號

7、串集合。上的符號串集合。 兩個符號串集合兩個符號串集合A A和和B B的乘積定義為的乘積定義為 若集合若集合A=A= a,ba,b B=B= c,dc,d 則則 AB=AB= ac,ad,bc,bdac,ad,bc,bd (x=x=x)(x=x=x) 使用使用 * *表示表示 上的所有有窮長的串（包括上的所有有窮長的串（包括）的集合。的集合。* *稱為稱為的的。 從從 * *中除去中除去得到的集合記為得到的集合記為 + + 。 + +稱為稱為的的。* = 0 1 2 n + = 1 2 n * = 0 + = * = *+ = * -設設=0,1，則則* =, 0, 1, 00, 01, 10

8、, 11, 000, 001, 010,設設=a,b=a,b，則則 * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab, + +=a,b,aa,ab,ba,bb,aaa,aab,=a,b,aa,ab,ba,bb,aaa,aab,四、文法和語言的形式定義四、文法和語言的形式定義1 1、文法的形式定義、文法的形式定義1 1）規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式）：是）規(guī)則（重寫規(guī)則、產(chǎn)生式或生成式）：是一個有序?qū)Γㄒ粋€有序?qū)Γ?，）。）。記為記為或?，其中其中VV+ +，VV* * 。 稱為規(guī)則的左部稱為規(guī)則的左部( (或生成式的左部或生成式的左

9、部) )。 稱為規(guī)則的右部稱為規(guī)則的右部( (或生成式的右部或生成式的右部) )。2 2）文法）文法GSGS：文法為文法為（V VN N，V VT T，P P，S S） V VN N ：非終結(jié)符集非終結(jié)符集 V VT T ：終結(jié)符集終結(jié)符集 P P：產(chǎn)生式（規(guī)則）集合產(chǎn)生式（規(guī)則）集合 S S：開始符號（識別符號）開始符號（識別符號）V VN N、V VT T 和和 P P 是非空有窮集。是非空有窮集。S S 至少在一條規(guī)則至少在一條規(guī)則中作為左部出現(xiàn)。中作為左部出現(xiàn)。V VN NVVT T=， SV SVN NV=VV=VN NVVT T，稱為文法稱為文法G G的字母表（字匯表）的字母表（字

10、匯表） 例例: : 文法文法G=G=（V VN N，V VT T，P P，S S）V VN N = S , V = S , VT T = 0, 1 = 0, 1 P= S0S1, S01 P= S0S1, S01 S S為開始符號為開始符號例例: : 文法文法G=G=（V VN N，V VT T，P P，S S）V VN N = =標識符，字母，數(shù)字標識符，字母，數(shù)字 V VT T =a,b,c,x,y,z,0,1,9 =a,b,c,x,y,z,0,1,9P=P= a, a, z z 0, 0, 99S=S= 習慣上只將產(chǎn)生式寫出。并有如下約定：習慣上只將產(chǎn)生式寫出。并有如下約定：第一條產(chǎn)生式

11、的左部是開始符號第一條產(chǎn)生式的左部是開始符號用尖括號括起的是非終結(jié)符，否則為終結(jié)用尖括號括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字符?；蛘叽髮懽帜副硎痉墙K結(jié)符，小寫字母表示終結(jié)符母表示終結(jié)符G G可寫成可寫成GSGS，其中其中S S是開始符號是開始符號 例例:文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S為開始符號為開始符號 可寫成：可寫成： G：S0S1 S01 或?qū)懗桑夯驅(qū)懗桑?GS：S0S1 S01五、推導的定義五、推導的定義 1 1）直接推導）直接推導“” 是文法是文法G G的產(chǎn)生式，的產(chǎn)生式，,V,V* *，

12、若將，若將作用于作用于 v=v=得到得到 w=,w=,則則記作記作 v vw w，讀作讀作v v（應用規(guī)則應用規(guī)則）直接產(chǎn)生直接產(chǎn)生w w（w w是是v v的的或或w w到到v v）例：例：G G：S0S1S0S1，S01S01直接推導：直接推導：0 0S1S100110011（v=0S1v=0S1，w=0011w=0011，使用規(guī)則使用規(guī)則S01S01，=0=0，=1=1）S S0S10S1（v=Sv=S，w=0S1w=0S1，使用規(guī)則使用規(guī)則S0S1S0S1，= =，= =）0 0S1S100S1100S11（v=0S1v=0S1，w=00S11w=00S11，使用規(guī)則使用規(guī)則S0S1S0

13、S1，=0=0，=1=1）例例 文法文法G=（VN，VT，P，S）VN =標識符，字母，數(shù)字標識符，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= a, z z 0,0,99S=指出下面直接推導所使用的規(guī)則：指出下面直接推導所使用的規(guī)則： abcabc abc5abc52）長度為長度為n的推導（有限次推導）的推導（有限次推導） 若存在若存在v =w0 w1 . wn=w, (n0)， 則稱則稱v出出w（或或w到到v）. 記作記作 v w。3）若有若有v w，或或v=w， 則記為則記為v w+*例：例：G G： S0S1 S0S1， S01 S010S10S100S1100S11000

14、S111000S11100001111 00001111 即即 0S1 000011110S1 00001111也記作也記作 0S1 000011110S1 00001111+*1 1）句型）句型 設設GS是一文法是一文法，如果符號串如果符號串x是從是從識別符號識別符號推推導出來的，即導出來的，即S x，則稱則稱x是文法是文法GS的句型。的句型。*例：例：G G： S0S1， S01S 0S1 00S11 000S111 00001111*2 2）句子）句子x僅由僅由終結(jié)符號終結(jié)符號組成組成（即即S x，且且xVVT T* *），），則稱則稱x是是GS的句子的句子。3 3）語言）語言 由文法由

15、文法G G產(chǎn)生的所有句子組成的集合叫做文法產(chǎn)生的所有句子組成的集合叫做文法G G所成描述的語言，記為所成描述的語言，記為L(G)L(G)。 例：例：G G： S0S1， S01 L(G)=0n1n|n1 注：產(chǎn)生式中含有遞歸式，產(chǎn)生的句子是無窮的注：產(chǎn)生式中含有遞歸式，產(chǎn)生的句子是無窮的*L(G)=x|S x，其中其中S為文法的開始符號為文法的開始符號，且且x VVT T* * 例例: :文法文法GS：（1）SdAdAB（2）AaA（3）Aaa（4）BBBb（5）BL（G）=?G G生成的每個串都在生成的每個串都在L(G)L(G)中中L(G)L(G)中的每個串確實能被中的每個串確實能被G G生

16、成生成例：構(gòu)造生成語言例：構(gòu)造生成語言L= 的文的文法。法。分析：分析：n1n1，所以必須用遞歸規(guī)則。所以必須用遞歸規(guī)則。a a和和b b的的個數(shù)個數(shù) 一樣多，但一樣多，但c c的個數(shù)不同，所以將生成的個數(shù)不同，所以將生成含含 a,b a,b的部分與生成含的部分與生成含e e的部分分開，的部分分開，A A生成生成 abab，B B生成生成e.e. GZ:ZAB GZ:ZAB AaAb|ab AaAb|ab BeB| BeB|0, 1|inebainn4)4)文法的等價文法的等價 若若L L（G G1 1）=L=L（G G2 2），），則稱文法則稱文法G G1 1和和G G2 2是等價的。是等價

17、的。如文法如文法G G1 1AA：A0R A0R 與與 G G2 2SS：S0S1 S0S1 等價等價 A01 S01A01 S01 RA1 RA1七、文法的類型七、文法的類型 （1）0型文法型文法(短語文法短語文法)：對任一產(chǎn)生式對任一產(chǎn)生式，都有都有(V(VN NVVT T) )+ +， (V (VN NVVT T) )* * （2 2）1 1型文法型文法( (上下文有關(guān)文法上下文有關(guān)文法) )： 對任一產(chǎn)生式對任一產(chǎn)生式，都有都有| |， 僅僅僅僅 SS除除外。即外。即1 1AA2 21 12 2( (A A在在V VN N中中，其他在其他在V V* *中中，) )（3 3）2 2型文法

18、型文法（上下文無關(guān)文法上下文無關(guān)文法）： 對任一產(chǎn)生式對任一產(chǎn)生式，都有都有VVN N ， (V (VN NVVT T) )* * 即即AA( (A A在在V VN N中中，在在V V* *中中，) )（4 4）3 3型文法型文法（正規(guī)文法正規(guī)文法）：）：任一產(chǎn)生式任一產(chǎn)生式的形式都的形式都為為AaBAaB或或AaAa，其中其中AVAVN N ，BVBVN N ，aVaVT T 例：例：1 1型（上下文有關(guān)）文法型（上下文有關(guān)）文法 文法文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee 例：例：2 2型（上下文無關(guān)）文法型（上下文無關(guān)）文法 文法文法GS： SaB|bAaB

19、|bAAa|aS|bAAa|aS|bAABb|bS|aBBb|bS|aBB 文法文法GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0 例：定義標識符的例：定義標識符的3 3型（正規(guī)）文法型（正規(guī)）文法 文法文法GI：I lT lTI l lT lT lTT dT dTT l lT d d文法和語言文法和語言0 0型文法產(chǎn)生的語言稱為型文法產(chǎn)生的語言稱為0 0型語言型語言1 1型文法或上下文有關(guān)文法（型文法或上下文有關(guān)文法（ CSG CSG ）產(chǎn)生的語產(chǎn)生的語言稱為言稱為1 1型語言或上下文有關(guān)語言（型語言或上下文有關(guān)語言（CSLCSL）2 2型

20、文法或上下文無關(guān)文法（型文法或上下文無關(guān)文法（ CFG CFG ）產(chǎn)生的語產(chǎn)生的語言稱為言稱為2 2型語言或上下文無關(guān)語言（型語言或上下文無關(guān)語言（ CFL CFL ） 3 3型文法或正則（正規(guī)）文法（型文法或正則（正規(guī)）文法（ RG RG ）產(chǎn)生的產(chǎn)生的語言稱為語言稱為3 3型語言或正則（正規(guī)）語言（型語言或正則（正規(guī)）語言（ RL RL ）八、上下文無關(guān)文法及其語法樹八、上下文無關(guān)文法及其語法樹 上下文無關(guān)文法有足夠的能力描述現(xiàn)今程上下文無關(guān)文法有足夠的能力描述現(xiàn)今程序設計語言的語法結(jié)構(gòu)。序設計語言的語法結(jié)構(gòu)。 算術(shù)表達式算術(shù)表達式 語句語句 賦值語句賦值語句 條件語句條件語句 循環(huán)語句循

21、環(huán)語句 用于描述上下文無關(guān)文法的用于描述上下文無關(guān)文法的句型推導句型推導的的直觀方法直觀方法 例例: : GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的語法樹（推導樹）的語法樹（推導樹）葉子結(jié)點：樹中沒有子孫的結(jié)點。葉子結(jié)點：樹中沒有子孫的結(jié)點。從左到右讀出推導樹的葉子標記，所得的句從左到右讀出推導樹的葉子標記，所得的句型為推導樹的結(jié)果。也把該推導樹稱為該句型為推導樹的結(jié)果。也把該推導樹稱為該句型的語法樹。型的語法樹。推導過程中施用產(chǎn)生式的推導過程中施用產(chǎn)生式的順序順序 例例: GS:SaASASbAASSSaAba S a A S S

22、 b A a a b a句型句型aabbaa的語法樹（推導樹）的語法樹（推導樹）SaASaAaaSbAaaSbbaaaabbaa在推導的任何一步在推導的任何一步，其中其中、是句型，是句型，都是對都是對中的最左（右）非終結(jié)符進行替換。中的最左（右）非終結(jié)符進行替換。 最右推導被稱為最右推導被稱為。 由規(guī)范推導所得的句型稱為由規(guī)范推導所得的句型稱為SaASaAaaSbAaaSbbaaaabbaa（最右推導最右推導）SaASaSbASaabASaabbaSaabbaa（最左推導最左推導）SaASaSbASaSbAaaabAaaabbaa 例例: GS:SaASASbAASS Sa Aba問題：一個句

23、型是否對應唯一的一棵語法樹？問題：一個句型是否對應唯一的一棵語法樹？ 例：例：GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的兩個不同的最左推導的兩個不同的最左推導：推導推導2：E E*E i*E i*E+E i*i+E i*i+i推導推導1：E E+E E*E+E i*E+E i*i+E i*i+i3 3、二義文法、二義文法若一個文法存在若一個文法存在某個某個句子對應兩棵

24、不同的語法句子對應兩棵不同的語法樹，則稱這個文法是樹，則稱這個文法是二義二義的。的?；蛘?，若一個文法存在或者，若一個文法存在某個某個句子有兩個不同的句子有兩個不同的最左（右）推導，則稱這個最左（右）推導，則稱這個文法文法是是二義二義的。的。產(chǎn)生某上下文無關(guān)語言的每一個文法都是二義產(chǎn)生某上下文無關(guān)語言的每一個文法都是二義的，則稱此的，則稱此語言語言是是先天二義先天二義的。的。排除文法二義性的兩種方法：排除文法二義性的兩種方法：（1 1）在語義上加些限制（如優(yōu)先順序和結(jié)）在語義上加些限制（如優(yōu)先順序和結(jié)合律）。合律）。（2 2）重構(gòu)無二義性的文法。）重構(gòu)無二義性的文法。GE: E IGE: E I

25、 E E+E E E+E E EE E* *E E E (E) E (E)GE: E T|E+TGE: E T|E+T T F|T T F|T* *F F F F （E E）|i|i 練習：有文法練習：有文法GN： NSE|E S SD|D E 0|2|4|6|8|10 D 0|1|2|3|4|5|6|7|8|9（1）證明此文法有二義性證明此文法有二義性（2）此文法描述的語言是什么？）此文法描述的語言是什么？（3）試寫出另一文法，其產(chǎn)生的語言和）試寫出另一文法，其產(chǎn)生的語言和GN產(chǎn)產(chǎn)生的語言等價且是無二義性的。生的語言等價且是無二義性的。八、句型的分析八、句型的分析就是識別一個符號串是否為某文

26、法的就是識別一個符號串是否為某文法的句型，是某個推導的構(gòu)造過程。句型，是某個推導的構(gòu)造過程。在語言的編譯實現(xiàn)中，把完成句型分析的程序在語言的編譯實現(xiàn)中，把完成句型分析的程序稱為稱為或或。分析算法又稱。分析算法又稱識別識別算法算法。從左到右的分析算法從左到右的分析算法，即總是從左到右地識別，即總是從左到右地識別輸入符號串，首先識別符號串中的最左符號，輸入符號串，首先識別符號串中的最左符號，進而依次識別右邊的一個符號。進而依次識別右邊的一個符號。1、自上而下的語法分析：從文法的開始符號出發(fā)，、自上而下的語法分析：從文法的開始符號出發(fā)，反復使用各種產(chǎn)生式，尋找與輸入符號串匹配的推反復使用各種產(chǎn)生式，

27、尋找與輸入符號串匹配的推導。導。 例：文法例：文法G：S cAd A ab A a識別輸入串識別輸入串 w = cabd 是否該文法的句子是否該文法的句子SSScAdcAd a b推導過程推導過程：cabdcAd S2、自下而上的語法分析自下而上的語法分析：從輸入符號串開始，逐從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。步進行歸約，直至歸約到文法的開始符號。 例：文法例：文法G：S cAd A ab A a識別輸入串識別輸入串 w = cabd 是否該文法的句子是否該文法的句子SAA c a b d c a b d c a b d 規(guī)約過程規(guī)約過程：cabdcAd S3 3、句型

28、分析的有關(guān)問題、句型分析的有關(guān)問題1 1）如何選擇使用哪個產(chǎn)生式進行推導？）如何選擇使用哪個產(chǎn)生式進行推導？假定要被代換的最左非終結(jié)符號是假定要被代換的最左非終結(jié)符號是V V，且有且有n n條條規(guī)則：規(guī)則：VA1|A2|AnVA1|A2|An，那么如何確定用哪個那么如何確定用哪個右部去替代右部去替代V V？2 2）如何識別可歸約的串？如何識別可歸約的串？在自下而上的分析方法中，在分析程序工作的在自下而上的分析方法中，在分析程序工作的每一步，都是從當前串中選擇一個子串，將它每一步，都是從當前串中選擇一個子串，將它歸約到某個非終結(jié)符號，該子串稱為歸約到某個非終結(jié)符號，該子串稱為“可歸約可歸約串串”（“4 4、短語、直接短語、句柄的定義：、短語、直接短語、句柄的定義：文法文法GS，是是G的一個句型的一個句型，如果如果： S A且且A 則稱則稱是句型是句型相對于非終結(jié)符相對于非終結(jié)符A的的。若有若有A 則稱則稱是句型是句型相對于規(guī)則相對于規(guī)則A的的。一個句型的一個句型的最左直接短語最左直接