【正文】 N 稱為文法的識(shí)別符號(hào)或開始符號(hào)。 α稱為規(guī)則的左部， β稱為規(guī)則的右部。 文法的定義及其分類 ? 什么是文法，文法的直觀概念是，文法作為一種工具，不僅嚴(yán)格地定義句子的結(jié)構(gòu)，也是為了用適當(dāng)條數(shù)的規(guī)則把語(yǔ)言的全部句子描述出來(lái)，是以有窮的集合刻劃無(wú)窮的集合的工具。 ? 說(shuō)明：根據(jù)閉包和正閉包的定義，則有 Σ+=Σ*Σ=ΣΣ* ? 由于一個(gè)字母表的正閉包包含了該字母表中的符號(hào)所能組成的一切符號(hào)串，而語(yǔ)言是該字母表上某個(gè)符號(hào)串的集合，因此，在某個(gè)字母表上的語(yǔ)言是該字母表上正閉包的子集，且是真子集。 ? 定義 A的正閉包 A+=A1 ∪ A2 ∪ … ∪ An∪ … ? 顯然， A*= A0 ∪ A+ ，且 A+=AA*=A*A。 A的閉包定義如下： ? 定義 A的閉包 A*=A0∪ A1 ∪ A2 ∪ … ∪ An∪ …, 其中，An （ n=0， 1， 2， 3， … ）中所有的符號(hào)串的長(zhǎng)度為 n，因此字母表 A的閉包 A*為字母表上一切長(zhǎng)度為 n的符號(hào)串所組成的集合。 ?字母表上的符號(hào)串的集合通常用大寫字母來(lái)表示 A、 B、 C、 … 表示。對(duì)于字母表上的任何符號(hào)串 x，都有εx=xε=x ? 定義 符號(hào)串的方冪 ：設(shè) x是某個(gè)字母表上的符號(hào)串，把 x自身連接 n次，即 z=xx…x （ n個(gè) x），稱為符號(hào)串 x的 n次方冪，記為 z=xn。 ? 例題 {a,b,c}上有符號(hào)串 x=ab與y=cba，則 z=xy=abcba。若只對(duì)尾部感興趣，則記為 z=…x 。 ? 例題 假設(shè)字母表 ?={a,b,c}上的符號(hào)串 z=abc，則 ε、 a、ab、 abc都是 z的頭，且除 abc外都是 x的固有頭； ε、 c、bc、 abc都是 z 的尾，且除 abc外都是 z的固有尾。 ? 例題 Σ={a， b， c， d， +， ， *， /， (， )}上有符號(hào)串 x=a+b*(c+d)，則 a、 a+b*與（ c+d）等都是 x的子符號(hào)串，且其長(zhǎng)度分別為 ∣ a∣ = ∣ a+b*∣ =4與∣ (c+d)∣ =5 ? 4．符號(hào)串的頭和尾 ? 定義 如果 z=xy是一個(gè)符號(hào)串，則 x是 z的頭 ,而 y是 z的尾。 ε記為空串，長(zhǎng)度為 0。 ? 2．符號(hào)串的長(zhǎng)度 ? 符號(hào)串 x中所包含的符號(hào)的個(gè)數(shù)稱為符號(hào)串 x的長(zhǎng)度，記為 |x| 。 ? 例 某個(gè)字母表∑={a,b,c,…z,if,then,else,main,1,2,3,4,…,9,0,=,==,。 ? 例 ?={a,b}， ? ?={0,1}， ? ?={0,1， 2， 3， 4， 5， 6， 7， 8， 9}， ? ∑={a,b,c,…z,if,then,else,main,1,2,3,4,…,9,0,=,==,。 ? 定義 字母表是元素的非空有窮集合，字母表中的元素稱為 符號(hào) ，因此字母表也稱為 符號(hào)表 。每個(gè)程序可以看成基本符號(hào)串。本章主要內(nèi)容是 : ?文法和語(yǔ)言的形式定義 ?文法的分類 ?句型的分析和語(yǔ)法樹 ? 任何一種語(yǔ)言都是由基本符號(hào)構(gòu)成的。第二章 形式語(yǔ)言概述 本章學(xué)習(xí)目標(biāo) ?形式語(yǔ)言由 Chomsky于 1956年提出，主要討論語(yǔ)言和文法的數(shù)學(xué)機(jī)制以及語(yǔ)言和文法的分類。形式語(yǔ)言 的形成和發(fā)展，對(duì)編譯原理和技術(shù)產(chǎn)生了重要的影響。計(jì)算機(jī)高級(jí)語(yǔ)言作為計(jì)算機(jī)的語(yǔ)言，程序有語(yǔ)句構(gòu)成，語(yǔ)句有一些基本符號(hào)構(gòu)成，這些基本符號(hào)是保留字如 main，if， then等、字母、數(shù)字和專用符號(hào)等。將所有的基本符號(hào)定義成一個(gè)基本符號(hào)集合，則語(yǔ)言可以看成是在這個(gè)基本符號(hào)集合上定義的，按一定的規(guī)則構(gòu)成的一切基本符號(hào)串組成的集合，給出如下的一些基本概念。高級(jí)語(yǔ)言如 C語(yǔ)言的字母表是由字母、數(shù)字、特殊符號(hào)和一些專用符號(hào)構(gòu)成。（，） } ? 1．符號(hào)串 ? 定義 符號(hào)串是由字母表中的符號(hào)所組成的有窮序列。} ，則建立在 ∑上的符號(hào)串有： if (2+3==5) then a=6 else b=8。例如字母表 {0， 1}，則 |010110|=6。 ? 3．子字符串 ? 定義 設(shè)有非空符號(hào)串 u=xvy，其中 x、 v、 y是符號(hào)串，且 v≠ε，則稱 v為符號(hào)串 u的子符號(hào)串。如果 y非空，則 x是 z的固有頭，又稱為真前綴；若 x非空，則 y是 z的固有尾，又稱為真后綴。 ? 若只對(duì)符號(hào)串的頭部感興趣，記做 z=x… 。 ? 5．符號(hào)串的運(yùn)算 ? 定義 符號(hào)串的連接運(yùn)算 ：設(shè) x與 y是同一個(gè)字母表上的兩個(gè)符號(hào)串，把 y的各個(gè)符號(hào)相繼寫在 x的符號(hào)后所得到的符號(hào)串稱為 x與 y的連接，記為 xy。這里 ∣ x∣ =2, ∣ y∣ =3, ∣ z∣ =5。 ? 例如， x=ab ? 則 x3=ababab ?1．符號(hào)串集合的定義 ?定義 若集合 A中一切元素都是某字母表 ∑上的符號(hào)串，則稱 A是該字母表 ∑上的符號(hào)串的集合。 ?例題 設(shè)某個(gè)字母表 {a,b,c,d}上有兩個(gè)符號(hào)串的集合記為 A={a,bc},B={abc,cd,ab} ? 2．符號(hào)串集合的運(yùn)算 ? 定義 兩個(gè)符號(hào)串集合 A和 B的乘積 AB定義為： ? AB={xy∣ x∈ A ，且 y∈ B} ? 例題 設(shè) A={a,b}， B={c,d,e} 則AB={ac,ad,ae,bc,bd,be} ? 對(duì)于任何空集合 Φ，都有 ΦA(chǔ)=AΦ=A ? 類似于符號(hào)串的方冪，可以定義符號(hào)串集合的方冪，特別地定義字母表 A的方冪為： ? A0={ε}， A1=A， An=An1A (n0) ? 3．字母表的閉包與正閉包的運(yùn)算 ? 設(shè)有字母表 A，由它做方冪 A0， A1， A2， … A n, … 。 ? 如果不允許包含空串 ε，則得到字母表 A的正閉包。 ? 例題 設(shè)字母表 Σ={a,b,c},依次寫出長(zhǎng)度為 2… 的符號(hào)串，可得到 Σ的正閉包 ? Σ+ ： Σ+={a,b,c,aa,ab,ac,bb,bc,…}, 在 Σ+上添入空串 ε即得Σ*。對(duì)于 C語(yǔ)言，可以說(shuō)， C語(yǔ)言是基本符號(hào)集合的正閉包的真子集。 ? 1．重寫規(guī)則 ? 定義 重寫規(guī)則，也叫產(chǎn)生式規(guī)則，或稱為生成式 ，是形如 α→β或α::═β的（ α,β）有序?qū)?,其中 , α是某個(gè)字母表 V+中的一個(gè)元素， β是 V* 中的一個(gè)元素。 ? 例如 A??B?讀作“ A定義為 ?B?”，也就是說(shuō)它是一條關(guān)于 A的規(guī)則（產(chǎn)生式）。 ? 例題 ，假設(shè)我們定義標(biāo)識(shí)符的命名規(guī)則為字母 a、 b、 c開頭的，字母 a、 b、 c和數(shù)字 3的序列?！?|”讀做“或者”。 ? 0型文法 (短語(yǔ)文法 ) ? 設(shè) G=（ VN， VT， P， S），如果它的每個(gè)產(chǎn)生式 α→β是這樣一種結(jié)構(gòu)： α∈（ VN∪ VT ） + ，且至少含有一個(gè)非終結(jié)符，而 β∈ （ VN∪ VT ） *，則稱 G是一個(gè) 0型文法 。 ? 例如， ?A?→? ? 1型文法（上下文有關(guān)文法） ? 設(shè) G=（ VN， VT， P， S）為一文法，若 P中的每一個(gè)產(chǎn)生式 α→β均滿足 ∣ β∣ ≥∣ α∣ ，僅僅 S→ε除外，則文法 G是1型文法或上下文有關(guān)文法 。 ? 3． 2型文法（上下文無(wú)關(guān)文法） ? 設(shè) G=(VN， VT， P， S)，若 P中的每個(gè)產(chǎn)生式 α→β滿足 : α是一個(gè)非終結(jié)符 , β∈ (VN∪ VT ) *，則此文法稱為 2 型文法或上下文無(wú)關(guān)文法 。 也就是當(dāng)用 β取代非終結(jié)符 A時(shí)，與A所在的上下文無(wú)關(guān)。 ? 例題 2 型文法 ? G=（ VN， VT， P， N） ? 其中， VN={N， D} ? VT={0， 1， 2， 3， 4， 5， 6， 7， 8， 9} ? P={N→ND∣ D， D→0∣ 1∣ 2∣ 3∣ 4∣ 5∣ 6∣ 7∣ 8∣ 9} ? 該文法描述的符號(hào)串的集合是整數(shù)。 ? 例題 正規(guī)文法 G=（ VN