編譯原理第三章：文法和語(yǔ)言

1、北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系趙瑞蓮2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系2 2 22021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系2 2 2 P begin VDL;SL end. VDL VD | VD ; VDL VD var id : T SL S | S ; SL S id:= E | write(E) | read(

2、id) T int | real E id | num | E + E | E * E |(E) 2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系3 3 32021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系3 3 3Micro的詞法分析的詞法分析2.2 Micro2.2 Micro語(yǔ)言的詞法分析語(yǔ)言的詞法分析任務(wù)任務(wù) 2021-10-162021-

3、10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系4 4 4讀當(dāng)前字符流，直至文件結(jié)束。讀當(dāng)前字符流，直至文件結(jié)束。如果是：如果是： (1)(1)標(biāo)識(shí)符標(biāo)識(shí)符時(shí)判斷是保留字時(shí)判斷是保留字還是變量標(biāo)識(shí)符，構(gòu)造還是變量標(biāo)識(shí)符，構(gòu)造TokenToken表示；表示； (2)(2)數(shù)字?jǐn)?shù)字時(shí)判斷是整型還是時(shí)判斷是整型還是實(shí)型，構(gòu)造實(shí)型，構(gòu)造TokenToken表示；表示； (3)(3)構(gòu)造其它合法的符號(hào)的構(gòu)造其它合法的符號(hào)的TokenToken表示；表示； (4)(4)遇到非法符號(hào)則報(bào)錯(cuò)。遇到非法符號(hào)則報(bào)錯(cuò)。2

4、021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系4 4 4 end2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系5 5 52021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系5 5 5說(shuō)明：說(shuō)明：語(yǔ)法分析只用到單詞的語(yǔ)法分析只

5、用到單詞的Token表示，表示， 并不改變單詞的并不改變單詞的Token表示表示。2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系6 6 62021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系6 6 6Procedure Parser(); begin Match($begin,1); Match($var,2); LD: Match($id,3);

6、 Match($colon,4); Match($intC/$reaC,5); Match($semi,6); ReadToken(token); if token=$line then ReadToken(token); if token=$var then goto LD; LS: case token of ($write,-）Match($Lparen,7); Expr(); Match($Rparen,8); ($read,-) Match($Lparen,9); Match($id,10); Match($Rparen,11); ($id,-) Match($assig,12);

7、Expr(); other error(13) end; ReadToken(token);2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系7 7 72021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系7 7 7語(yǔ)義分析過(guò)程語(yǔ)義分析過(guò)程 讀入讀入Token 遇到遇到標(biāo)識(shí)符聲明標(biāo)識(shí)符聲明時(shí)，檢查是否已聲明，是則報(bào)錯(cuò)，時(shí)，檢查是否已聲明，是則報(bào)錯(cuò)， 否則

8、構(gòu)造標(biāo)識(shí)符的符號(hào)表；否則構(gòu)造標(biāo)識(shí)符的符號(hào)表； 遇到遇到標(biāo)識(shí)符定義和使用標(biāo)識(shí)符定義和使用時(shí)，檢查是否聲明過(guò)。時(shí)，檢查是否聲明過(guò)。 將變量的將變量的Token改為（改為（$id,entry)形式。形式。2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系8 8 82021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系8 8 82021-10-162021-10

9、-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系9 9 92021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系9 9 92021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1010102021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)

10、與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1111112021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1111112021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1212122021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技

11、術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系121212SemanStack(top):SemanStack的頂?shù)捻斣卦乇磉_(dá)式代碼表達(dá)式代碼生成程序生成程序id := E2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1313132021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1414142021-10-162021-10-16202

12、1-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系141414*c*d #a+b余下表達(dá)式余下表達(dá)式信息棧信息棧a+b*c*d2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1515152021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1515152021-10-1620

13、21-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系161616(a+b)*c*d2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系1717172021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系181818191919編譯器各階段工作的歸納 詞法分析：識(shí)

14、別單詞，至少分以下幾大類：關(guān)鍵字（保留字）、標(biāo)識(shí)符、數(shù)值量、特殊符號(hào)； 語(yǔ)法分析：得到語(yǔ)言結(jié)構(gòu)（以樹(shù)的形式表示）； 語(yǔ)義分析：考察結(jié)構(gòu)正確的句子是否語(yǔ)義合法； 中間代碼生成（可選）：生成一種既接近目標(biāo)語(yǔ)言，又與具體機(jī)器無(wú)關(guān)的表示，便于優(yōu)化與代碼生成； 中間代碼優(yōu)化（可選）：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實(shí)際上是一個(gè)等價(jià)變換，變換前后的指令序列完成同樣的功能，但是，在占用的空間上和程序執(zhí)行的時(shí)間上都更省、更有效。 目標(biāo)代碼生成：不同形式的目標(biāo)代碼匯編、可重定位; 符號(hào)表管理：合理組織符號(hào)，便于各階段查找、填寫(xiě)等； 出錯(cuò)處理：錯(cuò)誤的種類詞法錯(cuò)、語(yǔ)法錯(cuò)、靜態(tài)語(yǔ)義錯(cuò)、動(dòng)態(tài)語(yǔ)義錯(cuò)。2021-10-

15、162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系2020202021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系202020 P begin VDL;SL end. VDL VD | VD ; VDL VD var id : T SL S | S ; SL S id:= E | write(E) | read(id) T int | real E id | num

16、| E + E | E * E |(E) 2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系212121第第3 3章章 文法和語(yǔ)言的概念和表示文法和語(yǔ)言的概念和表示3.1 3.1 預(yù)備知識(shí)預(yù)備知識(shí) - - 形式語(yǔ)言基礎(chǔ)形式語(yǔ)言基礎(chǔ)3.2 3.2 文法的非形式定義文法的非形式定義3.3 3.3 文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義3.4 3.4 語(yǔ)法樹(shù)與二義性文法語(yǔ)法樹(shù)與二義性文法3.5 3.5 句子的分析句子的分析3.6 3.6 有關(guān)文法的實(shí)用限制有關(guān)文法的實(shí)用限制3

17、.7 3.7 文法的其它表示法文法的其它表示法3.8 3.8 文法和語(yǔ)言分類文法和語(yǔ)言分類2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系2222223.1 3.1 預(yù)備知識(shí)預(yù)備知識(shí)一、字母表和符號(hào)串一、字母表和符號(hào)串 字母表：字母表：符號(hào)的非空有限集符號(hào)的非空有限集 例：例： = =aa，b b，cc 符號(hào)：符號(hào)： 字母表中的元素字母表中的元素 例：例： a a，b b，c c 符號(hào)串：符號(hào)串：符號(hào)的有窮序列符號(hào)的有窮序列 例：例：a,aa,c,abca,aa,c,a

18、bc，. 空符號(hào)串：空符號(hào)串：無(wú)任何符號(hào)的符號(hào)串無(wú)任何符號(hào)的符號(hào)串( () 符號(hào)串集合：符號(hào)串集合：由符號(hào)串構(gòu)成的集合。由符號(hào)串構(gòu)成的集合。符號(hào)串的形式定義符號(hào)串的形式定義 有字母表有字母表 ，定義：，定義： （1）是是 上的符號(hào)串；上的符號(hào)串； （2）若）若x是是 上的符號(hào)串，且上的符號(hào)串，且a ，則，則ax或或xa是是 上的符號(hào)串；上的符號(hào)串； （3）y是是 上的符號(hào)串，上的符號(hào)串，iff（當(dāng)且僅當(dāng)）（當(dāng)且僅當(dāng)）y可由（可由（1）和（）和（2）產(chǎn)生。）產(chǎn)生。 2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算

19、機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系232323二、符號(hào)串和符號(hào)串集合的運(yùn)算二、符號(hào)串和符號(hào)串集合的運(yùn)算 1.符號(hào)串相等：符號(hào)串相等： 若若x、y是集合上的兩個(gè)符號(hào)串，則是集合上的兩個(gè)符號(hào)串，則xy iff組成組成x的每一個(gè)符號(hào)和組成的每一個(gè)符號(hào)和組成y的每一個(gè)符號(hào)依次相等。的每一個(gè)符號(hào)依次相等。 2.符號(hào)串的長(zhǎng)度：符號(hào)串的長(zhǎng)度： x為符號(hào)串，其長(zhǎng)度為符號(hào)串，其長(zhǎng)度|x|等于組成該符號(hào)串的符號(hào)個(gè)等于組成該符號(hào)串的符號(hào)個(gè)數(shù)。數(shù)。 例：例： xSTV ， |x|=33.1 3.1 預(yù)備知識(shí)預(yù)備知識(shí)2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)

20、系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系242424例：例：Aa,b,B=c,d, AB= ？ 4. 符號(hào)串集合的乘積運(yùn)算：符號(hào)串集合的乘積運(yùn)算： 令令A(yù)、B為符號(hào)串集合，定義為符號(hào)串集合，定義 AB xy|xA,yB ac，ad，bc，bd 3.3.符號(hào)串的聯(lián)接：符號(hào)串的聯(lián)接： 若若x、y是定義在是定義在是上的符號(hào)串，且是上的符號(hào)串，且xXY，yYX，則，則x和和y的聯(lián)接的聯(lián)接 xyXYYX也是也是上的符號(hào)串。上的符號(hào)串。 注意：一般注意：一般xyyx，而，而xx2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)

21、算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系2525256. 符號(hào)串集合的閉包運(yùn)算：符號(hào)串集合的閉包運(yùn)算： 設(shè)設(shè)A是符號(hào)串集合，定義是符號(hào)串集合，定義 A A1 A2 A3 An 稱為集合稱為集合A的正閉包。的正閉包。 A* A0 A稱為集合稱為集合A的（星）閉包。的（星）閉包。例：例：A=x,y A？ A* ？ 5. 符號(hào)串集合的冪運(yùn)算：符號(hào)串集合的冪運(yùn)算： 有符號(hào)串集合有符號(hào)串集合A，定義，定義A0 =,A1=A, A2=AA,A3=AAA, AnAn-1A=AAn-1 ，n0。x,y, xx, xy, yx, yy , xxx, xxy, xyx,

22、xyy, A1 A2 A3, x,y, xx, xy, yx,yy , xxx, xxy, xyx, xyy, A0 A1 A2 A32021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系262626若若A為某語(yǔ)言的基本字符集為某語(yǔ)言的基本字符集 Aa,b,z,0,1,9, +, /, ( , ), =B為單詞集為單詞集 B =begin, end, if, then,else,for, , +, /, 為什么對(duì)符號(hào)、符號(hào)串、符號(hào)串為什么對(duì)符號(hào)、符號(hào)串、符號(hào)串集合以及它們的運(yùn)

23、算感興趣集合以及它們的運(yùn)算感興趣？ 則則B A* 語(yǔ)言的句子是定義在語(yǔ)言的句子是定義在B上的符號(hào)串。上的符號(hào)串。 若令若令C為句子集合，則為句子集合，則C B * , 程序程序 C。 2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系2727272021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系2828283.2 3.2 文法的非形式討論文法的非形式

24、討論 1. 什么是文法：什么是文法： 文法是對(duì)語(yǔ)言結(jié)構(gòu)的定義與描述。文法是對(duì)語(yǔ)言結(jié)構(gòu)的定義與描述。 即從形式上用于描述和規(guī)定語(yǔ)言結(jié)構(gòu)的稱為即從形式上用于描述和規(guī)定語(yǔ)言結(jié)構(gòu)的稱為“文法文法” （或?yàn)椋ɑ驗(yàn)椤罢Z(yǔ)法語(yǔ)法”）。）。例：有一句子：例：有一句子：“我是大學(xué)生我是大學(xué)生” 。 這是一個(gè)在語(yǔ)法、語(yǔ)義上都正確定句子，怎么判斷在語(yǔ)這是一個(gè)在語(yǔ)法、語(yǔ)義上都正確定句子，怎么判斷在語(yǔ)法上是正確的？法上是正確的？2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系292929 2.2.

25、語(yǔ)法規(guī)則：語(yǔ)法規(guī)則： 我們通過(guò)建立一組規(guī)則，來(lái)描述句子的語(yǔ)法結(jié)構(gòu)。我們通過(guò)建立一組規(guī)則，來(lái)描述句子的語(yǔ)法結(jié)構(gòu)。 規(guī)定用規(guī)定用:= := =表示表示“由由組成組成”或或“定義為定義為”:=:= :=:=| :=:=你你| |我我| |他他 :=:= 王民王民| |大學(xué)生大學(xué)生| |工人工人| |英語(yǔ)英語(yǔ) :=:= :=:=是是| |學(xué)習(xí)學(xué)習(xí) :=:=| 3.2 3.2 文法的非形式討論文法的非形式討論2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系3030303.3. 由

26、規(guī)則推導(dǎo)句子：由規(guī)則推導(dǎo)句子： 有了一組規(guī)則之后，可以按照一定的方式用它們?nèi)ビ辛艘唤M規(guī)則之后，可以按照一定的方式用它們?nèi)?推導(dǎo)或產(chǎn)生句子。推導(dǎo)或產(chǎn)生句子。 推導(dǎo)方法：推導(dǎo)方法：從一個(gè)要識(shí)別的符號(hào)開(kāi)始推導(dǎo)，即用相應(yīng)從一個(gè)要識(shí)別的符號(hào)開(kāi)始推導(dǎo)，即用相應(yīng) 規(guī)則的規(guī)則的右部右部來(lái)替代規(guī)則的來(lái)替代規(guī)則的左部左部，每次僅用，每次僅用 一條規(guī)則去進(jìn)行推導(dǎo)。一條規(guī)則去進(jìn)行推導(dǎo)。 = = = 這種推導(dǎo)一直進(jìn)行下去，直到所有帶這種推導(dǎo)一直進(jìn)行下去，直到所有帶的符號(hào)都由的符號(hào)都由終結(jié)符號(hào)替代為止。終結(jié)符號(hào)替代為止。2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京

27、化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系313131 = = = 我我 =我我 =我我是是 =我是我是 =我是我是大學(xué)生大學(xué)生推導(dǎo)方法：推導(dǎo)方法：從一個(gè)要識(shí)別的符號(hào)從一個(gè)要識(shí)別的符號(hào) 開(kāi)始推導(dǎo)，即用相應(yīng)規(guī)則的開(kāi)始推導(dǎo)，即用相應(yīng)規(guī)則的 右部來(lái)替代規(guī)則的左部，每右部來(lái)替代規(guī)則的左部，每 次僅用一條規(guī)則去進(jìn)行推導(dǎo)。次僅用一條規(guī)則去進(jìn)行推導(dǎo)。2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系323232:=:= :=:= := :=the :=:=

28、big :=:=elephant :=:= :=:=ate :=:= := :=peanut例：例：有一英語(yǔ)句子：有一英語(yǔ)句子：The big elephant ate the peanut.2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系333333 = = = the = the big = the big elephant = the big elephant = the big elephant ate = the big elephant ate = the

29、big elephant ate the = the big elephant ate the peanut:=:= :=:= := :=the :=:=big :=:=elephant | peanut :=:= :=:=ate :=:= 2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系343434上述推導(dǎo)可寫(xiě)成上述推導(dǎo)可寫(xiě)成: = The big elephant ate the peanut.+說(shuō)明：說(shuō)明： (1) 有若干語(yǔ)法成分同時(shí)存在時(shí)，我們總是從最左的語(yǔ)法成

30、有若干語(yǔ)法成分同時(shí)存在時(shí)，我們總是從最左的語(yǔ)法成 分進(jìn)行推導(dǎo)，這稱之為分進(jìn)行推導(dǎo)，這稱之為最左推導(dǎo)最左推導(dǎo)，類似的有，類似的有最右推導(dǎo)最右推導(dǎo)（一般推（一般推 導(dǎo)）。導(dǎo)）。 (2) 從一組規(guī)則可推出不同的句子。從一組規(guī)則可推出不同的句子。3.2 3.2 文法的非形式討論文法的非形式討論以上規(guī)則還可推出以上規(guī)則還可推出: :大花生吃象、大花生吃花生、大大花生吃象、大花生吃花生、大象吃象等句子象吃象等句子. .它們?cè)谡Z(yǔ)法上都正確，它們?cè)谡Z(yǔ)法上都正確，但在語(yǔ)義上都不正確。但在語(yǔ)義上都不正確。2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)

31、信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系353535上述推導(dǎo)可寫(xiě)成上述推導(dǎo)可寫(xiě)成 = The big elephant ate the peanut.+ 所謂文法是在形式上對(duì)句子結(jié)構(gòu)的定義與描述，所謂文法是在形式上對(duì)句子結(jié)構(gòu)的定義與描述， 而未涉及語(yǔ)義問(wèn)題。而未涉及語(yǔ)義問(wèn)題。3.2 3.2 文法的非形式討論文法的非形式討論2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系363636 4.4.語(yǔ)法樹(shù)：語(yǔ)法樹(shù)：我們用語(yǔ)法樹(shù)來(lái)描述一個(gè)句子的語(yǔ)法結(jié)構(gòu)。我

32、們用語(yǔ)法樹(shù)來(lái)描述一個(gè)句子的語(yǔ)法結(jié)構(gòu)。Thebigelephantatethepeanut語(yǔ)法成分語(yǔ)法成分在形式語(yǔ)言中又在形式語(yǔ)言中又稱稱“非終結(jié)符非終結(jié)符”單詞符號(hào)單詞符號(hào)在形式語(yǔ)言中又在形式語(yǔ)言中又稱稱“終結(jié)符號(hào)終結(jié)符號(hào)”3.2 3.2 文法的非形式討論文法的非形式討論2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系3737373.3.5 3.3.5 句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄 2021-10-162021-10-162021-10-16北京

33、化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系3838383.3.1 文法的定義文法的定義 3.3 文法和語(yǔ)言的形式定義 定義定義1. 文法文法G=（Vn，Vt，P，Z） Vn：非終結(jié)符號(hào)集：非終結(jié)符號(hào)集 Vt：終結(jié)符號(hào)集：終結(jié)符號(hào)集 P：產(chǎn)生式或規(guī)則產(chǎn)生式或規(guī)則的集合的集合 Z：開(kāi)始符號(hào)（識(shí)別符號(hào)）：開(kāi)始符號(hào)（識(shí)別符號(hào)） ZVnVVn Vt 稱為文法的字匯表稱為文法的字匯表 Vn Vt 規(guī)則的定義規(guī)則的定義規(guī)則是一個(gè)有序?qū)σ?guī)則是一個(gè)有序?qū)?U, x), 通常寫(xiě)為通常寫(xiě)為: U : x 或或U x | U| = 1 |x| 0 2

34、021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系393939P = ； ； ； 00； 11； 99； Z = ；G=（Vn，Vt，P，Z）Vn, Vt = 0,1,2,3,9例：無(wú)符號(hào)整數(shù)的文法：例：無(wú)符號(hào)整數(shù)的文法：2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系404040幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明： 產(chǎn)生式產(chǎn)生式左邊左邊符號(hào)構(gòu)成集合符號(hào)構(gòu)成集合Vn，

35、且，且 Z Vn。 有些產(chǎn)生式具有相同的左部，可以合在一起。有些產(chǎn)生式具有相同的左部，可以合在一起。 例、例、 ； | ； 00 | 1 | 2 | 3 | | 9文法的文法的BNF表示表示無(wú)符號(hào)整數(shù)的文法簡(jiǎn)化為：無(wú)符號(hào)整數(shù)的文法簡(jiǎn)化為： （產(chǎn)生式集合產(chǎn)生式集合+識(shí)別符號(hào)識(shí)別符號(hào)）例、例、 G ； | ； 00 | 1 | 2 | 3 | | 92021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系4141413.3.2 推導(dǎo)的形式定義推導(dǎo)的形式定義 定義定義2：文法文法G：

36、vx Uy，wxuy, 其中其中x、y V* ，UVn, u V*, 若若U : uP，則，則v w。 若若xy，有，有U : u，則，則U u根據(jù)文法和推導(dǎo)定義，可推出終結(jié)符號(hào)串，所謂文根據(jù)文法和推導(dǎo)定義，可推出終結(jié)符號(hào)串，所謂文法能推出句子來(lái)。法能推出句子來(lái)。3.3 文法和語(yǔ)言的形式定義稱稱 v直接產(chǎn)生直接產(chǎn)生w 或或w是是v直接推導(dǎo)直接推導(dǎo) 或或w直接規(guī)約到直接規(guī)約到v 2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系424242 1 1 0(6)=(1)=(3)

37、(5)=(2) 當(dāng)符號(hào)串已沒(méi)有非終結(jié)符號(hào)時(shí)，推導(dǎo)就必須終止。當(dāng)符號(hào)串已沒(méi)有非終結(jié)符號(hào)時(shí)，推導(dǎo)就必須終止。因?yàn)橐驗(yàn)榻K結(jié)符不可能出現(xiàn)在規(guī)則左部終結(jié)符不可能出現(xiàn)在規(guī)則左部，所以將在規(guī)則，所以將在規(guī)則左部出現(xiàn)的符號(hào)稱為左部出現(xiàn)的符號(hào)稱為非終結(jié)符號(hào)非終結(jié)符號(hào)。例如：例如：G (1) ； (2) (3) (4) 0;0;(5) 1;1; (13) 9;9;請(qǐng)問(wèn)根據(jù)文法請(qǐng)問(wèn)根據(jù)文法G G能否推導(dǎo)出能否推導(dǎo)出1010？2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系434343 定義定

38、義3：文法文法G，U0, U1, U2,，Un V+ if v= U0 U1 U2 Unw 則則v w= G= G= G= G= G例：例： = = = =1 =1 0即即 10 = G3.3.2 推導(dǎo)的形式定義推導(dǎo)的形式定義 稱稱 v推導(dǎo)出（產(chǎn)生）推導(dǎo)出（產(chǎn)生）w或或w規(guī)約到規(guī)約到v（推導(dǎo)長(zhǎng)度為（推導(dǎo)長(zhǎng)度為n） 2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系444444 定義定義4：文法文法G，v，w V+ if v w , 或或v=w，則，則v w *= G= G

39、 定義定義5：規(guī)范推導(dǎo)：規(guī)范推導(dǎo)：有有xUy = xuy, if y Vt* ,則此推則此推 導(dǎo)為規(guī)范的，記為導(dǎo)為規(guī)范的，記為xUy = xuy |直觀意義：直觀意義：規(guī)范推導(dǎo)最右推導(dǎo)規(guī)范推導(dǎo)最右推導(dǎo)最最右右推導(dǎo)：若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，推導(dǎo)：若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，先推右邊先推右邊的。的。最最左左推導(dǎo)：若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，推導(dǎo)：若符號(hào)串中有兩個(gè)以上的非終結(jié)符時(shí)，先推左邊先推左邊的。的。 稱稱 v推導(dǎo)出（產(chǎn)生）推導(dǎo)出（產(chǎn)生）w，或或w規(guī)約到規(guī)約到v （推導(dǎo)長(zhǎng)度為（推導(dǎo)長(zhǎng)度為n） 3.3.2 推導(dǎo)的形式定義推導(dǎo)的形式定義 2021-10-162021-10-16

40、2021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系454545 文法文法GZGZ所產(chǎn)生的所產(chǎn)生的 所有句子的集合所有句子的集合 形式語(yǔ)言理論可以證明以下兩點(diǎn)：形式語(yǔ)言理論可以證明以下兩點(diǎn)： （1）G L（G）；）； （2）L(G)G1，G2，Gn； 已知文法，求語(yǔ)言，通過(guò)推導(dǎo)；已知文法，求語(yǔ)言，通過(guò)推導(dǎo)； 已知語(yǔ)言，構(gòu)造文法已知語(yǔ)言，構(gòu)造文法。 無(wú)形式化方法，更多是憑經(jīng)驗(yàn)。無(wú)形式化方法，更多是憑經(jīng)驗(yàn)。 定義定義6：文法：文法GZ （1）句型句型：x是句型是句型 Z x,且且xV*；（2）句子句子：x是句子是句子 Z x, 且且xVt*；（3）語(yǔ)言語(yǔ)言：L（GZ）=x| xVt*, Z x ； +*3.3.3 3.3.3 語(yǔ)言的形式定義語(yǔ)言的形式定義 3.3 文法和語(yǔ)言的形式定義2021-10-162021-10-162021-10-16北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)系464646例：例：abna|n1, 構(gòu)造其文法。構(gòu)造其文法。 定義定義7. G和和G是兩個(gè)不同的文法，若是兩個(gè)不同的文法，若 L(G) = L(