編譯原理第講文法和語(yǔ)法

編譯原理課件第講文法和語(yǔ)法第1頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第一節(jié)

語(yǔ)言語(yǔ)言:是由句子組成的集合。

漢語(yǔ)---所有符合漢語(yǔ)語(yǔ)法的句子的全體英語(yǔ)---所有符合英語(yǔ)語(yǔ)法的句子的全體程序設(shè)計(jì)語(yǔ)言---所有該語(yǔ)言的程序的全體研究語(yǔ)言：每個(gè)句子構(gòu)成的規(guī)律每個(gè)句子的含義每個(gè)句子和使用者的關(guān)系第2頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月研究程序設(shè)計(jì)語(yǔ)言：

每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序的含義每個(gè)程序和使用者的關(guān)系語(yǔ)言研究的三個(gè)方面：

語(yǔ)法Syntax

語(yǔ)義Semantics

語(yǔ)用Pragmatics第3頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月語(yǔ)法：

表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的

組合規(guī)律

語(yǔ)義：表示按照各種表示方法所表示的各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系）

語(yǔ)用：表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來(lái)源、使用和影響。

第4頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第二節(jié)文法“我是大學(xué)生”是否是該語(yǔ)言的句子？〈句子〉::=〈主語(yǔ)〉〈謂語(yǔ)〉〈主語(yǔ)〉::=〈代詞〉|〈名詞〉〈代詞〉::=你|我|他〈名詞〉::=王明|大學(xué)生|工人|英語(yǔ)〈謂語(yǔ)〉::=〈動(dòng)詞〉〈直接賓語(yǔ)〉〈動(dòng)詞〉::=是|學(xué)習(xí)〈直接賓語(yǔ)〉::=〈代詞〉|〈名詞〉以自然語(yǔ)言為例，用EBNF(擴(kuò)展的巴科斯范式)描述一種語(yǔ)言：第5頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月〈句子〉〈主語(yǔ)〉〈謂語(yǔ)〉

①〈句子〉::=〈主語(yǔ)〉〈謂語(yǔ)〉〈主語(yǔ)〉::=〈代詞〉|〈名詞〉〈代詞〉::=你|我|他〈名詞〉::=王明|大學(xué)生|工人|英語(yǔ)〈謂語(yǔ)〉::=〈動(dòng)詞〉〈直接賓語(yǔ)〉〈動(dòng)詞〉::=是|學(xué)習(xí)〈直接賓語(yǔ)〉::=〈代詞〉|〈名詞〉

〈代詞〉〈謂語(yǔ)〉②我〈謂語(yǔ)〉③我〈動(dòng)詞〉〈直接賓語(yǔ)〉⑤我是〈直接賓語(yǔ)〉⑥我是〈名詞〉⑦我是大學(xué)生④第6頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月〈句子〉::=〈主語(yǔ)〉〈謂語(yǔ)〉〈主語(yǔ)〉::=〈代詞〉|〈名詞〉〈代詞〉::=你|我|他〈名詞〉::=王明|大學(xué)生|工人|英語(yǔ)〈謂語(yǔ)〉::=〈動(dòng)詞〉〈直接賓語(yǔ)〉〈動(dòng)詞〉::=是|學(xué)習(xí)〈直接賓語(yǔ)〉::=〈代詞〉|〈名詞〉下列是否是句子?我大學(xué)生是 他是工程師大學(xué)生是王明第7頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月事實(shí)上，使用文法作為工具，不僅為了嚴(yán)格定義句子的結(jié)構(gòu)，也是為了用適當(dāng)條數(shù)的規(guī)則把語(yǔ)言的全部句子描述出來(lái)。文法是以有窮的集合刻畫(huà)無(wú)窮的集合的一個(gè)工具。第8頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第三節(jié)符號(hào)和符號(hào)串字母表：元素的非空有窮集合。（符號(hào)集）符號(hào)：字母表中的元素。例如：漢語(yǔ)的字母表中包括漢字、數(shù)字及標(biāo)點(diǎn)符號(hào)等。PASCAL語(yǔ)言的字母表是由字母、數(shù)字、若干專(zhuān)用符號(hào)及BEGIN、IF之類(lèi)的保留字組成。第9頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月符號(hào)串：由字母表中的符號(hào)組成的任何有窮序列稱(chēng)為該字母表上的符號(hào)串。1.空符號(hào)串ε(沒(méi)有符號(hào)的符號(hào)串)是上的符號(hào)串。2.若x是上的符號(hào)串，a是的元素，則xa和ax是上的符號(hào)串。3.

y是上的符號(hào)串,當(dāng)且僅當(dāng)它可以由1和2導(dǎo)出。

例如：Σ={a,b}

ε,a,b,aa,ab,aabba,…,都是上的符號(hào)串。第10頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例：Σ={0,1}

ε,0,1,00,01,11,1001110等都是上的符號(hào)串.例：Σ={a,b,c}上的符號(hào)串有：

a,b,c,ab,ba,aaca,acaa等.注意：符號(hào)串中的符號(hào)排列是有順序的.可以用字母表示符號(hào)串，如：x=aaca第11頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月如果z=xy是一符號(hào)串，那么：x是z的頭(前綴)，y是z的尾(后綴)；如果x非空，那么y是固有尾；如果y非空，那么x是固有頭。例：設(shè)z=abc,那么z的頭是：ε,a,ab,abc（除abc外都是固有頭）z的尾是：ε,c,bc,abc（除abc外都是固有尾）

第12頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月幾種表示法（x，z是符號(hào)串，t是符號(hào)）：z=x… x是符號(hào)串z的頭z=…x x是符號(hào)串z的尾z=…x… x在符號(hào)串z中某處出現(xiàn)z=t…符號(hào)t是符號(hào)串z的第一個(gè)符號(hào)z=…t符號(hào)t是符號(hào)串z的最后一個(gè)符號(hào)第13頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月符號(hào)串的運(yùn)算符號(hào)串的長(zhǎng)度：符號(hào)串中符號(hào)的個(gè)數(shù)。符號(hào)串s的長(zhǎng)度記為|s|。ε的長(zhǎng)度為0。連接：符號(hào)串x、y的連接,是把y的符號(hào)寫(xiě)在x的符號(hào)之后得到的符號(hào)串xy

例：x=ST，y=abu則xy=STabu

|x|=2，|y|=3，|xy|=5

εx=xε=x第14頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月方冪符號(hào)串x自身連接n次得到的符號(hào)串xx…xx(n個(gè)x)表示為xn

x0=ε,x1=x,x2=xx，…，xn=xx…xx=AB,則x0=ε,x1=AB,x2=ABAB,x3=ABABAB對(duì)于n>0,xn=xxn-1=xn-1x

第15頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月符號(hào)串集合：若集合A中一切元素都是某字母表上的符號(hào)串，則稱(chēng)A為字母表上的符號(hào)串集合。兩個(gè)符號(hào)串集合A和B的乘積：定義為AB=xy|xA且yB

例：若，集合A=a,bB=c,d

則，AB=ac,ad,bc,bd

{ε}A=A{ε}=A(∵εx=xε=x)閉包：

使用*表示上的所有有窮長(zhǎng)的串（包括ε）的集合。Σ*稱(chēng)為Σ的閉包。正閉包：

從*中除去ε得到的集合記為+。

Σ+稱(chēng)為Σ的正閉包。第16頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月Σ*=Σ0∪Σ1∪Σ2…∪Σn∪

…Σ+=Σ1∪Σ2…∪Σn∪

…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例1：設(shè)Σ={0,1}，則：Σ*={ε，0，1，00，01，10，11，000，001，010，…}例2：設(shè)Σ={a,b}，則Σ*={ε，a，b，aa，ab，ba，bb，aaa，aab，…}Σ+={a，b，aa，ab，ba，bb，aaa，aab，…}第17頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第四節(jié)文法和語(yǔ)言的形式定義產(chǎn)生式（重寫(xiě)規(guī)則、規(guī)則或生成式），是形如α→β或α∷=β的（α，β）有序?qū)Γ渲笑潦悄匙帜副鞻的正閉包V+中的一個(gè)符號(hào)串，β是V*中的一個(gè)符號(hào)串。（α∈V+，β∈V*)α稱(chēng)為產(chǎn)生式的左部(或規(guī)則的左部)。

β稱(chēng)為產(chǎn)生式的右部(或規(guī)則的右部)。第18頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月一、文法的定義文法G：定義為四元組（VN，VT，P，S），其中VN：非終結(jié)符集VT：終結(jié)符集P：產(chǎn)生式（規(guī)則）集合S：開(kāi)始符號(hào)（起始符、識(shí)別符號(hào)）VN、VT

和P是非空有窮集。S至少在一條規(guī)則中作為左部出現(xiàn)。VN∩VT=φ，S∈VN，V=VN∪VT，稱(chēng)為文法G的字母表（字匯表）

注：有的參考書(shū)用（VT,VN,S,P）表示文法。第19頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例3.1文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S為開(kāi)始符號(hào)或?qū)懗桑篏[S]：S→0S1,S→01第20頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例3.2文法G=（VN，VT，P，S） VN={標(biāo)識(shí)符，字母，數(shù)字}

VT={a，b，c，…，x，y，z，0，1，…，9} P={<標(biāo)識(shí)符>→<字母>， <標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母>， <標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字>， <字母>→a，…，<字母>→z，

<數(shù)字>→0，…,<數(shù)字>→9}

S=<標(biāo)識(shí)符>第21頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月習(xí)慣上只將產(chǎn)生式寫(xiě)出。并有如下約定：

第一條產(chǎn)生式的左部是開(kāi)始符號(hào)用尖括號(hào)括起的是非終結(jié)符，否則為終結(jié)符?；蛘叽髮?xiě)字母表示非終結(jié)符，小寫(xiě)字母表示終結(jié)符G可寫(xiě)成G[S]，其中S是開(kāi)始符號(hào)第22頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例3.3文法G=（VN，VT，P，S） VN={S},VT={0,1} P={S→0S1,S→01} S為開(kāi)始符號(hào)可寫(xiě)成：

G[S]：S→0S1 S→01或?qū)懗桑?/p>

G[S]：S→0S1│01

注：把“0S1”和“01”稱(chēng)為產(chǎn)生式S→0S1│01的候選式第23頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月二、推導(dǎo)的定義直接推導(dǎo)“”α→β是文法G的產(chǎn)生式，γ,δ∈V*，若有v,w滿(mǎn)足：v=γαδ,w=γβδ,則說(shuō)：v（應(yīng)用規(guī)則α→β）直接產(chǎn)生w或說(shuō)：w是v的直接推導(dǎo)，或說(shuō)：w直接歸約到v，記作

vw例：G：S→0S1，S→01直接推導(dǎo)：0S10011

（v=0S1，w=0011，使用規(guī)則S→01，γ=0，δ=1）S0S1（v=S，w=0S1，使用規(guī)則S→0S1，γ=ε，δ=ε）

0S100S11

（v=0S1，w=00S11，使用規(guī)則S→0S1，γ=0，δ=1）第24頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例文法G=（VN，VT，P，S） VN={標(biāo)識(shí)符，字母，數(shù)字}； VT={a,b,c,…x,y,z,0,1,…,9} P={<標(biāo)識(shí)符>→<字母> <標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母> <標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字> <字母>→a,…,<字母>→z<數(shù)字>→0,…,<數(shù)字>→9}

S=<標(biāo)識(shí)符>指出下面直接推導(dǎo)所使用的規(guī)則：<標(biāo)識(shí)符>

<標(biāo)識(shí)符><字母><標(biāo)識(shí)符>

<字母><數(shù)字>

<字母><字母><數(shù)字>abc<數(shù)字>abc5第25頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例：G：S→0S1，S→010S100S11000S11100001111即0S100001111也記作0S100001111若存在v=w0w1...wn=w,(n>0)，則稱(chēng)v推導(dǎo)出（產(chǎn)生）w（推導(dǎo)長(zhǎng)度為n），或稱(chēng)w歸約v.記作vw。若有vw，或v=w，則記為vw+++*+**和注：包含0步推導(dǎo)；而不包含0步推導(dǎo)。*+推導(dǎo)第26頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例G:<標(biāo)識(shí)符>→<字母> <標(biāo)識(shí)符>→<標(biāo)識(shí)符><字母> <標(biāo)識(shí)符>→<標(biāo)識(shí)符><數(shù)字> <字母>→a│b│…│z<數(shù)字>→0│1│…│9

<標(biāo)識(shí)符><標(biāo)識(shí)符><數(shù)字><字母><數(shù)字>x<數(shù)字>x1即：<標(biāo)識(shí)符>x1也可記作：<標(biāo)識(shí)符>x1+*第27頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月句型設(shè)G[S]是一文法，如果符號(hào)串x是從開(kāi)始符號(hào)推導(dǎo)出來(lái)的，即Sx，則稱(chēng)x是文法G[S]的句型。句子x僅由終結(jié)符號(hào)組成（即Sx，且x∈VT*），則稱(chēng)x是G[S]的句子。例：G：S→0S1，S→01S0S100S11000S11100001111三、文法的句型、句子的定義**第28頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月四、語(yǔ)言的定義由文法G生成的語(yǔ)言記為L(zhǎng)(G)，它是文法G的全部句子的集合:L(G)={x|Sx，且x∈VT*，其中S為文法的開(kāi)始符號(hào)}文法描述的語(yǔ)言是該文法一切句子的集合。

例：G：S→0S1，S→01S0S100S11…

0n-1S1n-1

0n1nL(G)={0n1n|n≥1}*第29頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例3.3設(shè)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→eeS

an-1S(BE)n-1an(BE)nanBnEn…anbnen

L(G)={anbnen|n≥1}**第30頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月五、文法的等價(jià)若L(G1)=L(G2)，則稱(chēng)文法G1和G2是等價(jià)的。

如文法G1[A]：A→0R與G2[S]：S→0S1等價(jià)

A→01S→01R→A1注：語(yǔ)言和文法的對(duì)應(yīng)關(guān)系是一對(duì)多（1：n）的關(guān)系。第31頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第五節(jié)文法的類(lèi)型通過(guò)對(duì)產(chǎn)生式施加不同的限制，Chomsky將文法分為四種類(lèi)型（稱(chēng)為Chomsky文法）第32頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月一、文法的類(lèi)型0型文法：對(duì)任一產(chǎn)生式α→β，都有α∈(VN∪VT)+，且至少包含一非終結(jié)符，β∈(VN∪VT)*

1型文法：對(duì)任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅S→ε除外

2型文法：對(duì)任一產(chǎn)生式α→β，都有α∈VN，β∈(VN∪VT)*

3型文法：任一產(chǎn)生式α→β的形式都為(1)A→aB或

A→a，其中A∈VN，B∈VN，a∈VT*(右線性文法)

或(2)A→Ba或

A→a，其中A∈VN，B∈VN，a∈VT*(左線性文法)第33頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月1型文法：對(duì)任一產(chǎn)生式α→β，都有|β|≥|α|，僅僅S→ε除外上下文有關(guān)文法：α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε)2型文法：對(duì)任一產(chǎn)生式α→β，都有α∈VN，β∈(VN∪VT)*上下文無(wú)關(guān)文法：A→β(A在VN中，β在V*中，)3型文法也叫正規(guī)文法第34頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例：1型（上下文有關(guān)）文法文法G[S]： S→aSBE S→aBE EB→BE aB→ab bB→bb bE→be eE→ee第35頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例：2型（上下文無(wú)關(guān)）文法文法G[S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB

例:3型文法G[S]：S→0A|1B|0 A→0A|1B|0S B→1B|1|0第36頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月四種文法之間的關(guān)系是將產(chǎn)生式做進(jìn)一步限制而定義的，他們之間的逐級(jí)“包含”關(guān)系2型文法1型文法0型文法3型文法第37頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月二、文法和語(yǔ)言0型文法(PSG)產(chǎn)生的語(yǔ)言稱(chēng)為0型語(yǔ)言1型文法或上下文有關(guān)文法（CSG）產(chǎn)生的語(yǔ)言稱(chēng)為1型語(yǔ)言或上下文有關(guān)語(yǔ)言（CSL）2型文法或上下文無(wú)關(guān)文法（CFG）產(chǎn)生的語(yǔ)言稱(chēng)為2型語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言（CFL）

3型文法或正則（正規(guī)）文法（RG）產(chǎn)生的語(yǔ)言稱(chēng)為3型語(yǔ)言或正則（正規(guī)）語(yǔ)言（RL）第38頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第六節(jié)上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù)上下文無(wú)關(guān)文法有足夠的能力描述現(xiàn)今程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)算術(shù)表達(dá)式語(yǔ)句賦值語(yǔ)句條件語(yǔ)句讀語(yǔ)句……第39頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月算術(shù)表達(dá)式上下文無(wú)關(guān)文法表示：文法G=({E},{+,*,i,(,)},P,E） P: E→i E→E+E E→E*E E→(E)條件語(yǔ)句上下文無(wú)關(guān)文法表示<條件語(yǔ)句>→if<條件>then<語(yǔ)句>|

if<條件>then<語(yǔ)句>else<語(yǔ)句>第40頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月一、上下文無(wú)關(guān)文法的語(yǔ)法樹(shù)用于描述上下文無(wú)關(guān)文法的句型推導(dǎo)的直觀方法設(shè)G=(VN,VT,P,S)為一cfg，若一棵樹(shù)滿(mǎn)足下列4個(gè)條件，則此樹(shù)稱(chēng)作G的語(yǔ)法樹(shù)(推導(dǎo)樹(shù))(派生樹(shù)）：1.每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)2.根的標(biāo)記是S3.若一結(jié)點(diǎn)n至少有一個(gè)它自己除外的子孫，并且有標(biāo)記A，則肯定A∈VN4.如果結(jié)點(diǎn)n有標(biāo)記A,其直接子孫結(jié)點(diǎn)從左到右的次序是n1，n2，…，nk，其標(biāo)記分別為A1，A2，…，Ak，那么A→A1A2，…，Ak一定是P中的一個(gè)產(chǎn)生式第41頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例:G[S]: S→aAS A→SbA A→SS S→a A→ba

SaASSbAaaba句型aabbaa的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）葉子結(jié)點(diǎn)：樹(shù)中沒(méi)有子孫的結(jié)點(diǎn)。

從左到右讀出推導(dǎo)樹(shù)的葉子標(biāo)記，所得的句型為推導(dǎo)樹(shù)的結(jié)果。也把該推導(dǎo)樹(shù)稱(chēng)為該句型的語(yǔ)法樹(shù)。第42頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月推導(dǎo)過(guò)程中施用產(chǎn)生式的順序例:G[S]: S→aAS A→SbA A→SS S→a A→ba

SaASSbAaaba句型aabbaa的語(yǔ)法樹(shù)（推導(dǎo)樹(shù)）SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa第43頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月最右（最左）推導(dǎo)：在推導(dǎo)的任何一步αβ，其中α、β是句型，都是對(duì)α中的最右（左）非終結(jié)符進(jìn)行替換最右推導(dǎo)被稱(chēng)為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱(chēng)為規(guī)范句型SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa例:G[S]: S→aAS A→SbA A→SS S→a A→ba第44頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月一棵語(yǔ)法樹(shù)表示了一個(gè)句型的種種可能的(但未必是所有的)不同推導(dǎo)過(guò)程，包括最左(最右)推導(dǎo)。但是，一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)呢?一個(gè)句型是否只有唯一的一個(gè)最左(最右)推導(dǎo)呢?第45頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月例：G[E]:

E→i E→E+E E→E*E E→(E)

EE+EE*Eiii

EE*EiE+Eii句型i*i+i的兩個(gè)不同的最左推導(dǎo)：推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i問(wèn)題：一個(gè)句型是否對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)？第46頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月二、二義文法

若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義的。

或者說(shuō)，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱(chēng)這個(gè)文法是二義的。文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G′，其中G是二義的，但是卻有L(G)=L(G′)，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。產(chǎn)生某上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則稱(chēng)此語(yǔ)言是先天二義的。第47頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的。但可以為無(wú)二義性尋找一組充分條件。

二義文法改造為無(wú)二義文法G[E]:E→iG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|i E→(E)規(guī)定優(yōu)先順序和結(jié)合律對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。第48頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月第七節(jié)句型的分析句型分析

就是識(shí)別一個(gè)符號(hào)串是否為某文法的句型，是某個(gè)推導(dǎo)的構(gòu)造過(guò)程。在語(yǔ)言的編譯實(shí)現(xiàn)中，把完成句型分析的程序稱(chēng)為分析程序或識(shí)別程序。分析算法又稱(chēng)識(shí)別算法。從左到右的分析算法，即總是從左到右地識(shí)別輸入符號(hào)串，首先識(shí)別符號(hào)串中的最左符號(hào)，進(jìn)而依次識(shí)別右邊的一個(gè)符號(hào)。第49頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月分析算法可分為：

自上而下分析法（推導(dǎo)）：

從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找與輸入符號(hào)匹配的推導(dǎo)。（從文法符號(hào)開(kāi)始，將它做為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的結(jié)果正好是輸入符號(hào)串）

自下而上分析法（歸約）：

從輸入符號(hào)串開(kāi)始，逐步進(jìn)行歸約，直至歸約到文法的開(kāi)始符號(hào)。（從輸入符號(hào)串開(kāi)始，以它做為語(yǔ)法樹(shù)的結(jié)果，自底向上的構(gòu)造語(yǔ)法樹(shù)）

兩種方法反映了兩種不同的語(yǔ)法樹(shù)的構(gòu)造過(guò)程第50頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月一、自上而下的語(yǔ)法分析例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否為該文法的句子？

S S S c A d c A d ab推導(dǎo)過(guò)程：ScAdcabd第51頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月二、自下而上的語(yǔ)法分析例：文法G：S→cAd

A→ab

A→a

識(shí)別輸入串w=cabd是否該文法的句子

S A A cabd cabd cabd

歸約過(guò)程：ScAdcabd第52頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月自上而下的語(yǔ)法分析

(1)S→cAd(2)A→ab(3)

A→a

識(shí)別輸入串w=cad是否為該文法的句子若ScAd后選擇(2)擴(kuò)展A，ScAdcabd那將會(huì)？

w的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn)a得以匹配，但第三個(gè)符號(hào)卻不能與下一葉子結(jié)點(diǎn)d匹配？宣告分析失敗（其意味著，識(shí)別程序不能為串cad構(gòu)造語(yǔ)法樹(shù)，即cad不是句子）-顯然是錯(cuò)誤的結(jié)論。導(dǎo)致失敗的原因是在分析中對(duì)A的選擇不是正確的。

ScAdab

這時(shí)應(yīng)該回朔，把A為根的子樹(shù)剪掉，掃描過(guò)的輸入串中的a吐出來(lái),再試探用產(chǎn)生式（3）第53頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月自下而上的語(yǔ)法分析

(1)S→cAd(2)A→ab(3)A

→a

識(shí)別輸入串w=cabd是否為該文法的句子對(duì)串cabd的分析中，如果不是選擇ab用產(chǎn)生式(2),而是選擇a用產(chǎn)生式(3)將a歸約到了A，那么在cAbd中無(wú)法找到一個(gè)可歸約串了，最終就達(dá)不到歸約到S的結(jié)果，因而也無(wú)從知道cabd是一個(gè)句子cabd

cAbd

a第54頁(yè)，課件共63頁(yè)，創(chuàng)作于2023年2月三、句型分析的有關(guān)問(wèn)題1）如何選擇使用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)？ 在自上而下的分析方法中，假定要被代換的最左非終結(jié)符號(hào)是V，且有n條規(guī)則：V→A1|A2|…