編譯方法形式語(yǔ)言和文法課件

1、2.1 形式語(yǔ)言形式語(yǔ)言 2.4 文法的二義性文法的二義性 2.3 文法的分類和化簡(jiǎn)文法的分類和化簡(jiǎn) 2.2 文法文法 符號(hào)串的集合。符號(hào)串的集合。 元素元素 符號(hào)串符號(hào)串該語(yǔ)言的一個(gè)句子。該語(yǔ)言的一個(gè)句子。 字母表字母表符號(hào)串中符號(hào)的來(lái)源。符號(hào)串中符號(hào)的來(lái)源。 句子的構(gòu)成句子的構(gòu)成按一定規(guī)則。按一定規(guī)則。v 程序設(shè)計(jì)語(yǔ)言：程序設(shè)計(jì)語(yǔ)言： 程序的集合程序的集合 句子句子程序（一個(gè)或長(zhǎng)或短的字符串）程序（一個(gè)或長(zhǎng)或短的字符串） 。 字母表字母表固定的字符集，語(yǔ)言可以使用的所有符號(hào)。固定的字符集，語(yǔ)言可以使用的所有符號(hào)。 編程時(shí)必須遵循一定的規(guī)則編程時(shí)必須遵循一定的規(guī)則 和和。v 語(yǔ)言的描述工具語(yǔ)

2、言的描述工具文法文法 一個(gè)元素的非空有窮集合，其中的元素也稱符號(hào)。一個(gè)元素的非空有窮集合，其中的元素也稱符號(hào)。 每個(gè)語(yǔ)言均有一固定的字母表。每個(gè)語(yǔ)言均有一固定的字母表。 C語(yǔ)言的字母表由基本字符集（字母，數(shù)字，括號(hào)，專用字符語(yǔ)言的字母表由基本字符集（字母，數(shù)字，括號(hào)，專用字符+、 *、 ）、保留字（）、保留字（int、 long、 if、struct、static、 typedef、 sizeof、 ）等組成。）等組成。通常用通常用V、或其他大寫字母表示。或其他大寫字母表示。例如例如V=0，1，=a，b，c，d，e等。等。 相關(guān)術(shù)語(yǔ)：相關(guān)術(shù)語(yǔ)：符號(hào)串中符號(hào)的個(gè)數(shù)。符號(hào)串中符號(hào)的個(gè)數(shù)。 符號(hào)串符

3、號(hào)串x 的長(zhǎng)度表示為的長(zhǎng)度表示為x，x= m0 0。無(wú)任何符號(hào)的串，簡(jiǎn)稱空串，用無(wú)任何符號(hào)的串，簡(jiǎn)稱空串，用表示，表示，|=0 0z = x z = x z = x =a，b，c，z，x =“l(fā)augh”，則，則 |x|=5 =I，you，he，am，is，are，a，student， y=“I am a student”，空格不計(jì)算長(zhǎng)度，則，空格不計(jì)算長(zhǎng)度，則 |y|=4。 符號(hào)串符號(hào)串x、y的連接的連接 xy 為一個(gè)新的符號(hào)串，該串的前面部分為為一個(gè)新的符號(hào)串，該串的前面部分為 x ， 后面部分為后面部分為 y 。 成立的等式：成立的等式： | xy | = | x | + | y | x

4、 = x=x 若若 x = “home”，y = “work” 則則 | x | = 4 , | y | = 4 xy = “homework” | xy | = 4+4 = 8 符號(hào)串符號(hào)串 x 的方冪就是的方冪就是 n個(gè)個(gè)x 自身連接自身連接 次，表示為次，表示為 xn 。 規(guī)定規(guī)定 x0 =。 若若 x = “ab” 則則 x0 = x1 = “ab” x2 = “abab” x3 = “ababab” 成立的等式：成立的等式： x1=x ， x2=xx ， x3=xxx ， 若若n0，則有：，則有： xn = xxn-1 = xn-1x 表示表示 x 的任意多次方冪（可以是的任意多次方

5、冪（可以是 0 次）次） 表示表示 x 的任意非的任意非 0 次方冪。次方冪。 兩符號(hào)串集兩符號(hào)串集U、V 的乘積為的乘積為 成立的等式：成立的等式： U = U = U V n = VVV （n個(gè)個(gè)V） 規(guī)定：規(guī)定： V 0 = V * = V 0V 1V 2 V + = V 1V 2 若若 U = a，b ， V = c，d 則則 UV = ac，ad，bc，bd 若指定字母表若指定字母表，則，則*表示表示上的所有有窮長(zhǎng)的串的集合。上的所有有窮長(zhǎng)的串的集合。 * =012n 稱為集合稱為集合的的 + =12n 稱為集合稱為集合的的 * =0+ ， + =* =* 若符號(hào)串若符號(hào)串 x 是是

6、*的元素的元素, ,則表示為則表示為 x* , ,否則否則 x * 。 語(yǔ)言的句子個(gè)數(shù)有限語(yǔ)言的句子個(gè)數(shù)有限 語(yǔ)言的句子有很多甚至是無(wú)窮多個(gè)語(yǔ)言的句子有很多甚至是無(wú)窮多個(gè) 給出一些規(guī)則給出一些規(guī)則 說(shuō)明這個(gè)語(yǔ)言的句子的組成結(jié)構(gòu)。說(shuō)明這個(gè)語(yǔ)言的句子的組成結(jié)構(gòu)。 規(guī)則規(guī)則 文法規(guī)則：文法規(guī)則： studentEnglish computer Iyouhe amisarehavestudy aanthe （1）嚴(yán)格定義了一個(gè)語(yǔ)言的句子的結(jié)構(gòu)；）嚴(yán)格定義了一個(gè)語(yǔ)言的句子的結(jié)構(gòu)；（2）用適當(dāng)條數(shù)的規(guī)則描述了一個(gè)語(yǔ)言的全部句子。）用適當(dāng)條數(shù)的規(guī)則描述了一個(gè)語(yǔ)言的全部句子。v 表示語(yǔ)言中的語(yǔ)法單位的符號(hào)，常

7、用尖括號(hào)表示語(yǔ)言中的語(yǔ)法單位的符號(hào)，常用尖括號(hào)“”括起。括起。v 一個(gè)非終結(jié)符一般可以推導(dǎo)出終結(jié)符串。一個(gè)非終結(jié)符一般可以推導(dǎo)出終結(jié)符串。v 一個(gè)語(yǔ)言可使用的所有非終結(jié)符組成的集合稱為非終結(jié)符集，一個(gè)語(yǔ)言可使用的所有非終結(jié)符組成的集合稱為非終結(jié)符集， 用用表示。表示。不可分割的符號(hào)串，是組成句子的最基本的單位。不可分割的符號(hào)串，是組成句子的最基本的單位。 一個(gè)語(yǔ)言允許使用的所有終結(jié)符組成的集合稱為終結(jié)符集，一個(gè)語(yǔ)言允許使用的所有終結(jié)符組成的集合稱為終結(jié)符集， 用用 表示。表示。 形如形如 或或 或或的有序?qū)Γ渲械挠行驅(qū)?，其?：某字母表：某字母表V 的的 V + 中的一個(gè)符號(hào)串（左部）中的一

8、個(gè)符號(hào)串（左部） ：V * 中的一個(gè)符號(hào)串（右部）中的一個(gè)符號(hào)串（右部） 定義：一個(gè)文法是一個(gè)定義：一個(gè)文法是一個(gè) ： 非終結(jié)符集（非空）；非終結(jié)符集（非空）； ： 終結(jié)符集（非空），終結(jié)符集（非空）， ； ： 識(shí)別符號(hào)或開(kāi)始符號(hào)，識(shí)別符號(hào)或開(kāi)始符號(hào)， 且至少在一條規(guī)則中作為左部出現(xiàn)；且至少在一條規(guī)則中作為左部出現(xiàn)； ： 規(guī)則（產(chǎn)生式）的集合。規(guī)則（產(chǎn)生式）的集合。 用用 表示表示 ，稱，稱G的字母表或詞匯表。的字母表或詞匯表。G：S0S1 或或 GS：S0S1 或或 G： S0S1 | 01 S01 S01 注意：左部相同的產(chǎn)生式可合并，用注意：左部相同的產(chǎn)生式可合并，用“|”表示表示“或或

9、”。（產(chǎn)生式），且第一條（產(chǎn)生式），且第一條 規(guī)則的左部規(guī)則的左部 是開(kāi)始符號(hào)，用是開(kāi)始符號(hào)，用“”括起的或大寫字母表示非終結(jié)符，括起的或大寫字母表示非終結(jié)符， 不用不用“”括起的或小寫字母表示終結(jié)符。括起的或小寫字母表示終結(jié)符。 文法文法 也常寫成也常寫成，方括號(hào)中的，方括號(hào)中的S為開(kāi)始符號(hào)。為開(kāi)始符號(hào)。 有一文法有一文法G（VN ，VT ，S ， P） 其中其中: VN = S VT = 0，1 開(kāi)始符號(hào)是開(kāi)始符號(hào)是 S P = S0S1， S01 文法文法G=(VN，VT，S ，P)為：為： VN= ， ， ， VT= student，computer，sister，English，I，

10、you，he ， am，is，are，have，study， a，an，the 開(kāi)始符號(hào)是開(kāi)始符號(hào)是 P= studentcomputersisterEnglish Iyouhe amisarehavestudy aanthe FORTRAN語(yǔ)言中對(duì)標(biāo)識(shí)符的規(guī)定是字母開(kāi)頭、長(zhǎng)度小于等于語(yǔ)言中對(duì)標(biāo)識(shí)符的規(guī)定是字母開(kāi)頭、長(zhǎng)度小于等于8的的 字母數(shù)字串，則標(biāo)識(shí)符的規(guī)則可以描述為：字母數(shù)字串，則標(biāo)識(shí)符的規(guī)則可以描述為： 巴科斯巴科斯-諾爾范式（巴科斯范式）諾爾范式（巴科斯范式） 采用四個(gè)元符號(hào)描述文法：采用四個(gè)元符號(hào)描述文法：“”（或（或“ ”）、）、“”，“|” 增加三對(duì)元符號(hào)：增加三對(duì)元符號(hào)： 表

11、示符號(hào)串表示符號(hào)串t的多次重復(fù)，的多次重復(fù)，n為重復(fù)的最小次數(shù)，為重復(fù)的最小次數(shù)，m為重為重 復(fù)的最大次數(shù)，省略復(fù)的最大次數(shù)，省略n、m表示表示t可以重復(fù)可以重復(fù)0到任意多次。到任意多次。 mnt70| 數(shù)數(shù)字字字字母母字字母母字字母母 用于提取產(chǎn)生式的公共因子，從而可以簡(jiǎn)化產(chǎn)生式。用于提取產(chǎn)生式的公共因子，從而可以簡(jiǎn)化產(chǎn)生式。 若有文法規(guī)則若有文法規(guī)則 Ax1| x2| xn 表示為表示為 Ax(1| 2| n)文法規(guī)則文法規(guī)則 S0S1|01 簡(jiǎn)化為簡(jiǎn)化為 S0(S1|1) 或或 S(0S|0)1 或或 S0(S| )1：表示符號(hào)串表示符號(hào)串t可選（即可有可無(wú)）?？蛇x（即可有可無(wú)）。C程序

12、設(shè)計(jì)語(yǔ)言的條件語(yǔ)句的文法規(guī)則程序設(shè)計(jì)語(yǔ)言的條件語(yǔ)句的文法規(guī)則 BNF表示：表示：if () ； | if () ；else ； 擴(kuò)展擴(kuò)展BNF表示：表示： if () ；else ； C語(yǔ)言條件語(yǔ)句的語(yǔ)法圖語(yǔ)言條件語(yǔ)句的語(yǔ)法圖else語(yǔ)句語(yǔ)句條件條件)語(yǔ)句語(yǔ)句 對(duì)文法對(duì)文法G： S 0S1 S 01 有直接推導(dǎo)序列：有直接推導(dǎo)序列： S 0S1 00S11000111 ：如：如是文法是文法G（VN ，VT ，S ， P）的一條規(guī)則，的一條規(guī)則， 、V * ， 若有符號(hào)串若有符號(hào)串 v、w 滿足滿足 則稱則稱v（應(yīng)用規(guī)則（應(yīng)用規(guī)則）直接產(chǎn)生）直接產(chǎn)生w ，或稱，或稱 w 是是 v 的的，反過(guò)，反

13、過(guò) 來(lái)稱來(lái)稱 w 到到 v ，記作，記作 。如果存在直接推導(dǎo)序列：如果存在直接推導(dǎo)序列： 則稱則稱v 出出w，為為n ，反過(guò)來(lái)稱，反過(guò)來(lái)稱w 到到v， 記作記作 。 如果有如果有 v w ，或，或 v = w ，則記作則記作 。+ S 0S1 00S11 000111 S 推導(dǎo)出推導(dǎo)出 “ 000111” ， 推導(dǎo)長(zhǎng)度推導(dǎo)長(zhǎng)度3 “ 000111” 歸約到歸約到 S 表示成表示成 S 000111+ 推導(dǎo)推導(dǎo) S 0S1 00S11 000111 文法文法G（VN，VT，S ，P），若符號(hào)串），若符號(hào)串x可由開(kāi)始符號(hào)可由開(kāi)始符號(hào)S推導(dǎo)出推導(dǎo)出 （），則稱），則稱 x 是是 G 的一個(gè)的一個(gè)，若

14、，若x僅由終結(jié)符組成，僅由終結(jié)符組成， 則稱則稱 x 為為G 的一個(gè)的一個(gè)。文法描述的語(yǔ)言是該文法的所有句子的集合，文法描述的語(yǔ)言是該文法的所有句子的集合， 記作記作 L(G)。集合形式表示：。集合形式表示： 文法文法G： S 0S1 S 01 描述的語(yǔ)言：描述的語(yǔ)言：L(G)= 0n1n | n1 有文法有文法 GA： A0R A01 RA1若有文法若有文法G1、G2，它們描述的語(yǔ)言相同，即，它們描述的語(yǔ)言相同，即 則稱兩文法則稱兩文法 G1 和和 G2 。 描述的語(yǔ)言描述的語(yǔ)言 L(G) = 0n1n | n1 。：含有遞歸規(guī)則的文法稱遞歸文法。：含有遞歸規(guī)則的文法稱遞歸文法。：形如：形如

15、P1P2的規(guī)則稱遞歸規(guī)則。的規(guī)則稱遞歸規(guī)則。 若若1=則稱左遞歸規(guī)則則稱左遞歸規(guī)則; 若若2=則稱右遞歸規(guī)則。則稱右遞歸規(guī)則。P1P2的遞歸稱的遞歸稱,含間接遞歸的文法也是遞歸文法。含間接遞歸的文法也是遞歸文法。 + 設(shè)設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式，如果它的每個(gè)產(chǎn)生式滿足滿足、 (VNVT)*，且，且至少含有一個(gè)非終結(jié)符，則至少含有一個(gè)非終結(jié)符，則G是一個(gè)是一個(gè)0型文法。型文法。 0型文法的能力相當(dāng)于圖靈機(jī)，它所定義的語(yǔ)言為型文法的能力相當(dāng)于圖靈機(jī)，它所定義的語(yǔ)言為0型語(yǔ)言。型語(yǔ)言。 任何任何0型語(yǔ)言都是遞歸可枚舉的，反之，遞歸可枚舉集也必定是型語(yǔ)言都是遞歸可枚舉的，反之，

16、遞歸可枚舉集也必定是 一個(gè)一個(gè)0型語(yǔ)言，可由圖靈機(jī)來(lái)識(shí)別。型語(yǔ)言，可由圖靈機(jī)來(lái)識(shí)別。 設(shè)設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式，如果它的每個(gè)產(chǎn)生式滿足滿足 |（僅（僅S除外），則除外），則G是一個(gè)是一個(gè)1型文法。型文法。 另一種描述：文法的產(chǎn)生式形如另一種描述：文法的產(chǎn)生式形如 其中其中AVN，、(VNVT)*且且 1型文法型文法GS： S xSYZ | xYZ yZyz xYxy ZYYZ yYyy zZzz2型文法型文法GS： SE TP | TP Fi | (E) ET | ET PF | FP 設(shè)設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式，如果它的每個(gè)產(chǎn)生式中的中的 是

17、一個(gè)非終結(jié)符，則是一個(gè)非終結(jié)符，則G是一個(gè)是一個(gè)2型文法或上下文無(wú)關(guān)文法。型文法或上下文無(wú)關(guān)文法。3型文法型文法GS ： S aA A aA A a S a A dA A d 設(shè)設(shè)G=(VN，VT，P，S)，如果它的每個(gè)產(chǎn)生式均形如，如果它的每個(gè)產(chǎn)生式均形如 AaB 或或 Aa 其中其中A、BVN，aVT。 0 0型文法型文法 1 1型文法型文法 2 2型文法型文法 3 3型文法型文法 0 0型語(yǔ)言型語(yǔ)言遞歸可枚舉遞歸可枚舉1 1型語(yǔ)言型語(yǔ)言上下文有關(guān)上下文有關(guān)3 3型語(yǔ)言型語(yǔ)言正規(guī)正規(guī)2 2型語(yǔ)言型語(yǔ)言上下文無(wú)關(guān)上下文無(wú)關(guān)描述句法描述句法描述詞法描述詞法| | | | |VN = aB |

18、a含有含有A的文法產(chǎn)生的語(yǔ)言也可由不含的文法產(chǎn)生的語(yǔ)言也可由不含 A的另一個(gè)的另一個(gè) 文法產(chǎn)生（文法產(chǎn)生（S除外）。除外）。若存在一個(gè)上下文有關(guān)文法若存在一個(gè)上下文有關(guān)文法 G，則必存在另一個(gè)上下文有，則必存在另一個(gè)上下文有 關(guān)文法關(guān)文法 G1，使得，使得 L(G1) = L(G) ，且，且 G1 的開(kāi)始符號(hào)不出現(xiàn)在的開(kāi)始符號(hào)不出現(xiàn)在 任何產(chǎn)生式的右邊。任何產(chǎn)生式的右邊。 v 文法應(yīng)沒(méi)有多余的或有害的規(guī)則。文法應(yīng)沒(méi)有多余的或有害的規(guī)則。 v 化簡(jiǎn)：化簡(jiǎn)：(1) 刪除形如刪除形如AA的產(chǎn)生式。的產(chǎn)生式。 (2) 刪除刪除文法符號(hào)及其相應(yīng)的產(chǎn)生式。文法符號(hào)及其相應(yīng)的產(chǎn)生式。 (3) 刪除刪除非終結(jié)

19、符及其相應(yīng)的產(chǎn)生式。非終結(jié)符及其相應(yīng)的產(chǎn)生式。 文法文法G： S aS | W | U U a V bV | ac W aW化簡(jiǎn)后的文法化簡(jiǎn)后的文法G： S aS | U U a整數(shù)整數(shù)xz變量變量表達(dá)式表達(dá)式y(tǒng)% * +3a表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式變量變量變量變量變量變量賦值語(yǔ)句賦值語(yǔ)句語(yǔ)法樹(shù)是語(yǔ)法樹(shù)是 一棵數(shù)據(jù)結(jié)構(gòu)意義上的一棵數(shù)據(jù)結(jié)構(gòu)意義上的“樹(shù)樹(shù)”，滿足四個(gè)條件：，滿足四個(gè)條件： 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記 （字母表（字母表V的一個(gè)符號(hào)）；的一個(gè)符號(hào)）； 根的標(biāo)記是根的標(biāo)記是S（文法的開(kāi)始符號(hào)）；（文法的開(kāi)始符號(hào)）； 若一個(gè)結(jié)點(diǎn)若一個(gè)結(jié)點(diǎn)n至少有一個(gè)它自身除外的子孫，且有標(biāo)記至少有一個(gè)它自身除外的子孫，且有標(biāo)記 A，則，則A必在必在VN中（是非終結(jié)符）；中（是非終結(jié)符）； 若標(biāo)記為若標(biāo)記為A的結(jié)點(diǎn)的結(jié)點(diǎn)n的直接子孫從左到右的次序是結(jié)點(diǎn)的直接子孫從左到右的次序是結(jié)點(diǎn) n1、n2、nk ，其標(biāo)記分別為，其標(biāo)記分別為A1、A2、 Ak， 則則AA1A2Ak 必是文法產(chǎn)生式集必是文法產(chǎn)生式集P中的一個(gè)產(chǎn)生式。中的一個(gè)產(chǎn)生式。