編譯原理-2-形式語(yǔ)言與自動(dòng)機(jī)-I

1、第二章 形式語(yǔ)言與自動(dòng)機(jī)Part I 形式語(yǔ)言2021-7-312Part I 形式語(yǔ)言 程序設(shè)計(jì)語(yǔ)言 形式語(yǔ)言 符號(hào)和符號(hào)串 文法 推導(dǎo)及語(yǔ)法樹(shù) 語(yǔ)言 語(yǔ)言文法 文法限制 文法和語(yǔ)言分類2021-7-313程序設(shè)計(jì)語(yǔ)言范型程序設(shè)計(jì)語(yǔ)言范型 命令式語(yǔ)言 函數(shù)式語(yǔ)言 基于規(guī)則的語(yǔ)言 面向?qū)ο蟮恼Z(yǔ)言LISP:Define (function1) (paras) (statements) (function2) (paras) (statements) (function3) (paras) (statements) (functionn) (paras) (statements)(function

2、i actual-paras)(functioni actual-paras)(functioni actual-paras)PROLOGHanoi(N):-move(N,left,centre,right)Move(0,-,-,-):-!Move(N,A,B,C):-M is N-1, move(M,A,C,B),move(M,C,B,A)?-hanoi(3)2021-7-314文法的直觀概念和語(yǔ)言概述文法的直觀概念和語(yǔ)言概述當(dāng)我們表述一種語(yǔ)言時(shí)，是希望說(shuō)明這種語(yǔ)言包含的句子：如果語(yǔ)言只含有有窮多個(gè)句子，則只需列出句子的有窮集就行了，但對(duì)于含有無(wú)窮句子的語(yǔ)言來(lái)講，存在著如何給出它的有窮表示的

3、問(wèn)題。以自然語(yǔ)言為例，人們無(wú)法列出全部句子，但是人們可以給出一些規(guī)則，用這些規(guī)則來(lái)說(shuō)明(或者定義)句子的組成結(jié)構(gòu)，比如漢語(yǔ)句子可以是由主語(yǔ)+謂語(yǔ)而成，構(gòu)成謂語(yǔ)的是動(dòng)詞和直接賓語(yǔ)，我們采用第2章所介紹的EBNF來(lái)表示這種句子的構(gòu)成規(guī)則： 2021-7-315“我是大學(xué)生我是大學(xué)生”。是漢語(yǔ)的一個(gè)句子。是漢語(yǔ)的一個(gè)句子句子 =主語(yǔ)謂語(yǔ)主語(yǔ) =代詞名詞代詞 =我你他名詞 =王明大學(xué)生工人英語(yǔ)謂語(yǔ) =動(dòng)詞直接賓語(yǔ)動(dòng)詞 =是學(xué)習(xí)直接賓語(yǔ) =代詞名詞 2021-7-316有了一組規(guī)則以后，按照如下方式用它們導(dǎo)出句子：開(kāi)始去找 =左端的帶有句子的規(guī)則并把它由 =右端的符號(hào)串代替，這個(gè)動(dòng)作表示成：句子 主語(yǔ)謂

4、語(yǔ)， 然后在得到的串主語(yǔ)謂語(yǔ)中，選取主語(yǔ)或謂語(yǔ)，再用相應(yīng)規(guī)則的 =右端代替之。比如，選取了主語(yǔ)，并采用規(guī)則主語(yǔ) =代詞， 那么得到：主語(yǔ)謂語(yǔ) 代詞謂語(yǔ)， 重復(fù)做下去， 句子：“我是大學(xué)生”的全部動(dòng)作過(guò)程是：句子 主語(yǔ)謂語(yǔ) 代詞謂語(yǔ) 我謂語(yǔ) 我動(dòng)詞直接賓語(yǔ) 我是直接賓語(yǔ) 我是名詞 我是大學(xué)生 2021-7-317“我是大學(xué)生”的構(gòu)成符合上述規(guī)則，而“我大學(xué)生是”不符合上述規(guī)則，我們說(shuō)它不是句子。這些規(guī)則成為我們判別句子結(jié)構(gòu)合法與否的依據(jù)，換句話說(shuō)，這些規(guī)則看成是一種元語(yǔ)言，用它描述漢語(yǔ)。這里僅僅涉及漢語(yǔ)句子的結(jié)構(gòu)描述。其中一種描述元語(yǔ)言稱為文法。英語(yǔ)句子英語(yǔ)句子sentence subject

5、This | Computers | Iverb-phrase | adverb neververb is | run | am | tellobject the | a | noun university | world | cheese | liesThis is a university.Computers run the world.I am the cheese.I never tell lies.英語(yǔ)句子英語(yǔ)句子sentence subject This | Computers | Iverb-phrase | adverb neververb is | run | am | te

6、llobject the | a | noun university | world | cheese | liesThis is a university.Computers run the world.I am the cheese.I never tell lies.語(yǔ)言概述語(yǔ)言概述語(yǔ)言是由句子組成的集合，是由一組符號(hào)所構(gòu)語(yǔ)言是由句子組成的集合，是由一組符號(hào)所構(gòu)成的集合。成的集合。漢語(yǔ)漢語(yǔ)-所有符合漢語(yǔ)語(yǔ)法的句子的全體所有符合漢語(yǔ)語(yǔ)法的句子的全體英語(yǔ)英語(yǔ)-所有符合英語(yǔ)語(yǔ)法的句子的全體所有符合英語(yǔ)語(yǔ)法的句子的全體程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言-所有該語(yǔ)言的程序的全體所有該語(yǔ)言的程序的全體 每個(gè)句

7、子構(gòu)成的規(guī)律每個(gè)句子構(gòu)成的規(guī)律研究語(yǔ)言研究語(yǔ)言 每個(gè)句子的含義每個(gè)句子的含義 每個(gè)句子和使用者的關(guān)系每個(gè)句子和使用者的關(guān)系研究程序設(shè)計(jì)語(yǔ)言研究程序設(shè)計(jì)語(yǔ)言 每個(gè)程序構(gòu)成的規(guī)律每個(gè)程序構(gòu)成的規(guī)律 每個(gè)程序的含義每個(gè)程序的含義 每個(gè)程序和使用者的關(guān)系每個(gè)程序和使用者的關(guān)系語(yǔ)言研究的三個(gè)方面語(yǔ)言研究的三個(gè)方面 語(yǔ)法語(yǔ)法 Syntax 語(yǔ)義語(yǔ)義 Semantics 語(yǔ)用語(yǔ)用 Pragmatics語(yǔ)法語(yǔ)法 - 表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律表示構(gòu)成語(yǔ)言句子的各個(gè)記號(hào)之間的組合規(guī)律語(yǔ)義語(yǔ)義 - 表示各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)表示各個(gè)記號(hào)的特定含義。（各個(gè)記號(hào)和記號(hào)所表示的對(duì)象之間的關(guān)系

8、）所表示的對(duì)象之間的關(guān)系）語(yǔ)用語(yǔ)用 -表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來(lái)源、表示在各個(gè)記號(hào)所出現(xiàn)的行為中，它們的來(lái)源、使用和影響。使用和影響。每種語(yǔ)言具有兩個(gè)可識(shí)別的特性，即語(yǔ)言的形式每種語(yǔ)言具有兩個(gè)可識(shí)別的特性，即語(yǔ)言的形式和該形式相關(guān)聯(lián)的意義。和該形式相關(guān)聯(lián)的意義。語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的，其相關(guān)聯(lián)的意語(yǔ)言的實(shí)例若在語(yǔ)法上是正確的，其相關(guān)聯(lián)的意義可以從兩個(gè)觀點(diǎn)來(lái)看，其一是該句子的創(chuàng)立義可以從兩個(gè)觀點(diǎn)來(lái)看，其一是該句子的創(chuàng)立者所想要表示的意義，另一是接收者所檢驗(yàn)到者所想要表示的意義，另一是接收者所檢驗(yàn)到的意義。這兩個(gè)意義并非總是一樣的，前者稱的意義。這兩個(gè)意義并非總是一樣的，前者稱為

9、語(yǔ)言的語(yǔ)義，后者是其語(yǔ)用意義。幽默、雙為語(yǔ)言的語(yǔ)義，后者是其語(yǔ)用意義。幽默、雙關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差異。關(guān)語(yǔ)和謎語(yǔ)就是利用這兩方面意義間的差異。 如果不考慮語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)如果不考慮語(yǔ)義和語(yǔ)用，即只從語(yǔ)法這一側(cè)面來(lái)看語(yǔ)言，這種意義下的語(yǔ)言稱作面來(lái)看語(yǔ)言，這種意義下的語(yǔ)言稱作形式語(yǔ)形式語(yǔ)言言。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)。形式語(yǔ)言抽象地定義為一個(gè)數(shù)學(xué)系統(tǒng)?！靶问叫问健笔侵高@樣的事實(shí)：語(yǔ)言的所有規(guī)則是指這樣的事實(shí)：語(yǔ)言的所有規(guī)則只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。形式只以什麼符號(hào)串能出現(xiàn)的方式來(lái)陳述。形式語(yǔ)言理論是對(duì)語(yǔ)言理論是對(duì)符號(hào)串集合符號(hào)串集合的表示法、結(jié)構(gòu)及的表示

10、法、結(jié)構(gòu)及其特性的研究，是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研其特性的研究，是程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析研究的基礎(chǔ)。究的基礎(chǔ)。2021-7-3115程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言 一個(gè)程序設(shè)計(jì)語(yǔ)言是一個(gè)記號(hào)系統(tǒng)，包括：語(yǔ)法、語(yǔ)義和語(yǔ)用。2021-7-3116 例如：賦值語(yǔ)句 x:=a+b*c2021-7-3117形式語(yǔ)言形式語(yǔ)言 形式化描述程序設(shè)計(jì)語(yǔ)言，包括其由哪些符號(hào)串構(gòu)成，它們的表示、結(jié)構(gòu)和特性。2021-7-3118符號(hào)和符號(hào)串符號(hào)和符號(hào)串 任何一種語(yǔ)言都是由該語(yǔ)言的基本符號(hào)組成的符號(hào)串集合。2021-7-3119符號(hào)和符號(hào)串符號(hào)和符號(hào)串一些基本概念一些基本概念字母表符號(hào)符號(hào)串（空符號(hào)串）符號(hào)串集合2021-7-

11、3120 符號(hào)符號(hào) 一個(gè)抽象實(shí)體,我們不再形式地定義它(就象幾何中的”點(diǎn)”一樣).例如字母是符號(hào),數(shù)字也是符號(hào)。 字母表字母表 字母表是元素的非空有窮集合，我們把字母表中的元素稱為符號(hào)，因此字母表也稱為符號(hào)集。 不同的語(yǔ)言可以有不同的字母表，例如漢語(yǔ)的字母表中包括漢字、數(shù)字及標(biāo)點(diǎn)符號(hào)等。PASCAL語(yǔ)言的字母表是由字母、數(shù)字、若干專用符號(hào)及BEGIN、IF之類的保留字組成。2021-7-3121符號(hào)串符號(hào)串 由字母表中的符號(hào)組成的任何有窮序列稱為符號(hào)串，例如00 11 10 是字母表 =0，1上的符號(hào)串. 字母表A=a,b,c上的一些符號(hào)串有：a,b,c,ab,aaca。 在符號(hào)串中，符號(hào)的順

12、序是很重要的，符號(hào)串a(chǎn)b就不同于ba,abca和aabc也不同。 可以使用字母表示符號(hào)串，如x=STR表示“x是由符號(hào)S、T和R，并按此順序組成的符號(hào)串”。符號(hào)串的長(zhǎng)度符號(hào)串的長(zhǎng)度 如果某符號(hào)串x中有m個(gè)符號(hào)，則稱其長(zhǎng)度為m，表示為x=m，如001110的長(zhǎng)度是6。空符號(hào)串空符號(hào)串，即不包含任何符號(hào)的符號(hào)串，用表示，其長(zhǎng)度為0，即=0。2021-7-3122符號(hào)串的頭符號(hào)串的頭, ,尾，固有頭和固有尾尾，固有頭和固有尾：如果z=xy是一符號(hào)串，那么x是z的頭，y是z的尾，如果x是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。舉個(gè)例子:設(shè)z=abc,那么z的頭是,a,ab,abc,除a

13、bc外，其它都是固有頭；z的尾是,c,bc,abc,z的固有尾是,c,bc。 當(dāng)對(duì)符號(hào)串z=xy的頭感興趣而對(duì)其余部分不感興趣時(shí)，采用省略寫(xiě)法：z=x； 如果只是為了強(qiáng)調(diào)x在符號(hào)串z中的某處出現(xiàn)，則可表示為：z=x；符號(hào)t是符號(hào)串z的第一個(gè)符號(hào)，則表示為z=t。2021-7-3123符號(hào)串的連接符號(hào)串的連接：設(shè)x和y是符號(hào)串，它們的連接xy是把y的符號(hào)寫(xiě)在x的符號(hào)之后得到的符號(hào)串. 由于 的含義，顯然有 x=x =x。例如 x=ST，y=abu，則它們的連接xy=STabu，看出x=2，y=3，xy=5符號(hào)串的符號(hào)串的方冪方冪：符號(hào)串自身連接n次得到的符號(hào)串 an 定義為 aaaa n個(gè)a a

14、1=a, a2=aa且a0=例；若x=AB 則: x0 = x1 =AB x2 = ABAB x3 = ABABAB xn = xxn-1 = xn-1 x (n0)2021-7-3124符號(hào)串集合符號(hào)串集合：若集合A中所有元素都是某字母表上的符號(hào)串，則稱A為字母表上的符號(hào)串集合。 兩個(gè)符號(hào)串集合兩個(gè)符號(hào)串集合A A和和B B的乘積的乘積 定義為 AB =xy|xA且yB 若 集合A=ab,cde 集合B = 0,1 則 AB =ab1,ab0,cde0,cde1 使用 * 表示上的一切符號(hào)串（包括）組成的集合。 * *稱為稱為的閉包的閉包。 上的除外的所有符號(hào)串組成的集合記為+ 。 + +稱

15、為稱為的正閉包的正閉包。2021-7-3125文法文法 符號(hào)符號(hào)串句子語(yǔ)言 并非所有符號(hào)串都能形成句子2021-7-3126如何描述一種語(yǔ)言？如何描述一種語(yǔ)言？如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以如果語(yǔ)言是有窮的（只含有有窮多個(gè)句子），可以將句子逐一列出來(lái)表示將句子逐一列出來(lái)表示如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。語(yǔ)言的如果語(yǔ)言是無(wú)窮的，找出語(yǔ)言的有窮表示。語(yǔ)言的有窮表示有兩個(gè)途經(jīng)：有窮表示有兩個(gè)途經(jīng)： 生成方式生成方式 （文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)（文法）：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。格定義的規(guī)則來(lái)構(gòu)造。 識(shí)別方式識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一任（

16、自動(dòng)機(jī)）：用一個(gè)過(guò)程，當(dāng)輸入的一任意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止意串屬于語(yǔ)言時(shí)，該過(guò)程經(jīng)有限次計(jì)算后就會(huì)停止并回答并回答“是是”，若不屬于，要麼能停止，若不屬于，要麼能停止并回答并回答“不不是是”，（要麼永遠(yuǎn)繼續(xù)下去。），（要麼永遠(yuǎn)繼續(xù)下去。） 2021-7-3127 文法即是文法即是生成方式生成方式描述語(yǔ)言的：語(yǔ)言中描述語(yǔ)言的：語(yǔ)言中的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)的每個(gè)句子可以用嚴(yán)格定義的規(guī)則來(lái)構(gòu)造。下面給出造。下面給出文法文法的定義，進(jìn)而在該定的定義，進(jìn)而在該定義的基礎(chǔ)上，給出義的基礎(chǔ)上，給出推導(dǎo)推導(dǎo)的概念，的概念，句型句型、句子句子和和語(yǔ)言語(yǔ)言的定義的定義.2021-7

17、-3128文法文法 文法是對(duì)語(yǔ)言結(jié)構(gòu)的形式化定義和描述。 文法由產(chǎn)生式（規(guī)則）構(gòu)成。 產(chǎn)生式（規(guī)則） ：U:=x 或U x 開(kāi)始符號(hào)，字匯表/字母表，終結(jié)符號(hào)，非終結(jié)符2021-7-3129回顧回顧 EBNFEBNF 引入的符號(hào)引入的符號(hào)( (元符號(hào)元符號(hào)) )： 用左右尖括號(hào)括起來(lái)的語(yǔ)法成分為用左右尖括號(hào)括起來(lái)的語(yǔ)法成分為非終結(jié)符非終結(jié)符= () = () 定義為定義為 =() =() 的左部由右部定義的左部由右部定義 | | 或或 表示花括號(hào)內(nèi)的語(yǔ)法成分可重復(fù)任意次或限定表示花括號(hào)內(nèi)的語(yǔ)法成分可重復(fù)任意次或限定次數(shù)次數(shù) 表示方括號(hào)內(nèi)的語(yǔ)法成分為任選項(xiàng)表示方括號(hào)內(nèi)的語(yǔ)法成分為任選項(xiàng)( ) (

18、 ) 表示圓括號(hào)內(nèi)的成分優(yōu)先表示圓括號(hào)內(nèi)的成分優(yōu)先2021-7-3130例：用例：用EBNFEBNF描述描述 的定義的定義 ： =+|-=+|- =0|1|2|3|4|5|6|7|8|9=0|1|2|3|4|5|6|7|8|9 或更好的寫(xiě)法或更好的寫(xiě)法 =+|-=+|-|0|0 =1|2|3|4|5|6|7|8|9 =1|2|3|4|5|6|7|8|9 =0|=0| 2021-7-3131文法G定義為四元組(VN，VT，P，S )其中VN為非終結(jié)符號(hào)(或語(yǔ)法實(shí)體，或變量)集；VT為終結(jié)符號(hào)集；P為產(chǎn)生式(也稱規(guī)則)的集合； VN，VT和P是非空有窮集。 S稱作開(kāi)始符號(hào)或識(shí)別符號(hào)，它是一個(gè)非終結(jié)

19、符，至少要在一條產(chǎn)生式中作為左部出現(xiàn)。 VN和VT不含共有的元素，即VN VT = 用V表示VN VT ，稱為文法G的字母表或字匯表規(guī)則規(guī)則，也稱重寫(xiě)規(guī)則重寫(xiě)規(guī)則、產(chǎn)生式產(chǎn)生式或生成式生成式，是形如或 =的(，)有序?qū)?，其中是字母表V的正閉包V+中的一個(gè)符號(hào)，是V*中的一個(gè)符號(hào)。稱為規(guī)則的左部，稱作規(guī)則的右部。2021-7-3132文法文法 例：GE: E :=E+TT :=FT :=T*FF :=(E)F :=iVN =? VT =? V=?2021-7-3133 VN = E,T,F VT =+,(,),*,i V=E,T,F,+,(,),*,i2021-7-3134Define a gr

20、ammarA A grammar G grammar G is defined as a 4-tuple is defined as a 4-tuple (VN，VT，P，S ) VN is a set of nonterminals VT is a set of terminals P is a set of productions，each production consists of a left side,an arrow(or :=),and a right side S is a designation of one of the nonterminals as the start

21、 symbolV =VN VT is the alphabet of G2021-7-3135文法的定義文法的定義例例 文法文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S為開(kāi)始符號(hào)為開(kāi)始符號(hào)2021-7-3136例例 文法文法G=（VN，VT，P，S）VN =標(biāo)識(shí)符，字母，數(shù)字標(biāo)識(shí)符，字母，數(shù)字VT =a,b,c,x,y,z,0,1,9P= a, z z 0,0, , 99 S=2021-7-3137文法的寫(xiě)法文法的寫(xiě)法1 1 G G：SaASaAb AabAab AaAAaAb A A2 GS2 GS： AabAab AaAAaAb A A

22、 SaASaAb 3 GSGS： AabAab | |aAaAb | | SaASaAb2021-7-3138元元符號(hào): = = | | 習(xí)慣表示習(xí)慣表示 大寫(xiě)字母：非終結(jié)符大寫(xiě)字母：非終結(jié)符 小寫(xiě)字母：終結(jié)符小寫(xiě)字母：終結(jié)符S ABA Ax | yB z2021-7-3139 遞歸 遞歸規(guī)則，遞歸文法 左遞歸，右遞歸，直接遞歸，間接遞歸2021-7-3140推導(dǎo)的定義推導(dǎo)的定義直接推導(dǎo)直接推導(dǎo)“”是文法是文法G G的產(chǎn)生式，若有的產(chǎn)生式，若有v,wv,w滿足：滿足：v=,w= , v=,w= , 其中其中VV* *,V,V* * 則稱則稱v v直接直接推導(dǎo)推導(dǎo)到到w,w,記作記作 v v w

23、 w 也稱也稱w w直接直接歸約歸約到到v v例：例：G G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S12021-7-3141. . . VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END.2021-7-3142推導(dǎo)的定義推導(dǎo)的定義 若存在若存在v =w0 w1 . wn=w,(n0) 則記為則記為v =+ w，v推導(dǎo)出推導(dǎo)出w，或或w歸約到歸約到v 若有若有v =+ w，或或v=w， 則記為則記為v =* w2021-7-3143例：例：G G： S0S1， S010S1 00S11

24、00S11 000S111000S111 00001111 S 0S1 00S11 000S111 00001111 S =+ 00001111 S =* S 00S11 =* 00S112021-7-3144What are DerivationsDerivation is a way that a grammar defines a language .In the process of derivation a production is treated as a rewriting rule in which the nonterminal on the left side is re

25、placed by the string on the right side of the productionA production u v is used by replacing an occurrence of u by v . Formally, if we apply a production p P to a string of symbols w in V to yield a new string of symbols z in V, we say that z derived from w using p, written as follows: w =p z . We

26、also use:w = z z derives from w (production unspecified)w =* z z derives from w using zero or more productionsw =+ z z derives from w using one or more productions2021-7-3145 最左推導(dǎo)：xUy=xuy, x Vt* 最右推導(dǎo)：xUy=xuy, y Vt* 規(guī)范推導(dǎo) 規(guī)范規(guī)約2021-7-3146 例：GE: E:=E+TE:= TT :=FT :=T*FF :=(E)F :=a a*（a+a）的推導(dǎo):2021-7-3147

27、句型、句子的定義句型、句子的定義句型句型有文法有文法G，若若S =* x，則稱則稱x是文法是文法G的句型。的句型。句子句子有文法有文法G，若若S =* x，且且xVVT T* *，則稱則稱x是文法是文法G的句子。的句子。例：例：G G： S0S1， S01S 0S1 00S11 000S111 00001111G的句型S, 0S1, 00S11,000S111, 00001111G的句子00001111, 012021-7-3148例：例：GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE E.a+a*a句子：用符號(hào)句子：用符號(hào)a，+，*，( 和和

28、 ) 構(gòu)成的算術(shù)表達(dá)式構(gòu)成的算術(shù)表達(dá)式2021-7-3149 E EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a E EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a2021-7-3150語(yǔ)言的定義語(yǔ)言的定義 由文法由文法G生成的語(yǔ)言記為生成的語(yǔ)言記為L(zhǎng)(G),它是文法它是文法G的一切句子的集合的一切句子的集合: L(G)=x|S =* x，其中其中S為文法的開(kāi)始符為文法的開(kāi)始符號(hào)，且號(hào)，且x VVT T* * 例：例：G G

29、： S0S1， S01 L(G)=0n1n|n12021-7-3151例例 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEee L（G）= anbnen | n1 2021-7-3152S a S BE (SaSBE) a aBEBE (SaBE) aabEBE ( aBab ) aabBEE ( EBBE ) aabbEE （bBbb) aabbeE （bEbe) aabbee （eEee)G生成的每個(gè)串都在生成的每個(gè)串都在L(G)中中L(G)中的每個(gè)串確實(shí)能被中的每個(gè)串確實(shí)能被G生成生成使用產(chǎn)生式(1)n-1次，得到推導(dǎo)序列：

30、S =* an-1S(BE)n-1，然后使用產(chǎn)生式(2)一次，得到：S =* an-1S(BE)n-1 an(BE)n。然后從an(BE)n繼續(xù)推導(dǎo)，總是對(duì)EB使用產(chǎn)生式(3)的右部進(jìn)行替換，而最終在得到的串中，所有的B都先于所有的E。例如，若n=3, aaaBEBEBE aaaBBEEBE aaaBBEBEE aaaBBBEEE。即有：S =* anBnEn接著，使用產(chǎn)生式(4)一次，得到S =* anbBn-1En，然后使用產(chǎn)生式(5)n-1次得到：S =* anbnEn，最后使用產(chǎn)生式(6)一次，使用產(chǎn)生式(7)n-1次，得到：S =* anbnen 也能證明， 對(duì)于n1，串a(chǎn)nbnen

31、是唯一形式的終結(jié)符號(hào)串 文法的等價(jià)文法的等價(jià)若若L(G1)=L(G2), 則稱文法則稱文法G1和和G2是等價(jià)的。是等價(jià)的。如文法如文法G G1AA：A0R A0R 與與G G2SS：S0S1 S0S1 等價(jià)等價(jià) A01 S01A01 S01 RA1 RA12021-7-3155語(yǔ)法樹(shù)文法GZ的語(yǔ)法樹(shù)： 每個(gè)結(jié)點(diǎn)都是G的符號(hào) 樹(shù)根是文法的開(kāi)始符號(hào) 若某個(gè)結(jié)點(diǎn)至少有一個(gè)從它出來(lái)的分支，則該結(jié)點(diǎn)一定是非終結(jié)符 若某個(gè)結(jié)點(diǎn)A有n個(gè)分支，假設(shè)其分支結(jié)點(diǎn)為B1,B2,Bn，則 A:=B1B2B3Bn 一定是文法的一條規(guī)則。2021-7-3156語(yǔ)法樹(shù) 語(yǔ)法樹(shù)可以從推導(dǎo)過(guò)程產(chǎn)生。 凡使用一條規(guī)則推導(dǎo)，則可以

32、從規(guī)則左部符號(hào)結(jié)點(diǎn)長(zhǎng)出若干分支。2021-7-3157構(gòu)造語(yǔ)法樹(shù)構(gòu)造語(yǔ)法樹(shù)GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a2021-7-3158E EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aE EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a E E E + T E + T T T T T *

33、* F F F F a F F a a a a a 看不出句型中的符號(hào)被替代的看不出句型中的符號(hào)被替代的順序順序句型的分析句型的分析句型分析句型分析就是就是識(shí)別識(shí)別一個(gè)符號(hào)串是否為某文法一個(gè)符號(hào)串是否為某文法的的句型句型，是某個(gè)，是某個(gè)推導(dǎo)推導(dǎo)的構(gòu)造過(guò)程。的構(gòu)造過(guò)程。在語(yǔ)言的編譯實(shí)現(xiàn)中，把在語(yǔ)言的編譯實(shí)現(xiàn)中，把完成句型分析完成句型分析的的程程序序稱為稱為分析程序分析程序或或識(shí)別程序識(shí)別程序。分析算法又。分析算法又稱稱識(shí)別算法識(shí)別算法。從左到右的分析算法從左到右的分析算法，即，即總是從總是從左左到到右右地地識(shí)識(shí)別輸入符號(hào)串別輸入符號(hào)串，首先識(shí)別符號(hào)串中的，首先識(shí)別符號(hào)串中的最左最左符號(hào)，進(jìn)而符號(hào)

34、，進(jìn)而依次識(shí)別右邊依次識(shí)別右邊的一個(gè)符號(hào)，的一個(gè)符號(hào)，直直到分析結(jié)束到分析結(jié)束。句型的分析算法分類句型的分析算法分類分析算法可分為：分析算法可分為：自上而下分析法自上而下分析法：從文法的開(kāi)始符號(hào)出發(fā)從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用文法的，反復(fù)使用文法的產(chǎn)生式，產(chǎn)生式，尋找尋找與與輸入符號(hào)串輸入符號(hào)串匹配匹配的的推導(dǎo)推導(dǎo)。自下而上分析法自下而上分析法：從從輸入符號(hào)串輸入符號(hào)串開(kāi)始開(kāi)始，逐步進(jìn)行逐步進(jìn)行歸約歸約，直至，直至歸約歸約到到文法的文法的開(kāi)始符號(hào)開(kāi)始符號(hào)。 兩種方法反映了兩種語(yǔ)法樹(shù)的構(gòu)造過(guò)程。兩種方法反映了兩種語(yǔ)法樹(shù)的構(gòu)造過(guò)程。自上而下方法自上而下方法是從文法符號(hào)開(kāi)始，將它做為語(yǔ)法樹(shù)的根，向

35、下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的結(jié)果正好是輸入符號(hào)串自下而上方法自下而上方法則是從輸入符號(hào)串開(kāi)始，以它做為語(yǔ)法樹(shù)的結(jié)果，自底向上地構(gòu)造語(yǔ)法樹(shù)自上而下的語(yǔ)法分析自上而下的語(yǔ)法分析例：文法例：文法G：S cAd A ab A a識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的是否為該文法的句子句子SSScAdcAd a b推導(dǎo)過(guò)程：推導(dǎo)過(guò)程：S cAd cAd cabd自下而上的語(yǔ)法分析自下而上的語(yǔ)法分析例：文法例：文法G： S cAd A ab A a識(shí)別輸入串識(shí)別輸入串w=cabd是否該文法的是否該文法的句子句子SAA c a b d c a b d c a b d 規(guī)約規(guī)約過(guò)程構(gòu)造的推導(dǎo)：過(guò)程構(gòu)造

36、的推導(dǎo)： cAd cabd S cAd(1)S cAd (2) A ab (3)A a識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的是否為該文法的句子句子自上而下的語(yǔ)法分析自上而下的語(yǔ)法分析若S cAd 后選擇(3)擴(kuò)展A，S cAd cad那將會(huì)？ w的第二個(gè)符號(hào)可以與葉子結(jié)點(diǎn)a得以匹配，但第三個(gè)符號(hào)卻不能與下一葉子結(jié)點(diǎn)d匹配？宣告分析失敗（其意味著，識(shí)別程序不能為串cad構(gòu)造語(yǔ)法樹(shù)，即cad不是句子）-顯然是錯(cuò)誤的結(jié)論。導(dǎo)致失敗的原因是在分析中對(duì)A的選擇不是正確的。 S c A d a(1)S cAd (2) A ab (3)A a識(shí)別輸入串識(shí)別輸入串w=cabd是否為該文法的是否為該文法

37、的句子句子自下而上的語(yǔ)法分析自下而上的語(yǔ)法分析對(duì)串cabd的分析中，如果不是選擇ab用產(chǎn)生式(2),而是選擇a用產(chǎn)生式(3)將a歸約到了A，那么最終就達(dá)不到歸約到S的結(jié)果，因而也無(wú)從知道cabd是一個(gè)句子c a b d c A b d a句型分析的有關(guān)問(wèn)題句型分析的有關(guān)問(wèn)題1）在自上而下的分析方法中）在自上而下的分析方法中如何如何選擇選擇使用使用哪個(gè)哪個(gè)產(chǎn)產(chǎn)生式進(jìn)行推導(dǎo)生式進(jìn)行推導(dǎo)？假定要被代換的最左非終結(jié)符號(hào)是假定要被代換的最左非終結(jié)符號(hào)是B，且有且有n條條規(guī)則：規(guī)則：BA1|A2|An，那么如何確定用哪個(gè)右那么如何確定用哪個(gè)右部去替代部去替代B？2）在自下而上的分析方法中在自下而上的分析方

38、法中如何如何識(shí)別可歸約的串識(shí)別可歸約的串？在分析程序工作的每一步，都是從當(dāng)前串中在分析程序工作的每一步，都是從當(dāng)前串中選擇選擇一個(gè)一個(gè)子串子串，將它，將它歸約歸約到到某個(gè)非終結(jié)符號(hào)某個(gè)非終結(jié)符號(hào)，該子串，該子串稱為稱為“可歸約串可歸約串”刻畫(huà)刻畫(huà)“可歸約串可歸約串”文法文法GS句型的短語(yǔ)句型的短語(yǔ)S =* A且且 A =+ ，則稱則稱是是句型句型相對(duì)于非終結(jié)符相對(duì)于非終結(jié)符A的的短語(yǔ)短語(yǔ)句型的直接短語(yǔ)句型的直接短語(yǔ)若有若有A ，則稱則稱是句型是句型相對(duì)于非終結(jié)相對(duì)于非終結(jié)符符A 的的直接短語(yǔ)直接短語(yǔ)句型的句柄句型的句柄一個(gè)句型的一個(gè)句型的最左直接短語(yǔ)最左直接短語(yǔ)稱為稱為該句型該句型的的句柄句柄

39、2021-7-3168 短語(yǔ)是句型中某非終結(jié)符號(hào)通過(guò)若干步推導(dǎo)出的子串。 如果每次都從當(dāng)前句型的句柄進(jìn)行歸約，則可以歸約到文法的開(kāi)始符號(hào)。例例 ：a a* *a+aa+a 的短語(yǔ)、直接短語(yǔ)和句柄的短語(yǔ)、直接短語(yǔ)和句柄 E E + T T FT * F a3 短語(yǔ)短語(yǔ)：a1* * a2+ + a3， a1* * a2 ，F(xiàn) a2 a1 ， a2 ， a3 。 a1 直接短語(yǔ)直接短語(yǔ)： a1 ， a2 ， a3 。 句柄句柄： a1 GEGE：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|aF(E)|a句型：句型：a a* *a+aa+a2021-7-3170 從語(yǔ)法樹(shù)判斷句型

40、的短語(yǔ)，簡(jiǎn)單短語(yǔ)，句柄很簡(jiǎn)單。 子樹(shù) 簡(jiǎn)單子樹(shù) 短語(yǔ) 簡(jiǎn)單短語(yǔ) 句柄2021-7-3171 如果語(yǔ)法樹(shù)已經(jīng)生成，則可以從語(yǔ)法樹(shù) 自下而上歸約 句柄2021-7-3172 根據(jù)語(yǔ)法樹(shù)，可以發(fā)現(xiàn)文法的二義性。 文法二義性：兩棵語(yǔ)法樹(shù)對(duì)應(yīng)同一句子2021-7-3173二義文法二義文法 若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法若一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是樹(shù)，則稱這個(gè)文法是二義二義的的或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的或者，若一個(gè)文法存在某個(gè)句子有兩個(gè)不同的最左（右）推導(dǎo)，則稱這個(gè)文法是最左（右）推導(dǎo)，則稱這個(gè)文法是二義二義的的 判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，

41、判定任給的一個(gè)上下文無(wú)關(guān)文法是否二義，或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)或它是否產(chǎn)生一個(gè)先天二義的上下文無(wú)關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，關(guān)語(yǔ)言，這兩個(gè)問(wèn)題是遞歸不可解的，但可以為無(wú)二義性尋找一組充分條件但可以為無(wú)二義性尋找一組充分條件 2021-7-3174文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。因?yàn)榭赡苡袃蓚€(gè)不同的文法的文法G G和和GG，其中其中G G是二義的，但是卻有是二義的，但是卻有L(G)=L(G)L(G)=L(G)，也就是說(shuō)，也就是說(shuō)，這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。這兩個(gè)文法所產(chǎn)生的語(yǔ)言是相同的。二義文法改造為

42、無(wú)二義文法二義文法改造為無(wú)二義文法GE: E i GEGE: E i GE：E T|E+TE T|E+T E E+E T F|T E E+E T F|T* *F F E E E E* *E F E F （E E）|i|i E (E) E (E) 規(guī)定優(yōu)先順序和結(jié)合律規(guī)定優(yōu)先順序和結(jié)合律 如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先如果產(chǎn)生上下文無(wú)關(guān)語(yǔ)言的每一個(gè)文法都是二義的，則說(shuō)此語(yǔ)言是先天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義天二義的。對(duì)于一個(gè)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分析是唯一的。的，因?yàn)橄Ｍ麑?duì)它的每個(gè)語(yǔ)句的分

43、析是唯一的。2021-7-3175文法和語(yǔ)言文法和語(yǔ)言 文法語(yǔ)言 語(yǔ)言文法文法的類型文法的類型通過(guò)對(duì)產(chǎn)生式施加不同的限制，通過(guò)對(duì)產(chǎn)生式施加不同的限制，Chomsky將文將文法分為四種類型：法分為四種類型：0型文法：對(duì)任一產(chǎn)生式型文法：對(duì)任一產(chǎn)生式，都有都有(V(VN NVVT T) )+ +， (V (VN NVVT T) )* *1 1型文法：型文法：對(duì)任一產(chǎn)生式對(duì)任一產(chǎn)生式，都有都有| |， 僅僅僅僅 SS除外除外2 2型文法：型文法：對(duì)任一產(chǎn)生式對(duì)任一產(chǎn)生式，都有都有VVN N， (V(VN NVVT T) )* *3 3型文法：型文法：任一產(chǎn)生式任一產(chǎn)生式的形式都為的形式都為AaBAaB或或AaAa，其中其中AVAVN N，BVBVN N，aVaVT TA hierarchy of gram