Chapt23 形式語(yǔ)言.ppt

1、第四部分是形式語(yǔ)言和自動(dòng)機(jī)的理論基礎(chǔ)。眾所周知，計(jì)算機(jī)是數(shù)學(xué)和電子學(xué)結(jié)合的產(chǎn)物，它的數(shù)學(xué)模型是圖靈定義的計(jì)算模型。在當(dāng)今的信息社會(huì)，計(jì)算無(wú)處不在，每個(gè)人都在計(jì)算，計(jì)算影響著每個(gè)人。計(jì)算機(jī)科學(xué)在這個(gè)信息社會(huì)中發(fā)揮著越來(lái)越重要的作用。計(jì)算機(jī)科學(xué)有許多基礎(chǔ)理論，但計(jì)算模型的基礎(chǔ)理論主要包括形式語(yǔ)言和自動(dòng)機(jī)理論、可計(jì)算性理論、邏輯和程序設(shè)計(jì)理論。形式化和抽象是計(jì)算機(jī)科學(xué)理論的重要特征。本文主要介紹計(jì)算模型基礎(chǔ)理論中的形式語(yǔ)言和自動(dòng)機(jī)理論。第二十三章形式語(yǔ)言、符號(hào)和符號(hào)串是形式語(yǔ)言中非常重要的基本概念。象征主義在計(jì)算機(jī)科學(xué)的發(fā)展中一直占據(jù)著非常重要的地位。語(yǔ)言以字母表為基礎(chǔ)。23.1符號(hào)，符號(hào)串及其操作

2、，字母表：一個(gè)非空的有限集合被稱為字母表，它通常由西方字母表示或大寫(xiě)。字母表中的元素被稱為字母或符號(hào)，通常由小寫(xiě)字母和數(shù)字表示。符號(hào)串：符號(hào)串是由字母表中的字母組成的有限序列。符號(hào)串長(zhǎng)度：符號(hào)串中包含的符號(hào)數(shù)稱為符號(hào)串長(zhǎng)度。符號(hào)串w的長(zhǎng)度表示為|w|?？兆址洪L(zhǎng)度為0的符號(hào)字符串稱為空字符串，由。連接是符號(hào)串的基本操作。兩個(gè)符號(hào)串X和y的并集，表示為XY，是在X后面跟隨y形成的符號(hào)串.符號(hào)串的連接：讓=1，2是一個(gè)字母表。讓X=11和Y=22是上的兩個(gè)符號(hào)串。那么：XY=1122是兩個(gè)符號(hào)串x和y的連接，XY是一個(gè)符號(hào)串on。YX=2211是兩個(gè)符號(hào)串y和x的連接，YX也是世界上的一個(gè)符號(hào)串

3、。一般來(lái)說(shuō)，符號(hào)串的連接不滿足交換定律。顯然，符號(hào)串的連接滿足關(guān)聯(lián)定律，即，(XY)Z=X(YZ)。在上面的例子中，顯然有XYYX，(XY)X=X(YX)=112211。因?yàn)樗且粋€(gè)沒(méi)有符號(hào)的符號(hào)串(空串)，它存在于任何符號(hào)串X中，X=X=X.因此，我們可以把它看作是符號(hào)串聯(lián)運(yùn)算的單位元。假設(shè)x是一個(gè)符號(hào)串，在連接x本身n次后，符號(hào)串Z，也就是，Z=XXXX=Xn，被稱為x的冪。我們同意X0=。這個(gè)定義可以遞歸地表示為：符號(hào)串的冪：符號(hào)串v是符號(hào)串W的子串，當(dāng)且僅當(dāng)有符號(hào)串x和y，所以W=XVY。這里，x和y都可以是空字符串。如果x和y都是，顯然W=V，那么每個(gè)符號(hào)串都是它自己的子串。如果X=

4、，v是w的前綴，如果同時(shí)有Y，v是w的真前綴。如果Y=，v是w的后綴，如果同時(shí)有X，v是w的真后綴，符號(hào)串的子串、前綴和后綴：讓A和B都是符號(hào)串的集合， 并且設(shè)集合A和集合B之間的連接為AB=XY | XA和YB，即集合A和集合B之間的連接是集合A中的符號(hào)串和集合B中的符號(hào)串之間的連接形成的集合。設(shè)A為一組符號(hào)串，在A本身被連接n次之后，新的集合A，即安=AAA，被稱為集合A的冪。我們同意A0=1。 這個(gè)定義可以遞歸地表示為：集合的冪：設(shè)A是符號(hào)串的集合，用A*表示A的所有有限冪的并集，那么A*稱為集合A上的閉包，即A*=A0 A12an稱為集合A上的正閉包，顯然，有A*=A0 A，A * A

5、=AA *。注意：閉包A*和正閉包A之間的區(qū)別在于它是否包含空字符串。當(dāng)空字符串從閉包A*中移除后，它就變成了正閉包A。A *有一個(gè)可數(shù)的無(wú)限個(gè)符號(hào)字符串。集合的閉包和正閉包：使它成為一個(gè)字母表。如果L *，那么L是字母表中的一種語(yǔ)言。也就是說(shuō)，l是由字母表上的字符串組成的集合。語(yǔ)言：語(yǔ)言是用語(yǔ)法來(lái)描述的。語(yǔ)法實(shí)際上是一套有限的規(guī)則。這些正則表達(dá)式給出了語(yǔ)言中的各種語(yǔ)法元素以及它們?nèi)绾螛?gòu)成句子。為了定義正則表達(dá)式，需要引入一類新的符號(hào)，即語(yǔ)法符號(hào)。23.2語(yǔ)法和語(yǔ)言的正式定義。為了區(qū)分字母表上的符號(hào)和語(yǔ)法符號(hào)，我們分別稱它們?yōu)榻K止符和非終止符。終結(jié)符：一種語(yǔ)言字母表中的符號(hào)。讓我們把它寫(xiě)下來(lái)。

6、非終結(jié)符(一個(gè)過(guò)渡符號(hào)):它也是一個(gè)符號(hào)，但不是字母表中的一個(gè)符號(hào)。讓我們把它記為V。對(duì)于形式語(yǔ)言L，讓T和V是它的終止符集和非終止符集，顯然有L T*，和TV=，語(yǔ)法符號(hào)，定義23.1:一個(gè)產(chǎn)品是一個(gè)有序?qū)?，)，它通常可以寫(xiě)成下面的形式=或其中：V，V*，V=VT。生產(chǎn)的左邊部分稱為生產(chǎn)的右邊部分。注意：V是非終止符，也就是說(shuō)，產(chǎn)品的左邊部分不允許是空字符串。V*表示產(chǎn)品的右邊部分是這樣一個(gè)符號(hào)字符串，它可以包含終止符、非終止符和空字符串。語(yǔ)法的正式定義，定義23。語(yǔ)法G被定義為四重G=(V，t，p，s)，其中：1。v是一個(gè)非空的有限集，稱為非終集。2.t是一個(gè)非空的有限集，稱為終止集，V

7、T=1。3.p是一組非空的有限生產(chǎn)表達(dá)式。4.SV被稱為語(yǔ)法的開(kāi)始符號(hào)，s應(yīng)該作為至少一個(gè)生產(chǎn)中的左邊部分出現(xiàn)在P中，語(yǔ)法的形式定義，例23.6讓語(yǔ)法G=(A，E，A，P，A)，其中P=Aa，A aE，E aA。在許多語(yǔ)法中，有許多左部相同的生產(chǎn)形式，所以左部相同的生產(chǎn)形式可以寫(xiě)成組合生產(chǎn)形式。在這個(gè)示例方法g中，P中前兩個(gè)表達(dá)式的左邊部分是相同的，都是A，可以組合成A | A | aE，因此P=A a | aE，E=aA。在很多情況下，你只需要寫(xiě)出語(yǔ)法的產(chǎn)出來(lái)展示語(yǔ)法。慣例：第一個(gè)生成的左邊部分是語(yǔ)法的開(kāi)始，語(yǔ)法的正式定義，定義23.3:給定一個(gè)語(yǔ)法G=(V，T，P，S)，如果它是G中的一個(gè)

8、生成，并且是V*中的任何符號(hào)，如果有一個(gè)符號(hào)串X，y滿足：x=，y=，那么X使用該生成直接生成y。派生的形式定義，定義23.4:給定一個(gè)語(yǔ)法G=(V，T，P，S)，讓x，yV*，如果：1，有下面的直接派生序列：x=w0 w1 w2 wn=y(n0)，那么x被調(diào)用來(lái)派生(產(chǎn)生)y，并且派生長(zhǎng)度為n，或者y被簡(jiǎn)化為x. 2。我們用x，y來(lái)表示n0和x，n，y的存在。X*y表示x y或x=y.最左邊(右邊)的派生：如果在x中最左邊(右邊)的非終止符在派生的每一步都被生產(chǎn)所取代，那么這個(gè)派生稱為最左邊(右邊)的派生。最右邊的推導(dǎo)也稱為規(guī)范推導(dǎo)。定義23。5:給定一個(gè)語(yǔ)法G=(V，T，P，S)，如果符號(hào)

9、串x是從語(yǔ)法G的起始符號(hào)S，即S *x派生出來(lái)的，那么x稱為語(yǔ)法G的句型。如果符號(hào)串x是一個(gè)只由終止符組成的句型，即S*x和xT*，那么x是一個(gè)語(yǔ)法G的句子。從規(guī)范派生出來(lái)的句型稱為規(guī)范句型。標(biāo)準(zhǔn)句型，定義23。設(shè)GS是一個(gè)語(yǔ)法，x=w是一個(gè)句子類型，如果：S*A和A * w，那么W是相對(duì)于非終止符A的句型X的一個(gè)短語(yǔ)；如果：S*A和Aw，w是句型x相對(duì)于非終結(jié)符的直接短語(yǔ)(或簡(jiǎn)單短語(yǔ))；如果w是句型x的最左邊的直接短語(yǔ)，w被稱為句型x的句柄，短語(yǔ)，直接短語(yǔ)和句柄，定義23.7:給定語(yǔ)法G=(V，T，P，S)，由G生成的語(yǔ)言被表示為L(zhǎng)(G)，讓L(G)=x | S x和xT*，其中x被稱為語(yǔ)言

10、L(G)的句子。也就是說(shuō)，L(G)是一個(gè)由所有句子組成的集合，從語(yǔ)法G的起始符號(hào)S派生而來(lái)，語(yǔ)言的形式定義，例23.8給定語(yǔ)法GS:S aSb | ab由這個(gè)語(yǔ)法生成的任何句子是：首先用產(chǎn)生式S aSb幾次得到：S AsB AASB an-1S bn-1，即San-1sBN-1；然后，公式S ab被使用一次以獲得：S an-1S bn-1 anbn。用數(shù)學(xué)歸納法證明從這種語(yǔ)法中導(dǎo)出的所有符號(hào)串都是anbn形式并不難。另一方面，用數(shù)學(xué)歸納法證明符號(hào)串的長(zhǎng)度并不難。任何形式為anbn，n1的符號(hào)串都可以通過(guò)語(yǔ)法GS推導(dǎo)出來(lái)，也就是說(shuō)，有派生的ANBN。因此，L(GS)=anbn | n1。例23.

11、9設(shè)置語(yǔ)法gv: v AVB，Vb bW，abW c.找到由語(yǔ)法GV生成的語(yǔ)言。解答：V是語(yǔ)法的開(kāi)始。該公式被多次使用，推導(dǎo)結(jié)果為anVbn，n1。在anVbn中，為了消除非終止符v，必須使用生產(chǎn)公式VbbW，推導(dǎo)結(jié)果為：AnBbn-1=an-1 Bwbn-1，n1。只有利用生成公式abWc，才能剔除非終止子w，最終得到推導(dǎo)結(jié)果：an-1cbn-1，n1。另一方面，也不難證明任何形式為ancbn和n0的符號(hào)串都可以通過(guò)語(yǔ)法GV推導(dǎo)出來(lái)。因此，由語(yǔ)法GV生成的語(yǔ)言是L(GV)=an-1cbn-1 | n1=ancbn | n0。示例23.10語(yǔ)法ga: AAR、Aab、RAb生成語(yǔ)言L(GA)=

12、anbn | n1。從上面可以看出，盡管示例23.7中的語(yǔ)法GA和語(yǔ)法GS是兩種不同的語(yǔ)法，但是生成的語(yǔ)言是相同的，并且它們都是n | n | 1。定義1.8給定任意兩個(gè)文法G1和G2，如果它們產(chǎn)生相同的語(yǔ)言，即L(G1)=L(G2)，那么G1和G2的文法是等價(jià)的。語(yǔ)法樹(shù)是句型推導(dǎo)的圖形表示。例如，假設(shè)句子bd0的最右邊的派生或規(guī)范派生是：0 0 d0 d0 bd0，語(yǔ)法樹(shù)，定義1.9如果一個(gè)語(yǔ)法有兩個(gè)以上不同的語(yǔ)法樹(shù)對(duì)應(yīng)于一個(gè)句子，或者有兩個(gè)以上不同的最左邊(右邊)派生，那么這個(gè)語(yǔ)法就被認(rèn)為是不明確的(編程語(yǔ)言不能是不明確的)。定義1.10如果語(yǔ)言L的任何語(yǔ)法是二元語(yǔ)法，那么語(yǔ)言L就是二元語(yǔ)

13、言。理論上，已經(jīng)證明了這種模糊語(yǔ)言的存在。語(yǔ)法歧義和語(yǔ)言歧義是兩個(gè)不同的概念。1956年，喬姆斯基將語(yǔ)法分為四種類型：0型語(yǔ)法、1型語(yǔ)法、2型語(yǔ)法和3型語(yǔ)法。這種語(yǔ)法分類被稱為喬姆斯基分類。根據(jù)語(yǔ)法的四種類型，語(yǔ)法生成的語(yǔ)言也分為四種類型，即0型語(yǔ)言、1型語(yǔ)言、2型語(yǔ)言和3型語(yǔ)言。喬姆斯基建立的形式語(yǔ)言理論對(duì)計(jì)算機(jī)科學(xué)的發(fā)展產(chǎn)生了深遠(yuǎn)的影響，尤其是對(duì)計(jì)算機(jī)編程語(yǔ)言的設(shè)計(jì)、編譯方法和計(jì)算復(fù)雜性的影響。語(yǔ)法和語(yǔ)言類型，定義1.12讓語(yǔ)法G=(V，T，P，S)，如果P滿足| | | |(S除外)，那么語(yǔ)法G被稱為類型1語(yǔ)法或上下文相關(guān)語(yǔ)法，縮寫(xiě)為CSG。類型1語(yǔ)法的產(chǎn)生形式也被描述為：1A212，其

14、中：1，2，(VT)，反病毒。它能更好地反映“語(yǔ)境相關(guān)”的含義，因?yàn)橹挥蠥出現(xiàn)在1和2之間(1在A之上，2在A之下)，它被允許代替A。由類型1語(yǔ)法產(chǎn)生的語(yǔ)言被稱為類型1語(yǔ)言或語(yǔ)境相關(guān)語(yǔ)言(簡(jiǎn)稱CSL)。類型1語(yǔ)法，定義1.13讓語(yǔ)法G=(V，T，P，S)，如果對(duì)于P滿足V，(VT)*，那么G稱為類型2語(yǔ)法或上下文無(wú)關(guān)語(yǔ)法，縮寫(xiě)為CFG。上下文無(wú)關(guān)語(yǔ)法被命名為“上下文無(wú)關(guān)”的原因是字符總是可以被字符串自由替換，而不考慮字符出現(xiàn)的上下文。由類型2語(yǔ)法產(chǎn)生的語(yǔ)言被稱為類型2語(yǔ)言或上下文無(wú)關(guān)語(yǔ)言(簡(jiǎn)稱CFL)。上下文無(wú)關(guān)語(yǔ)法的一個(gè)簡(jiǎn)單例子是S-aSb |。由于這種語(yǔ)法的生成在左邊有一個(gè)非終結(jié)符S，在右

15、邊有一個(gè)由終結(jié)符或非終結(jié)符組成的符號(hào)串a(chǎn)Sb和，因此它滿足了上下文無(wú)關(guān)語(yǔ)法生成的要求。這種語(yǔ)法產(chǎn)生的語(yǔ)言是ann :n 0。類型2語(yǔ)法，定義1.14:讓語(yǔ)法G=(V，T，P，S)，如果P中的每個(gè)產(chǎn)品都是AaB或Aa，其中：a，BV，aT，那么G稱為類型3語(yǔ)法或普通語(yǔ)法，縮寫(xiě)為r G。由類型3語(yǔ)法產(chǎn)生的語(yǔ)言被稱為類型3語(yǔ)言或正常語(yǔ)言(縮寫(xiě)為RL)。類型3語(yǔ)言相當(dāng)于有限自動(dòng)機(jī)，也就是說(shuō)，有限自動(dòng)機(jī)可以識(shí)別類型3語(yǔ)言。在忽略句子的情況下，根據(jù)喬姆斯基的分類定義，任何類型3語(yǔ)言都是類型2語(yǔ)言，任何類型2語(yǔ)言都是類型1語(yǔ)言，任何類型1語(yǔ)言都是類型0語(yǔ)言。喬姆斯基層次的形式語(yǔ)言，范式是由較簡(jiǎn)單的范式按照一

16、套定義規(guī)則組成的，而每一個(gè)范式e代表一種語(yǔ)言L(e)(范式集)。定義1.15字母表上的正規(guī)表達(dá)式和正規(guī)集遞歸定義如下：1 .任何一個(gè)A都是字母表上的正規(guī)表達(dá)式，它所代表的正規(guī)集合是a2?？兆址巧系恼１磉_(dá)式，它所代表的正常集是。3.符號(hào)是上的正常表達(dá)式，它所代表的正常集是。23.3正常表達(dá)；4.設(shè)e1和e2都是上的正規(guī)表達(dá)式，它們所代表的正規(guī)集是L(e1)和L(e2)，那么(1)e1 e2也是正規(guī)表達(dá)式，它所代表的正規(guī)集是L(e1 e2)=L(e1)L(e2) (2)e1e2也是正規(guī)表達(dá)式。它所代表的正規(guī)集是L(e1e2)=L(e1)L(e2) (3)(e1)*，這也是一個(gè)正規(guī)表達(dá)式。它所

17、代表的正規(guī)集是L(e1)*)=(L(e1)*，示例23.14使=A，B。下表列出了上的一些正規(guī)表達(dá)式和相應(yīng)的正規(guī)表達(dá)式。下一個(gè)優(yōu)先級(jí)是“連接”運(yùn)算符，它類似于代數(shù)運(yùn)算中的乘法。最低優(yōu)先級(jí)是“與”操作(運(yùn)算符)。它類似于代數(shù)運(yùn)算中的加法。您可以通過(guò)在正則表達(dá)式中添加括號(hào)來(lái)更改操作的優(yōu)先級(jí)。正常表達(dá)式運(yùn)算符的優(yōu)先順序，一種正常語(yǔ)言可以由正常語(yǔ)法或正常形式來(lái)定義，而對(duì)于任何正常語(yǔ)法，都有一種正常形式來(lái)定義同一種語(yǔ)言；相反，對(duì)于每一種正常的形式，都有一種正常的語(yǔ)法產(chǎn)生相同的語(yǔ)言。正規(guī)表達(dá)式和正規(guī)語(yǔ)法可以相互轉(zhuǎn)換。23.4正常語(yǔ)法和正常表達(dá)，將正常表達(dá)r轉(zhuǎn)換為正常語(yǔ)法G=(V，t，s，p)的方法如下：1 .讓t=；