編譯原理及其習題解答武漢大學出版社課件.ppt

1,第二章 文法和語言,要點(本章是基礎) 1、概念:文法,推導,直接推導,最左(右)推導,產(chǎn)生式,句型,短語,直接短語,句柄,語法樹,規(guī)范推導,二義文法等 2、4種文法的定義、文法的構造和文法的推導 3、語法樹的構造和最左（右）推導； 4、二義文法、二義性的證明； 5、句型分析；,2,詞法規(guī)則：自動機 語法規(guī)則：上下文無關文法,3,引言,語言包括語法和語義兩方面。 語法是一組規(guī)則，用以判斷什么樣的符號序列是合法的； 語義指含義，如變量的類型、作用域是否符合正確的語法。常把程序設計語言的語義分為二類：靜態(tài)語義和動態(tài)語義。靜態(tài)語義是一系列限定規(guī)則，并確定哪些合乎語法的程序是合適的；動態(tài)語義（或稱運行語義、執(zhí)行語義），表明程序要做些什么，要計算什么。 闡明語法的一個工具是文法，常采用上下文無關文法作為程序設計語言語法的描述工具。,4,補充： 文法的直觀概念(1/5),描述一種語言，無非是說明這種語言的句子。如果該語言所含的句子是有限的，那么只要一一列舉出即可；若是無限的，則存在如何給出有窮表示的問題。但無論如何，某語言的句子總是存在著一種組成結構，即所謂的規(guī)則（或稱文法）。 文法：描述語言的語法結構的形式規(guī)則（即語法規(guī)則）。,5,直觀文法舉例(2/5),例如：簡單的漢語句子的構成規(guī)則 := := | := 我 | 你 | 他 :=王明| 大學生|工人|英語 := :=是 |學習 := | 則 “我是大學生”是句子,6,“我是大學生”的推導過程： 我 我 我是 我是 我是大學生 依次可以推導出句子“王明是大學生”、“我學習英語”等等,推導過程(3/5),7,程序設計語言對文法的要求(4/5),這些規(guī)則必須是準確的，易于理解的，且應當有相當強的描述能力，足以描述各種不同的結構。,8,文法作用(5/5),（1）定義句子的結構； （2）用適當條數(shù)的規(guī)則把語言的全部句子描述出來，以有窮集合刻劃無窮集合。,9,2 符號串及其運算 （1）符號串：由字母表中的符號組成的任何有窮序列。 說明: 字母間的順序 不同順序組成的符號串是不同的； （2）符號串長度 符號串內(nèi)所含符號的個數(shù)，若x=string,則|x|=6; 其中不含任何符號的符號串稱為空符號串，長度| |0,2.1 語言成分,1 字母表（符號表）與符號 元素（或稱符號）的非空有窮集合，用符號表示。 不同語言有不同的字母表。如漢語包括漢字、數(shù)字、標點符號等；C語言包括字母、數(shù)字和保留字等等。,10,符號串的運算(1/3),符號串的頭尾，固有頭和固有尾： 設 z=xy 是一個符號串，則x是z的頭，y是z的尾。如果x是非空的，那么y是是固有尾；如果y是非空的，那么x是固有頭。,例：z=abc，則 z的頭：、a、ab、abc； 固有頭： 、a、ab； z的尾：、c、bc、abc； 固有尾： 、c、bc；,當我們對符號z=xy 的頭感興趣而對其余部分不感興趣時，我們可以采用省略寫法：z=x。如果只是為了強調x在符號串中的某處出現(xiàn)，則可表示為：z=x；符號t是符號串z的第一個符號，則表示為：z=t。,11,(3)符號串的連接,設x和y是符號串，它們的連接xy是把y的符號寫在x的符號之后得到的符號串。 例如：x=abc，y=DEF，則xy=abcDEF；,若| x | = n，| y |m，則| xy | = n+m,對任意的符號串x，有 x = x = x,12,（4） 符號串集合的乘積,設A、B是兩個符號串的集合，則AB表示A與B的乘積，定義為： AB=xy|xA,yB 如：若A=ab,c, B=d,efg,則AB=abd,abefg,cd,cefg 特別地，有：A=A=A 空集 表示不含任何元素的空集。 有： A=A = 請區(qū)別： ，三種表示方法的含義,13,（5） 符號串的方冪,同一符號串的連接可以寫成方冪的形式。 設x是符號串，把x自身連接n次得到的符號串z，即z=xxxx，稱為符號串x的方冪，記作z=xn，有： x0= x1= x x2= xx x3= xxx 當n0時， xn x xn-1 = xn-1 x,14,（6）符號串集合的方冪,同一符號串集合的連接也可以寫成方冪的形式。 設符號串集合為A，則有： A0= A1= A A2= AA A3= AAA 當n0時， An A An-1 = An-1 A 例如：A=ab，c，則AA= AAA= ,15,（7）符號串集合的正閉包,設符號串集合為A，則A的正閉包記為A+ ，定義為： A+ = A1 A2 An 表示A上所有有窮長串的集合 例如：A=ab，c，AA= ， AAA= ,（8）符號串集合的自反閉包,設符號串集合為A，則A的自反閉包記為A* ，定義為： A* = A0 A1 A2 An 即A* = A0 A+ = A+ 例如： A= a,b，則 A*=, a, b, aa, ab, ba, bb, aaa, ,A+ = A* A = AA*,16,2.2 產(chǎn)生式文法和語言,2.2.1 文法的形式定義是一個四元組 G =（VN，VT，P，S） VN 非終結符號集，非終結符號代表的是語法范疇，也就是它是一類（或集合）的記號，而不是一個個體記號。如“表達式”、“語句”、“分程序”等等，都是表達一定的語法概念。因此，每個非終結符表示一定符號串的集合（由終結符和非終結符 組成）；(如簡單漢語句子中。）,VT 終結符號集合，終結符是構成語言的基本符號，也就是說，它是一個語言的不可再分的基本符號；,P 產(chǎn)生式（或稱規(guī)則,重寫規(guī)則,生成式）集合。所謂產(chǎn)生式是定義語法范疇的一種書寫規(guī)則。一個產(chǎn)生式的形式是 （或:= )，其中 “”讀為“是”或“定義為”； 產(chǎn)生式的左部 (VNVT )*且至少含有一個非終結符號，右部(VNVT)* ,即由終結符或（與）非終結符組成的一符號串，允許是空字,17,2.2 產(chǎn)生式文法和語言,例如：簡單的漢語句子的構成規(guī)則 := := | := 我 | 你 | 他 :=王明| 大學生|工人|英語 := :=是 |學習 := | 則 “我是大學生”是句子,18,文法的形式定義,S 開始符號，即文法的第一個非終結符。 開始符號代表了所定義的語言中我們最感興趣的語法范疇，如在程序語言中，我們感興趣的是“程序”,注意： 1、 VN VT 即不含公共元素 ； 2 、產(chǎn)生式是有限的； 3、開始符號S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次； 4、為書寫方便，若干個左部相同的產(chǎn)生式如： P1, P2，Pn 合并成： P1|2|n 其中i稱為P的一個候選式。,19,文法定義舉例1,例2.1 表示算術表達式的文法描述：G1 =（VN，VT，P，S） 其中VNE VT =i , +,*, ( , ) P=E i , E E + E , E E * E , E ( E ) S=E 或者直接寫為： G1 =(E, i , +,*, ( , ) , E i , E E + E , E E * E , E ( E ) , E ),20,文法定義舉例2,例2 文法G =（VN，VT，P，S） 其中VN標識符，字母，數(shù)字， VT a, b, c, , x, y, z, 0,1, , 8, 9 P= | | , a|b|c|x|y|z, 0|1|2|8|9 S = ,21,用文法定義語言的中心思想是：從文法的開始符號出發(fā)，反復連續(xù)使用產(chǎn)生式，對非終結符施行替換和展開。 例如文法G：E E+E | E*E | ( E ) | i，其中唯一非終結符E可以看成是代表一類算術表達式。 從E出發(fā)，進行一系列的推導，推出種種不同的算術表達式。如根據(jù)上述規(guī)則可推出 ( i+i )： E = ( E )= ( E+E )= ( i+E )= ( i+i) 我們稱這樣的一串替換是從E推出( i+i )的一個推導，這個推導提供了一個證明，證明( i+i )是文法G所定義的一個算術表達式。,2.2.2 文法的推導,22,有關推導的定義,定義2.3 直接推導 = 若A直接推導出 ，即 A=，當且僅當A-是一個產(chǎn)生式，且、(VNVT)* 符號 =指推導一步，即推導每前進一步總是引用一條規(guī)則（產(chǎn)生式）,定義2.4 長度為n（n1）的推導 若存在直接推導序列a1= a2= =an，則稱a1可推導出an。 a1 an 表示：從a1出發(fā)經(jīng)過一步或若干步，可推導出an 。,定義2.5 長度為n（n0）的推導 a1 an 表示：從a1出發(fā)經(jīng)過0步（ a1 an ）或若干步，可推導出an 。,23,2.2.3 句型、句子、語言,例1：證明終結符號串( i*i+i )是文法G：E E+E | E*E | (E)| i的一個句子 證明： E =( E ) =(E+E)=(E*E+E) =(i*E+E) =(i*i+E)=(i*i+i) 是從開始符號E到( i*i+i )的一個推導。 其中E、(E)、(E+E)、(E*E+E)、 (i*E+E) 、 (i*i+E) 、 (i*i+i)都是這個文法的一個句型,1.句型：設GS是一個文法，S是它的開始符號，若S ,則稱是文法GS的句型。 2.句子：僅含終結符的句型是一個句子，即S ，VT*, 則是句子。 3.語言：文法G所產(chǎn)生的句子的全體是一個語言，記作L(G) L(G)=|S ,且VT*,24,語言的例子,例2：文法G2 A ：A bA | cc，證明cc、bcc、bbcc屬于L(G2)。 證明： A=cc， A= Ba=bcc， A =bA =bbA = bbcc cc、bcc、bbcc、是屬于L(G2)的,例3：文法GS： (1) S0S1；(2) S01。GS的語言是什么？ 解：對第一個產(chǎn)生式使用n-1次，然后使用第二個產(chǎn)生式一次，得到： S = 0S1 = 00S11= = 0n-1S1n-1 = 0n1n 因此L(G)=0n1n|n 1,例4：下列文法的語言是什么？ GS=（S, , S - , S ） GA=（A， ， ，A ）,25,2.2.4 文法的等價,若L(G1) = L(G2)，則稱文法G1和G2是等價的 例1：G1=(VN, VT, P, S)， VN =S， VT =0, 1，P由下列產(chǎn)生式組成： (1) S0S1； (2) S01； G2=(VN, VT, P, A)， VN =A, R， VT =0, 1，P由下列產(chǎn)生式組成： (1) A 0R ; (2) A 01; (3) R A1,26,什么是遞歸文法？,1.遞歸規(guī)則：規(guī)則右部有與左部相同的符號 對于 U - xUy 若x=,即U - Uy，左遞歸； 若y=,即U - xU，右遞歸；,2.遞歸文法：文法G，存在U VN 若 U=U, 則G為遞歸文法； 若 U=U, 則G為左遞歸文法； 若 U=U, 則G為右遞歸文法；,27,4. 遞歸文法的優(yōu)點：可用有窮條規(guī)則，定義無窮語言,例：對于前面給出的標識符的文法是有遞歸文法，用y有限條規(guī)則就可以定義出所有的標識符。若不用遞歸文法，那將要用多少條規(guī)則呢？,!,3. 左遞歸文法的缺點：不能用自頂向下的方法來進行語 分析,會造成死循環(huán),28,2.3 文法的分類,2.3.1 文法分類 喬姆斯基（Chomsky)建立的形式語言對計算機科學的發(fā)展具有深刻的意義。他把文法分成四種類型：0型、1型、2型和3型。0型強于1型，1型強于2型，2型強于3型，它們的差別在于對產(chǎn)生式施加不同的限制。,29,定義 0型文法（或稱短語文法, phrase structure grammar,PSG）,G=( VN, VT, P, S)是0型文法是指： 若它的每個產(chǎn)生式是這樣一種結構: (VNVT)+且至少含有一個非終結符， (VNVT)*。 任何0型文法都是遞歸可枚舉的。 0型文法的能力相當于圖靈機（計算機的一種簡單的理論模型）。 稱L為遞歸可枚舉的：若存在一個產(chǎn)生L的過程。 稱L為遞歸的：若存在一個識別L的算法。,30,定義 1型文法（或稱上下文有關文法,CSG Context Sensitive Grammar）,如果對0型文法加以以下的限制，則可得到1型文法。 設G=( VN, VT, P, S)為一文法，若G的任何產(chǎn)生式 均滿足| | (指符號串的長度)，僅僅S 例外。 課本P24例2.2。,例：設G=(VN, VT, P, S)， VN =S, B, E， VT =a, b, e，P由下列產(chǎn)生式組成： (1) S aSBE ； (2) S aBE ; (3) EB BE ; (4) aB ab ; (5) bB bb ; (6) bE be ; (7) eE ee ; 求 GS的語言是什么。,31,接上頁例子,分析：條產(chǎn)生式中只有第條具有遞歸性，其它的產(chǎn)生式最終都向終結符靠攏。 注意： S aSBE 與S0S1的相似性，都可用同一模板來表示S S 使用產(chǎn)生式(1) n-1次，得推導序列：S an-1S(BE)n-1； 使用產(chǎn)生式(2) 一次，得到： S an(BE)n； 使用產(chǎn)生式(3)的右部替換EB，使最終得到的串中，所有的B都先于所有的E，即S anBnEn；,32,接上例,使用產(chǎn)生式(4)一次，得到S an bBn1En； 使用產(chǎn)生式(5) n-1次，得到S an bnEn； 使用產(chǎn)生式(6) 一次，得到S an bn eEn-1； 使用產(chǎn)生式(7) n-1次，得到S an bn en； 因此，L(G)=an bn en | n 1,說明：上述分析中，步驟是關鍵一步，否則不能推導出終結符號串。例如假設n=3，S aaaBEBEBE aaaBBEEBE aaabBEEBE aaabbEEBE aaabbeEBE aaabbeeBE,33,上下文有關，顧名思義就是對非終結符進行替換時必須考慮上下文。例如，1型文法G的產(chǎn)生式也可寫成A ，其中、都在(VNVT)*中，且 ，A VN ，則說明了非終結符A必須在、這樣一個上下文環(huán)境中才可以替換。 上下文有關文法能生成anbncn類特征的語言。但它不能描述L=c|(a|b)*類語言。,對上下文有關文法的說明,34,定義 2型文法（或稱上下文無關文法，CFG Context Free Grammar）,設G=( VN, VT, P, S)為一文法，若G的任何產(chǎn)生式形似A ，其中A VN， (VNVT)+ 。,例：G=(S,A,B,a,b,P,S)，其中P由下列產(chǎn)生式組成 SaB|bA Aa|aS|bAA Bb|bS|aBB 例：G=(VN, VT, P, S)， VN =S， VT =0, 1，P由下列產(chǎn)生式組成： (1) S0S1； (2) S01；,35,上下文無關文法的說明,上下文無關，顧名思義就是非終結符的替換可以不必考慮上下文。由于這種文法對程序已基本可以描述，因此，上下文無關文法常簡稱為文法。 上下文無關文法最多能生成anbn類特征的語言，不能生成anbncn類特征的語言。,36,設G=( VN, VT, P, S)為一文法，若G的任何產(chǎn)生式A 或A B ，其中A、B VN ， VT* 。 對任何正規(guī)文法G，都可以設計一個不確定的有窮自動機NFA，它能夠而且只能夠識別G的語言。,定義 3型文法（或稱正規(guī)文法，RG Regular Grammar）,例：文法G=(S,A,B,0,1,P,S)，其中P由下列產(chǎn)生式組成 S 0A|1B|0 A 0A|1B|0S B 1B|1|0,37,左線性文法,設G=( VN, VT, P, S)為一文法，若G的任何產(chǎn)生式A或A B ，其中A、B VN ， VT* 。,左線性文法=右線性文法（非嚴格的轉換） 設左線性文法為G=( VN, VT, P, S)，右線性文法為G=( VN, VT, P, S)，其中 VN= VN+S,P轉化方式為：,38,2.3.2 文法分類的意義,自動機 具有有窮描述的某種機器，對于給定文法，可接收某個終結符號串，并確定是否能從該文法推導出來。 分析器 判定（分析）一個終結符號串是否是某個文法的句子，給出給定串的推導序列，完成此工作的自動機，稱為分析器。 正規(guī)文法與自動機 自動機由一個有窮狀態(tài)集和一個狀態(tài)對偶之間的轉換集組成。 CFG與自動機 CFG可以由下推自動機來識別。,39,文法分類的意義,文法的分類，對于實現(xiàn)程序設計語言的編譯程序， 具有重要意義。 語言的詞法規(guī)則：用正規(guī)文法（RG）描述。 語言的語法規(guī)則：局部語法用CFG描述； 全局語法用CSG描述。 語言的語義描述：CSG（實際定義采用CFG）。 編譯程序在實現(xiàn)時，一般采用CFG識別技術（易實現(xiàn)，高效）。,40,2.3.3 文法舉例,例2.6 1型文法G6 = ( VN, VT, P, S)，其中 VN S，X，Y，Z VT =x, y, z P= S-xSYZ|xYZ, xY-xy, yY-yy, yZ-yz, ZY-YZ, zZ - zz L(G6)為？,例2.7 2型文法G7 = ( VN, VT, P, S)，其中 VN S，T VT =a, b, c, d P= S-aTd, T-bT | cT | b | c,L(G6) = xnynzn | n0 ,L(G7) = ad | b, c+ ,41,2.3.3 文法舉例(2),例2.8 2型文法G8 = ( VN, VT, P, B)，其中 VN B VT = ( , ) P= B - ( B ) | BB | ( ) ,例2.9 2型文法G9 = ( VN, VT, P, S)，其中 VN S VT =0 , 1 P= S-0S1 , S - 01,L(G8) = (n )n (m )m (k )k | n0, m=0, k=0 ,L(G9) = 0n 1n | n0 ,42,2.3.3 文法舉例(3),例2.10 所有以0開頭，以零個或多個10組成的符號串的語言。 （1）右線性文法 G10 S：S - 0A A -10A | （2）左線性文法 G11 S：S - S10 | 0 （3）正規(guī)文法 G12 S：S - 0B | 0 B -1S,43,2.3.4 文法的構造（補充）,以an、anbn、anbncn、r0|1*的構造為基礎，以它們?yōu)橐罁?jù)來構造其它文法。 給出下面語言相應的文法 1、L1=abna | n 0； 2、L2=an bn+mcm | m,n 1； 3、L3=anbnci | n 1，i 0； 4、L4=aibncn | n 1，i 0； 5、L5=anbncn|n 1 ,對文法的構造的求解要多做練習。,44,文法的構造的分析（補充）,類型：A A或A A對應于an| n 1類 A A對應于anbcn| n 1類 分步：先用A A對應于an(BC)n| n 1，然后再通過改變排列順序，最終實現(xiàn) anbncn| n 1類,45,文法構造的方法（補充）,分析所用文法的類型 對照典型的幾種文法構造方法，來指導構造新的文法 利用模塊化設計思想來指導構造過程 注意邊界問題,46,文法的構造舉例(1/3),1、L1=abna | n 0； 對應模板： A A或A A 劃分模塊：bn 2、L2=an bn+mcm | m,n 1； 對應模板： A A 劃分模塊： ； 對應an bn， 對應 bmcm,47,文法的構造舉例（2/3）,3、L3=anbnci | n 1，i 0； 對應模板： A A或A A A A 劃分模塊： ； 對應an bn， 對應 ci 4、L4=aibncn | n 1，i 0； 同,48,文法的構造舉例（3/3）,5、L5=anbncn|n 1 對應模板： A A 劃分模塊： ； 對應an bn， 對應 cn或 對應an ， 對應 bn cn,49,2.4 文法及其語法樹,文法和語言,一、語法樹（推導樹） 直觀定義：用圖表示上下文無關文法句型的推導的直觀方法。 語法樹有助于理解一個句子的語法層結構的層次，語法樹通常表示 成一棵倒立的樹，根在上，枝葉在下。,2. 形式定義 對文法G=( VN, VT, P, S)相關聯(lián)的語法樹49滿足以下4個條件： （1）根結點由開始符號S所標記； （2）每個結點都有一個標記，此標記是V(即VN VT)的一個符號； （3） 若某結點至少有一個子孫結點，則該結點所標記的符號是個非終結符； （4）從左到右，若結點A1 , A2 , , Ak是結點A的孩子結點，則存在產(chǎn)生式A A1 A2 Ak。,50,從根結點S開始推導，當非終結符被它的某個候選式所替換時，這個非終結符的相應結點就產(chǎn)生出下一代新結點，候選式中自左向右的每個符號對應一個新結點，并用這些符號標記其相應的新結點。每個新結點與其父結點間都有一條連線。在一棵語法樹生長過程中的任何時刻，所有那些沒有后代的端末結自左向右排列起來就是一個句型。,語法樹構造的過程,例1 文法G= ( E, +, *, i , (, ), P, E)，其中P為： E E+E | E*E | (E) | i 對該文法關于(i*i+i)的推導的語法樹如下所示：,51,接語法樹構造舉例,E(根),（,E,）,E,+,+,E,E,*,E,i,i,i,什么是樹的邊沿？,52,文法和語言,語法樹的問題分析,（1）允許產(chǎn)生同名結點（反映遞歸性）； （2）沒有后代的結點為端末結； （3）語法樹不能反映產(chǎn)生后代的先后順序；（例子在下一頁） （4）一棵語法樹表示了一個句型種種可能的（但未必是所有的）不同推導過程。,53,語法樹例子,推導過程中施用產(chǎn)生式的順序,例: GS: SaAS ASbA ASS Sa Aba,S a A S S b A a a b a,SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa,54,2.5 文法和語言的一些特性,文法和語言,2.5.1 無用非終結符號,如果文法的某個非終結符不出現(xiàn)在文法的任何一個句型中，并且不能從它推導出終結符號串，則稱該非終結符為無用非終結符。,例2.13 設文法G13 A： A - aaBbb B - aBb | ab C -cD | c D -Ef 哪些符號是無用非終結符號？,無用非終結符號：D E,對于文法GS，為了保證任一非終結符A在句子推導中出現(xiàn)，必須滿足如下兩個條件： 1）A必須在某句型中出現(xiàn)。 2）必須能從A推出終結符號串t來。,55,文法和語言,2.5.2 不可達文法符號,如果一個非終結符不出現(xiàn)在文法的任何一條產(chǎn)生式的右部，則稱該非終結符為不可達文法符號。,例2.13 設文法G13 A： A - aaBbb B - aBb | ab C -cD | c D -Ef 哪些符號是不可達文法符號？,不可達文法符號：C,56,文法和語言,多余符號和多余規(guī)則,無用非終結符和不可達文法符號都是多余符號。 包含有多余符號的規(guī)則（產(chǎn)生式），是多余規(guī)則。 形如 U - U 的產(chǎn)生式，也是多余規(guī)則。,例1 設文法G13 A： A - aaBbb | a B - aBb | aCb C -cD | C D -Ef 應刪除哪些多余規(guī)則？,57,文法和語言,多余符號和多余規(guī)則,應刪除哪些多余規(guī)則？,例2：GS 1) SBe 2) BCe 3) BAf 4) AAe 5) Ae 6) CCf 7) Df,SBe BAf AAe Ae,58,文法和語言,2.5.3 可空非終結符,若存在產(chǎn)生式 A - ，則該產(chǎn)生式稱為空產(chǎn)生式，A稱為可空非終結符。 空產(chǎn)生式有時候帶來方便，所以，可以往一個文法里增加空產(chǎn)生式。,59,2.5.4 最左推導/最右推導/規(guī)范推導,最左推導：任何一步= 都是對中的最左非終結符進行替換。 最右推導（又稱規(guī)范推導）：任何一步=都是對中的最右非終結符進行替換。 由規(guī)范推導所得到的句型稱為規(guī)范句型。,從一個句型到另一個句型的推導過程往往是不唯一的。 例如 E+E (i+i)： （a）E+E = E+i = i+i 最右推導 （b）E+E = i+E = i+i 最左推導,60,語法樹的特點,文法和語言,一棵語法樹是這些不同推導過程的共性抽象，是它們的代表。一棵語法樹完全等價于一個最左（右）推導，這種等價性包括樹的步步生長和推導的步步展開是完全一致的。 例：推導(i*i+i) 最左推導：E =(E) =(E+E)=(E*E+E)=(i*E+E)=(i*i+E)= (i*i+i) 最右推導：E=(E)=(E+E)=(E+i)=(E*E+i)=(E*i+i)=(i*i+i) 但兩種推導的語法樹相同。,61,文法和語言,一個句型是否只對應唯一的一棵語法樹？,例：GE: E i E E+E E E*E E (E),句型 i*i+i 的兩個不同的最左推導： 推導1：E E+E E*E+E i*E+E i*i+E i*i+i 推導2：E E*E i*E i*E+E i*i+E i*i+i,62,文法和語言,定義2.13 ： 一個文法，如果它的一個句子對應有兩棵或兩棵以上不同的語法樹，則這個文法是二義的。 或 一個文法的某個句子有兩個不同的最左（右）推導，則這個文法是二義的。,2.5.5 二義性,區(qū)別 文法的二義性：存在兩個不同文法G(二義)、G(無二義)，卻有L(G)=L(G)，即產(chǎn)生語言相同。 語言的二義性：若不存在無二義性的文法，則該語言是二義性的。,63,二義性其它問題,文法和語言,人們已證明，二義性問題是不可判定的，即不存在一個算法，它能在有限步驟內(nèi)，確切地判斷一個文法是否是二義的。我們所能做的就是為無二義性尋找一些充分條件。 例如對文法GE： E E+E | E*E | (E) | i 修改，規(guī)定運算符“+”與“*”的優(yōu)先關系和結合規(guī)則，設“*”的優(yōu)先性高于“+”，且服從左結合。 G： E T | E+T T F | T*F F (E) | i,64,文法和語言,2.6 分析方法簡介,句型分析的任務就是按文法的產(chǎn)生式，識別輸入的符號是否是該文法的句型。語法樹是句型推導過程的幾何表示，可以十分直觀的顯示某句型的結構。因此在句型時，對輸入符號串構造語法樹，以此識別它是否是該文法的一個句型（或句子）。因此，語法樹又可稱為語法分析樹或分析樹。我們把完成句型分析的程序稱為分析程序或識別程序，分析算法又稱識別算法。 分析算法又分為：,從左到右分析算法； 從右到左分析算法；,自上而下的分析法 自下而上的分析法,65,文法和語言,自上而下的分析法,基本思想：從文法的開始符號出發(fā)，反復使用各種產(chǎn)生式，尋找“匹配”輸入符號串的推導。即對任何輸入符號串，從文法的開始符號（根結）出發(fā)，自上而下地為輸入串建立一棵語法樹，直到語法樹結果正好是輸入的符號串為止。,例如：文法GS: S xAy A aa | a，識別輸入串xay是否是該文法的一個句子。,66,文法和語言,自上而下分析法的缺陷,關鍵：回溯問題（ 其分析過程是一種試探過程） 回溯問題是從各種可能的候選式中任選一個，進行推導后發(fā)現(xiàn)該候選式是錯誤的，則退回去重新選擇候選式的方式。例如上例中的(3)。,S,S,S,x,A,y,(3) 選用第1個候選式,a,回溯的產(chǎn)生使算法代價極低，效率很低。關于解決回溯問題將在第5章中介紹。,a,67,自下而上的分析法,文法和語言,基本思想：從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號。即從語法樹的末端開始，步步向上“歸約”，直到根結。 歸約：若V= ，W=， 是文法的產(chǎn)生式，如有V=W，則W直接歸約到V。,68,自下而上的語法分析舉例,例1：文法G：S cAd A ab A a 識別輸入串w=cabd是否該文法的句子,S A A c a b d c a b d c a b d 規(guī)約過程：S cAd cabd,69,文法和語言,例2： 文法GS： (1)S aAcBe (2) A b (3)A Ab (4) B d 識別abbcde是否為文法S的一個句子。,解題思想：掃描abbcde，從中找出一個子串，該子串與某一產(chǎn)生式的右部相匹配。,70,自下而上分析法舉例,文法和語言,例2解：,71,自下而上分析法存在的問題,文法和語言,可歸約串的問題；（ 該分析的每一步就是從當前串中找一個子串（稱“可歸約串”），將它歸約到某個非終結符號） 自下而上分析法的關鍵就是找哪個子串是“可歸約串”，哪個不是“可歸約串”。例如上例中的(3),因此必須精確定義“可歸約串”，事實上存在著種種不同的方法刻畫“可歸約串”，對這個概念的不同定義，形成了不同的自下而上的分析法。在“規(guī)范歸約”的分析中，用“句柄”來刻畫“可歸約串”。,72,短語、直接短語、句柄,文法和語言,1、短語： 令文法G，開始符號為S，是G的句型（即S ），如果S A且A ，則稱是句型相對于非終結符A的短語。 2、直接短語 如短語中有A=，則稱是句型相對于規(guī)則A 的直接短語。 3、句柄 一個句型的最左直接短語稱為該句型的句柄。,73,解題方法,文法和語言,例：文法GE: E T | E+T T F | T*F F (E) | i 證明i+i*i是G的一個句型，并指出這個句型的所有短語、直接短語、句柄。,證明：E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i,74,接上例,文法和語言,語法樹：,E,E,+,T,T,T,*,F,F,F,i3,i1,i2,第1層 i1+i2*i3 相對于E 第2層 i1 相對于E ; i2*i3 相對于T 第3層 i1 ,i2 相對于T; i3 相對于F 第4層 i1 ,i2 相對于F(F i直接短語) 第5層, i+i*i是G的一個句型，其中i1 , i2 , i3, i2*i3 , i1+i2*i3 都是句型i1+i2*i3 的短語，且i1 , i2 , i3 為直接短語， i1為句柄,75,分析說明,文法和語言,(2)作為“短語”的兩個條件是不可缺少的，僅僅有A ，未必意味著就是句型的一個短語，因為還需要有S 這個條件。,例如：上例中有E i1+i2，但i1+i2并不是該句型的一個短語，因為不存在從E（開始符號）到E* i3的推導。,(1)短語、直接短語、句柄是針對某一句型（S ）而言的;,76,解題方法,先證明前提 給出語法樹（注意文法是否是二義性的） 如題文法GE: E E+E|E*E|(E) | i 證明i+i*i是G的一個句型，并指出這個句型的所有短語、直接短語、句柄。 根據(jù)每顆語法樹得出短語、直接短語、句柄 （注意編號）,77,練習1題目,文法GT: T F | T*F F F P | P P (T) | i 證明T*P (T*F)是文法G的一個句型，并指出這個句型的所有短語、直接短語、句柄。,78,練習解答,證明：T T*F T*FP T*F(T) T*F(T*F) T*P(T*F),語法樹：,T,T,*,F,F,P,P,T,(,),T,*,F,第1層 T*P(T*F) 相對于T 第2層 P(T*F) 相對于F; 第3層 P 相對于F; (T*F) 相對于P 第4層 T*F 相對于T 第5層, T*P(T*F)是G的一個句型，其中T*F , P , (T*F), P(T*F), T*P(T*F) 都是該句型的短語，且T*F , P 為直接短語， P為句柄,79,練習2題目,文法和語言,設有文法GS: S V1 V1 V2 | V1iV2 V2 V3 | V2+V3 V3 )V1* | ( (1)給出 (+(i( 的最右推導，并畫出相應的語法樹； (2)證明V2+V3i( 是文法的一個句型，并指出這個句型的短語、直接短語、句柄。,80,練習解答（）,文法和語言,(1)解：S V1 V1iV2 V1iV3 V1i( V2i( V2+V3i( V2+(i( V3+(i( (+(i(,語法樹：,V1,V1,i,V2,(,S,V2,V2,+,V3,V3,V3,(,(,81,練習解答（）,文法和語言,(2)證明： S V1 V1iV2 V1iV3 V1i( V2i( V2+V3i( V2+V3i(是文法的一個句型 短語：V2+V3 , (, V2+V3i( 直接短語： V2+V3 , ( 句柄： V2+V3,82,3.7 有關文法實用中的一些說明(1/2),作為描述程序語言的上下文無關文法，我們對它有幾點小小的限制，在實用中，主要是在文法中不得含有有害規(guī)則和多余規(guī)則。 1、不含有害規(guī)則 有害規(guī)則是指形如PP的產(chǎn)生式，因為這樣的產(chǎn)生式除了引起二義外，沒有任何用處。 2、不含多余規(guī)則 (1)不可到達的 即文法中的某些非終結符不在任何規(guī)則的右部出現(xiàn)，則任何句子推導不可能用到它。也就是說 對非終結符P，不存在S P， , (VNVT)*,83,有關文法實用中的一些說明(2/2),文法和語言,(2) 不可終止的 即文法中的某些非終結符不能夠從它推出終結符串。也就是說 對非終結符P，不存在P t， t VT* 若文法均滿足以上兩個條件，則稱這個文法為簡化了的文法。,84,本章課后練習,習題二 P45： 2、5、6、7,