前后文無關(guān)文法和語言

前后文無關(guān)文法和語言第一頁，共六十七頁，編輯于2023年，星期五重點和難點重點：本章中涉及的概念和術(shù)語的理解文法和語言的形式定義難點：短語和句柄的識別二義性文法的判定第二頁，共六十七頁，編輯于2023年，星期五2.1語言及其表示方法規(guī)定一種語言首先要規(guī)定它各種構(gòu)造成分的形式，詞匯、句子等的構(gòu)造規(guī)則及表示法。編譯原理則應(yīng)建立有關(guān)語言的數(shù)學(xué)化（形式化）模型，以便對程序語言進行研究。第三頁，共六十七頁，編輯于2023年，星期五定義1：相當(dāng)大的地區(qū)內(nèi)公眾所懂得并使用的“話”，以及組成這些“話”的方法的統(tǒng)一體。缺點：不夠形式化和精確化定義2：某一個字母表上的符號串的（句子）的集合。缺點：缺乏語言句子的結(jié)構(gòu)性組成描述，缺乏判斷任一符號串是否為合法句子判斷機制。因此，如果能刻畫一個語言句子，就定義了該語言。1、語言第四頁，共六十七頁，編輯于2023年，星期五1956年，chomsky建立文法的數(shù)學(xué)模型，對形式化語言和自動機理論的研究取得較大的成果。1960年。P.Nuaur和J.Boukas首先用BNF成功對ALGOL語言的文法進行了描述，雖然對語義形式化描述不理想，但在程序設(shè)計語言的語法描述上有足夠的能力。至此，程序語言就有了形式化表述。第五頁，共六十七頁，編輯于2023年，星期五枚舉（句子有限）例：L={Wearelearningcomputerscience,itisinteresting}數(shù)學(xué)表示(句子無限)例:{1,1/2,1/3,……1/n}→{1/n|n∈N}

制定有限條規(guī)則，用來產(chǎn)生所需描述語言中的句子全部，這些規(guī)則即文法。建立一種算法能對于任給的符號串，判別是否為給定語言的合法句子——自動機理論。2、表示方法第六頁，共六十七頁，編輯于2023年，星期五

語言可以看成在一個基本符號集上定義的，按一定規(guī)則構(gòu)成的一切基本符號串組成的集合。第七頁，共六十七頁，編輯于2023年，星期五2.2文法的定義1、例：“我是大學(xué)生”是漢語的一個句子。〈句子〉∷=〈主語〉〈謂語〉〈主語〉∷=〈代詞〉｜〈名詞〉〈代詞〉∷=我｜你｜他〈名詞〉∷=王明｜大學(xué)生｜工人｜英語〈謂語〉∷=〈動詞〉〈直接賓語〉〈動詞〉∷=是｜學(xué)習(xí)〈直接賓語〉∷=〈代詞〉｜〈名詞〉返回第八頁，共六十七頁，編輯于2023年，星期五∷=左端的規(guī)則由∷=右端的符號串代替：〈句子〉〈主語〉〈謂語〉

〈代詞〉〈謂語〉我〈謂語〉我〈動詞〉〈直接賓語〉

我是〈直接賓語〉

我是〈名詞〉

我是大學(xué)生按照如下方式用它們導(dǎo)出句子：第九頁，共六十七頁，編輯于2023年，星期五大學(xué)生〈句子〉〈主語〉〈謂語〉〈代詞〉〈動詞〉〈直接賓語〉〈名詞〉我是“我大學(xué)生是”是否為<句子>?第十頁，共六十七頁，編輯于2023年，星期五sentence–><subject><verb-phrase><object>subject–>This|Computers|Iverb-phrase–><adverb><verb>|<verb>adverb–>neververb–>is|run|am|tellobject–>the<noun>|a<noun>|<noun>noun–>university|world|cheese|liesThisisauniversity.Computersruntheworld.Iamthecheese.Inevertelllies.英語句子第十一頁，共六十七頁，編輯于2023年，星期五2、文法的形式化表示符號：<>表示一個語法單位；∷=（–>）表示“定義為”；

|表示為“或”。文法：描述語言的形式結(jié)構(gòu)的規(guī)則。產(chǎn)生式，產(chǎn)生式左部，產(chǎn)生式右部第十二頁，共六十七頁，編輯于2023年，星期五文法的一般構(gòu)成：一組終結(jié)符號：僅出現(xiàn)在產(chǎn)生式右部的符號VT；一組非終結(jié)符號：至少在產(chǎn)生式左部出現(xiàn)過一次的符號VN；一個開始符號：特殊的非終結(jié)符，表示了定義語言中最感興趣的語法范疇。S；一組規(guī)則：P

G={VT，VN，S，P}

例如

第十三頁，共六十七頁，編輯于2023年，星期五VN，VT和P是非空有窮集；

VN和VT不含公共的元素，即VN∩VT=φ；用V表示VN∪VT，稱文法G的字母表或字匯表；產(chǎn)生式是形如→或∷=的（，）有序?qū)Γ渲惺亲帜副鞻的一個非空符號串(V+)，是V中的一個符號串，可為空串(V*)。稱為產(chǎn)生式左部，稱作產(chǎn)生式右部。

說明：第十四頁，共六十七頁，編輯于2023年，星期五2.3由文法產(chǎn)生句子1、推導(dǎo)〈句子〉

〈主語〉〈謂語〉

〈代詞〉〈謂語〉

我〈謂語〉

……過程：文法的開始符號開始，每次把當(dāng)前串的一個非終結(jié)符號用于之對應(yīng)的產(chǎn)生式右部來代換，得到一個新符號串，稱一步推導(dǎo)。2、推導(dǎo)長度第十五頁，共六十七頁，編輯于2023年，星期五文法的作用就是用有限條規(guī)則產(chǎn)生無限多句子。某一文法產(chǎn)生的全部句子所組成的集合——該文法產(chǎn)生的語言。第十六頁，共六十七頁，編輯于2023年，星期五一、基本定義1、符號：可以相互區(qū)別的記號（元素）。2、字母表：符號（元素）的非空有窮集合。3、符號串：由字母表中的符號組成的任何有窮序列。空符號串ε(沒有符號的符號串)是上的符號串。若x是上的符號串，a是的元素，則xa是上的符號串。

y是上的符號串，當(dāng)且僅當(dāng)它可以由1和2導(dǎo)出。例如：Σ={a,b}ε，a，b，aa，ab，aabba…都是上的符號串2.4有關(guān)定義和記號第十七頁，共六十七頁，編輯于2023年，星期五4、符號串s的頭（前綴）：移走符號串s尾部的零個或多于零個符號得到的符號串。如：b是符號串banana的一個前綴.banana是banana前綴。

5、符號串s的尾（后綴）：刪去符號串s頭部的零個或多于零個符號得到的符號串。如:nana是符號串banana的一個后綴.banana是banana后綴。第十八頁，共六十七頁，編輯于2023年，星期五6、符號串s的子串：從s中刪去一個前綴和一個后綴得到的符號串。如:ana是符號串banana的一個子串。7、符號串s的真前綴，真后綴，真子串：任何非空符號串x，是s的前綴，后綴或子串，并且sx。8、符號串的長度：符號串中符號的個數(shù)。符號串s的長度記為|s|。ε的長度為0。對于每個符號串s，s和ε兩者都是符號串s的前綴，后綴和子串。第十九頁，共六十七頁，編輯于2023年，星期五1、連接：符號串x、y的連接，是把y的符號寫在x的符號之后得到的符號串xy。如：x=ba,y=ck則xy=back有εa=aε2、方冪：符號串自身連接n次得到的符號串。

an定義為aa…aan個aa1=a,a2=aaa0=ε二、符號串的運算第二十頁，共六十七頁，編輯于2023年，星期五三、符號串集合若集合A中所有元素都是某字母表上的符號串，則稱A為字母表上的符號串集合。1、符號串集合乘積：兩個符號串集合A和B的乘積定義為

AB=xy|xA且yB例如：若集合A=ab，cdeB=0，1則AB=ab1，ab0，cde0，cde12、Σ的閉包：上的一切符號串（包括ε）組成的集合。記為Σ*

第二十一頁，共六十七頁，編輯于2023年，星期五3、Σ的正閉包：上的除ε外的所有符號串組成的集合。記為Σ+例：Σ={a,b}，求Σ*和Σ＋。Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}第二十二頁，共六十七頁，編輯于2023年，星期五Σ*包含Σ上的所有符號串，Σ+包含Σ上除空串ε外的任意符號串。第二十三頁，共六十七頁，編輯于2023年，星期五1、語言：由句子組成的集合，為一符號串集合。即：字母表上的一個語言是上的一些符號串的集合，是*的一個子集。

L={S|S∈*}{}、{ε}都是語言例如：字母表Σ={a,b}

集合{w|w∈Σ*且w=anbn,n≥1}為上的一個語言。集合{w|w∈Σ*且w=an,n≥1}為上的一個語言。四、語言上的有關(guān)運算第二十四頁，共六十七頁，編輯于2023年，星期五2、語言“并”運算：語言L和M的并為LM，是一個語言:{w|wisinLorisinM}如：L1={a,b,…y,z}，M1={1,2…8,9}

L1M1={a,b,…y,z，1,2…8,9}設(shè)L是（上的）一個語言，M是（上的）一個語言，語言L和M的“并”，“交”，“差”，“連接”運算結(jié)果是一個語言。第二十五頁，共六十七頁，編輯于2023年，星期五3、語言L和M的連接運算：記為L?M(可簡記為LM)。

LM={st|s∈L且t∈M}如：L={a,b,…y,z}，M={1,2…8,9}

LM={a1,b1,…y1,z1,a2,b2…a9…z9}特別的：有L

ε=εL=L。

L的n次連接Ln=LL...L第二十六頁，共六十七頁，編輯于2023年，星期五4、語言L的

閉包：記為L*，L*=L0L1L2...L0=ε

，Ln=L

Ln-1=Ln-1L(n1)5、語言L的正

閉包：記為L+，L+=L1L2L3...L+=LL*=L*L

L*=L+

ε

如：L1

={a,b,…y,z}M1={1,2…8,9}

（L1M1）={a,b,…y,z，1,2…8,9

}

（L1M1）*={a,b,…y,z，1,2…8,9,aa,1a,…,xyz,6789st..}

L1（L1M1）*={所有字母打頭的字母和數(shù)字符號串}第二十七頁，共六十七頁，編輯于2023年，星期五練習(xí)1：L={A,B,C,……Z,a,b,c……z}D={0,1,2,3,4,5,6,7,8,9}計算：L∪D，LD，L4

，L*，L(L∪D)*，D+練習(xí)2：考慮一個文法G1:S→bAA→aA|a它定義了一個什么語言呢？從開始符S出發(fā)，我們可以推出如下句子：

SbAbaSbAbaAbaaSbAbaA…baa…a可以寫為：L(G1)={ban|n≥1}第二十八頁，共六十七頁，編輯于2023年，星期五2.5語言和文法的形式定義一個上下文無關(guān)文法G定義為四元組(VN，VT，P，S)其中：VN：非終結(jié)符號(或語法實體，或變量)集；VT：終結(jié)符號集；P：產(chǎn)生式(也稱規(guī)則)的集合；A→其中，∈(VN∪

VT)*，A∈VN

VN，VT和P是非空有窮集。

S：稱作識別符號或開始符號的一個非終結(jié)符，它至少要在一條產(chǎn)生式中作為左部出現(xiàn)。S∈VNVN和VT不含公共的元素，即VN∩

VT=φ

用V表示VN∪

VT

，稱為文法G的字母表或字匯表1、上下文無關(guān)文法第二十九頁，共六十七頁，編輯于2023年，星期五例<1>文法G=（VN，VT，P，S）

VN={S},VT={0,1} P={S→0S1,S→01} S為開始符號對此產(chǎn)生式可進行推導(dǎo)產(chǎn)生句子。第三十頁，共六十七頁，編輯于2023年，星期五2、推導(dǎo)直接推導(dǎo)“”

α→β是文法G的產(chǎn)生式，若有v,w滿足：v=γαδ,w=γβδ,其中γ∈V*,δ∈V*

則稱v直接推導(dǎo)到w,記作vw；也稱w直接歸約到v例：G：S→0S1，S→01

0S100S1100S11000S111000S11100001111S0S1第三十一頁，共六十七頁，編輯于2023年，星期五例：G：S→0S1，S→01S0S100S11000S11100001111SS00S1100S11S00001111推導(dǎo)長度為4

若存在v=w0w1...wn=w(n>0)

則記為vw，稱作v推導(dǎo)出w，或w歸約到v

若有vw或v=w，則記為vw

推導(dǎo)的長度（長度為n的推導(dǎo)）第三十二頁，共六十七頁，編輯于2023年，星期五3、句型和句子例：G：S→0S1，S→01S0S100S11000S11100001111G的句型S，0S1，00S11，000S111，00001111G的句子00001111，01

句型

有文法G[S]，若Sx，x∈V*，則稱x是文法G的句型。

句子

有文法G[S]，若Sx，且x∈VT*，則稱x是文法G的句子。第三十三頁，共六十七頁，編輯于2023年，星期五例：G[E]：E→E+T|T

T→T*F|F

F→(E)|a

判斷：a+a*a是否為該文法的句子EE+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a句子：用符號a，+，*，(和)構(gòu)成的算術(shù)表達式第三十四頁，共六十七頁，編輯于2023年，星期五4、語言由文法G生成的語言記為L(G)，它是文法G的一切句子的集合:語言中的每個句子可以由上下文無關(guān)文法的開始符號產(chǎn)生。例：G=（{0，1}，{S}，S，P）

P:S→0S1，S→01L(G)={0n1n|n≥1}L(G)={x|Sx，S為文法的開始符號，且x∈VT*}第三十五頁，共六十七頁，編輯于2023年，星期五G生成的每個串都在L(G)中，L(G)中的每個串確實能被G生成。文法所產(chǎn)生的語言L(G)是無限語言，原因是所定義的文法中含有遞歸。第三十六頁，共六十七頁，編輯于2023年，星期五5、文法的遞歸性遞歸、直接遞歸：如果文法中有形如A→γAδ的產(chǎn)生式，其中γ，δ不同時為ε，則稱產(chǎn)生式A→是直接遞歸。例：G[E]：

E→E+T|TT→T*F|F

F→(E)|aAγAδ，直接遞歸AγAδ，遞歸A稱為遞歸和直接遞歸的非終結(jié)符號若存在A

γAδ,則稱A→是遞歸的。

左遞歸、右遞歸

γ=ε，δ≠ε左遞歸

γ≠ε，δ=ε右遞歸第三十七頁，共六十七頁，編輯于2023年，星期五直接遞歸是遞歸的一種特殊情況，如果一個語言是無限的，則定義此語法的文法必然是遞歸的。

例：語言L={anbbn|n1},寫出產(chǎn)生L的文法。

G[S]:SaAbAaAb|b第三十八頁，共六十七頁，編輯于2023年，星期五從語法定義的角度，遞歸定義是一種較好的方式，因為它不僅使文法形式簡練，而且也給無限語言的有限表示提供了一種有效的方法。然而左遞歸會影響某些語法分析方法實現(xiàn)，因此有時需要對文法進行等價改造，以便消除其中的左遞歸。第三十九頁，共六十七頁，編輯于2023年，星期五6、文法的等價性

若L（G1）=L（G2），則稱文法G1和G2是等價的。

如文法G1[A]：A→0R與G2[S]：S→0S1等價

A→01S→01R→A1第四十頁，共六十七頁，編輯于2023年，星期五2.6句型的分析如何表示語言中的句子？任給的一個符號串是否為某一文法的句子（型）？需要進行句型分析。自頂向下：從文法的開始符號，以給定的符號串為目標(biāo)，試圖推導(dǎo)出串。自底向上：給定符號串出發(fā)，反復(fù)用文法中有關(guān)產(chǎn)生式的左部替換當(dāng)前符號串中的相應(yīng)子串，以期最后歸約為文法開始符號。第四十一頁，共六十七頁，編輯于2023年，星期五例：G[E]：

E→E+T|T

T→T*F|F

F→(E)|a

E判定a+a*a是否為文法的句子？E+TT+TF+Ta+Ta+T*F

a+F*Fa+a*Fa+a*a第四十二頁，共六十七頁，編輯于2023年，星期五1、規(guī)范推導(dǎo)規(guī)范句型最左（最右）推導(dǎo)：推導(dǎo)的每一步αβ，其中α、β是句型，都是對α中的最左（右）非終結(jié)符進行替換。規(guī)范推導(dǎo)：最右推導(dǎo)稱為規(guī)范推導(dǎo)。規(guī)范句型：由規(guī)范推導(dǎo)所得的句型稱為規(guī)范句型。注意：文法中的每個句子都必定有最左(右)推導(dǎo)，但對于一個句型，則不一定。G[E]：E→E+T|T

T→T*F|F

F→(E)|a

對句型T+a+T的推導(dǎo)：EE+TT*F+TT*a+T第四十三頁，共六十七頁，編輯于2023年，星期五

問題：對于推導(dǎo)中的每一步，SαXβ,如果X→α1|α2|α3|……|αk，（α，β）∈V*，X∈VN，則面臨選哪一個αi去匹配當(dāng)前串的問題。使用不當(dāng)易引起回溯。2、句型分析過程自頂向下分析方法

從文法的開始符號出發(fā)，反復(fù)使用文法的產(chǎn)生式，尋找與輸入符號串匹配的推導(dǎo)。例：文法G：S→cAd

A→ab

A→a

識別輸入串w=cabd是否為該文法的句子

S S S

c A d

c A d

a

b推導(dǎo)過程：S

cAd

cAd

cabd第四十四頁，共六十七頁，編輯于2023年，星期五自底向上分析方法從輸入符號串開始，逐步進行歸約，直至歸約到文法的開始符號。例：文法G：S→cAd

A→ab

A→a

識別輸入串w=cabd是否該文法的句子

S

A

A

cabd

ca

bd

ca

b

d

歸約過程構(gòu)造的推導(dǎo)：cAd

cabdScAd第四十五頁，共六十七頁，編輯于2023年，星期五在自下而上的分析方法中，在分析程序工作的每一步，都是從當(dāng)前串中選擇一個子串，將它歸約到某個非終結(jié)符號，該子串稱為“可歸約串”。歸約的子串應(yīng)是當(dāng)前句型的句柄。第四十六頁，共六十七頁，編輯于2023年，星期五3、語法樹和二義性語法樹：設(shè)G=(VN,VT,P,S)為一cfg，若一棵樹滿足下列4個條件，則此樹稱作G的語法樹：每個結(jié)點都有一個標(biāo)記，此標(biāo)記是V的一個符號；根的標(biāo)記是S

若某結(jié)點至少有一個子孫，并且該結(jié)點標(biāo)記為A，則A∈VN；若某結(jié)點標(biāo)記A，其直接子孫結(jié)點從左到右的次序是n1，n2，…，nk，其標(biāo)記分別為A1，A2，…，Ak，那么A→A1A2，…，Ak定是P中的一個產(chǎn)生式第四十七頁，共六十七頁，編輯于2023年，星期五語法樹---句型推導(dǎo)的直觀表示給定上下文無關(guān)文法G=(VN,VT,P,S)，對于G的任何句型都能構(gòu)造與之相關(guān)的語法樹(推導(dǎo)樹)

定理：G為上下文無關(guān)文法， 對于

≠ε，有S=>*

，當(dāng)且僅當(dāng)文法G有以為結(jié)果的一棵語法樹(推導(dǎo)樹)第四十八頁，共六十七頁，編輯于2023年，星期五例:G[S]: S→aAS A→SbA A→SS S→a A→ba句子aabbaa的語法樹（推導(dǎo)樹）葉子結(jié)點：樹中沒有子孫的結(jié)點。

SaASSbAaaba第四十九頁，共六十七頁，編輯于2023年，星期五推導(dǎo)過程中使用產(chǎn)生式的順序

例:G[S]:S→aASA→SbA|SS|baS→aSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa

SaASSbAaaba第五十頁，共六十七頁，編輯于2023年，星期五一棵語法樹可表示一個句子的多種可能的不同推導(dǎo)過程，包括最左(最右)推導(dǎo)。

一個句子是否只對應(yīng)唯一的一棵語法樹?一個句子是否只有唯一的一個最左(最右)推導(dǎo)?第五十一頁，共六十七頁，編輯于2023年，星期五例：G[E]:

E→i E→E+E E→E*E E→(E)句型i*i+i的推導(dǎo)，有兩個不同的最左推導(dǎo)：推導(dǎo)1：EE+EE*E+Ei*E+Ei*i+Ei*i+i推導(dǎo)2：EE*Ei*Ei*E+Ei*i+Ei*i+i

EE+EE*Eiii

EE*EiE+Eii第五十二頁，共六十七頁，編輯于2023年，星期五

二義性文法若一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。若一個文法存在某個句子有兩個不同的最左（右）推導(dǎo)，則稱這個文法是二義的

注意：

判定任給的一個上下文無關(guān)文法是否二義，或它是否產(chǎn)生一個先天二義的上下文無關(guān)語言，這兩個問題是遞歸不可解的，但可以為無二義性尋找一組充分條件。第五十三頁，共六十七頁，編輯于2023年，星期五一個文法兼有左右遞歸是導(dǎo)致二義性的最常見原因。二義文法改造為無二義文法

G[E]:E→iG[E]：E→T|E+T E→E+ET→F|T*F E→E*EF→（E）|i E→(E)改寫文法，消除同時存在的左右遞歸。第五十四頁，共六十七頁，編輯于2023年，星期五4、短語和句柄SαAδ且A

β，則稱β是句型αβδ相對于非終結(jié)符A的短語對于文法G[S]：

句型的短語

句型的直接短語若有A

β，則稱β是句型αβδ相對于非終結(jié)符A的直接短語

句型的句柄一個句型的最左直接短語稱為該句型的句柄第五十五頁，共六十七頁，編輯于2023年，星期五i*i+i的短語、直接短語和句柄EE+T

TFT*F

i3

短語：i1*i2+i3，

i1*i2

，F(xiàn)i2

i1

，

i2

，

i3

。i1

直接短語：

i1

，

i2

，

i3

。句柄：i1

例：

G[E]：

E→E+T|T

T→T*F|F

F→(E)|i句型：i*i+i第五十六頁，共六十七頁，編輯于2023年，星期五G[S]: S→aAS

S→a A→SbA A→SS A→ba句子aabbaa的最左推導(dǎo)，指出此句子的全部短語、各步直接推導(dǎo)所得句型的句柄、該句子的句柄

S1a1A1S3S2b1A2a2a3b2a4練習(xí)第五十七頁，共六十七頁，編輯于2023年，星期五通過對產(chǎn)生式施加不同限制，Chomsky將文法分為四類：0型文法：對任一產(chǎn)生式α→β，有α∈V+，β∈V*;1型文法：對任一產(chǎn)生式α→β，有|β|≥|α|(α,β∈V+)，僅S→ε除外?；蛘咝稳绂罙β→αγβ產(chǎn)生式,A∈VN,γ∈V+,α,β∈V*2型文法：對任一產(chǎn)生式A→β，都有A∈VNβ∈V*;3型文法：任一產(chǎn)生式的形式都為A→αB或A→α(右線性)，A→Bα或A→α（左線性）其中A∈VN

，B∈VN

，a∈VT+2.8文法的類型第五十八頁，共六十七頁，編輯于2023年，星期五四種文法之間的逐級“包含”關(guān)系0型文法1型文法2型文法3型文法第五十九頁，共六十七頁，編輯于2023年，星期五AhierarchyofgrammarsType0:freeorunrestrictedgrammarsThesearethemostgeneral.Productionsareoftheformu–>vwherebothuandvarearbitrarystringsofsymbolsinV,withunon-null.Therearenorestrictionsonwhatappearsontheleftorright-handsideotherthantheleft-handsidemustbenon-empty.Type1:context-sensitivegrammarsProductionsareoftheformuXw–>uvwwhereu,vandwarearbitrarystringsofsymbolsinV,withvnon-null,andXasinglenonterminal.Inotherwords,Xmaybereplacedbyvbutonlywhenitissurroundedbyuandw.第六十頁，共六十七頁，編輯于2023年，星期五Type2:context-freegrammarsProductionsareoftheformX–>vwherevisanarbitrarystringofsymbolsinV,andXisasinglenonterminal.WhereveryoufindX,youcanreplacewithv(regardlessofcontext).Type3:regulargrammarsProductionsareoftheformX–>aorX–>aYwhereXandYarenonterminalsandaisaterminal.Thatistheleft-handsidemustbeasinglenonterminalandtheright-handsidecanbeeitherasingleterminalbyitselforwithasinglenonterminal.Thesegrammarsarethemostlimitedintermsofexpressivepower.第六十一頁，共六十七頁，編輯于2023年，星期五例：1型（上下文有關(guān)）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD