鄭州大學(xué)編譯原理第2章

第二章高級(jí)語(yǔ)言及其語(yǔ)法描述概述程序語(yǔ)言的結(jié)構(gòu)和主要的共同特征介紹程序語(yǔ)言的語(yǔ)法描述方法學(xué)習(xí)構(gòu)造編譯程序，必須掌握如下內(nèi)容：源語(yǔ)言（詞法、語(yǔ)法、語(yǔ)義）目標(biāo)語(yǔ)言（硬件系統(tǒng)結(jié)構(gòu)、指令集合、操作系統(tǒng)的功能）編譯方法

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!§2.1程序語(yǔ)言的定義

程序語(yǔ)言是一個(gè)記號(hào)系統(tǒng)，主要有語(yǔ)法、語(yǔ)義和語(yǔ)用等三方面定義?！裾Z(yǔ)法定義語(yǔ)言的詞法和語(yǔ)法的形式規(guī)則●語(yǔ)義定義語(yǔ)言的單詞符號(hào)和語(yǔ)法單位的意義●語(yǔ)用定義程序設(shè)計(jì)技術(shù)和語(yǔ)言成分的使用方法，它使語(yǔ)言的基本概念與語(yǔ)言的外界聯(lián)系起來(lái)鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!2.1.1語(yǔ)法

●

一個(gè)語(yǔ)言的語(yǔ)法規(guī)則定義了程序的形式結(jié)構(gòu)?！?/p>

任何語(yǔ)言程序都可看成是一定字符集上的一個(gè)字符串（有限序列）?！?/p>

語(yǔ)法規(guī)則是指這樣的一組規(guī)則，用它可以形成和產(chǎn)生一合式（合法）的程序。這些規(guī)則的一部分稱為詞法規(guī)則，另一部分稱為語(yǔ)法規(guī)則（或產(chǎn)生規(guī)則）。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!例如：字符串0.5*x+c

單詞符號(hào)：0.5xc*+語(yǔ)法單位：0.5*x+c（表達(dá)式）鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!語(yǔ)法規(guī)則語(yǔ)法規(guī)則規(guī)定了如何從單詞符號(hào)串中形成更大的結(jié)構(gòu)（即語(yǔ)法單位）。它是語(yǔ)法單位的形成規(guī)則。語(yǔ)法單位包括：表達(dá)式、語(yǔ)句、分程序、函數(shù)、過(guò)程、程序。描述語(yǔ)法規(guī)則的有效工具：上下文無(wú)關(guān)文法鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!2.1.3程序

所謂程序，是描述一定數(shù)據(jù)的處理過(guò)程，即包括描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算兩個(gè)功能。

程序結(jié)構(gòu)：程序子程序或分程序語(yǔ)句表達(dá)式數(shù)據(jù)引用算符函數(shù)調(diào)用

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!程序結(jié)構(gòu)

一個(gè)高級(jí)語(yǔ)言程序通常由若干子程序段（過(guò)程、函數(shù)）構(gòu)造。許多語(yǔ)言還引入了類、程序包等更高級(jí)的結(jié)構(gòu)。一、FORTRAN

一個(gè)Fortran程序由一個(gè)主程序和若干個(gè)輔程序段組成。

PROGRAMMAIN …… END SUBROUTINESUB1 …… END SUBROUTINESUB1 …… END

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!三、Ada

在Ada語(yǔ)言中引入了程序包（Package），它可以把數(shù)據(jù)和操作代碼封裝在一起，支持?jǐn)?shù)據(jù)抽象。一個(gè)程序包有兩部分：

可見的規(guī)范說(shuō)明：定義程序包外面可以訪問(wèn)的對(duì)象。程序包體：定義程序包的實(shí)現(xiàn)細(xì)節(jié)。

見P17

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!數(shù)據(jù)類型與操作一個(gè)數(shù)據(jù)類型通常包括以下三個(gè)要素：

●

用于區(qū)別這種類型的數(shù)據(jù)對(duì)象的屬性；

（類型名，作用域）

●

這種類型的數(shù)據(jù)對(duì)象可以具有的值；

（取值范圍）

●

可以作用于這種類型的數(shù)據(jù)對(duì)象的操作。

（運(yùn)算符）鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!語(yǔ)句與控制結(jié)構(gòu)一、表達(dá)式

表達(dá)式是由運(yùn)算量和運(yùn)算符組成的。運(yùn)算量亦稱操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用；運(yùn)算符有算術(shù)運(yùn)算符、邏輯運(yùn)算符、關(guān)系運(yùn)算符等，運(yùn)算符之間有規(guī)定的優(yōu)先級(jí)和結(jié)合性。表達(dá)式的形成規(guī)則：（1）變量、常量是表達(dá)式；（2）若E1，E2為表達(dá)式，是二元運(yùn)算符，則E1E2也是表達(dá)式；（3）若E為表達(dá)式，是一元運(yùn)算符，則

E(或E)也是表達(dá)式；(4)若E為表達(dá)式,則(E)也是表達(dá)式。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!§2.3程序語(yǔ)言的語(yǔ)法描述本節(jié)介紹高級(jí)語(yǔ)言語(yǔ)法結(jié)構(gòu)的形式化描述問(wèn)題基本概念

設(shè)∑是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)符號(hào)。∑上的一個(gè)符號(hào)串是指由∑中的符號(hào)所構(gòu)成的一個(gè)有窮序列。不包含任何符號(hào)的序列稱為空字，記為ε。

∑*表示∑上的所有符號(hào)串組成的集合。空字ε也包括在其中。

Φ表示不含任何元素的空集{}。

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!上下文無(wú)關(guān)文法

文法是描述語(yǔ)言語(yǔ)法結(jié)構(gòu)的形式規(guī)則，即語(yǔ)法規(guī)則。語(yǔ)法規(guī)則必須是正確的，且易于理解。

上下文無(wú)關(guān)文法是這樣一種文法，它所定義的語(yǔ)法范疇是完全獨(dú)立于這種范疇所可能出現(xiàn)的環(huán)境的。以后，凡“文法”一詞若無(wú)特別說(shuō)明，則均指上下文無(wú)關(guān)文法。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!例如:判斷Hegavemeabook.是否為正確句子

方法一：<句子><主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)><代詞><動(dòng)詞><代詞><冠詞><名詞>

Hegavemeabook若能利用語(yǔ)法規(guī)則，畫出其語(yǔ)法分析樹，則證明是正確的句子。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!上下文無(wú)關(guān)文法定義

歸納起來(lái)，一個(gè)上下文無(wú)關(guān)文法包括四個(gè)組成部分：一組終結(jié)符號(hào)如：me,book,gave等一組非終結(jié)符號(hào)如：<主語(yǔ)>，<謂語(yǔ)>等一個(gè)開始符號(hào)如:<句子>一組產(chǎn)生式如：

<間接賓語(yǔ)>→<代詞><直接賓語(yǔ)>→<冠詞><名詞>

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!若產(chǎn)生式的左部相同，則可以合并。例如：

P→α1P→α2

…P→αn可合并為：

P→α1|α2|…|αn

其中：每個(gè)αi稱為P的一個(gè)侯選式“→”讀為“定義為”“|”讀為“或”鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!例如：算術(shù)表達(dá)式的定義1.常量5、變量i是算術(shù)表達(dá)式；2.若E1，E2是算術(shù)表達(dá)式，則E1+E2,E1*E2,(E1)也是算術(shù)表達(dá)式。用產(chǎn)生式來(lái)描述G(E)：

E→E+EE→E﹡EE→(E)E→iE→5EE+E|E*E|(E)|i|5鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!例題證明i+5是一個(gè)算術(shù)表達(dá)式證明： E=>E+E(∵EE+E)

=>i+E(∵Ei)=>i+5(∵E5)故

i+5是算術(shù)表達(dá)式。解釋：=>僅表示使用一次規(guī)則的一步推導(dǎo)。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!4.用1n表示從1出發(fā)，經(jīng)過(guò)0步或多步，可推導(dǎo)出n即

1n意味著1=n或

1n

5.若S是開始符號(hào)，且S

則稱是文法的一個(gè)句型若

∈

VT*，則稱為文法的一個(gè)句子。術(shù)語(yǔ)**+*鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!例題2.2分析過(guò)程：A=>aA=>aaA=>aaaA=>……=>a…aB=>Bb=>Bbb=>Bbbb=>…….=>b…bS=>AB=>……=>a…ab…b文法G2:

SABAa|aABb|Bb求該文法定義的語(yǔ)言？解：G2定義的語(yǔ)言為：

L(G2)={ambn|m,n>0}鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!例題2.4構(gòu)造一個(gè)文法G4，使得

L(G4)={anban|n≧0}正解：文法G4:SaSa|b誤解：文法G4:SAbAAε|aA因?yàn)镾AbAbAbaA

baaAbaa

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!最左推導(dǎo)和最右推導(dǎo)下面兩個(gè)推導(dǎo)都是正確的:

(1)E+EE+ii+i

(2)E+Ei+Ei+i

從一個(gè)句型到另一個(gè)句型的推導(dǎo)過(guò)程不是唯一的。例如：E+Ei+i

為了對(duì)句子的結(jié)構(gòu)進(jìn)行確定性的分析，往往只考慮最左推導(dǎo)和最右推導(dǎo)。+鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!2.3.2語(yǔ)法分析樹和二義性語(yǔ)法分析樹也可以描述一個(gè)句型的推導(dǎo)。語(yǔ)法樹的根由開始符號(hào)所標(biāo)記。隨著推導(dǎo)的展開，當(dāng)某個(gè)非終結(jié)符被它的某個(gè)候選式所替換時(shí)，就產(chǎn)生下一代新結(jié)，候選式中自左自右的每個(gè)字符對(duì)應(yīng)一個(gè)新結(jié)。在一棵語(yǔ)法樹生長(zhǎng)過(guò)程中的任何時(shí)刻，所有那些沒有后代的端末（葉子）自左自右排列起來(lái)就是一個(gè)句型。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!

一棵語(yǔ)法樹是一個(gè)句型的種種不同推導(dǎo)過(guò)程的共性抽象，是它們的代表。一棵語(yǔ)法樹完全等價(jià)于一個(gè)最左（右）推導(dǎo)。文法的二義性

一個(gè)句型是否只對(duì)應(yīng)唯一的一棵語(yǔ)法樹呢？即，它是否只有唯一的一個(gè)最左推導(dǎo)？不盡然。例如：句子(i+i*i)就存在兩個(gè)不同的最左推導(dǎo)：(1)

E(E)(E+E)(i+E)(i+E*E)(i+i*E)(i+i*i)(2)E(E)(E*E)(E+E*E)(i+E*E)(i+i*E)(i+i*i)鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!

文法的二義性與語(yǔ)言的二義性是兩個(gè)不同的概念。注意：例題2.4

對(duì)算術(shù)表達(dá)式構(gòu)造一個(gè)無(wú)二義的文法。解：無(wú)二義的文法如下：

ET|E+TTF|T*FF(E)|i|5提示：考慮算符的優(yōu)先性和結(jié)合性。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!2.3.3形式語(yǔ)言鳥瞰（1）自從Chomsky于1956年建立形式語(yǔ)言的描述以來(lái)，形式語(yǔ)言的理論發(fā)展得很快。這種理論對(duì)計(jì)算機(jī)科學(xué)有著深刻的影響，特別是對(duì)程序語(yǔ)言的設(shè)計(jì)、編譯方法和計(jì)算復(fù)雜性等方面更有重大的作用。

Chomsky把文法分成四種類型，即0型、1型、2型和3型。這幾類文法的差別,在于對(duì)產(chǎn)生式的形式施加了不同的限制。從0型到3型依次增強(qiáng)，但它們表達(dá)語(yǔ)言的能力則依次減弱。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!2.3.3形式語(yǔ)言鳥瞰（3）1型文法又稱為上下文有關(guān)文法。2型文法又稱為上下文無(wú)關(guān)文法。3型文法又稱為正則（規(guī)）文法（或線性文法）。（1）若3型文法產(chǎn)生式的形式為：

A→αB或A→α則稱為右線性文法。（2）若3型文法產(chǎn)生式的形式為：

A→Bα或A→α則稱為左線性文法。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!(2)若產(chǎn)生式為A→αB，即A→a1a2…akB

則引入K-1個(gè)非終結(jié)符B1,B2,…,

Bk-1，此產(chǎn)生式等價(jià)于A→a1B1

B1→a2B2……Bk-2→ak-1Bk-1

Bk-1→akB因此，右線性文法的任何產(chǎn)生式均可表示為：A→a

BA→a

（證畢）鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!單詞符號(hào)單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本結(jié)構(gòu)。詞法規(guī)則定義了程序中單詞符號(hào)的形成規(guī)則。即字母表中的哪些字符可以構(gòu)成一個(gè)合法的單詞。單詞符號(hào)種類：常量、標(biāo)識(shí)符、基本字、界符、運(yùn)算符描述詞法規(guī)則的有效工具：

正規(guī)式、正規(guī)文法、有限自動(dòng)機(jī)鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!2.1.2語(yǔ)義語(yǔ)義規(guī)則是指這樣的一組規(guī)則，使用它可以定義一個(gè)程序的意義。描述語(yǔ)義規(guī)則的工具：基于屬性文法的語(yǔ)法制導(dǎo)下的翻譯方法

對(duì)于一個(gè)語(yǔ)言來(lái)說(shuō)，不僅要定義它的詞法、語(yǔ)法規(guī)則，而且還要定義它的單詞符號(hào)和語(yǔ)法單位的意義。這就是語(yǔ)義問(wèn)題。離開語(yǔ)義，語(yǔ)言只不過(guò)是一堆符號(hào)的集合。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!§2.2高級(jí)語(yǔ)言的一般特性高級(jí)語(yǔ)言的分類

從語(yǔ)言范型來(lái)分，程序設(shè)計(jì)語(yǔ)言分四類：●強(qiáng)制式語(yǔ)言（ImperativeLanguage）●應(yīng)用式語(yǔ)言（ApplicativeLanguage）●基于規(guī)則的語(yǔ)言（Rule-basedLanguage）●面向?qū)ο笳Z(yǔ)言（Object-OrientedLanguage）鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!二、PascalPascal是一個(gè)允許子程序嵌套的語(yǔ)言。

ProgramEX ……{說(shuō)明部分} procedureP1; …… procedurep11; …… begin …… end;

begin …… end;

Begin

……

{執(zhí)行語(yǔ)句部分}

End.

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!四、JAVA

Java是一種面向?qū)ο蟮母呒?jí)程序語(yǔ)言，它很重要的方面是類（Class）及繼承（Inheritance）的概念。同時(shí)支持多態(tài)性（Polymorphism）和動(dòng)態(tài)綁定（Dynamicbinding）等特性。

見P18鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!一、初等數(shù)據(jù)類型

數(shù)值數(shù)據(jù)、邏輯數(shù)據(jù)、字符數(shù)據(jù)、指針類型二、數(shù)據(jù)結(jié)構(gòu)數(shù)組、記錄、字符串、表格、棧和隊(duì)列

三、抽象數(shù)據(jù)類型

一個(gè)抽象數(shù)據(jù)類型包括：

（1）數(shù)據(jù)對(duì)象的一個(gè)集合；（2）作用于這些數(shù)據(jù)對(duì)象的抽象運(yùn)算的集合；（3）這種類型對(duì)象的封裝。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!二、語(yǔ)句

1、賦值句2、控制語(yǔ)句無(wú)條件轉(zhuǎn)移語(yǔ)句條件語(yǔ)句循環(huán)語(yǔ)句過(guò)程（或函數(shù)）調(diào)用語(yǔ)句返回語(yǔ)句3、說(shuō)明句4、簡(jiǎn)單句和復(fù)合句 鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第34頁(yè)!●

∑*的子集U和V的（連接）積定義為

UV={αβ|α∈U&β∈V}即集合UV中的符號(hào)串是由U和V的符號(hào)串連接而成的?！馰自身的n次積（連接）記為

Vn

=VV…V●規(guī)定V0={ε}

V*=V0UV1UV2UV3U…

稱V*是V的閉包?！?/p>

V+=VV*稱V+是V的正則閉包。例如

若∑={a,b}則∑*={ε,a,b,aa,ab,ba,bb,aaa,…}

鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第35頁(yè)!例如：英文的語(yǔ)法規(guī)則<句子>→<主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)><主語(yǔ)>→<代詞><謂語(yǔ)>→<動(dòng)詞><間接賓語(yǔ)>→<代詞><直接賓語(yǔ)>→<冠詞><名詞><代詞>→He|me<冠詞>→a<動(dòng)詞>→gave<名詞>→book“→”表示“由…組成”或“定義為”。有時(shí)，“→”也用“::=”表示，后者為巴科斯范式（BNF），前者為其簡(jiǎn)化表示。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第36頁(yè)!方法二：利用規(guī)則進(jìn)行推導(dǎo)。句子<主語(yǔ)><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>

<代詞><謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>

He<謂語(yǔ)><間接賓語(yǔ)><直接賓語(yǔ)>

He<動(dòng)詞><間接賓語(yǔ)><直接賓語(yǔ)>

Hegave<間接賓語(yǔ)><直接賓語(yǔ)>

Hegave<代詞><直接賓語(yǔ)>

Hegaveme<直接賓語(yǔ)>

Hegaveme<冠詞><名詞>

Hegavemea<名詞>

Hegavemeabook鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第37頁(yè)!上下文無(wú)關(guān)文法定義形式上說(shuō)，一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式：

G=（VT，VN，S，），其中：VT是一個(gè)非空有限集，它的每個(gè)元素為終結(jié)符號(hào)；VN是一個(gè)非空有限集，它的每個(gè)元素為非終結(jié)符號(hào)且VT∩VN=ΦS是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)；是產(chǎn)生式有限集合，形如A→α

其中：A∈VN，α∈(VTUVN)*。注：開始符號(hào)S是一個(gè)特殊的非終結(jié)符號(hào)，它至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第38頁(yè)!約定

1.大寫字母A、B、C……或漢語(yǔ)詞組通常代表非終結(jié)符；2.小寫字母a、b、c……代表終結(jié)符；3.、、……代表(VTUVN)*例如：下面是一個(gè)上下文無(wú)關(guān)文法。

G(E):

Ei|EAEA*|+鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第39頁(yè)!一個(gè)上下文無(wú)關(guān)文法是如何定義一個(gè)語(yǔ)言呢?

從開始符號(hào)出發(fā),反復(fù)連續(xù)使用產(chǎn)生式,對(duì)非終結(jié)符施行替換和展開,直到推導(dǎo)的字符串全由終結(jié)符組成（即句子），所有句子的集合即為該文法定義的語(yǔ)言。例如：文法G(S):SABAa|aABb|Bb則該文法定義的語(yǔ)言為：

L(G)={ambn|m,n>0}鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第40頁(yè)!術(shù)語(yǔ)1.稱串A能直接推出，即：A僅當(dāng)A

是一個(gè)產(chǎn)生式。2.

如果1

2……n

則稱從1可推導(dǎo)出n

3.用1n表示從1出發(fā)，經(jīng)過(guò)一步或多步，可推導(dǎo)出n

+鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第41頁(yè)!術(shù)語(yǔ)例題2.1

設(shè)文法G1如下，求所定義的語(yǔ)言？SbA

Aa|aA6.文法G所產(chǎn)生的句子的全體構(gòu)成一個(gè)語(yǔ)言L(G)

L(G)={|S&∈

VT*

}

分析：⑴S=>bA=>ba⑵S=>bA=>baA=>baaA=>…….=>baa…a解：L(G1)={ban|n>0}*鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第42頁(yè)!例題2.3誤解：文法G3:SABAa|aABb|bB構(gòu)造一個(gè)文法G3，使得

L(G3)={anbn|n>0}正解：文法G3:

SaSb|ab鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第43頁(yè)!例題2.5構(gòu)造一個(gè)文法G4，使得

L(G4)={ambn|m>n≧0}正解：文法G4:

SABAa|aABaBb|ε鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第44頁(yè)!最左推導(dǎo):

是指任何一步推導(dǎo)都是對(duì)的最左非終結(jié)符進(jìn)行替換的。最右推導(dǎo)：是指任何一步推導(dǎo)都是對(duì)的最右非終結(jié)符進(jìn)行替換的。例如：寫出句型(i+i*i)的最左推導(dǎo)。解：E(E)(E+E)(i+E)

(i+E*E)(i+i*E)(i+i*i)鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第45頁(yè)!

一棵語(yǔ)法樹表示了一個(gè)句型的種種可能的不同推導(dǎo)過(guò)程，它有助于理解一個(gè)句子語(yǔ)法結(jié)構(gòu)的層次。

E（E）E+EiE*Eii例如：

畫出句子(i+i*i)的語(yǔ)法樹。∵E(E)鄭州大學(xué)編譯原理第2章共51頁(yè)，您現(xiàn)在瀏覽的是第46頁(yè)!

在一個(gè)文法中，若存在某個(gè)句子有兩個(gè)