高級(jí)語(yǔ)言及其語(yǔ)法描述

1、第二章第二章 高級(jí)語(yǔ)言及其語(yǔ)法描述高級(jí)語(yǔ)言及其語(yǔ)法描述程序語(yǔ)言的定義程序語(yǔ)言的定義( (語(yǔ)法、語(yǔ)義語(yǔ)法、語(yǔ)義) )高級(jí)語(yǔ)言的一般特性（標(biāo)識(shí)符、數(shù)組等）高級(jí)語(yǔ)言的一般特性（標(biāo)識(shí)符、數(shù)組等）程序語(yǔ)言的語(yǔ)法描述程序語(yǔ)言的語(yǔ)法描述程序語(yǔ)言的定義程序語(yǔ)言的定義n程序語(yǔ)言主要由兩方面定義：程序語(yǔ)言主要由兩方面定義：n語(yǔ)法語(yǔ)法：一組規(guī)則，用來(lái)形成和產(chǎn)生一個(gè)合式：一組規(guī)則，用來(lái)形成和產(chǎn)生一個(gè)合式(well-formed)的程序的程序n詞法規(guī)則詞法規(guī)則n語(yǔ)法規(guī)則語(yǔ)法規(guī)則n語(yǔ)義語(yǔ)義: :一組規(guī)則，用來(lái)定義一個(gè)程序的意義一組規(guī)則，用來(lái)定義一個(gè)程序的意義單詞符號(hào)的形成規(guī)則。單詞符號(hào)的形成規(guī)則。單詞符號(hào)：常數(shù)、標(biāo)識(shí)符、

2、基本字、單詞符號(hào)：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符。算符、界符。描述及分析：正規(guī)式和有窮自動(dòng)機(jī)描述及分析：正規(guī)式和有窮自動(dòng)機(jī)詞法規(guī)則詞法規(guī)則語(yǔ)法單位的形成規(guī)則。語(yǔ)法單位的形成規(guī)則。語(yǔ)法單位：表達(dá)式、語(yǔ)句、分程序、語(yǔ)法單位：表達(dá)式、語(yǔ)句、分程序、函數(shù)、過(guò)程、程序等。函數(shù)、過(guò)程、程序等。描述及分析：上下文無(wú)關(guān)文法描述及分析：上下文無(wú)關(guān)文法語(yǔ)法規(guī)則語(yǔ)法規(guī)則用來(lái)定義一個(gè)程序的意義的規(guī)則。用來(lái)定義一個(gè)程序的意義的規(guī)則。描述：屬性文法描述：屬性文法分析：語(yǔ)法制導(dǎo)翻譯分析：語(yǔ)法制導(dǎo)翻譯語(yǔ)義語(yǔ)義n程序語(yǔ)言的基本功能：描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。程序語(yǔ)言的基本功能：描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。n所謂程序，本質(zhì)上說(shuō)是描述

3、一定數(shù)據(jù)的處理過(guò)程。所謂程序，本質(zhì)上說(shuō)是描述一定數(shù)據(jù)的處理過(guò)程。程序程序| |子程序或分程序、過(guò)程、函數(shù)子程序或分程序、過(guò)程、函數(shù)| |語(yǔ)句語(yǔ)句| |表達(dá)式表達(dá)式| |數(shù)據(jù)引用數(shù)據(jù)引用 算符算符 函數(shù)調(diào)用函數(shù)調(diào)用高級(jí)語(yǔ)言的一般特性高級(jí)語(yǔ)言的一般特性標(biāo)識(shí)符與名字標(biāo)識(shí)符與名字n標(biāo)識(shí)符標(biāo)識(shí)符：以字母開(kāi)頭的，由字母數(shù)字：以字母開(kāi)頭的，由字母數(shù)字組成的字符串。組成的字符串。n標(biāo)識(shí)符標(biāo)識(shí)符與與名字名字兩者有本質(zhì)區(qū)別：兩者有本質(zhì)區(qū)別：n標(biāo)識(shí)符標(biāo)識(shí)符是語(yǔ)法概念是語(yǔ)法概念n名字名字有確切的意義和屬性有確切的意義和屬性標(biāo)識(shí)符與名字標(biāo)識(shí)符與名字n名字：名字：n值：左值指存儲(chǔ)單元，右值指單元中的內(nèi)值：左值指存儲(chǔ)單元，

4、右值指單元中的內(nèi)容容n屬性：類型和作用域?qū)傩裕侯愋秃妥饔糜騨名字的性質(zhì)的說(shuō)明方式：名字的性質(zhì)的說(shuō)明方式：n由說(shuō)明語(yǔ)句來(lái)明確規(guī)定的由說(shuō)明語(yǔ)句來(lái)明確規(guī)定的n隱含說(shuō)明：隱含說(shuō)明：FORTRAN FORTRAN 以以I,J,K,NI,J,K,N為首的名為首的名字代表整型，否則為實(shí)型。字代表整型，否則為實(shí)型。n動(dòng)態(tài)確定：走到哪里，是什么，算什么動(dòng)態(tài)確定：走到哪里，是什么，算什么 數(shù)組數(shù)組n邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成邏輯上，數(shù)組是由同一類型數(shù)據(jù)所組成的某種的某種n n維矩形結(jié)構(gòu)，沿著每一維的距維矩形結(jié)構(gòu)，沿著每一維的距離，稱為離，稱為下標(biāo)下標(biāo)。n數(shù)組可變與不可變：編譯時(shí)能否確定其存數(shù)組可變與不可變

5、：編譯時(shí)能否確定其存貯空間的大小。貯空間的大小。n訪問(wèn)：給出數(shù)組名和下標(biāo)值訪問(wèn)：給出數(shù)組名和下標(biāo)值n存放方式存放方式: : 按行存放按行存放, ,按列存放按列存放數(shù)組元素地址計(jì)算數(shù)組元素地址計(jì)算n地址計(jì)算與存儲(chǔ)方式密切相關(guān)地址計(jì)算與存儲(chǔ)方式密切相關(guān)n數(shù)組數(shù)組A10,20A10,20的的A1A1，11為為a a，各維下標(biāo)各維下標(biāo)為為1 1，按行存放，那么，按行存放，那么AiAi，jj地址為：地址為：a+(i-1)a+(i-1)* *20+(j-1)20+(j-1)n數(shù)組元素地址計(jì)算公式數(shù)組元素地址計(jì)算公式編譯時(shí)對(duì)數(shù)組處理編譯時(shí)對(duì)數(shù)組處理n把數(shù)組有關(guān)信息記錄在一個(gè)把數(shù)組有關(guān)信息記錄在一個(gè)“內(nèi)情向量

6、內(nèi)情向量”中中n每個(gè)數(shù)組的內(nèi)情向量必須包括：維數(shù)，各維每個(gè)數(shù)組的內(nèi)情向量必須包括：維數(shù)，各維的上、下限，首地址，以及數(shù)組（元素）的的上、下限，首地址，以及數(shù)組（元素）的類型。類型。l1 u1 d1 l2 u2 d2 ln un dn n C type a 程序語(yǔ)言的語(yǔ)法描述程序語(yǔ)言的語(yǔ)法描述2.3 2.3 程序語(yǔ)言的語(yǔ)法描述程序語(yǔ)言的語(yǔ)法描述 n幾個(gè)概念幾個(gè)概念: :n考慮一個(gè)考慮一個(gè)有窮有窮 字母表字母表 字符集字符集n其中每一個(gè)元素稱為一個(gè)其中每一個(gè)元素稱為一個(gè)字符字符n上的上的字字( (也叫也叫字符串字符串) ) 是指由是指由中的字符所中的字符所構(gòu)成的一個(gè)有窮序列構(gòu)成的一個(gè)有窮序列n不包

7、含任何字符的序列稱為不包含任何字符的序列稱為空字空字，記為，記為n用用* *表示表示上的所有上的所有字的全體字的全體, ,包含空字包含空字n用用 表示不含任何元素的表示不含任何元素的空集空集例如例如: : 設(shè)設(shè) =a=a， bb，則，則 * *=,a,b,aa,ab,ba,bb,aaa,.=,a,b,aa,ab,ba,bb,aaa,.n*的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U & V n設(shè)：設(shè)：U a, aa V b, bb n那么：那么：UV= ab, abb, aab, aabb n*的子集的子集U和和V的的連接連接（積積）定義為）定義為UV | U &

8、amp; V nV自身的自身的 n次積記為次積記為Vn=VVVn規(guī)定規(guī)定V0= ，令，令 V*=V0V1V2V3 稱稱V*是是V的的閉包閉包;n記記 VVV* ，稱，稱V+是是V的正規(guī)閉包。的正規(guī)閉包。n設(shè)：設(shè)：U a, aa n那么：那么： U* = , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, n字母表包含了語(yǔ)言中所允許出現(xiàn)的一切符號(hào)。字母表包含了語(yǔ)言中所允許出現(xiàn)的一切符號(hào)。n一個(gè)語(yǔ)言的句子總是它的字母表的符號(hào)串。一個(gè)語(yǔ)言的句子總是它的字母表的符號(hào)串。這個(gè)符號(hào)串的組成必須是按照文法規(guī)則組合這個(gè)符號(hào)串的組成必須是按照文法規(guī)則組合而成的。而成的。n在本課程

9、中，語(yǔ)言被認(rèn)為是句子的集合。所在本課程中，語(yǔ)言被認(rèn)為是句子的集合。所以，一個(gè)語(yǔ)言就是對(duì)應(yīng)于它的字母表上的一以，一個(gè)語(yǔ)言就是對(duì)應(yīng)于它的字母表上的一個(gè)符號(hào)串集合個(gè)符號(hào)串集合n語(yǔ)法分析的一個(gè)重要任務(wù)就是：判斷一個(gè)符語(yǔ)法分析的一個(gè)重要任務(wù)就是：判斷一個(gè)符號(hào)串的組成是否滿足某個(gè)文法的規(guī)定。號(hào)串的組成是否滿足某個(gè)文法的規(guī)定。文法文法通俗地講，文法是用來(lái)精確而無(wú)歧義地通俗地講，文法是用來(lái)精確而無(wú)歧義地描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（語(yǔ)法描述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則（語(yǔ)法規(guī)則）。規(guī)則）。文法描述語(yǔ)言的時(shí)候不考慮語(yǔ)言的含義。文法描述語(yǔ)言的時(shí)候不考慮語(yǔ)言的含義。一般采用一般采用上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法來(lái)描述程序

10、設(shè)來(lái)描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則。計(jì)語(yǔ)言的語(yǔ)法規(guī)則。HeHe swims in river. swims in river.有關(guān)語(yǔ)法規(guī)則：有關(guān)語(yǔ)法規(guī)則：句子句子 主語(yǔ)謂語(yǔ)狀語(yǔ)主語(yǔ)謂語(yǔ)狀語(yǔ)主語(yǔ)主語(yǔ) 代詞代詞謂語(yǔ)謂語(yǔ) 動(dòng)詞動(dòng)詞狀語(yǔ)狀語(yǔ) 介詞介詞 名詞名詞代詞代詞HeHe動(dòng)詞動(dòng)詞swimsswims介詞介詞inin名詞名詞riverriver推導(dǎo)過(guò)程：句子推導(dǎo)過(guò)程：句子=主語(yǔ)謂語(yǔ)狀語(yǔ)主語(yǔ)謂語(yǔ)狀語(yǔ)=名詞謂語(yǔ)狀語(yǔ)名詞謂語(yǔ)狀語(yǔ)= = = He swims in river= He swims in river一個(gè)英文句子的例子一個(gè)英文句子的例子推導(dǎo)過(guò)程的圖示化：推導(dǎo)過(guò)程的圖示化：句子句子主語(yǔ)主語(yǔ)謂語(yǔ)謂語(yǔ)狀語(yǔ)

11、狀語(yǔ)代詞代詞動(dòng)詞動(dòng)詞界詞界詞名詞名詞Heswimsinriver上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法一組一組終結(jié)符號(hào)終結(jié)符號(hào)V VT T：組成語(yǔ)言的基本符號(hào)組成語(yǔ)言的基本符號(hào)。即單詞符號(hào)。如：基本字，標(biāo)識(shí)符，。即單詞符號(hào)。如：基本字，標(biāo)識(shí)符，常數(shù)，算符，界符等。常數(shù)，算符，界符等。一個(gè)上下文無(wú)關(guān)文法一個(gè)上下文無(wú)關(guān)文法G G包括四部分：包括四部分：一組一組非終結(jié)符號(hào)非終結(jié)符號(hào)V VN N：也稱語(yǔ)法變量，用來(lái)代表語(yǔ)法范疇也稱語(yǔ)法變量，用來(lái)代表語(yǔ)法范疇。如。如“算術(shù)表達(dá)式算術(shù)表達(dá)式”、“布爾表達(dá)式布爾表達(dá)式”、“賦值句賦值句”、“子程序子程序”、“函數(shù)函數(shù)”等。等。從語(yǔ)法分析的角度看，終結(jié)符是一個(gè)語(yǔ)言的不可

12、再分的基本從語(yǔ)法分析的角度看，終結(jié)符是一個(gè)語(yǔ)言的不可再分的基本符號(hào)。符號(hào)。一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ)法概念，是一個(gè)一個(gè)非終結(jié)符代表一個(gè)一定的語(yǔ)法概念，是一個(gè)類（集類（集合）合）記號(hào)，而不是一個(gè)個(gè)體記號(hào)。記號(hào)，而不是一個(gè)個(gè)體記號(hào)。一個(gè)一個(gè)開(kāi)始符號(hào)開(kāi)始符號(hào)S S：一個(gè)一個(gè)特殊的非終結(jié)符號(hào)特殊的非終結(jié)符號(hào)，代表我們最終感興趣的，代表我們最終感興趣的語(yǔ)法范疇，通常為語(yǔ)法范疇，通常為“句子句子”。一組一組產(chǎn)生式產(chǎn)生式P P：定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則定義語(yǔ)法范疇的一種書(shū)寫(xiě)規(guī)則。一個(gè)產(chǎn)生式形如一個(gè)產(chǎn)生式形如A A 或或A A :=:= 。左。左部部A VA VN N ；右部；右部A A （V VN NV

13、VT T）* *又稱為重寫(xiě)規(guī)則。又稱為重寫(xiě)規(guī)則。產(chǎn)生式的簡(jiǎn)寫(xiě)：產(chǎn)生式的簡(jiǎn)寫(xiě)： , , 可以可以簡(jiǎn)化為：簡(jiǎn)化為： | | 產(chǎn)生式的例子產(chǎn)生式的例子定義含定義含+ +、* *運(yùn)算和（、）的算術(shù)表達(dá)運(yùn)算和（、）的算術(shù)表達(dá)式這一語(yǔ)法范疇的產(chǎn)生式。式這一語(yǔ)法范疇的產(chǎn)生式。上下文無(wú)關(guān)文法的形式化上下文無(wú)關(guān)文法的形式化G=(VG=(VN N,V,VT T, S, P), S, P)其中：其中：V VN N 非空有限的非終結(jié)符號(hào)集非空有限的非終結(jié)符號(hào)集V VT T 非空有限的終結(jié)符號(hào)集，非空有限的終結(jié)符號(hào)集， V VN N V VT T = = S S 開(kāi)始符號(hào)開(kāi)始符號(hào)/ /識(shí)別符號(hào)，識(shí)別符號(hào)，S VS VN

14、 N P P 產(chǎn)生式集產(chǎn)生式集 ，每個(gè)產(chǎn)生式形如，每個(gè)產(chǎn)生式形如A A 。A VA VN N ；A A （V VN NVVT T）* *例子：例子：2929（2.12.1）由文法定義語(yǔ)言由文法定義語(yǔ)言 文法的作用是描述某種語(yǔ)言的句子的構(gòu)成文法的作用是描述某種語(yǔ)言的句子的構(gòu)成方式。使用文法我們可以產(chǎn)生對(duì)應(yīng)語(yǔ)言的句子。方式。使用文法我們可以產(chǎn)生對(duì)應(yīng)語(yǔ)言的句子。所有句子就構(gòu)成了文法所定義的語(yǔ)言。所有句子就構(gòu)成了文法所定義的語(yǔ)言?；舅枷耄夯舅枷耄簭淖R(shí)別符號(hào)開(kāi)始，不斷利用產(chǎn)生式，將從識(shí)別符號(hào)開(kāi)始，不斷利用產(chǎn)生式，將當(dāng)前符號(hào)串中的非終結(jié)符號(hào)替換為該符當(dāng)前符號(hào)串中的非終結(jié)符號(hào)替換為該符號(hào)的某個(gè)規(guī)則的右部

15、。直到當(dāng)前的符號(hào)號(hào)的某個(gè)規(guī)則的右部。直到當(dāng)前的符號(hào)串中所有的符號(hào)都是終結(jié)符號(hào)為止。串中所有的符號(hào)都是終結(jié)符號(hào)為止。例子：例子：i+ii+i推導(dǎo)和直接推導(dǎo)推導(dǎo)和直接推導(dǎo)直接推導(dǎo)：直接推導(dǎo)： A A = ，其中其中A A 是文法中的一個(gè)是文法中的一個(gè) 產(chǎn)生式，且產(chǎn)生式，且 、 （V VN NVVT T）* * 。推推 導(dǎo)：導(dǎo)：若若1 1 = =2 2 = = = = n n, ,則稱這個(gè)則稱這個(gè)序列為符號(hào)串序列為符號(hào)串1 1到到n n的一個(gè)推導(dǎo)。的一個(gè)推導(dǎo)。若若n=2,n=2,記為記為1 1 =+ =+ n n若若n=1,n=1,記為記為1 1 = =* * n n語(yǔ)言的定義語(yǔ)言的定義對(duì)于文法對(duì)于

16、文法GSGS， 稱為稱為G G的一個(gè)句型的一個(gè)句型, ,如果：如果： S =S =* * 識(shí)別符號(hào)是最簡(jiǎn)單的句型。識(shí)別符號(hào)是最簡(jiǎn)單的句型。GSGS的一個(gè)句型的一個(gè)句型被稱為句子，被稱為句子，如果：如果： V VT T* *也就是說(shuō)句子是全部由終結(jié)符號(hào)也就是說(shuō)句子是全部由終結(jié)符號(hào)組成的句型。組成的句型。句型句型: :句子句子: :語(yǔ)言的定義語(yǔ)言的定義文法的語(yǔ)言：文法的語(yǔ)言：文法所產(chǎn)生的句子的全體是文法所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，記為一個(gè)語(yǔ)言，記為L(zhǎng)(G).L(G).L(G) = | S =+ L(G) = | S =+ 并且并且 V VT T* * 一個(gè)文法的語(yǔ)言就是該文一個(gè)文法的語(yǔ)言就是該文

17、法的所有的句子的集合。法的所有的句子的集合。例子例子G1G1：A bA|aA bA|a；L(G1)=bL(G1)=bi ia|i=0a|i=0G2G2：Z AbZ Ab；A aaA A aaA aaA A aaL(G2) = aL(G2) = a2n2nb|n=1b|n=1構(gòu)造一個(gè)文法，使得它識(shí)別語(yǔ)言構(gòu)造一個(gè)文法，使得它識(shí)別語(yǔ)言a an nb bn np.30.p.30.例子例子文法等價(jià)：文法等價(jià)：設(shè)設(shè)G G和和GG是兩個(gè)文法，如果是兩個(gè)文法，如果L(G)L(G)等于等于L(G)L(G)，那么我們說(shuō)，那么我們說(shuō)G G和和GG等價(jià)。等價(jià)。例例 子：子：G S SABC AAa|a BBb|b C

18、Cc|cG S SABC AAa|a BBb|b CCc|cGS SSc|Bc BBb|Ab AAa|aGS SSc|Bc BBb|Ab AAa|a兩個(gè)兩個(gè)CFGCFG文法是否等價(jià)是不可判定的。文法是否等價(jià)是不可判定的。語(yǔ)言的定義語(yǔ)言的定義從一句型到另一句型的推導(dǎo)往往從一句型到另一句型的推導(dǎo)往往不唯一不唯一。最左推導(dǎo)：最左推導(dǎo)：最右推導(dǎo)：最右推導(dǎo)： 在一個(gè)推導(dǎo)的過(guò)程中，如果每一步在一個(gè)推導(dǎo)的過(guò)程中，如果每一步直接推導(dǎo)所被替換的總是最左（右）直接推導(dǎo)所被替換的總是最左（右）的非終結(jié)符號(hào)，那么這種推導(dǎo)稱為的非終結(jié)符號(hào)，那么這種推導(dǎo)稱為最左（右）推導(dǎo)。最左（右）推導(dǎo)。最右推導(dǎo)又稱為規(guī)范推導(dǎo)。最右推導(dǎo)

19、又稱為規(guī)范推導(dǎo)。語(yǔ)言的定義語(yǔ)言的定義例如：例如：i+ii+i最左推導(dǎo)的例子最左推導(dǎo)的例子標(biāo)識(shí)符文法標(biāo)識(shí)符文法GS:GS:S L|SD|SL, S L|SD|SL, L a|b|c|x|y|z,L a|b|c|x|y|z,D 0|1|2|7|8|9D 0|1|2|7|8|9最左推導(dǎo)：最左推導(dǎo)：S= SD= SDD= S= SD= SDD= LDD= aDD= a6D= a69LDD= aDD= a6D= a69最右推導(dǎo)的例子最右推導(dǎo)的例子最右推導(dǎo)：最右推導(dǎo)：S= SD= S9= S= SD= S9= SD9= S69= D69= a69SD9= S69= D69= a69標(biāo)識(shí)符文法標(biāo)識(shí)符文法GS

20、:GS:S L|SD|SL, S L|SD|SL, L a|b|c|x|y|z,L a|b|c|x|y|z,D 0|1|2|7|8|9D 0|1|2|7|8|9語(yǔ)法樹(shù)的概念語(yǔ)法樹(shù)的概念作為識(shí)別句子的輔助工具，語(yǔ)法樹(shù)有助于理解句子的語(yǔ)法作為識(shí)別句子的輔助工具，語(yǔ)法樹(shù)有助于理解句子的語(yǔ)法結(jié)構(gòu)。這一點(diǎn)對(duì)于其后的語(yǔ)義分析有非常重要的意義。結(jié)構(gòu)。這一點(diǎn)對(duì)于其后的語(yǔ)義分析有非常重要的意義。語(yǔ)法樹(shù)語(yǔ)法樹(shù)：設(shè)文法設(shè)文法G=(VG=(VN N,V,VT T,P,S ),P,S ),對(duì)于文法對(duì)于文法G G的任意的任意一個(gè)一個(gè)句型句型都存在一棵相應(yīng)的都存在一棵相應(yīng)的語(yǔ)法樹(shù)語(yǔ)法樹(shù)：結(jié)點(diǎn)由符號(hào)組成。結(jié)點(diǎn)由符號(hào)組成。根結(jié)

21、點(diǎn)對(duì)應(yīng)于識(shí)別符號(hào)。根結(jié)點(diǎn)對(duì)應(yīng)于識(shí)別符號(hào)。只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。只有非終結(jié)符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)有子結(jié)點(diǎn)。并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對(duì)應(yīng)并且，一個(gè)結(jié)點(diǎn)和它的子結(jié)點(diǎn)分別對(duì)應(yīng)于文法中的一個(gè)規(guī)則的左部和右部。于文法中的一個(gè)規(guī)則的左部和右部。語(yǔ)法樹(shù)的相關(guān)概念語(yǔ)法樹(shù)的相關(guān)概念對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。對(duì)應(yīng)于一個(gè)符號(hào)。結(jié)點(diǎn)的名字就是該符號(hào)。結(jié)結(jié) 點(diǎn)：點(diǎn)：沒(méi)有邊進(jìn)入的結(jié)點(diǎn)。沒(méi)有邊進(jìn)入的結(jié)點(diǎn)。沒(méi)有向下射出的邊的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)。沒(méi)有向下射出的邊的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)。在相對(duì)于句型的語(yǔ)法樹(shù)中，可能是非終結(jié)符號(hào)。在相對(duì)于句型的語(yǔ)法樹(shù)中，可能是非終結(jié)符號(hào)。又稱末端結(jié)點(diǎn)。又稱末端結(jié)點(diǎn)。兩個(gè)結(jié)點(diǎn)之間的連線。兩

22、個(gè)結(jié)點(diǎn)之間的連線。某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。父子結(jié)點(diǎn)某個(gè)結(jié)點(diǎn)向下射出的邊和其結(jié)點(diǎn)稱為分支。父子結(jié)點(diǎn)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)根結(jié)點(diǎn)：根結(jié)點(diǎn)：葉結(jié)點(diǎn)：葉結(jié)點(diǎn)：邊：邊：分分 支：支：子子 樹(shù)：樹(shù)：語(yǔ)法樹(shù)的某個(gè)結(jié)點(diǎn)和它向下射出的部分。語(yǔ)法樹(shù)的某個(gè)結(jié)點(diǎn)和它向下射出的部分。從推導(dǎo)構(gòu)造語(yǔ)法樹(shù)從推導(dǎo)構(gòu)造語(yǔ)法樹(shù)步驟步驟1 1：根結(jié)點(diǎn)為識(shí)別符號(hào)。：根結(jié)點(diǎn)為識(shí)別符號(hào)。步驟步驟2 2：對(duì)于每一次推導(dǎo)使用的規(guī)則：對(duì)于每一次推導(dǎo)使用的規(guī)則A A ，找出，找出A A對(duì)應(yīng)的結(jié)點(diǎn)（此時(shí)對(duì)應(yīng)的結(jié)點(diǎn)（此時(shí)應(yīng)該是末端結(jié)點(diǎn)），從該結(jié)點(diǎn)向下應(yīng)該是末端結(jié)點(diǎn)），從該結(jié)點(diǎn)向下畫(huà)分支，子結(jié)點(diǎn)從左到右分別是畫(huà)分支，子結(jié)點(diǎn)從左到右分別是中從左到

23、右的符號(hào)。中從左到右的符號(hào)。重復(fù)步驟重復(fù)步驟2 2直到推導(dǎo)的最后一步。直到推導(dǎo)的最后一步。語(yǔ)法樹(shù)的例子語(yǔ)法樹(shù)的例子P.31.P.31.圖圖2.22.2SABabcBdcdS=AB=abB=abcBd=abccdd語(yǔ)法樹(shù)的例子語(yǔ)法樹(shù)的例子語(yǔ)法語(yǔ)法GS:GS:S ABS ABA aAb | abA aAb | abB cBd | cdB cBd | cd語(yǔ)法樹(shù)與推導(dǎo)的關(guān)系語(yǔ)法樹(shù)與推導(dǎo)的關(guān)系一棵語(yǔ)法樹(shù)表示了一個(gè)句型種種可能（但一棵語(yǔ)法樹(shù)表示了一個(gè)句型種種可能（但未必是所有的）的不同推導(dǎo)過(guò)程。未必是所有的）的不同推導(dǎo)過(guò)程。一棵語(yǔ)法樹(shù)等價(jià)于一個(gè)最左（右）推導(dǎo)。一棵語(yǔ)法樹(shù)等價(jià)于一個(gè)最左（右）推導(dǎo)。一個(gè)句型

24、不一定只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)。一個(gè)句型不一定只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)。例如：例如：i i* *i+Ii+I的另一棵語(yǔ)法樹(shù)。的另一棵語(yǔ)法樹(shù)。P32P32圖圖2.32.3文法的二義性文法的二義性如果一個(gè)文法如果一個(gè)文法存在某個(gè)句子存在某個(gè)句子對(duì)應(yīng)對(duì)應(yīng)兩棵不同兩棵不同的語(yǔ)法樹(shù)的語(yǔ)法樹(shù)，則該文法是二義性的。，則該文法是二義性的。這里的二義性是指這里的二義性是指語(yǔ)法結(jié)構(gòu)上語(yǔ)法結(jié)構(gòu)上的。的。如果一個(gè)句子具有二義性，那么對(duì)這個(gè)句子的結(jié)如果一個(gè)句子具有二義性，那么對(duì)這個(gè)句子的結(jié)構(gòu)可能有多種構(gòu)可能有多種正確正確的解釋。通常情況下，句的解釋。通常情況下，句子的語(yǔ)義要通過(guò)其語(yǔ)法結(jié)構(gòu)來(lái)定義，所以，二義子的語(yǔ)義要通過(guò)其語(yǔ)

25、法結(jié)構(gòu)來(lái)定義，所以，二義性一般是有害的。性一般是有害的。文法的二義性是不可判定的。文法的二義性是不可判定的。文法的二義性不等于語(yǔ)言的二義性。文法的二義性不等于語(yǔ)言的二義性。EEE+E*EEE+EE*E文法二義性例子文法二義性例子文法文法GEGE：E E + E | E E E + E | E * * E | (E) | i E | (E) | i文法的句子文法的句子: : i+ii+i* *i i，其語(yǔ)法樹(shù)如下：，其語(yǔ)法樹(shù)如下：二義性二義性一般來(lái)講，二義性是一般來(lái)講，二義性是針對(duì)文法針對(duì)文法而言的，說(shuō)語(yǔ)言而言的，說(shuō)語(yǔ)言二義性是無(wú)意義的。二義性是無(wú)意義的。如果某個(gè)語(yǔ)言對(duì)應(yīng)的文如果某個(gè)語(yǔ)言對(duì)應(yīng)的文法都是二義性的，那么法都是二義性的，那么這個(gè)語(yǔ)言被稱為先天二這個(gè)語(yǔ)言被稱為先天二義性的。義性的。即使文法是無(wú)二義性的，其句子對(duì)應(yīng)的語(yǔ)義仍即使文法是無(wú)二義性的，其句子對(duì)應(yīng)的語(yǔ)義仍然必須有嚴(yán)格的定義，才可以避免然必須有嚴(yán)格的定義，才可以避免語(yǔ)義語(yǔ)義的二義的二義性。性。語(yǔ)言語(yǔ)言的二義性：的二義性：作業(yè)作業(yè)3 3、7 7、8 8、9 9補(bǔ)充作業(yè)：補(bǔ)充作業(yè)：1 1、構(gòu)造、構(gòu)造L=aL=an nbbbbn n|