第2章 文法和語言

編譯系統(tǒng)原理電氣與信息學(xué)院

王艷§2.1字母表和符號(hào)串§2.2文法§2.3推導(dǎo)§2.4句型和句子§2.5語言§2.6遞歸規(guī)則與遞歸定義§2.7短語、簡(jiǎn)單短語和句柄§2.8語法樹§2.9子樹與短語§2.10由樹構(gòu)造推導(dǎo)過程§2.11文法的二義性§2.12有關(guān)文法的實(shí)用限制§2.13文法和語言的分類第二章文法和語言語言的組成語言：句子的集合句子：多個(gè)單詞按一定規(guī)則組成單詞：多個(gè)字符按一定規(guī)則組成程序設(shè)計(jì)語言編程語言程序的語句集合語句：多個(gè)單詞按語法規(guī)則組成單詞：多個(gè)字符按詞法規(guī)則組成程序設(shè)計(jì)語言和自然語言的組成結(jié)構(gòu)語言定義的方法枚舉方法一個(gè)語言中的句子有限（非形式化描述）形式化描述方法（文法）一組數(shù)學(xué)符號(hào)（形式化描述）產(chǎn)生語言中全部句子的有限個(gè)規(guī)則自動(dòng)機(jī)方法識(shí)別某字母表上所有符號(hào)串是否是該語言句子的一種裝置（算法或過程）產(chǎn)生的觀點(diǎn)識(shí)別的觀點(diǎn)§2.1字母表和符號(hào)串2.1.1

字母表元素的非空有限集合，字母表中的每個(gè)元素稱為符號(hào)，字母表也稱符號(hào)表。例：={a，b，c}

={0，1}={a，b，c，+，*}

={begin,end,if,then,else}§2.1字母表和符號(hào)串字母表辨析：

例：1={aa，bb，cc}

2={a,a’,b,b’}3={a，b，a}4={}解析：1和2是字母表，體現(xiàn)了字母表的整體性和可辨認(rèn)性；3中有相同的符號(hào)；4也不是字母表，因?yàn)橐笞帜副矸强铡！?.1字母表和符號(hào)串2.1.2

符號(hào)串由字母表中的0個(gè)或多個(gè)符號(hào)組成的任何有窮序列例：Σ={a,b}ε,a,b,aa,ab,aabba…都是上的符號(hào)串

空符號(hào)串：無任何符號(hào)的符號(hào)串,記為ε§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合的運(yùn)算1.符號(hào)串的長(zhǎng)度：x為字母表上的字符串，則長(zhǎng)度指x中所含符號(hào)的個(gè)數(shù)，記為|x|。例：|abc|=|abccba|=|ε|=363§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合的運(yùn)算2.符號(hào)串相等：x、y為上的兩個(gè)符號(hào)串，當(dāng)且僅當(dāng)組成x的各符號(hào)與組成y的各符號(hào)依次相等時(shí)，則符號(hào)串x與符號(hào)串y相等，記作x=y。例：x=abbc，y=abbc，x’=ab，y’=ba則xy，x’y’=≠§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合的運(yùn)算3.符號(hào)串的前綴和后綴：從符號(hào)串x的末尾刪除0個(gè)或多個(gè)符號(hào)后得到的符號(hào)串稱為x的前綴；從x的開頭刪除0或多個(gè)符號(hào)后得到的符號(hào)串稱為x的后綴。例：設(shè)z=abc,z的前綴是ε，a，ab，abc；

z的后綴是ε，c，bc，abc。

§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合的運(yùn)算4.符號(hào)串的子串：指從符號(hào)串x的開頭和結(jié)尾刪除0個(gè)或多個(gè)符號(hào)后得到的符號(hào)串。例：z=abc，其中b及前綴、后綴都是abc的子串。§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合運(yùn)算5.字符串的連接：設(shè)x和y是兩個(gè)字符串，則xy被稱為符號(hào)串x與y連接。εx=xε=x(xy)z=x(yz)|xy|=|x|+|y|例：x=ST，y=abu，則xy=STabu，可看出|x|=2，|y|=3，|xy|=56.字符串A與B的乘積：設(shè)A和B為符號(hào)串集合，則

A與B的乘積定義為AB=xy|xA且yB例：若集合A=ab,cde集合B=0,1

則AB=ab0,ab1,cde0,cde1

對(duì)于空集合{ε}有{ε}A=A{ε}=A§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合運(yùn)算7.符號(hào)串的冪運(yùn)算：即把x重復(fù)寫n次，記為z=xn。

例：若x=AB則:

x0=εx1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n>0)對(duì)于m,n≥0xmxn=xm+n(xm)n=xmn§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合運(yùn)算8.集合的冪運(yùn)算：設(shè)A為符號(hào)串集合，則A的冪運(yùn)算定義為A0={ε}，A1=A，A2=AA，…,An=AAn-1=An-1Ax(n>0)

例：若A={a,b}則:

A0=εA1={a,b}A2={aa,ab,ba,bb}…§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合運(yùn)算9.字符串集合的正閉包：設(shè)A為集合，則A+=A1∪A2∪…∪An，n>1例：若∑=0,1

則∑+=0,1,00,01,10,11,000,001,…

注：指定字母表A后，可用An表示A上所有長(zhǎng)度為n的串的集合?！?.1字母表和符號(hào)串2.1.3符號(hào)串及其集合運(yùn)算10.字符串集合的閉包(星閉包)：設(shè)A為集合，則A*=A0∪A1∪A2∪…∪An,n≥0A*可表示A上所有有窮長(zhǎng)的串的集合；A*=A0∪A+A+=AA*=A*AA*=A+∪{ε}，A+=A*-{ε}例：若∑=0,1,則∑*=ε,0,1,00,01,10,11,…§2.1字母表和符號(hào)串2.1.3符號(hào)串及其集合運(yùn)算

若A為某語言的基本字符集

A＝{a,b,……z,0,1,……,9,+,－,×,_/,(,),=……}B為單詞集

B={begin,end,if,then,…,<標(biāo)識(shí)符>,<常量>,……}

則BA*

。語言的句子是定義在B上的符號(hào)串。若令C為句子集合，則CB*,程序C

為什么對(duì)符號(hào)、符號(hào)串、符號(hào)串集合以及它們的運(yùn)算感興趣？§2.2文法2.2.0文法的直觀理解1.什么是文法

文法是對(duì)語言結(jié)構(gòu)的定義與描述，即從形式上描述和規(guī)定語言結(jié)構(gòu)，也稱為語法。

例：句子：“我是大學(xué)生”。該句子的結(jié)構(gòu)（稱為語法結(jié)構(gòu)）是由它的語法決定的。

如何定義該句子的語法結(jié)構(gòu)呢？

——語法規(guī)則2.語法規(guī)則

通過建立一組規(guī)則（產(chǎn)生式），來描述句子的語法結(jié)構(gòu)。規(guī)定用“::=”表示“由…組成”或“定義為…”。<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=

王民|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>§2.2文法2.2.0文法的直觀理解3.由產(chǎn)生式推導(dǎo)句子推導(dǎo)方法：從一個(gè)要識(shí)別的符號(hào)開始推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部來替代產(chǎn)生式的左部，每次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)?！?.2文法2.2.0文法的直觀理解<句子>

<主語><謂語>

<代詞><謂語>

我<謂語>

我<動(dòng)詞><直接賓語>

我是<直接賓語>

我是<名詞>

我是大學(xué)生<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=

王民|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>推導(dǎo)方法：從一個(gè)要識(shí)別的符號(hào)開始推導(dǎo)，即用相應(yīng)產(chǎn)生式的右部來替代產(chǎn)生式的左部，每次僅用一條產(chǎn)生式去進(jìn)行推導(dǎo)。例：給定一組語法規(guī)則，考察一個(gè)句子：“我是大學(xué)生”的推導(dǎo)過程。4.語法樹<句子><主語><謂語><代詞><動(dòng)詞><直接賓語><代詞>我大學(xué)生語法成分（在形式語言中又稱“非終結(jié)符”）單詞符號(hào)（在形式語言中又稱“終結(jié)符號(hào)”)是§2.2文法2.2.0文法的直觀理解

定義:文法G[S]定義為一個(gè)四元組，

G[S]=（Vn，Vt，P，Z）

Vn

：非終結(jié)符號(hào)集

Vt

：終結(jié)符號(hào)集

P：產(chǎn)生式或規(guī)則的集合

Z：開始符號(hào)（識(shí)別符號(hào)）,S∈VN其中:①非終結(jié)符號(hào)：出現(xiàn)在產(chǎn)生式的左部或右部,且能推出符號(hào)或符號(hào)串，用來表示語言的語法成分。②終結(jié)符號(hào)：不出現(xiàn)在產(chǎn)生式的左部,且不能推出符號(hào)或符號(hào)串，是組成語言的基本單位。Vt∪Vn

是字母表。③產(chǎn)生式：產(chǎn)生式是一個(gè)有序?qū)?α,β),通常寫為:α::β

或αβ；讀作“定義為”?！?.2文法2.2.1文法形式定義2型文法：上下文無關(guān)文法。產(chǎn)生式的左部都是非終結(jié)符，右部是終結(jié)符和非終結(jié)符組成的有窮符號(hào)串。這樣只需給出產(chǎn)生式集合，并指定識(shí)別符即可。§2.2文法2.2.1文法形式定義例2-1形式化描述P14頁文法

文法G=（Vn，Vt，P，Z）Vn={句子,主語,謂語,冠詞,名詞,動(dòng)詞,直接賓語}Vt={the,ate,banana,monkey}P:

Z：<句子><句子>→<主語><謂詞><主語>→<冠詞><名詞><冠詞>→the<謂語>→<動(dòng)詞><直接賓語><動(dòng)詞>→ate<直接賓語>→<冠詞><名詞><名詞>→banana<名詞>→monkey§2.2文法2.2.1文法形式定義<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=

王民|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞>練習(xí)：

文法G=（VN，VT，P，Z）VN={句子,主語,代詞,名詞,謂語,動(dòng)詞,直接賓語}VT={你,我,他,農(nóng)民,大學(xué)生,工人,英語,是,學(xué)習(xí)}P:Z：<句子>§2.2文法2.2.1文法形式定義<句子>::=<主語><謂語><主語>::=<代詞>|<名詞><代詞>::=你|我|他<名詞>::=

王民|大學(xué)生|工人|英語<謂語>::=<動(dòng)詞><直接賓語><動(dòng)詞>::=是|學(xué)習(xí)<直接賓語>::=<代詞>|<名詞><無符號(hào)整數(shù)>→<數(shù)字串>；<數(shù)字串>→<數(shù)字串><數(shù)字>；<數(shù)字串>→<數(shù)字>；<數(shù)字>→0；

<數(shù)字>→1；

…………<數(shù)字>→9；

例2-2：如下規(guī)則集，給出終結(jié)符號(hào)、非終結(jié)符和識(shí)別符號(hào)：§2.2文法2.2.1文法形式定義G=（VN，VT，P，S）VN＝{<無符號(hào)整數(shù)>,<數(shù)字串>,<數(shù)字>}VT={0,1,2,3,……9}Z：<無符號(hào)整數(shù)>（1）元符號(hào)“|”，表示或，用于具有相同左部的一系列規(guī)則。例如：<數(shù)字>→0；

<數(shù)字>→1；

…………<數(shù)字>→9；上述表示文法的方式稱為BNF（巴克斯—諾爾范式）。EBNF為擴(kuò)充的BNF表示，采用一些元符號(hào)來提高文法規(guī)則的表達(dá)能力。§2.2文法2.2.2文法的EBNF表示表示為：<數(shù)字>→0|1|2|3|4|5|6|7|8|9（2）元符號(hào)“<”和“>”，用于括起由中文字組成的非終結(jié)符或由多個(gè)字母組成的符號(hào)。例如：<數(shù)字>，<monkey>§2.2文法2.2.2文法的EBNF表示（3）元符號(hào)“{”和“}”，表示可重復(fù)性連接。表示符號(hào)串t可連接n~m次，而{t}表示符號(hào)串t可連接0到無窮次。*<無符號(hào)整數(shù)>→<數(shù)字>|<數(shù)字><數(shù)字>|<數(shù)字><數(shù)字><數(shù)字>*E→E+T|T*以字母開頭，后面跟數(shù)字或字母的不超過8個(gè)字符的標(biāo)識(shí)符*<無符號(hào)整數(shù)>→*E→T+{T}*<標(biāo)識(shí)符>→<字母>（4）元符號(hào)“[”和“]”，[t]表示其中的符號(hào)串t可有可無。例如：<if語句>→if<布爾表達(dá)式>then<語句>[else<語句>]§2.2文法2.2.2文法的EBNF表示（5）元符號(hào)“（”和“）”，表示括號(hào)內(nèi)的成分優(yōu)先，常用于在規(guī)則中提取公因子。例如：U→xy|xw|…|xz可寫成U→x（y|w|…|z）α→β是文法G的產(chǎn)生式，現(xiàn)有符號(hào)串xαy，其中xy是該文法的任意符號(hào)串（可為空），推導(dǎo)就是利用α→β，將xαy中α替換為β。xαyxβy，稱xαy直接推導(dǎo)（產(chǎn)生）xβy，也稱xβy直接歸約到xαy。

例1：文法G[S]:S→0S1，S→01

有直接推導(dǎo)0S10011

§2.3推導(dǎo)2.3.1直接推導(dǎo)/直接規(guī)約例2：文法G[S]:S→0S1，S→01

有直接推導(dǎo)S0S1

§2.3推導(dǎo)2.3.1直接推導(dǎo)/直接規(guī)約例3：文法G[S]:S→0S1，S→01

有直接推導(dǎo)0S100S11

若存在直接推導(dǎo)序列

w0w1...wn，（n>0）

+

則記為w0

wn，稱w0推導(dǎo)出（產(chǎn)生）wn，或wn歸約到w0

。

§2.3推導(dǎo)2.3.2推導(dǎo)/規(guī)約

說明：當(dāng)符號(hào)串已沒有非終結(jié)符號(hào)時(shí)，推導(dǎo)就必須終止。因?yàn)榻K結(jié)符不可能出現(xiàn)在產(chǎn)生式左部，所以將在產(chǎn)生式左部出現(xiàn)的符號(hào)稱為非終結(jié)符號(hào)。例：G[N]：N→ND|DD→0|1|2|3|4|5|6|7|8|9

NNDNDDND9N09D09109

§2.3推導(dǎo)2.3.2推導(dǎo)/規(guī)約+*

如果v

w，或v

w，則記作v

w

。

例：

S0S100S11000S11100001111

+

則有S00001111

*

S00001111§2.3推導(dǎo)2.3.2推導(dǎo)/規(guī)約例：無符號(hào)整數(shù)的文法G[{<無符號(hào)整數(shù)>]:<無符號(hào)整數(shù)>→<數(shù)字串>；

<數(shù)字串>→<數(shù)字串><數(shù)字>；

<數(shù)字串>→<數(shù)字>；

<數(shù)字>→0|1|2|…|9；

如整數(shù)10的推導(dǎo)過程：

<無符號(hào)整數(shù)><數(shù)字串><數(shù)字串><數(shù)字>

<數(shù)字串>0<數(shù)字>010§2.3推導(dǎo)2.3.2推導(dǎo)/規(guī)約§2.3推導(dǎo)2.3.3規(guī)范推導(dǎo)也叫最右推導(dǎo)，即每步推導(dǎo)只變換符號(hào)串中最右邊的非終結(jié)符。xαyxβy，若y只包含終結(jié)符號(hào)或?yàn)榭眨敲催@種推導(dǎo)稱為規(guī)范推導(dǎo)，記作xαyxβy，其中y∈Vt*。若x只包含終結(jié)符或空，則稱最左推導(dǎo)。若α0

αn的每一步都是規(guī)范的，那么α0

αn稱為規(guī)范的。記作α0

αn。+++§2.4句型和句子1.句型

*有文法G[Z]，若Zx，則稱x是文法G的句型。例：G[S]：S→0S1，S→01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111等

G的句子00001111,01等2.句子

對(duì)文法G[Z]，若Zx，且x∈VT*，則稱x是文法G的句子。+§2.4句型和句子注意：

（1）句子是特色的句型

（2）規(guī)范推導(dǎo)產(chǎn)生的句型為規(guī)范句型

（3）每個(gè)句子都有一個(gè)規(guī)范推導(dǎo)

（4）并非每一個(gè)句型都有規(guī)范推導(dǎo)§2.5語言例：G[S]：S→0S1，S→01S0S100S110n-1S1n-10n1n

L(G)={0n1n|n≥1}

文法G生成的語言記為L(zhǎng)(G(Z))，它是文法G(Z)的一切句子的集合:

L(G(Z))={x|Zx，且x∈VT*}+注意：給定一文法，就能從結(jié)構(gòu)上唯一的確定其語言；給定一種語言，能確定其文法，但不唯一。例：G[A]:A→0RA→01R→A1L(G(A))={0n1n|n≥1}

G和G'是兩個(gè)不同的文法，若L(G)=L(G'),

則G和G’為等價(jià)文法?！?.5語言

給定文法G[A]：A→bA|cc，下面的符號(hào)串中，為該文法句子的是：①cc②bcbc③bcbcc④bccbcc⑤bbbcc練習(xí)√√注意：

已知文法求語言，通過推導(dǎo)；

已知語言構(gòu)造文法，全憑經(jīng)驗(yàn)。已知句子L(G)={abna|n≥1}，構(gòu)造文法。練習(xí)G1[S]：S→aBa，B→b|BbG2[S]：S→aBa，B→b|bB2.6.1遞歸規(guī)則§2.6遞歸規(guī)則與遞歸文法指在規(guī)則右部含有規(guī)則左部相同符號(hào)的規(guī)則，例如U→xUy；U→Uy稱左遞歸規(guī)則；U→xU稱右遞歸規(guī)則。2.6.2遞歸文法直接遞歸：包含至少一條遞歸規(guī)則間接遞歸：經(jīng)過幾步推導(dǎo)，造成文法的遞歸性§2.6遞歸規(guī)則與遞歸文法2.6.2遞歸文法遞歸文法：對(duì)文法中的任一非終結(jié)符號(hào)，若能建立一個(gè)推導(dǎo)過程，推導(dǎo)所得的符號(hào)串中又出現(xiàn)了該終結(jié)符號(hào)，則稱文法是遞歸的，否則是非遞歸的。*遞歸文法使人們能用有窮的文法刻畫無窮語言例：判定如下文法描述的語言是否是有窮的Z→aBaB→bB|b§2.7短語、簡(jiǎn)單短語和句柄對(duì)文法G[Z]，w=xuy是文法的一個(gè)句型。如

果有ZxUy且Uu，U∈Vn，u∈V+則稱u

是句型

w相對(duì)于非終結(jié)符U的短語。如有Uu，則稱u是句型w相對(duì)于非終結(jié)符U的直接短語，也稱簡(jiǎn)單短語。一個(gè)句型的最左簡(jiǎn)單短語稱為該句型的句柄?！?.7短語、簡(jiǎn)單短語和句柄例2-7：對(duì)于文法G[<無符號(hào)整數(shù)>]，確定句型<數(shù)字串1>的所有短語、簡(jiǎn)單短語和句柄推導(dǎo)過程：<無符號(hào)整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字串>1（1）<無符號(hào)整數(shù)><無符號(hào)整數(shù)><無符號(hào)整數(shù)><數(shù)字串>1<數(shù)字串>1是相對(duì)<無符號(hào)整數(shù)>的短語（2）<無符號(hào)整數(shù)><數(shù)字串><數(shù)字串><數(shù)字串>1<數(shù)字串>1是相對(duì)<數(shù)字串>的短語（3）<無符號(hào)整數(shù)><數(shù)字串><數(shù)字><數(shù)字>11是相對(duì)<數(shù)字>的短語，簡(jiǎn)單短語，句柄§2.8語法樹

設(shè)文法G=(VN,VT,P,Z)，若一棵樹滿足下列4個(gè)條件，則此樹稱作G的語法樹(推導(dǎo)樹或分析樹）：每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記，此標(biāo)記是V的一個(gè)符號(hào)根的標(biāo)記是Z如果結(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)生式樹的葉結(jié)點(diǎn)符號(hào)從左至右恰好構(gòu)成句型推導(dǎo)過程用圖表示，即語法樹，也叫推導(dǎo)樹§2.8語法樹語法樹的畫法

方法：把開始符號(hào)做為根結(jié)點(diǎn)，對(duì)每一個(gè)直接推導(dǎo)畫一個(gè)分支，分支的名字是直接推導(dǎo)中被替換的非終結(jié)符號(hào)，直到再無分支可畫結(jié)束。例如：推導(dǎo)SABAcBdAccddabccddSBBdbaAcdc§2.8語法樹語法樹的用途

用于描述句型和句子的語法結(jié)構(gòu)。句型的推導(dǎo)過程對(duì)應(yīng)于語法樹的構(gòu)造過程。例:G[S]:S→aAS|a A→SbA|SS|ba構(gòu)造句型aabbaa的語法樹

從左到右讀出語法樹的葉子標(biāo)記連接成的文法符號(hào)串，為G[S]的句型。SSaAASbaaba§2.8語法樹練習(xí)：<無符號(hào)整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字串>3<數(shù)字串><數(shù)字>3<數(shù)字串>23<數(shù)字>23123無符號(hào)整數(shù)數(shù)字串?dāng)?shù)字串?dāng)?shù)字?jǐn)?shù)字串?dāng)?shù)字?jǐn)?shù)字123§2.9子樹和短語子樹：由該樹的某個(gè)結(jié)點(diǎn)(子樹的根)連同它所有的后裔構(gòu)成，子樹與短語一一對(duì)應(yīng)。例:根據(jù)G[<無符號(hào)整數(shù)>]，找句子123的短語，簡(jiǎn)單短語和句柄子樹1：樹根<無符號(hào)整數(shù)>，短語123子樹2：樹根<數(shù)字串>，短語123子樹3：樹根<數(shù)字串>，短語12子樹4：樹根<數(shù)字串>，短語1子樹5：樹根<數(shù)字>，短語1，簡(jiǎn)單短語，句柄子樹6：樹根<數(shù)字>，短語2，簡(jiǎn)單短語子樹7：樹根<數(shù)字>，短語3，簡(jiǎn)單短語短語為123,12,1,2,3；簡(jiǎn)單短語1,2,3；句柄1?！?.10由樹構(gòu)造推導(dǎo)過程復(fù)習(xí)：最左推導(dǎo)和最右推導(dǎo)

如果在推導(dǎo)的任何一步αβ，其中

α、β是句型，都是對(duì)α中的最左

（右）非終結(jié)符進(jìn)行替換，則稱為最左

（右）推導(dǎo)。在形式語言中，最右推導(dǎo)常被稱作規(guī)范

推導(dǎo)。由規(guī)范推導(dǎo)所得的句型稱為規(guī)范

句型?！?.10由樹構(gòu)造推導(dǎo)過程從上到下：從根開始，由上逐層向下，用子結(jié)點(diǎn)代替父

結(jié)點(diǎn)。當(dāng)一層中有兩棵子樹時(shí)，原則上選擇

哪棵都可以，若每步都對(duì)右邊樹根進(jìn)行替換，

則構(gòu)造出的推導(dǎo)為規(guī)范推導(dǎo)。從下而上：由下而上逐層修剪子樹末端結(jié)點(diǎn)，當(dāng)有兩棵

子樹時(shí)，原則上選擇哪棵都可以，若每次總

是修剪最左邊的子樹，稱規(guī)范規(guī)約。規(guī)范推導(dǎo)與規(guī)范規(guī)約互為逆過程§2.10由樹構(gòu)造推導(dǎo)過程例：對(duì)下圖語法樹自底向上及自上向下建立推導(dǎo)過程<無符號(hào)整數(shù)><數(shù)字串><數(shù)字串><數(shù)字><數(shù)字串>3<數(shù)字串><數(shù)字>3<數(shù)字串>23<數(shù)字>23123123

<數(shù)字>23<數(shù)字串>23<數(shù)字串><數(shù)字>3<數(shù)字串>3<數(shù)字串><數(shù)字><數(shù)字串><無符號(hào)整數(shù)>§2.11文法的二義性

若一個(gè)文法存在某個(gè)句子或句型，它存在兩棵不同的語法樹，則稱該句子或句型是二義性的，對(duì)應(yīng)的文法也是二義性的。

例：有文法G[E]，E::=i|(E)|E*E|E+E，分析該文法是否具有二義性。EE+EE*EiiiEE*EiE+Eii考慮句子i*i+i的語法樹該文法具有二義性§2.11文法的二義性練習(xí):<語句>::=if<布爾表達(dá)式>then<語句>|if<布爾表達(dá)式>then<語句>else<語句>|<其它>說明該文法是二義性文法提示：if<布爾表達(dá)式>thenif<布爾表達(dá)式>then<語句>else<語句>§2.11語法樹和二義性

以上是自頂向下來看文法的二義性，我們還可以自底向上來看文法的二義性。語法的二義性意味著句型的句柄不唯一。如句型E+E*i。EEE+EE*iEEE*EE+i§2.11文法的二義性

若文法是二義性的，則在編譯時(shí)就會(huì)產(chǎn)生不確定性，遺憾的是在理論上已經(jīng)證明：文法的二義性是不可判定的，即不可能構(gòu)造出一個(gè)算法，通過有限步驟來判定任一文法是否有二義性?，F(xiàn)在的解決辦法是：提出一些限制條件，稱為無二義性的充分條件，當(dāng)文法滿足這些條件時(shí)，就可以判定文法是無二義性的。EE*EiE+Eii§3.4語法樹和二義性四、文法的二義性SifE1thenSifE2thenS1elseS2SifE1thenSelseS2ifE2thenS1EE+EE*Eiii§2.12有關(guān)文法的實(shí)用限制有害規(guī)則：形如U→U的產(chǎn)生式。會(huì)引起文法的二義性，若有，則刪去。

例如存在U::=U，U::=a|b,則有兩棵語法樹：UaUUa§2.12有關(guān)文法的實(shí)用限制多余規(guī)則：指文法中任何句子的推導(dǎo)都不會(huì)用到的規(guī)則，若有，則刪去。文法中某些非終結(jié)符不在任何規(guī)則的右部出現(xiàn)，該非終結(jié)符稱為不可到達(dá)。文法中某些非終結(jié)符，由它不能推出終結(jié)符號(hào)串，該非終結(jié)符稱為不可終止。§2.12有關(guān)文法的實(shí)用限制例：G[Z]：

1）Z→Aa 2)A→Ca|Bb 3)B→Ba|a 4)C→Cb 5)D→b

多余規(guī)則，C為不可終止非終結(jié)符多余規(guī)則，D為不可到達(dá)非終結(jié)符多余規(guī)則§2.12有關(guān)文法的實(shí)用限制

練習(xí)：G[S]：1)S→Be 2)B→Ce 3)B→Af 4)A→Ae 5)A→e 6)C→Cf 7)D→f

推不出終結(jié)符號(hào)串，為多余規(guī)則推不出終結(jié)符號(hào)串，為多余規(guī)則。C為不可終止的非終結(jié)符。D不在右部出現(xiàn)，為多余規(guī)則。D為不可到達(dá)的非終結(jié)符。§2.13文法的分類Chomsky對(duì)文法中的規(guī)則施加不同限制，將文法和語言分為四大類：0型文法0型語言或短語結(jié)構(gòu)語言1型文法1型語言或上下文有關(guān)語言2型文法2型語言或上下文無關(guān)語言3型文法3型語言或正則（正規(guī)）語言§2.13文法的分類

對(duì)任一產(chǎn)生式α→β，都有α∈V+，β∈V*，即α，β均是V上的符號(hào)序列，但α不能為空，β可為空。1、0型文法(短語結(jié)構(gòu)文法)說明：對(duì)產(chǎn)生式基本無限制例：文法G，其中VN={A,B,S}VT={0,1}P={S→0AB1B→0B→SA|01A1→SB1A0→S0B}§2.13文法的分類有如下形式規(guī)則：αUβ→αuβ，其中U∈Vn，α,β∈V*,u∈V+,左部可為符號(hào)序列，其中U為非終結(jié)符號(hào)且只有左右為α,β的環(huán)境下U可