第三章文法和語(yǔ)言

第三章

文法和語(yǔ)言—文法的目的在于描述程序設(shè)計(jì)語(yǔ)言本章主要內(nèi)容：3.1形式語(yǔ)言簡(jiǎn)介3.2文法及語(yǔ)言的形式定義3.3文法的類型3.4語(yǔ)法樹(shù)與句型的分析幾個(gè)基本定義：語(yǔ)言語(yǔ)法語(yǔ)義文法字母表符號(hào)符號(hào)串語(yǔ)言是記號(hào)系統(tǒng)是句子的集合包含語(yǔ)法和語(yǔ)義兩方面的內(nèi)容描述語(yǔ)言就是描述語(yǔ)言的所有句子語(yǔ)法是一組規(guī)則，用來(lái)定義什么樣的符號(hào)序列是合法的而與符號(hào)的含義無(wú)關(guān)語(yǔ)義符號(hào)、符號(hào)序列、片段等的含義靜態(tài)語(yǔ)義動(dòng)態(tài)語(yǔ)義語(yǔ)法分析和語(yǔ)義分析的比較語(yǔ)法分析是對(duì)語(yǔ)言的形式（符號(hào)序列）的判斷，語(yǔ)義分析是對(duì)語(yǔ)言內(nèi)容的判斷語(yǔ)法分析較易，語(yǔ)義分析較難對(duì)形式的判斷常用的手段是上下文無(wú)關(guān)文法，對(duì)內(nèi)容的判斷無(wú)法用上下文無(wú)關(guān)文法文法定義語(yǔ)法的一組規(guī)則就是文法這些規(guī)則可以對(duì)語(yǔ)言的形式進(jìn)行描述，即文法是闡明語(yǔ)法的工具文法以有窮的集合刻劃了無(wú)窮的集合

字母表基本符號(hào)集是字母表

符號(hào)字母表中的元素稱為符號(hào)

符號(hào)串字母表中的元素組成的任何有窮序列符號(hào)串可以是所定義的語(yǔ)句,也可以不是語(yǔ)句可以使用字母表示符號(hào)串字符串的長(zhǎng)度空字符串符號(hào)串的首尾符號(hào)串的連接符號(hào)串的方冪符號(hào)串集合§

3.1形式語(yǔ)言簡(jiǎn)介幾個(gè)基本概念:字母表:

一個(gè)非空有窮集合。例：∑={a，b，c}符號(hào):字母表的元素稱為符號(hào)。例a，b，c符號(hào)串:

符號(hào)的有窮序列。符號(hào)串也稱為字。用ε表示空符號(hào)串（什么符號(hào)也沒(méi)有）。長(zhǎng)度:

設(shè)X為一符號(hào)串，則把X的長(zhǎng)度定義為其中所包含的符號(hào)個(gè)數(shù)，并記|x|。例如：|ε|=0，|a|=1，|abab|=4連接:

設(shè)x和y是符號(hào)串，則xy為它們的連接。例如，假定有x=aa,y=bb，則有:xy=aabb。特別對(duì)任一符號(hào)串β有εβ=βε=β集合乘積:設(shè)A和B是符號(hào)串的集合，則用AB表示集合A、B的乘積。

AB={xy|xA，yB}。因?yàn)棣纽?βε=β所以有{ε}A=A{ε}=A空集:不包含任何元素的集合稱為空集合，記為φ。對(duì)任一集合，有φA=Aφ=φ集合乘積定義如下：方冪:

同一符號(hào)串的序列可表示成方冪形式x0

=εx1

=xx2

=xx…xn

=xx…x（n個(gè)x）對(duì)符號(hào)串集合也定義方冪：A0

={ε}A1

=AA2=AA…An=An-1A其中A是任一集合閉包:設(shè)∑為字母表或一集合，∑上的所有有窮長(zhǎng)的串的集合用∑*表示,稱為集合∑的閉包。寫(xiě)成：∑*=∑0∪∑

1∪∑2

…∪∑n…正閉包:

設(shè)∑為任一字母表或集合，則用∑+表示∑的正閉包。其定義如下：∑

+=∑1∪∑2∪∑3∪…

∑n…∑*=∑0

∪∑+={ε}∪∑+

§3.2文法及語(yǔ)言的形式定義定義：設(shè)VN和VT都是非空有窮集，S∈VN

且VN∩VT

=Φ。記V=VN∪VT，稱G=（VN，VT，P，S）為文法。其中：VN

：G的變量集，非終結(jié)符的有窮集合（大寫(xiě)字母表示）VT：終結(jié)符的非空有窮集合（小寫(xiě)字母表示）P：G的產(chǎn)生式集（形為→β的產(chǎn)生式的有窮集合）S:被指定為文法的開(kāi)始符號(hào)。（

S∈VN）其中：∈（VN∪VT）+，β∈（VN∪VT）終結(jié)符：不能再推導(dǎo)的符號(hào)非終結(jié)符：可再推導(dǎo)下去的符號(hào)句型分析算法從上而下分析法從下而上分析法從上而下分析—推導(dǎo)推導(dǎo)：如果用若干次規(guī)則式可從符號(hào)串X推導(dǎo)出符號(hào)Y，則稱Y為X的推導(dǎo)。即從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”于輸入符號(hào)串的過(guò)程直接推導(dǎo)：設(shè)X和Y是符號(hào)串，若用一次規(guī)則式可從X推導(dǎo)出Y，則稱為X的直接推導(dǎo)，并記為XY。推導(dǎo)：如果用若干次規(guī)則式可從符號(hào)串X推導(dǎo)出符號(hào)Y，則稱Y為X的推導(dǎo)，并記為:X+Y為方便起見(jiàn)，再引進(jìn)符號(hào)，其定義如下：X*Y

當(dāng)且僅當(dāng)

X=Y或X+Y。顯然，根據(jù)定義對(duì)任一符號(hào)串X都有

X*X

長(zhǎng)度為n的推導(dǎo)若存在直接推導(dǎo)的序列：

V=W0W1W2Wn=W（n>0）

則稱V推導(dǎo)出W,推導(dǎo)長(zhǎng)度為n。從下而上分析從輸入符號(hào)串開(kāi)始，逐步進(jìn)行“歸約”，直至歸約到文法的開(kāi)始符號(hào)

V=W0W1W2Wn=W（n>0），稱W歸約到V。記作V+W歸約和推導(dǎo)是相對(duì)的概念，推導(dǎo)是把句型中的非終極符用規(guī)則式的一個(gè)右部來(lái)替換的過(guò)程。而歸約是把句型中的某子串用一個(gè)非終極符替換的過(guò)程。令G是一文法，且U→u

是G中的規(guī)則式。有x

U

y

xuy

（直接推導(dǎo)），則有

xuy

x

Uy（規(guī)約）。歸約句型：設(shè)G[S]是一文法，如果符號(hào)串X是從識(shí)別符號(hào)（開(kāi)始符）推導(dǎo)出來(lái)的，即有S*x，則稱x是文法G的句型。句子：不包含非終極符的句型稱為句子。也就是說(shuō)，x是一個(gè)句子當(dāng)且僅當(dāng)Z*x且x∈VT*。語(yǔ)言：所有句子的集合稱為語(yǔ)言。設(shè)G是給定文法,S是開(kāi)始符，由文法G所定義的語(yǔ)言L（G）可描述如下：

L（G）={x|S*x且

x∈VT*}設(shè)G1和G2是給定文法,若有L（G1）=L（G2）則稱G1和G2等價(jià)。這就是說(shuō)，不同的文法可定義相同的語(yǔ)言。等價(jià)文法：形式語(yǔ)言的文法按結(jié)構(gòu)可分為四類：0型文法（短語(yǔ)結(jié)構(gòu)文法）:規(guī)則式具有下面形式;

→β，其中α、β都是符號(hào)串，

,β

∈（VN∪VT）*，且至少含有一個(gè)非終極符

§3.3文法的類型1型文法（上下文有關(guān)文法）：規(guī)則式限制為下面形式：Aβ→uβ

其中A∈VN，u是非空串，顯然有|Aβ|≤|uβ|（產(chǎn)生式非縮減的）這里把A替換為符號(hào)串u是有條件的，即A前面必須是

，A后面必須是β，因此稱為上下文有關(guān)文法。

1型文法：2型文法（上下文無(wú)關(guān)文法）：規(guī)則式限制為下面形式：A→β

所有產(chǎn)生式左端是一非終極符，其中A∈VN，β∈（VN∪VT）*，β為非空串，β取代A時(shí)與A所在的上下文無(wú)關(guān)。大部分程序設(shè)計(jì)語(yǔ)言的文法近似于2型文法，因此2型文法是我們研究對(duì)象。2型文法：3型文法（正規(guī)文法）：規(guī)則式限制為下面形式之一：

A→a

A→aB

其中A、B∈VN，a∈VT*。3型文法與自動(dòng)機(jī)有密切關(guān)系。上面的分類格式是由Chomsky與1959年提出的。

3型文法:3型文法2型文法1型文法0型文法上面分析得出四種文法間的關(guān)系:3型文法必是2型文法，2型文法必是1型文法，1型文法必是0型文法。即：

文法的遞歸性：說(shuō)A是直接左遞歸的，其規(guī)則式為：A→A…說(shuō)A是直接右遞歸的，其規(guī)則式為：

A→…A若有推導(dǎo)式：A+A…，說(shuō)A是左遞歸的若有推導(dǎo)式：A+…A，說(shuō)A是右遞歸的文法的遞歸性表達(dá)式項(xiàng)因子§3.4語(yǔ)法樹(shù)與句型的分析1.語(yǔ)法樹(shù)語(yǔ)法樹(shù)：按推導(dǎo)過(guò)程，畫(huà)出一棵樹(shù)型結(jié)構(gòu)稱為語(yǔ)法樹(shù)。

語(yǔ)法樹(shù)：設(shè)G=（VN

，VT，P，S）是給定文法，則滿足下面條件的樹(shù)稱為G的一棵語(yǔ)法樹(shù)，也叫推導(dǎo)樹(shù)。⑴每個(gè)結(jié)點(diǎn)都有標(biāo)記，該標(biāo)記是G中的某一終極符或非終極符。⑵樹(shù)根的標(biāo)記是文法的開(kāi)始符S。⑶若結(jié)點(diǎn)的標(biāo)記為A，并且它至少有一個(gè)從它出來(lái)的分枝，則A一定是非終極符。子樹(shù)：由某一結(jié)點(diǎn)及其所有分枝組成的部分稱為原樹(shù)的一棵子樹(shù)。簡(jiǎn)單子樹(shù)：只有單層分枝的子樹(shù)稱為簡(jiǎn)單子樹(shù)。⑷如果標(biāo)記為A的結(jié)點(diǎn)有n個(gè)從它出來(lái)的分枝，并且這些分枝結(jié)點(diǎn)的標(biāo)記從左至右分別為A1，A2，…An，則A→A1，A2，…An一定是G的一個(gè)文法規(guī)則式。規(guī)范推導(dǎo)：設(shè)xUyxuy是一個(gè)直接推導(dǎo)。如果y是終極符串或空，即U是句型xUy中的最右非終極符，則稱這種推導(dǎo)為規(guī)范直接推導(dǎo)。記為：xUyr右

xuy（XUyr右

Xuy）若推導(dǎo)x+y中的每步都是規(guī)范直接推導(dǎo)，則稱該推導(dǎo)為規(guī)范推導(dǎo)。并記為x

+r右y，也稱為最右推導(dǎo)。短語(yǔ)：設(shè)G為給定文法，S是開(kāi)始符，W=xuy是一個(gè)句型，如果滿足下面兩個(gè)條件：①

S*xUy②U+u則稱句型xuy中的子串u為句型xuy相對(duì)于非終極符U的短語(yǔ)。直接短語(yǔ)（簡(jiǎn)單短語(yǔ)）：如果滿足條件①S*

xUy②Uu則稱u為句型xuy的直接短語(yǔ)（簡(jiǎn)單短語(yǔ)）。第二個(gè)條件表示有文法規(guī)則式Uu存在。

句柄：一個(gè)句型多個(gè)簡(jiǎn)單短語(yǔ)中最左邊的直接短語(yǔ)稱為該句型的句柄。2、句型的分析自上而下的分析從根符號(hào)開(kāi)始的對(duì)句型構(gòu)造的語(yǔ)法樹(shù)的方法是從上向下分析的方法。自下而上的分析從輸入串開(kāi)始，逐步進(jìn)行“歸約”，直至歸到文法的開(kāi)始符號(hào)?；蛘哒f(shuō)，從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約”直到根部。3、文法的二義性二義性：如果文法G的一個(gè)句子有兩棵以上語(yǔ)法樹(shù)，則稱該句子有二義性。例如，對(duì)于例3．6的文法G,句型i*i+i就有兩個(gè)不同的最左推導(dǎo)，它們所對(duì)應(yīng)的語(yǔ)法樹(shù)分別如圖3．2和圖3．3所示。有害規(guī)則：指形如U→U的產(chǎn)生式，該種產(chǎn)生式對(duì)描述語(yǔ)言是沒(méi)有必要的，只會(huì)引起文法的二義性多余規(guī)則：指文法中連一個(gè)句子的推導(dǎo)都用不到的規(guī)則，分為不可達(dá)到和不可終止兩種情況有關(guān)文法的說(shuō)明:重新審視例:ifi=5thenx=y詞法分析器（3，‘if’）（1，指向I的符號(hào)表入口）（4，‘=’）（2，‘5’）（3，‘then’）（1，指向x的符號(hào)表入口）（4，‘=’）（1，指向y的符號(hào)表入口）1）結(jié)果用二元式表示2）二元式形式是：（單詞種別，單詞自身的值）3）定義單詞種別為： 1：標(biāo)識(shí)符 2：常數(shù) 3：保留字 4：運(yùn)算符 5：界符詞法例子的結(jié)論單詞歸