CHAPTER 2(Grammar and Language)

1、2021-7-171 Chapter2 Grammar and Language n串和語言（串和語言（Strings and Languages ） n文法和語言的定義文法和語言的定義 （Definitions of Grammar and Language） n文法和語言的分類文法和語言的分類 （Classification of Grammar and Language） n分析樹與句型分析樹與句型 （Parse Tree and Sentential form） 2021-7-172 2.1 2.1 串和語言串和語言 n 字母表（字母表（alphabet）：）： n字母表是符號(hào)（sym

2、bols）的非空有窮集合， 用表示 n符號(hào)：可以相互區(qū)別的記號(hào)（元素） n不同的語言有不同的字母表 n漢語漢字 n英語26個(gè)英文字母 2021-7-173 2.1 2.1 串和語言串和語言 n符號(hào)串（符號(hào)串（String）：）： n符號(hào)串是由字母表中的符號(hào)所組成的有窮序列 n在語言理論中，符號(hào)串又稱為: 句子（句子（sentence）、字（字（word） n例如： =a,b a, b, aa, ab, aabba都是上的符號(hào)串 n是任何上的符號(hào)串 2021-7-174 2.1 2.1 串和語言串和語言 n符號(hào)串的長(zhǎng)度 n符號(hào)串中包含符號(hào)的個(gè)數(shù) n符號(hào)串 s 的長(zhǎng)度記為 |s| n例，對(duì)于字母表

3、a,b,c，aab 是其上的一個(gè)符號(hào) 串， | aab |=3 n注意：空符號(hào)串， | |=0 2021-7-175 2.1 2.1 串和語言串和語言 n符號(hào)串的前綴（prefix）、后綴（suffix）、子 串（substring） n后綴：刪去符號(hào)串 s 頭部的零個(gè)或多于零 個(gè)符號(hào)得到的符號(hào)串 n例如： nana是符號(hào)串banana的一個(gè)后綴 n前綴：移走符號(hào)串 s 尾部的零個(gè)或多于零 個(gè)符號(hào)得到的符號(hào)串 n例如： b是符號(hào)串banana的一個(gè)前綴 2021-7-176 2.1 2.1 串和語言串和語言 n符號(hào)串的真（proper）前綴、真后綴和真 子串非空 n子串：從 s 中刪去一個(gè)前綴

4、和一個(gè)后綴得 到的符號(hào)串 n例如：ana是符號(hào)串banana的一個(gè)子串 n* 對(duì)于每個(gè)符號(hào)串s， s和兩者都是符號(hào)串 s的 前綴，后綴和子串 2021-7-177 2.1 2.1 串和語言串和語言 n 語言（語言（Language）：）： n某個(gè)字母表上的符號(hào)串的集合集合 n例: 漢語所有符合漢語語法的句子構(gòu)成的集合 PASCAL語言所有合法的PASCAL程序構(gòu)成的 集合 n注意：空集 、 和的不同 2021-7-178 2.1 2.1 串和語言串和語言 n符號(hào)串的運(yùn)算： n連接（concatenation）：符號(hào)串x、y的連接，是把 y 的符號(hào)寫在 x 的符號(hào)之后得到的符號(hào)串 xy n如 x

5、 = ab, y = cd 則 xy = abcd n注： = = n方冪（exponentiation）：符號(hào)串自身連接n次得到 的符號(hào)串 nn 定義為 n個(gè) n1 =, 2 =，注：0 = 2021-7-179 2.1 2.1 串和語言串和語言 n語言的運(yùn)算（operations on languages）： n語言是符號(hào)串的集合，集合的運(yùn)算有并、交、 差等 n并運(yùn)算 等同于集合的并運(yùn)算 2021-7-1710 2.1 2.1 串和語言串和語言 n連接（乘積） n兩個(gè)符號(hào)串集合 A 和 B 的乘積定義為： AB = xy | x A 且 y B n例如：集合A=ab,cde B=0,1 則

6、 AB= ab1,ab0,cde0,cde1 nL = L = L nLLL = Ln L0 = 2021-7-1711 2.1 2.1 串和語言串和語言 n* 閉包（Kleene closure） nL* = L0L1L2L3 n+閉包（Positive closure） nL+ = L1L2L3 nL* = L+ 2021-7-1712 2.1 2.1 串和語言串和語言 n注: 后面通常是考慮字母表的 * 閉包和 + 閉包 n例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab, 2021-7-1713 2.1 2.1 串

7、和語言串和語言 n綜合性的例子：P120(75) example 3.3 n L = A,B,C,Z,a,b,c,z n D = 0,1,9 n把 L 和 D 兩個(gè)字母表看作長(zhǎng)度為1的符號(hào)串集 合，即語言 1. L D 2. LD 3. L4 4. L* 5. L(L D)* 6. D+ 2021-7-1714 2.2 2.2 文法和語言的定義文法和語言的定義 n如何來描述一種語言？如何來描述一種語言？ n如果語言是有窮的（只含有有窮多個(gè)句子）， 可以將句子逐一列出來表示 n如果語言是無窮的，找出語言的有窮表示。 2021-7-1715 2.2 2.2 文法和語言的定義文法和語言的定義 n語言

8、的有窮表示有兩個(gè)途經(jīng)： n生成方式 （文法）：語言中的每個(gè)句子可以用嚴(yán)格 定義的規(guī)則來構(gòu)造。 n識(shí)別方式（自動(dòng)機(jī)）：用一個(gè)過程，當(dāng)輸入的一任 意串屬于語言時(shí)，該過程經(jīng)有限次計(jì)算后就會(huì)停止 并回答“是”，若不屬于，要么能停止并回答“不 是”，（要么永遠(yuǎn)繼續(xù)下去。） n文法即是以生成方式描述語言的：語言中的每 個(gè)句子可以用嚴(yán)格定義的規(guī)則來構(gòu)造. 2021-7-1716 2.2 2.2 文法和語言的定義文法和語言的定義 n文法文法 G 定義為四元組（定義為四元組（VT，VN，S，P）：）： nVT ：終結(jié)符（terminals）集，其中的元素一般用小寫 字母或數(shù)字表示（a,b,c0,1.），代表語言

9、中不可再語言中不可再 分的基本符號(hào)分的基本符號(hào)，如漢語中的漢字、PASCAL語言中的基 本字 nVN ：非終結(jié)符（nonterminals）集，其中的元素一般 用大寫字母表示（A,B,C），或者用尖括號(hào)括起，代 表語法單位語法單位，如漢語中的語句、段落，PASCAL語言中 的語句、表達(dá)式、子程序等 2021-7-1717 2.2 2.2 文法和語言的定義文法和語言的定義 nS 是一個(gè)特殊的非終結(jié)符號(hào)，稱為開始符號(hào)（start symbol） nS 至少要在一條產(chǎn)生式中作為左部出現(xiàn) nP是一個(gè)產(chǎn)生式（production）的集合 n產(chǎn)生式（重寫規(guī)則、生成式），是形如或 = 的（，）有序?qū)?，且V+

10、，V* 其中 V = （VTVN） n稱為產(chǎn)生式的左部，不能為空 n稱為產(chǎn)生式的右部，可以為空（如：A ） 2021-7-1718 2.2 2.2 文法和語言的定義文法和語言的定義 例1：文法 G = （VT，VN，S，P） VN = S VT = 0, 1 P = S0S1, S01 n可以只寫出產(chǎn)生式，通過產(chǎn)生式可以得到文法的其它 部分 n左部相同的產(chǎn)生式可以寫在一起，如: S 0S1 | 01 2021-7-1719 2.2 2.2 文法和語言的定義文法和語言的定義 例2：文法 G = （VT，VN，S，P） VN = ， VT = a,b,c,x,y,z,0,1,9 P = a, z

11、0, 9 S = 2021-7-1720 2.2 2.2 文法和語言的定義文法和語言的定義 n推導(dǎo)（推導(dǎo)（derivation）與歸約（）與歸約（reduction）：）： n直接推導(dǎo)與直接歸約 n如果 A 是 G 的一條產(chǎn)生式，則稱用代替 A為一步直接推導(dǎo)直接推導(dǎo)，記為A =；稱用A 代替為一步直接歸約直接歸約，記為 0S1 = 00S11 = 000111，長(zhǎng)度為3 記為：S 000111 S S * * 2021-7-1722 2.2 2.2 文法和語言的定義文法和語言的定義 n最左推導(dǎo)與最右推導(dǎo) n =是一步推導(dǎo)， ， （VTVN）* n最左推導(dǎo)(=lm) 對(duì) 中的最左非終結(jié)符進(jìn)行展

12、開 n最右推導(dǎo)(=rm) 對(duì) 中的最右非終結(jié)符進(jìn)行展 開 2021-7-1723 2.2 2.2 文法和語言的定義文法和語言的定義 n例子：表達(dá)式文法 E E + T E T T T * F T F F （E） F a 最左推導(dǎo)：E=lmT=lmT*F=lmF*F=lma*F=lma*a * 最右推導(dǎo)又稱為規(guī)范推導(dǎo) 最右推導(dǎo)：E=rmT=rmT*F=rmT*a=rmF*a=rma*a 2021-7-1724 2.2 2.2 文法和語言的定義文法和語言的定義 n最右歸約與最左歸約 n最左推導(dǎo)的逆過程是最右歸約，即對(duì)最右邊的可歸 約串進(jìn)行歸約 a*a = a*F = F*F = T*F = T=

13、E n最右推導(dǎo)的逆過程是最左歸約，即對(duì)最左邊的可歸 約串進(jìn)行歸約 a*a = F*a = T*a = T*F =T T =T*F =F*F =a*F =a*a 中， 句型有： E 、T、T*F 、F*F 、a*F 、a*a 句子是： a*a 2021-7-1727 2.2 2.2 文法和語言的定義文法和語言的定義 n語言的形式定義：語言的形式定義： n文法 G 推導(dǎo)出的所有句子組成的集合，稱為語言語言，記 為 L（G） nL（G）=| S ， VT* * 2021-7-1728 2.2 2.2 文法和語言的定義文法和語言的定義 n例子： nG1： S A A 0A1 A 01 是由一個(gè)或多個(gè)

14、0 開頭，后跟同樣數(shù) 目的 1 的符號(hào)串構(gòu)成的集合（語言）， 可記為：L(G)=0n1n|n1 2021-7-1729 2.2 2.2 文法和語言的定義文法和語言的定義 nG2： E id E E + E E E * E E （E） 產(chǎn)生的是表達(dá)式的集合 2021-7-1730 2.2 2.2 文法和語言的定義文法和語言的定義 nG3： E E + T E T T T * F T F F （E） F id 產(chǎn)生的也是表達(dá)式的集合 2021-7-1731 2.2 2.2 文法和語言的定義文法和語言的定義 n一個(gè)文法對(duì)應(yīng)一個(gè)語言，但一個(gè)語言可能有若干個(gè)文 法產(chǎn)生它，這若干個(gè)文法是等價(jià)的，稱為 等價(jià)

15、（等價(jià)（equivalent）文法）文法 n例 G2 與 G3 2021-7-1732 2.3 2.3 文法和語言的分類文法和語言的分類 n喬姆斯基（喬姆斯基（Chomsky）在）在 1956 年提出形式語言年提出形式語言 理論，他將形式文法分為四類理論，他將形式文法分為四類 ( 0 , 1 , 2 , 3 )， 對(duì)應(yīng)四類形式語言對(duì)應(yīng)四類形式語言 ( 0 , 1 , 2 , 3 ) n分類的方法是對(duì)文法的產(chǎn)生式進(jìn)行不同的限制分類的方法是對(duì)文法的產(chǎn)生式進(jìn)行不同的限制 2021-7-1733 2.3 2.3 文法和語言的分類文法和語言的分類 n0 型文法 | | 0，即 （ ） n1 型（上下文有

16、關(guān)）文法 | | | | （ ） n2 型（上下文無關(guān)）文法 A VN， （VTVN）* （ A ） n3 型（正規(guī)）文法 nAa 或 AaB（右線性） nAa 或 ABa（左線性） 2021-7-1734 2.3 2.3 文法和語言的分類文法和語言的分類 例：例：1 1 型（上下文有關(guān)）文法型（上下文有關(guān)）文法 文法文法 G G ： SCDSCD AbbA AbbA CaCACaCABaaBBaaB CbCBCbCBBbbBBbbB ADaDADaDCC BDbDBDbDDD AabDAabD L(G)=ww|wa,bL(G)=ww|wa,b* * 2021-7-1735 2.3 2.3 文

17、法和語言的分類文法和語言的分類 例：例：2 2 型（上下文無關(guān)）文法型（上下文無關(guān)）文法 文法文法 G G1 1 ： ： SaB|bASaB|bA Aa|aS|bAAAa|aS|bAA Bb|bS|aBBBb|bS|aBB 文法文法 G G2 2 ： ： S0A|1B|0S0A|1B|0 A0A|1B|0SA0A|1B|0S B1B|1|0B1B|1|0 2021-7-1736 2.3 2.3 文法和語言的分類文法和語言的分類 例：例：3 3 型（正規(guī)）文法型（正規(guī)）文法 文法文法 G G ：S0A|1B|0S0A|1B|0 A0A|1B|0SA0A|1B|0S B1B|1|0B1B|1|0

18、2021-7-1737 2.3 2.3 文法和語言的分類文法和語言的分類 n0 型文法產(chǎn)生的語言稱為 0 型語言 n1 型文法或上下文有關(guān)文法產(chǎn)生的語言稱為 1 型語言或上下文有關(guān)語言 n2 型文法或上下文無關(guān)文法（ Context-Free Grammar ）產(chǎn)生的語言稱為 2 型語言或上下文 無關(guān)語言（ Context-Free Language） n3 型文法或正則（正規(guī)）文法（ Regular Grammar ）產(chǎn)生的語言稱為 3 型語言正則（正 規(guī)）語言（ Regular Language ） 2021-7-1738 2.3 2.3 文法和語言的分類文法和語言的分類 n四種文法（語言

19、）之間的逐級(jí)“包含”關(guān)系 2 型文法型文法（語言）（語言） 1 型文法型文法（語言）（語言） 0 型文法（語言）型文法（語言） 3 型文法（語言）型文法（語言） 2021-7-1739 2.3 2.3 文法和語言的分類文法和語言的分類 n識(shí)別各類語言的數(shù)學(xué)模型（自動(dòng)機(jī)）識(shí)別各類語言的數(shù)學(xué)模型（自動(dòng)機(jī)） n圖靈機(jī)（ 0 型語言） n有界圖靈機(jī)、線性有界自動(dòng)機(jī)（1 型語言） n下推自動(dòng)機(jī)（ 2 型語言） n有限自動(dòng)機(jī)（ 3 型語言） 2021-7-1740 2.4 2.4 分析樹與句型分析樹與句型 n上下文無關(guān)文法能夠描述現(xiàn)今程序設(shè)計(jì)語上下文無關(guān)文法能夠描述現(xiàn)今程序設(shè)計(jì)語 言的大部分語法結(jié)構(gòu)言的大

20、部分語法結(jié)構(gòu) n算術(shù)表達(dá)式 n賦值語句 n條件語句等 2021-7-1741 2.4 2.4 分析樹與句型分析樹與句型 n表達(dá)式文法：G = ( +,*,id,(,), E, E, P ) P:E id E E+E E E*E E (E) E表示算術(shù)表達(dá)式， id表示程序的“變量”，該文法 定義了由變量，+，*，( 和 ) 組成的算術(shù)表達(dá)式的語法結(jié) 構(gòu)，即： 變量是算術(shù)表達(dá)式；若E1和E2是算術(shù)表達(dá)式，則 E1+ E2，E1*E2和 (E1) 也是算術(shù)表達(dá)式。 2021-7-1742 2.4 2.4 分析樹與句型分析樹與句型 n描述一種簡(jiǎn)單賦值語句的產(chǎn)生式： 賦值語句 id = E n描述條件

21、語句的產(chǎn)生式： 條件語句 if條件then語句 if條件then語句else語句 2021-7-1743 2.4 2.4 分析樹與句型分析樹與句型 n分析樹分析樹是描述上下文無關(guān)文法句型推導(dǎo)的一 種直觀方法，也稱為推導(dǎo)樹 2021-7-1744 2.4 2.4 分析樹與句型分析樹與句型 n為句型推導(dǎo)構(gòu)造分析樹 n例子： E =T nE E + T E T T T * F T F F （E） F a =T*F =F*F =a*F T T*F F a a E =a*a 2021-7-1745 2.4 2.4 分析樹與句型分析樹與句型 n分析樹的特性：分析樹的特性： n根標(biāo)識(shí)為開始符號(hào) n內(nèi)部結(jié)點(diǎn)標(biāo)

22、識(shí)為非終結(jié)符號(hào) n每一內(nèi)部結(jié)點(diǎn)及其子結(jié)點(diǎn)對(duì)應(yīng)一條產(chǎn)生式， 該結(jié)點(diǎn)是產(chǎn)生式的左部，子結(jié)點(diǎn)從左至右 排列構(gòu)成產(chǎn)生式的右部 n葉結(jié)點(diǎn)從左至右排列構(gòu)成句型 T T*F F a a E 2021-7-1746 2.4 2.4 分析樹與句型分析樹與句型 n分析樹與句型推導(dǎo)的關(guān)系分析樹與句型推導(dǎo)的關(guān)系 n一次推導(dǎo)（不是一個(gè)句型）對(duì)應(yīng)一棵分析樹 n一棵分析樹可能對(duì)應(yīng)若干個(gè)推導(dǎo) n例如下面的推導(dǎo)對(duì)應(yīng)的也是上面那棵分析樹 E =T=T*F =T*a =F*a =a*a T T*F F a a E 2021-7-1747 2.4 2.4 分析樹與句型分析樹與句型 n說明分析樹沒有嚴(yán)格反映推導(dǎo)的順序 n但是一棵分析樹

23、對(duì)應(yīng)一個(gè)最左推導(dǎo)，也 只能對(duì)應(yīng)一個(gè)最右推導(dǎo) T T*F F a a E 2021-7-1748 2.4 2.4 分析樹與句型分析樹與句型 n句型的短語、直接短語和句柄（句型的短語、直接短語和句柄（handle） n如果 S A和 A ，則稱是關(guān)于 A的， 句型的一個(gè)短語短語（子樹的葉子） * S A 2021-7-1749 2.4 2.4 分析樹與句型分析樹與句型 例：句型 F*a 的短語 T T*F Fa E F*a 、F、a 2021-7-1750 2.4 2.4 分析樹與句型分析樹與句型 n如果S A和 A =，則稱是關(guān)于 A的， 句型的一個(gè)直接短語直接短語（只有父子兩代的 子樹的葉子） * S A 2021-7-1751 2.4 2.4 分析樹與句型分析樹與句型 例：句型 F*a 的直接短語 T T*F Fa E F、a 2021-7-1752 2.4 2.4 分析樹與句型分析樹與句型 n最左直接短語稱為句柄句柄 n最左性體現(xiàn)在分析樹和句型中 S A 2021-7-1753 2.4 2.4 分析樹與句型分析樹與句型 例：句型 F*a 的句柄 T T*F Fa E F 2021-7-1754 2.4 2.4 分析樹與句型分析樹與句型