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

1、 設(shè)x和y是符號(hào)串，則 xy為它們的連接。例如，假定有 x=aa, y=bb，則有:xy = aabb。 特別對(duì)任一符號(hào)串特別對(duì)任一符號(hào)串 有有 =設(shè)A和B是符號(hào)串的集合，則用 AB表示集合A、B的乘積。 AB= xy |x A，y B。因因?yàn)闉?所以有所以有 A = A= AA = A= A 不包含任何元素的集合稱(chēng)為空集合，不包含任何元素的集合稱(chēng)為空集合，記為記為。 對(duì)任一集合，有對(duì)任一集合，有A = A = A = A = 集合乘積定義如下：集合乘積定義如下： 同一符號(hào)串的序列可表示成方冪形式x0 =x1 = xx2 = xxxn = xxx （n個(gè)x）對(duì)符號(hào)串集合也定義方冪：對(duì)符號(hào)串集合

2、也定義方冪：A0 =A1 = AA2=AAAn = An-1A 其中A是任一集合 設(shè)設(shè)為字母表或一集合，為字母表或一集合， 上的所有有窮上的所有有窮長(zhǎng)的串的集合用長(zhǎng)的串的集合用*表示表示, 稱(chēng)為集合稱(chēng)為集合的閉包。的閉包。寫(xiě)成寫(xiě)成： *= 0 1 2 n 設(shè)設(shè)為任一為任一字母表或字母表或集合，則用集合，則用+ 表示表示的正閉包。其定義如下：的正閉包。其定義如下： + = 1 2 3 n *= 0 + = + 設(shè)V VN和V VT T都是非空有窮集，S VS VN 且且V VNVVT T = =。記記 V=VV=VNVVT T，稱(chēng)G =G =（V VN，V VT T，P P，S S）為文法。其中

3、： ：G G的變量集，非終結(jié)符的有窮集合（大寫(xiě)字母表示）：終結(jié)符的非空有窮集合（小寫(xiě)字母表示） ：G G的產(chǎn)生式集（形為 的產(chǎn)生式的有窮集合） : : 被指定為文法的開(kāi)始符號(hào)。（。（ S VS VN ）其中： （V VN NVVT T）+ +，（V VN NVVT T） 不能再推導(dǎo)的符號(hào)：可再推導(dǎo)下去的符號(hào)n從上而下分析法n從下而上分析法如果用若干次規(guī)則式可從符號(hào)串X X推導(dǎo)出符號(hào)Y Y，則稱(chēng)Y Y為X X的推導(dǎo)。即從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找“匹配”于輸入符號(hào)串的過(guò)程設(shè)X和Y是符號(hào)串，若用一次規(guī)則式可從X推導(dǎo)出Y，則稱(chēng)為X的直接推導(dǎo)，并記為XY。如果用若干次規(guī)則式可從符號(hào)串

4、X X推導(dǎo)出符號(hào)Y Y，則稱(chēng)Y Y為X X的推導(dǎo)，并記為記為: :為方便起見(jiàn)，再引進(jìn)符號(hào)為方便起見(jiàn)，再引進(jìn)符號(hào) ，其定義如下： 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) X = Y 或或X + Y。顯然，根據(jù)定義對(duì)任一符號(hào)串顯然，根據(jù)定義對(duì)任一符號(hào)串X都有都有 X * Xn若存在直接推導(dǎo)的序列：V=W0W1W2Wn=W（n0）則稱(chēng)V推導(dǎo)出W,推導(dǎo)長(zhǎng)度為n。n從輸入符號(hào)串開(kāi)始，逐步進(jìn)行n“”，直至歸約到文法的開(kāi)始符號(hào)V=W0W1W2Wn=W（n0），稱(chēng)W歸約到V。記作歸約和推導(dǎo)是相對(duì)的概念，推導(dǎo)是把句型中的非終極符用規(guī)則式的一個(gè)的過(guò)程。而歸約是把句型中的某子串的過(guò)程。令G G是一文法，且 U u 是G中的規(guī)則式。 有有

5、x U y x u y （），），則有 x u y x U y（）。）。：設(shè)GS是一文法，如果符號(hào)串X是從識(shí)別符號(hào)（開(kāi)始符開(kāi)始符）推導(dǎo)出來(lái)的，即有S* x，則稱(chēng)x是文法G的句型。：不包含非終極符的句型稱(chēng)為句子。也就是說(shuō)，x是一個(gè)句子Z* x 且x VT*。所有句子的集合稱(chēng)為語(yǔ)言。設(shè)G G是給定文法,S S是開(kāi)始符，由文法G G所定義的語(yǔ)言L L（G G）可描述如下： L（G）= x | S * x 且 x VT* 設(shè)G1和G2是給定文法,若有L（G1）= L（G2）則稱(chēng)G1和G2等價(jià)。這就是說(shuō)，不同的文法可定義相同的語(yǔ)言。等價(jià)等價(jià)文法：（短語(yǔ)結(jié)構(gòu)文法）（短語(yǔ)結(jié)構(gòu)文法）:規(guī)則式具有下面形式; ，

6、 其中、都是符號(hào)串， , （VNVT）*，且 至少含有一個(gè)非終極符（上下文有關(guān)文法）：（上下文有關(guān)文法）：規(guī)則式限制為下面形式： A u 其中其中AVN，u是非空串，顯然有| A| | u|（產(chǎn)生式非縮減的）這里把A替換為符號(hào)串u是有條件的，即A前面必須是 ，A后面必須是，因此稱(chēng)為上下文有關(guān)文法。 （上下文無(wú)關(guān)文法）：規(guī)則式限制為下面形式：A 所有產(chǎn)生式左端是一非終極符，其中AVN，（VNVT）*，為非空串，取代A時(shí)與A所在的上下文無(wú)關(guān)。大部分程序設(shè)計(jì)語(yǔ)言的文法近似于2型文法，因此2型文法是我們研究對(duì)象。（正規(guī)文法）：規(guī)則式限制為下面形式之一： A aA a A a BA a B 其中 A A

7、、BVBVN N，aVaVT T* *。3 3型文法與自動(dòng)機(jī)有密切關(guān)系。上面的分類(lèi)格式是由ChomskyChomsky與19591959年提出的。 上面分析得出上面分析得出四種文法間的關(guān)系四種文法間的關(guān)系:3 3型文法必是型文法必是2 2型文法，型文法，2 2型文法必是型文法必是1 1型文法，型文法，1 1型文法必是型文法必是0 0型文法。即：型文法。即： 文法的遞歸性：說(shuō)A是直接左遞歸的，其 規(guī)則式為：A A說(shuō)A是直接右遞歸的，其規(guī)則式為： A A若有推導(dǎo)式：A + A，說(shuō)A是左遞歸的若有推導(dǎo)式：A + A，說(shuō)A是右遞歸的文法的遞歸性v表達(dá)式v項(xiàng)v因子按推導(dǎo)過(guò)程，畫(huà)出一棵樹(shù)型結(jié)構(gòu)稱(chēng)為語(yǔ) 法樹(shù)

8、。 ：設(shè)G=G=（V VN ，V VT，P P，S S）是給定文法，則滿足下面條件的樹(shù)稱(chēng)為G G的一棵語(yǔ)法樹(shù)，也叫推推導(dǎo)樹(shù)。導(dǎo)樹(shù)。每個(gè)結(jié)點(diǎn)都有標(biāo)記，該標(biāo)記是G G中的某一終極符 或非終極符。樹(shù)根的標(biāo)記是文法的開(kāi)始符S S。若結(jié)點(diǎn)的標(biāo)記為A A，并且它至少有一個(gè)從它出來(lái)的分枝，則A A一定是非終極符。由某一結(jié)點(diǎn)及其所有分枝組成的部分稱(chēng)為原樹(shù)的一棵子樹(shù)。：只有單層分枝的子樹(shù)稱(chēng)為簡(jiǎn)單子樹(shù)。如果標(biāo)記為A A的結(jié)點(diǎn)有n n個(gè)從它出來(lái)的分枝，并且這些分枝結(jié)點(diǎn)的標(biāo)記從左至右分別為A A1 1，A A 2， A An，則AAAA1 1，A A 2 2， A An一定是G G的一個(gè)文法規(guī)則式。設(shè)xUy xuy

9、是一個(gè)直接推導(dǎo)。如果y是終極符串或空，即U是句型xUy中的最右非終極符，則稱(chēng)這種推導(dǎo)為規(guī)范直接推導(dǎo)。記為： xUy r右 xuy （XUy r右 Xuy ）若推導(dǎo)x + y中的每步都是規(guī)范直接推導(dǎo)， 則稱(chēng)該推導(dǎo)為規(guī)范推導(dǎo)。 并記為x +r右 y，也稱(chēng)為最右推導(dǎo)。 ：設(shè)G為給定文法，S是開(kāi)始符，W= xuy是一個(gè)句型，如果滿足下面兩個(gè)條件： S *xUy U+u 則稱(chēng)句型xuyxuy中的子串u為句型xuyxuy相對(duì)于非終極符U的短語(yǔ)。（簡(jiǎn)單短語(yǔ)）：）：如果滿足條件 S * xUy U u則稱(chēng)u為句型xuy的直接短語(yǔ)（簡(jiǎn)單短語(yǔ)）。第二個(gè)條件表示有文法規(guī)則式Uu存在存在。 一個(gè)句型多個(gè)簡(jiǎn)單短語(yǔ)中最左

10、邊的直一個(gè)句型多個(gè)簡(jiǎn)單短語(yǔ)中最左邊的直接短語(yǔ)稱(chēng)為該句型的句柄。接短語(yǔ)稱(chēng)為該句型的句柄。 從根符號(hào)開(kāi)始的對(duì)句型構(gòu)造的語(yǔ)法樹(shù)的方法是從上向下分析的方法。從輸入串開(kāi)始，逐步進(jìn)行“”，直至歸到文法的開(kāi)始符號(hào)?；蛘哒f(shuō)，從語(yǔ)法樹(shù)的末端開(kāi)始，步步向上“歸約”直到根部。二義性二義性：如果文法G G的一個(gè)句子有兩棵以上語(yǔ)法樹(shù)，則稱(chēng)該句子有二義性。例如，對(duì)于例36的文法G,句型 i*i+i 就有兩個(gè)不同的最左推導(dǎo)，它們所對(duì)應(yīng)的語(yǔ)法樹(shù)分別如圖32和圖33所示。：指形如UU的產(chǎn)生式，該種產(chǎn)生式對(duì)描述語(yǔ)言是沒(méi)有必要的，只會(huì)引起文法的二義性：指文法中連一個(gè)句子的推導(dǎo)都用不到的規(guī)則，分為不可達(dá)到和不可終止兩種情況有關(guān)文法的說(shuō)明有關(guān)文法的說(shuō)明:if i=5 then x=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é)論n單詞歸根結(jié)底是一個(gè)符號(hào)串n這些符號(hào)處在一個(gè)基本符號(hào)集中n基本符號(hào)集是一非空有窮集合n單詞符號(hào)是基本符號(hào)按一定規(guī)則構(gòu)成的基本符號(hào)串，是定義在基本符號(hào)集上的標(biāo)識(shí)符單詞