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

2、也定義方冪：A0 =A1 = AA2=AAAn = An-1A 其中A是任一集合 設(shè)設(shè)為字母表或一集合，為字母表或一集合， 上的所有有窮上的所有有窮長的串的集合用長的串的集合用*表示表示, 稱為集合稱為集合的閉包。的閉包。寫成寫成： *= 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，稱G =G =（V VN，V VT T，P P，S S）為文法。其中

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

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

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

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

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

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

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

10、邊的直一個句型多個簡單短語中最左邊的直接短語稱為該句型的句柄。接短語稱為該句型的句柄。 從根符號開始的對句型構(gòu)造的語法樹的方法是從上向下分析的方法。從輸入串開始，逐步進行“”，直至歸到文法的開始符號?；蛘哒f，從語法樹的末端開始，步步向上“歸約”直到根部。二義性二義性：如果文法G G的一個句子有兩棵以上語法樹，則稱該句子有二義性。例如，對于例36的文法G,句型 i*i+i 就有兩個不同的最左推導(dǎo)，它們所對應(yīng)的語法樹分別如圖32和圖33所示。：指形如UU的產(chǎn)生式，該種產(chǎn)生式對描述語言是沒有必要的，只會引起文法的二義性：指文法中連一個句子的推導(dǎo)都用不到的規(guī)則，分為不可達到和不可終止兩種情況有關(guān)文法的說明有關(guān)文法的說明:if i=5 then x=y詞法分析器（3，if）（1，指向I的符號表入口）（4，=）（2，5）（3，then）（1，指向x的符號表入口）（4，=）（1，指向y的符號表入口）1）結(jié)果用二元式表示2）二元式形式是：（單詞種別，單詞自身的值）3）定義單詞種別為：1：標(biāo)識符2：常數(shù)3：保留字4：運算符5：界符詞法例子的結(jié)論n單詞歸根結(jié)底是一個符號串n這些符號處在一個基本符號集中n基本符號集是一非空有窮集合n單詞符號是基本符號按一定規(guī)則構(gòu)成的基本符號串，是定義在基本符號集上的標(biāo)識符單詞