第 4 講,編譯原理,西北農(nóng)林科技大學(xué)本科教程,主講教師：趙建邦,第三章 語法分析,3.1 文法和語言 3.2 推導(dǎo)與語法樹 3.3 自頂向下的語法分析 3.4 自底向上的語法分析 3.5 規(guī)范規(guī)約的自底向上語法分析方法,第三章語法分析 3.1 文法和語言 文法和語言的基本概念 形式語言分類（4類） 正規(guī)表達(dá)式與上下文無關(guān)文法 重點(diǎn)掌握 正規(guī)表達(dá)式與上下文無關(guān)文法,本講目標(biāo),定位 語法分析是編譯過程的第二個階段，也是核心部分 任務(wù) 根據(jù)語言的語法規(guī)則對單詞序列進(jìn)行語法分析，識別合法的語法單位（如表達(dá)式、語句、程序段等），若不存在語法錯誤則給出正確的語法結(jié)構(gòu) 理論依據(jù)：上下文無關(guān)文法 方法 自頂向下分析（推導(dǎo)：開始符號 句子） 自底向上分析（規(guī)約：句子 開始符號）,語法分析：,3.1 文法和語言,文法(Grammar)是程序語言的生成系統(tǒng)，用文法可以精確定義一個語言，并依據(jù)該文法構(gòu)造出識別這個語言的自動機(jī) 文法對程序語言和編譯程序的構(gòu)造具有重要意義，如程序語言的詞法可用正規(guī)文法描述，語法可用上下文無關(guān)文法描述，而語義則要借助于上下文有關(guān)文法描述,3.1 文法和語言,3.1.1 文法和語言的基本概念 1、語言 通常我們用表示字母表，字母表中的每個元素稱為字符或符號。不同語言的字母表可能是不同的，程序語言的字母表通常是ASCII字符集。 由字母表中的字符所組成的有窮系列稱為上的字符串或字，字母表上的所有字符串(包括空串)組成的集合用*表示。 那么，對字母表來說，*上的任意一個子集都稱為上的一個語言，記為L( )，該語言的每一個字符串稱為語言L的一個語句或句子。,3.1 文法和語言,3.1.1 文法和語言的基本概念 1、語言,例如，設(shè) = a, b, c，則: L = , a, aa, ab, aaa, aab, aba, abb, 為上的一個語言。 如果a表示字母，b表示數(shù)字，c看做其它符號，則L即是程序語言中的標(biāo)識符集，其中的每個標(biāo)識符就是標(biāo)識符集中的一個句子。,3.1 文法和語言,3.1.1 文法和語言的基本概念 2、文法 （定義） 文法通常表示成四元組GS = (VT，VN，S，): (1) VT為終結(jié)符號集，這是一個非空有限集，它的每個元素稱為終結(jié)符號。 (2) VN為非終結(jié)符號集，它也是一個非空有限集，其每個元素稱為非終結(jié)符號，且有VTVN = ； (3) S為文法開始符，是一個特殊的非終結(jié)符號，即SVN；,3.1 文法和語言,3.1.1 文法和語言的基本概念 2、文法（文法中的基本概念） 終結(jié)符號：是指語言不可再分的基本符號，通常是一個語言的字母表；終結(jié)符代表了語法的最小元素，是一種個體記號。 非終結(jié)符號：也稱語法變量，它代表語法實(shí)體或語法范疇；非終結(jié)符代表一個一定的語法概念，因此，一個非終結(jié)符是一個類、一個集合。,注意： 1、字母表可以稱為文法中的終結(jié)符集 2、非終結(jié)符不能是字母表中的字符,3.1 文法和語言,3.1.1 文法和語言的基本概念 2、文法 （定義） 文法通常表示成四元組GS = (VT，VN，S，): (4) 是產(chǎn)生式的非空有限集，其中每個產(chǎn)生式(或稱規(guī)則)是一序偶(，)，通常寫作 或 := 讀作“產(chǎn)生”、 “是”或“定義為”。在此，為產(chǎn)生式的左部，而為產(chǎn)生式的右部，、是由終結(jié)符和非終結(jié)符組成的符號串，(VTVN) + 且至少有一個非終結(jié)符，而(VTVN) *。,3.1 文法和語言,3.1.1 文法和語言的基本概念 2、文法（文法中的基本概念） 文法開始符號S：是一個特殊的非終結(jié)符，它代表文法所定義的語言中我們最終感興趣的語法實(shí)體，即語言的目標(biāo)，而其它語法實(shí)體只是構(gòu)造語言目標(biāo)的中間變量 產(chǎn)生式： (也稱產(chǎn)生規(guī)則或規(guī)則)是定義語法實(shí)體的一種書寫規(guī)則。一個語法實(shí)體的相關(guān)規(guī)則可能不止一個。,P1 P2 Pn,如果：,P 1 | 2 | | n,其中，每個i(i=1, 2, , n)稱為P的一個候選式，直豎“ | ”讀為“或”，它與“”一樣是用來描述文法的元語言符號(即不屬于的字符)。,3.1 文法和語言,例如，定義一個僅包含加和乘運(yùn)算的表達(dá)式的文法GE: GS = (VT，VN，S，): VT =+ * ( ) i VN = E, T, F S = E 為以下產(chǎn)生式的集合： EE + T | T TT * F | F F (E)|i 兩種文法都可以識別包含加和乘運(yùn)算的表達(dá)式，它們的區(qū)別將在后面的課程中講解,VT =+ * ( ) i VN = E S = E : Ei| E+E| E*E |(E),3.1 文法和語言,3.1.1 文法和語言的基本概念 關(guān)于文法表示的約定： 在此后的討論中，用大寫字母A、B、S、E等表示非終結(jié)符，用小寫字母a、b、i、j等表示終結(jié)符，并用希臘字母等表示文法符號串，即、等均屬于(VTVN)*。,2.3 正規(guī)表達(dá)式與優(yōu)先自動機(jī)簡介,例3.1 試構(gòu)造產(chǎn)生標(biāo)識符的文法。 解答 首先，標(biāo)識符是以字母開頭的字母數(shù)字串， 用L表示“字母”類非終結(jié)符， 用D表示“數(shù)字”類非終結(jié)符，,T L | D （單個的字母或數(shù)字字符）,S T | ST （字母或數(shù)字串）,其次，如果用S表示“字母數(shù)字串”類，則T是一字母或數(shù)字，ST也是字母數(shù)字串，即有,L a | b | | z D 0 | 1 | | 9,而用T表示“字母或數(shù)字”類非終結(jié)符，則有：,其中，產(chǎn)生式ST | ST是一種左遞歸形式，由它可以產(chǎn)生一串T,課本例題,最后，作為“標(biāo)識符”的非終結(jié)符I，它或者是一單個字母，或者為一字母后跟字母數(shù)字串，即 I L | LS,因此，產(chǎn)生標(biāo)識符的文法GI為： GI = ( VT， VN， I，): = (a, b, , z, 0, , 9, I, S, T, L, D, I, ) : I L | LS S T | ST T L | D L a | b | | z D 0 | 1 | | 9,課本例題,解答 根據(jù)題意，我們可以將奇數(shù)劃分為如圖3-1所示的三個部分，即最高位允許出現(xiàn)19，用非終結(jié)符B表示；中間部分可以出現(xiàn)任意多位數(shù)字09，每一位用非終結(jié)符D表示；最低位只允許出現(xiàn)1、3、5、7、9等奇數(shù)，用A表示。,例3.2 寫一文法，使其語言是奇數(shù)集合，但不允許出現(xiàn)以0打頭的奇數(shù)。,課本例題,圖3-1 奇數(shù)劃分示意,課本例題,GN = (0, 1, , 9, N, A, M, B, D, N, ) : NA | MA /*一位數(shù)字 | 多位數(shù)字*/ MB | MD /*僅兩位數(shù)字(無中間位) | 多于兩位數(shù)字*/ A1 | 3 | 5 | 7 | 9 B1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 D0 | B,由于中間部分可出現(xiàn)任意位，所以另引入了一個非終結(jié)符M，它包括最高位和中間位部分。假定開始符為N，則可得到文法GN為,課本例題,3.1 文法和語言,3.1.1 文法和語言的基本概念 3、文法產(chǎn)生的語言 設(shè)文法GS = (VT, VN, S, )，且、(VTVN)*，如果存在產(chǎn)生式A (VTVN)*)，則稱A可直接推出，即 其中 “=”表示直接推導(dǎo)，是應(yīng)用產(chǎn)生規(guī)則進(jìn)行推導(dǎo)的記號，這里僅使用一次規(guī)則 注意“=”與“”不同，“”是產(chǎn)生式中的定義記號。直接推導(dǎo)是指對文法符號串A中的非終結(jié)符A用相應(yīng)的產(chǎn)生式A的右部來替換，從而得到,A =,3.1 文法和語言,推導(dǎo)的說明： (1)如果1可直接推出2，2可直接推出3，n-1可直接推出n ，即存在一個自1至n的推導(dǎo)序列：1=2=3=n(n0)，則稱1可推導(dǎo)出n，記為1 =n，它表示從1出發(fā)經(jīng)過一步或若干步可推導(dǎo)出n。 (2) 如果記1 = 1， 1 = n則表示從1出發(fā)，經(jīng)過0步或若干步可推導(dǎo)出n；也即1 = n，意味著或者1 =n，或者 1 =n。這個概念叫做“廣義推導(dǎo)” 顯然：直接推導(dǎo)的長度是1，推導(dǎo)的長度1， 廣義推導(dǎo)的長度0,+,0,*,*,+,3.1 文法和語言,推導(dǎo)的舉例： 例如，對下面的文法GE： E E + E | E * E | (E) | i (3.1) 其中，惟一的非終結(jié)符E可以看成是代表一類算術(shù)表達(dá)式?？梢詮腅出發(fā)進(jìn)行一系列的推導(dǎo)，如表達(dá)式 i+i*i 的推導(dǎo)如下：,E=E+E = E+E*E = E+E*i = E+i*i =i+i*i,注意：在每一步推導(dǎo)過程中，只能對其中的一個非終結(jié)符用其對應(yīng)的產(chǎn)生式右部的一個候選式來替換。,3.1 文法和語言,3.1.1 文法和語言的基本概念 句型：假定GS是一個文法，S是它的開始符號，如果S=，(VTVN)*，則稱是文法GS的一個句型； 句子：如果 VT *，則稱是文法GS的一個句子。僅含終結(jié)符的句型是一個句子。 由定義可知，開始符S本身只能是文法的一個句型而不可能是一個句子； 句子是特殊的句型。 上面推導(dǎo)出的i+i*i是文法GE的一個句子(當(dāng)然也是一個句型)，而E+E、E+E*E、E+E*i和E+i*i都是文法GE的句型 思考：文法 GS: SaB|Bb Ba|b 的句型和句子有多少個？,*,3.1 文法和語言,3.1.1 文法和語言的基本概念 文法產(chǎn)生的語言：對于文法GS，它所產(chǎn)生的句子的全體稱為由文法GS 產(chǎn)生的語言，記為L(G)，即有： L(G) = | S=且 VT * 注意： (1) S至少進(jìn)行一次推導(dǎo)； (2) S所推導(dǎo)出的必須全部由終結(jié)符組成； (3) 當(dāng)文法給定，語言也就唯一地確定，即G L(G) ； 給定一個語言，它所對應(yīng)的文法不是唯一的； (4) L(G)是VT *的子集，屬于VT *的符號串不一定屬 于L(G)；,+,3.1 文法和語言,3.1.2 形式語言分類 語言學(xué)家Noam Chomsky于1956年首先建立了形式語言的描述，定義了四類文法及相應(yīng)的形式語言，它對程序語言的設(shè)計(jì)、編譯方法、計(jì)算復(fù)雜性等方面都產(chǎn)生了重大影響： 0型文法與0型語言(對應(yīng)圖靈機(jī)) 1型文法與1型語言(對應(yīng)線性界限自動機(jī)，自然語言) 2型文法與2型語言(對應(yīng)下推自動機(jī)，程序設(shè)計(jì)語言) 3型文法與3型語言(對應(yīng)有限自動機(jī)),*,3.1 文法和語言,3.1.2 形式語言分類 1、0型文法與0型語言 如果文法GS的每一個產(chǎn)生式具有下列形式： 其中，V*VNV* (注：V = VNVT)，即至少含有一個非終結(jié)符；V*；則稱文法GS為0型文法或短語文法，記為PSG(Phrase Structure Grammar)。0型文法相應(yīng)的語言稱為0型語言或稱遞歸可枚舉集，它的識別系統(tǒng)是圖靈(Turing)機(jī)。,例如： S ACaB Ca aaC CB DB CB E aD Da AD AC aE Ea AE ,3.1 文法和語言,3.1.2 形式語言分類 2、1型文法與1型語言 文法GS的每一個產(chǎn)生式，均在0型文法的基礎(chǔ)上增加了字符長度滿足| | |的限制，則稱文法GS為1型文法或上下文有關(guān)文法，記為CSG。1型文法相應(yīng)的語言稱為1型語言或上下文有關(guān)語言，它的識別系統(tǒng)是線性界限自動機(jī)。 1型文法的等價定義 文法GS的每一個產(chǎn)生式具有下列形式： A 其中，、V*，AVN， V+ 。顯然，它滿足前述定義的長度限制，但它更明確地表達(dá)了上下文有關(guān)的特性，即A必須在、的上下文環(huán)境中才能被所替換。,3.1 文法和語言,3.1.2 形式語言分類 3、2型文法與2型語言 文法GS的每一個產(chǎn)生式具有下列形式： A 其中，A VN ，V*，則稱文法GS為2型文法或上下文無關(guān)文法，記為CFG。2型文法相應(yīng)的語言稱為2型語言或上下文無關(guān)語言，它的識別系統(tǒng)是下推自動機(jī)。 例：GS=(a,b,S S, SaSb , Sab ) 產(chǎn)生的語言為：,3.1 文法和語言,3.1.2 形式語言分類 3、2型文法與2型語言 上下文無關(guān)文法有足夠能力描述現(xiàn)今程序設(shè)計(jì)語言的語法結(jié)構(gòu)。 例如：產(chǎn)生條件句的文法片段 語句-if 條件 then 語句 | if 條件 then 語句 else 語句 | 其他語句,3.1 文法和語言,3.1.2 形式語言分類 4、3型文法與3型語言 文法GS的每個產(chǎn)生式具有下列形式： A a 或 A aB 其中，A、B VN ，a VT *，則文法GS稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應(yīng)的語言稱為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動機(jī)。3型文法還可以呈現(xiàn)左線性形式： A a 或 A Ba,3.1 文法和語言,3.1.2 形式語言分類 4、3型文法與3型語言 文法GS的每個產(chǎn)生式具有下列形式： A a 或 A aB 其中，A、B VN ，a VT *，則文法GS稱為3型文法、正規(guī)文法或右線性文法，記為RG。3型文法相應(yīng)的語言稱為3型語言或正規(guī)語言，它的識別系統(tǒng)是有限自動機(jī)。3型文法還可以呈現(xiàn)左線性形式： A a 或 A Ba,3.1 文法和語言,3.1.2 形式語言分類 5、4類文法的關(guān)系與區(qū)別 關(guān)系： (1) 從0型文法到3型文法的限制逐漸增； (2) 13型文法都屬于0型文法； (3) 2、3型文法不一定屬于1型文法：因?yàn)?型文法不允許存在“A ”形式的產(chǎn)生式，則：如果2、3文法不含有類似產(chǎn)生式，則該文法屬于1型文法。,3.1 文法和語言,3.1.2 形式語言分類 5、4類文法的關(guān)系與區(qū)別 區(qū)別： (1) 1型文法中不允許有形如“A”的產(chǎn)生式存在，而2、3型文法則允許形如“A”的產(chǎn)生式存在； (2) 0