compiler_ch21

1、Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.1 語言的語法和語義本節(jié)展開思路從文法和語言的直觀概念文法、語言的運(yùn)算和形式定義表示方法類型二義性問題關(guān)于語言：自然語言 人與人交互的工具；程序設(shè)計(jì)語言 人機(jī)交互的工具。語言要素語法 （語言的描述規(guī)則）語義 （語言的含義）語法是一種媒介，語義以語法為媒介來予以說明。語言是由單詞按一定規(guī)則（文法）組成句子來表達(dá)特定意思。故對(duì)語言的分析集中于對(duì)句子的分析。而句子的分析依據(jù)語言的文法規(guī)則。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.1 語言的語法和語義動(dòng)詞 吃例2.1 : 設(shè)有語句 “小八哥吃大花生”。設(shè)有漢語語法規(guī)則的一個(gè)子集：句

2、子主語謂語主語形容詞名詞謂語動(dòng)詞賓語賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.1 語言的語法和語義8巴科斯諾爾（BackusNaur Form）范式表示法，簡(jiǎn)稱BNF。 ：表示語法成分。|：（通常也用 := ）表示“定義為”或“由組合成”的含義。：“或”的含義。表示具有相同左部的產(chǎn)生規(guī)則可用“|”分開。元語言符號(hào)元語言: 描述另一個(gè)語言的語言。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.1 語言的語法和語義語句“小八哥吃大花生”分析的語法樹上下句子主語謂語形容詞名詞 動(dòng)詞 賓語小八哥吃形容詞名詞大花生Ch2 形式語言

3、自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.1 語言的語法和語義Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.1 語言的語法和語義句子的推導(dǎo) 小八哥吃 小八哥吃 小八哥吃大小八哥吃大花生句子句子的歸約謂語主語形容詞 名詞 動(dòng)詞賓語小八哥吃花生大下形容詞 名詞上Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.1 語言的語法和語義Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義2.1.2 文法和語言的定義一.二.三.四.字符和字符串文法形式定義字符串運(yùn)算語 言Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義一. 字符、字符串

4、任何一種語言，都是由該語言的基本字符所組成的字符串的集合。例如，程序設(shè)計(jì)語言的基本字符集是由字母、數(shù)字、運(yùn)算符等其它符號(hào)組成，則任何程序都是由這些基本字符組成的序列。定義2.1 ( 字母表 )字母表是元素的非空有窮集合。字母表中的元素稱為符號(hào)，因此字母表也稱為符號(hào)集。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義例如:漢語的字母表中包括漢字、數(shù)字和標(biāo)點(diǎn)符號(hào)等。二進(jìn)制數(shù)語言的字母表是0,1。C語言的字母表可以認(rèn)為是一切可打印字符組成的集合。用希臘字母或大寫英文字母等表示字母表，用集合元素表示形式枚舉字母表中的符號(hào)。例如，字母表 A=a,b,c,d與字母表 =0,1

5、等。定義2.2 (符號(hào)串)由字母表中的符號(hào)組成的任何有窮序列稱為符號(hào)串。例如:1) 001110是字母表= 0,1上的符號(hào)串；2) 字母表A= a,b,c上的一些符號(hào)串有：a, b, c, ab, ba, aaca等。通常使用小寫字母表示符號(hào)串，如x =STR表示x是由符號(hào)S、T和R，并按此順序組成的符號(hào)串。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義字 句子 串Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義從離散數(shù)學(xué)的角度定義符號(hào)串，則有：（1） 字母表上的字符是上的符號(hào)串；（2） 若x是上的符號(hào)串，且a,則xa或ax是上的符

6、號(hào)串；（3） y是上的符號(hào)串，當(dāng)且僅當(dāng)y可由(1)和(2)產(chǎn)生。符號(hào)串長度如果某符號(hào)串x中有m個(gè)符號(hào)，則稱其長度為m，記為 | x | = m。允許不包含任何符號(hào)的符號(hào)串，稱其為空符號(hào)串或空串?？沾帽硎?，其長度為0，記為 | | = 0。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義例如:1） 定義在字母表=0，1上的符號(hào)串| 001110 | = 62） 定義在字母表= x，y，z，=，0， ，1，+，; 上的符號(hào)串| x=y+; z=0; | = 11符號(hào)串的前綴、后綴和子符號(hào)串設(shè)x是一個(gè)符號(hào)串，把從x的尾部刪去0個(gè)或若干個(gè)符號(hào)之后剩余的部分稱為x的前綴。

7、從x的首部刪去0個(gè)或若干個(gè)符號(hào)之后剩余的部分稱為x的后綴。若x的前綴(后綴)不是x自身，則將其稱為x的真前綴(真后綴)。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義例如: 設(shè)x = abc則,a,ab,abc都是x的前綴，且除abc外都為真前綴。,c,bc,abc都是x的后綴，且除abc外都為真后綴。abc是x的前綴或后綴，但既不是真前綴也不是真后綴。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義子符號(hào)串（子串）從一個(gè)符號(hào)串中刪去它的一個(gè)前綴或(和)一

8、個(gè)后綴之后剩余的部分稱為該符號(hào)串的子符號(hào)串或子串。例如:x = abcd則,a,b,c,ab,bc,cd,abc,bcd及abcd都是x的子字符串。而ac，ad，cb，bd，ba等都不是x的子字符串。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義2.1.2 文法和語言的定義一.二.三.四.字符和字符串文法形式定義字符串運(yùn)算語 言Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義二. 文法定義2.3:一部文法G是一個(gè)四元組G =（ VN, VT, S, P）其中：VN：非空有限的非終結(jié)符號(hào)集(一般用大寫字母表示)。VT：非空有限的終結(jié)符

9、號(hào)集（一般用小寫字母表示）。設(shè)V是文法G的符號(hào)集，則有V= VT VN ，VT VN= 。S：文法的開始符號(hào)或識(shí)別符號(hào)，亦稱公理，S VN。S代表語言最終要得到的語法范疇。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義設(shè)有漢語語法規(guī)則的一個(gè)子集：句子主語謂語主語形容詞名詞謂語動(dòng)詞賓語賓語形容詞名詞形容詞 小 | 大名詞 八哥 | 花生動(dòng)詞 吃VNVTSCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義P：有限產(chǎn)生式集。產(chǎn)生式就是按一定格式書寫的定義語法范疇的文法規(guī)則，它是一部文法的實(shí)體。產(chǎn)生式的形式:P或P:=其中: P稱為產(chǎn)生式的左部，

10、為產(chǎn)生式的右部或稱為P的侯選式，有PV+，V*。注意，公理S至少且必須在文法某個(gè)產(chǎn)生式的左部出現(xiàn)一次。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義例2.2 : 數(shù)字文法定義為 0 | 1 | 2 | 3 | | 9其中: VN = NUMBER ，VT =0,1,2, ,9，S= VN，P為定義式本身。例如，簡(jiǎn)單的算術(shù)表達(dá)式文法G1定義為 E，i, +, *, (, )，E，E i | i+i | i *i | (E) 四元式形式Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義注意:E iE i+iE i *iE (E)E i | i

11、+i | i *i | (E)簡(jiǎn)寫Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義三. 符號(hào)串運(yùn)算定義2.4 ( 符號(hào)串的連接 )設(shè)x和y是兩個(gè)符號(hào)串，如果將符號(hào)串y直接拼接在符號(hào)串x之后，則稱此操作為符號(hào)串x和y的連接，記作xy。例如， 設(shè)有字符串 j=abc，k=xyz則jk=abcxyz，kj=xyzabc。連接運(yùn)算是有序的。一般來說xyyx，僅當(dāng)為空串，則有x=x=x。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義2.1.2 文法和語言的定義一.二.三.四.字符和字符串文法形式定義字符串運(yùn)算語 言Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2

12、.1 文法和語言2.1.2 文法和語言的定義注意定義2.5 ( 符號(hào)串的方冪 )設(shè)x是某字母表上符號(hào)串，把x自身連接 n 次得到符號(hào)串z，即 z = xxx (n個(gè)x) ，稱z是符號(hào)串 x的n次冪，記作z=xn。設(shè)x是符號(hào)串，則有定義x0=x1=xx2=xxx3= x2x= xx2=xxxxn= xn-1x= xxn-1=xx xn個(gè)Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義例如， 設(shè)x=abc則 x2=abcabcx3=abcabcabc定義2.6 ( 符號(hào)串集合的乘積 )設(shè)A、B 是兩個(gè)符號(hào)串集合，AB表示A與B的乘積，則有定義AB=xy | (xA)(y

13、B) Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義例如，設(shè)A=ab,c, B=d,ef,則AB=abd, abef, cd, cef注意：有 A= A=A, A= A = ，其中 為空集。注意： = 。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義定義2.7 ( 符號(hào)串集合的方冪 )設(shè)A是符號(hào)串集合，A自身的乘積可以用方冪表示。則有定義設(shè)P為字符串集：A0= A1=AA2=AAA3= A2A =AAAAn= An-1A =AAACh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義顯然有：Ai+j = Ai A

14、j例如， P= ab, x, aby ，則P2 = PP=abab, abx,ababy, xab, xx, xaby,abyab, abyx, abyabyCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義定義2.8 ( 符號(hào)串集合的并 )設(shè)P、Q為字符串集，集合P Q為P和Q 的并，它的元素是P或Q中的元素。例如，P=0, 1, 01Q=0, 10, 11, 00 ,則 P Q = 0, 1, 01, 10, 11, 00Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義定義2.9 ( 符號(hào)串集合的閉包 )設(shè)A為符號(hào)串集，A的正閉包記作A

15、+，則有A+= A1 A2 AnA的自反閉包記作A*，則有A*= A0 A+= A+= A+由定義知，A+= A A*A * = A0 A +Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義例如， 設(shè)有 A=01,10則A* = ，01，10，0110，1001，010101，100110，A+ = 01，10，0110，1001，010101，100110，Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義串集合運(yùn)算應(yīng)用：設(shè)有 L=A.Z, a.z D= 0,1,2, ,9 1) L D= 由字母和數(shù)字構(gòu)成的集合 2) LD= 所有一個(gè)字

16、母后跟隨一個(gè)數(shù)字組成的字符串的集合 3)L*= 由所有字母按任意順序組成的字符串（含 ）所構(gòu)成的集合 4) L( LD )*= 由所有一個(gè)字母開頭后跟隨字母或數(shù)字組成的字符串或的集合 Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義2.1.2 文法和語言的定義一.二.三.四.字符和字符串文法形式定義字符串運(yùn)算語 言Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義四. 語言1. 語言的非形式化定義給定一部文法G, 從G的開始符號(hào)S出發(fā)，反復(fù)使用產(chǎn)生式對(duì)非終結(jié)符進(jìn)行替換，最后所得到的終結(jié)符號(hào)串的全體，即為文法G所描述的語言L（G）。例2.3

17、: 設(shè)有文法GS P | aPbP ba | bQaQ ab則： L(G)=ba, abab, baba, abababCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義S P baS aPb ababS P bQa babaS aPb abQab abababCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和語言的定義定義2.10 ( 直接推導(dǎo) “ = ” )有V=A=W(,(VNVT)*),當(dāng)且僅當(dāng)P中存在一條規(guī)則A，稱V直接推導(dǎo)出W （或W直接歸約到V），記作：V = W。定義2.11 ( 直接推導(dǎo)序列 )如果存在V= 0= 1, 1= 2, n

18、-1= n= W或 1= 2= 3= = n-1= n，+則V經(jīng)過n步(n0)可以推導(dǎo)出 W，記作: V = W 。當(dāng)+ *V = W或V = W，記作：V = W。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義定義2.12 (最左(右)推導(dǎo))在推導(dǎo)過程中，總是對(duì)句型中的最左(右)邊的非終結(jié)符進(jìn)行替換，稱為最左(右)推導(dǎo)。定義2.13 ( 句型 )*為GS的句型 。定義2.14 ( 句子 )*GS的句子。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義定義2.15 (規(guī)范推導(dǎo)/規(guī)范句型/ 規(guī)范歸約)最右推導(dǎo)也稱為規(guī)范推導(dǎo) 。僅用規(guī)范

19、推導(dǎo)得到的句型稱為規(guī)范句型 。規(guī)范推導(dǎo)的逆序?yàn)橐?guī)范歸約。注意：對(duì)給定的一個(gè)句子或句型其最左和最右推導(dǎo)的惟一性。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義例2.4: 設(shè)有文法GE：E E *E | E+E | (E) | i設(shè)有句子$1: i*i+i= =L L L LE = E *E = E *E+E = E *E+i = E *i+i = i*i+iR R R R R最左推導(dǎo)最右推導(dǎo)/規(guī)范推導(dǎo)規(guī)范句型句子句型Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義定義2.16 ( 文法的遞歸 )設(shè)有文法G，A 是G的產(chǎn)生式，若具有A+

20、若= ，則G為左遞歸文法。若= ，則G為右遞歸文法。直接遞歸遞歸文法間接遞歸左（右）遞歸Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義例2.5： 設(shè)有文法G1： E E+E | E*E | (E) | i有E = E 則文法G1是直接遞歸文法。例2.6： 設(shè)有文法G2：T Qc | cQ Rb | bR Ta | a+有T=Qc =Rbc =Tabc，即 T= Tabc，則文法G2是間接遞歸文法。L(G) = | VTS = ，S是文法Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義2. 語言的形式定義定義2.17 ( 語言 )文法

21、 G所產(chǎn)生的語言L(G)：*+的開始符號(hào) 例2.7: 設(shè)有語言 L(G1)= abna | n=0 , 求G1？G1 ： S aa | aRaR b | RbCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義S S0 | 0求L (G) ？L (G) = 0n | n=1 例2.8: 設(shè)有文法 G：S 0S1 | 01求L(G)？L（G）= 0n1n | n=1 例2.9: 設(shè)有文法 G：G:S 0S | 0L(G) = L(G)Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.2 文法和 語言的定義定義2.18 ( 文法等價(jià) )若 L(G1)= L(G2)，

22、則稱文法G1和G2是等價(jià)的 。例2.11:設(shè)有語言L(G) :L(G)= a(bn)a | n=0 = a()a, a(b)a, a(bb)a, G: S a(B)aG: S a()a | a(B)aB Bb | b | B Bb | bCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.3 文法的表示1. BNF表示法元語言符號(hào)集： , , | 2. 擴(kuò)充BNF表示法 （EBNF）1) 引入花括號(hào) t 表示字符串t 的多次獲任意次出現(xiàn)，其中下角標(biāo)n 表示串t重復(fù)的最小次數(shù)，上角標(biāo)m表示字符串 t 重復(fù)的最大次數(shù)。mnCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.3 文法的表示例

23、2.12: FORTRAN語言中標(biāo)識(shí)符的定義。假設(shè)標(biāo)識(shí)符是長度8的字母開頭后跟字母或數(shù)字的字符串，則有： | 70Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.3 文法的表示2) 引入圓括號(hào) “(” “)”提取產(chǎn)生式中的公共因子，簡(jiǎn)化產(chǎn)生式的表示。例2.13: 有文法規(guī)則U xa | xb | | xz引入圓括號(hào)提取公共字符串x后有：U x（a | b | | z）Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.3 文法的表示3) 引入方括號(hào) t 表示字符串 t 可有可無。例2.14:設(shè)有條件語句的文法 |else IF THEN引入方括號(hào)后，可簡(jiǎn)化為： else IF TH

24、ENCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.3 文法的表示3. 語法圖例2.15: PASCAL語言中標(biāo)識(shí)符的定義如下圖。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.4 語法樹與二義性一 . 語法樹與二義性語法樹是句子結(jié)構(gòu)的圖形表示，它代表了句子的推導(dǎo)結(jié)果，有利于理解句子語法結(jié)構(gòu)的層次。表示：語法樹的根結(jié)點(diǎn)語法樹的中間結(jié)點(diǎn)語法樹的葉結(jié)點(diǎn)結(jié)點(diǎn)間關(guān)系G的SG的VNG的VTG的產(chǎn)生式規(guī)則Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.4 語法樹與二義性例2.16 ： 設(shè)有無符號(hào)整數(shù)的文法 | 0 | 1 | 2 | | 9對(duì)句子25的最左推導(dǎo)過程是： = = =

25、= 2 = 25對(duì)句子25的最右推導(dǎo)過程是： = = =5 = 5 = 25Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.4 語法樹與二義性無符號(hào)整數(shù)數(shù)字串?dāng)?shù)字串?dāng)?shù)字?jǐn)?shù)字5注意：一棵語法樹包括了一個(gè)句型的所有可能的推導(dǎo)過程。一個(gè)句型是否只對(duì)應(yīng)一棵語法樹？是否只有惟一的最左（右）推導(dǎo)？2文法二義性問題Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.4 語法樹與二義性定義2.19 ( 二義文法 )對(duì)一部文法G，如果至少存在一個(gè)句子,有兩棵( 或兩棵以上 )不同的語法樹，則稱該句子是二義性的。包含有二義性句子的文法稱為二義文法。否則，該文法是無二義性的。定義提供了對(duì)給定文法在某一范

26、圍內(nèi)判定是否是二義性文法的充分條件。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.4 語法樹與二義性例2.17： 設(shè)有文法G1：E E+E | E*E | (E) | i=L L L LE=E +E =E *E+E = i *E+E = i *i+E =i*i+iL L L L LEE * EiE + EiiEE + EE * EiiiCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.4 語法樹與二義性二. 文法二義性的消除例如， 對(duì)有文法G1： E E+E | E*E | (E) | i1） 分析二義性原因a) 運(yùn)算符 “+”和“*”未體現(xiàn)優(yōu)先級(jí)；b) “+”和“*”自身結(jié)合

27、規(guī)則不明確；2） 構(gòu)造G1 ，使L( G1）=L( G1)G1:E T | E+TT F | T*FF (E) | iCh2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.5 文法和語言的類型N.Chomsky 分類 ：1. 0型文法（ 短語文法 ）定義2.20：如果對(duì)文法G中的規(guī)則不加任何限制，則稱G為0型文法或短語文法。其中，,(VTVN) *且。0型文法相應(yīng)的語言為0型語言L0，0型語言可由圖靈機(jī)（Turing）來識(shí)別。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.5 文法和語言的類型例2.18: 設(shè)有文法GS aQbaQb caRbcaRb caba顯然，G是0型文法。Ch2 形式語言自動(dòng)機(jī)理論基礎(chǔ)2.1 文法和語言2.1.5 文法和語言的類型21型文法（ 上下文有關(guān)文法 ）定義2.21：設(shè)文法G=(VN,VT,S,P)，對(duì)P中的每個(gè)產(chǎn)生式限制為形如：A其中，AVN，,(VTVN)，(VTVN)+，則稱文法G為1型文法或上下文有關(guān)文法。1型文法相應(yīng)的語言為1型語言L1，1型語言可由線性有界自動(dòng)機(jī)來識(shí)別