《編譯方法》第2章形式語(yǔ)言和文法.ppt

《《編譯方法》第2章形式語(yǔ)言和文法.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《編譯方法》第2章形式語(yǔ)言和文法.ppt（40頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

2 1形式語(yǔ)言 第2章形式語(yǔ)言和文法 2 4文法的二義性 2 3文法的分類(lèi)和化簡(jiǎn) 2 2文法 2 1形式語(yǔ)言 2 1 1語(yǔ)言的概念 2 1 2語(yǔ)言的定義方式 語(yǔ)言 符號(hào)串的集合 元素 符號(hào)串 該語(yǔ)言的一個(gè)句子 字母表 符號(hào)串中符號(hào)的來(lái)源 句子的構(gòu)成 按一定規(guī)則 程序設(shè)計(jì)語(yǔ)言 程序的集合句子 程序 一個(gè)或長(zhǎng)或短的字符串 字母表 固定的字符集 語(yǔ)言可以使用的所有符號(hào) 編程時(shí)必須遵循一定的規(guī)則 語(yǔ)法規(guī)則和語(yǔ)義規(guī)則 語(yǔ)言的描述工具 文法 2 1 1語(yǔ)言的概念 2 1語(yǔ)言 1 什么是語(yǔ)言 1 有窮字母表一個(gè)元素的非空有窮集合 其中的元素也稱(chēng)符號(hào) 每個(gè)語(yǔ)言均有一固定的字母表 例 C語(yǔ)言的字母表由基本字符集 字母 數(shù)字 括號(hào) 專(zhuān)用字符 保留字 int long if struct static typedef sizeof 等組成 2 1 1語(yǔ)言的概念 2 1語(yǔ)言 2 符號(hào)串的相關(guān)概念和術(shù)語(yǔ) 通常用V 或其他大寫(xiě)字母表示 例如V 0 1 a b c d e 等 2 符號(hào)串字母表中的符號(hào)組成的任何有窮序列 相關(guān)術(shù)語(yǔ) 長(zhǎng)度 符號(hào)串中符號(hào)的個(gè)數(shù) 符號(hào)串x的長(zhǎng)度表示為 x x m 0 空符號(hào)串 無(wú)任何符號(hào)的串 簡(jiǎn)稱(chēng)空串 用 表示 0省略寫(xiě)法 z x z xz x 2 1 1語(yǔ)言的概念 2 1語(yǔ)言 例2 1 a b c z x laugh 則 x 5 I you he am is are a student y Iamastudent 空格不計(jì)算長(zhǎng)度 則 y 4 3 符號(hào)串的運(yùn)算 連接 符號(hào)串x y的連接xy為一個(gè)新的符號(hào)串 該串的前面部分為x 后面部分為y 成立的等式 xy x y x x x 例2 2 若x home y work 則 x 4 y 4xy homework xy 4 4 8 2 1 1語(yǔ)言的概念 2 1語(yǔ)言 方冪 符號(hào)串x的方冪就是n個(gè)x自身連接次 表示為xn 規(guī)定x0 例2 3 若x ab 則x0 x1 ab x2 abab x3 ababab 成立的等式 x1 x x2 xx x3 xxx 若n 0 則有 xn xxn 1 xn 1xx 表示x的任意多次方冪 可以是0次 x 表示x的任意非0次方冪 2 1 1語(yǔ)言的概念 2 1語(yǔ)言 4 符號(hào)串的集合若集合A中的所有元素都是某字母表上的符號(hào)串 則稱(chēng)A為該字母表上的符號(hào)串集合 乘積 兩符號(hào)串集U V的乘積為UV U V 成立的等式 U U UVn VV V n個(gè)V 規(guī)定 V0 V V0 V1 V2 V V1 V2 例2 4 若U a b V c d 則UV ac ad bc bd 2 1 1語(yǔ)言的概念 2 1語(yǔ)言 閉包 若指定字母表 則 表示 上的所有有窮長(zhǎng)的串的集合 0 1 2 n 稱(chēng)為集合 的閉包 1 2 n 稱(chēng)為集合 的正閉包 成立的等式 0 若符號(hào)串x是 的元素 則表示為x 否則x 2 1 1語(yǔ)言的概念 2 1語(yǔ)言 語(yǔ)言的句子個(gè)數(shù)有限 枚舉語(yǔ)言的句子有很多甚至是無(wú)窮多個(gè) 給出一些規(guī)則說(shuō)明這個(gè)語(yǔ)言的句子的組成結(jié)構(gòu) 規(guī)則 文法規(guī)則 2 1 2語(yǔ)言的定義方式 2 1語(yǔ)言 例2 5 文法規(guī)則 student English computer I you he am is are have study a an the 文法規(guī)則的作用 1 嚴(yán)格定義了一個(gè)語(yǔ)言的句子的結(jié)構(gòu) 2 用適當(dāng)條數(shù)的規(guī)則描述了一個(gè)語(yǔ)言的全部句子 2 1 2語(yǔ)言的定義方式 2 1語(yǔ)言 2 2文法 2 2 1文法的形式定義 2 2 2文法的表示方法 2 2 3相關(guān)概念 2 2文法 表示語(yǔ)言中的語(yǔ)法單位的符號(hào) 常用尖括號(hào) 括起 一個(gè)非終結(jié)符一般可以推導(dǎo)出終結(jié)符串 一個(gè)語(yǔ)言可使用的所有非終結(jié)符組成的集合稱(chēng)為非終結(jié)符集 用VN表示 1 終結(jié)符 不可分割的符號(hào)串 是組成句子的最基本的單位 一個(gè)語(yǔ)言允許使用的所有終結(jié)符組成的集合稱(chēng)為終結(jié)符集 用VT表示 2 非終結(jié)符 2 2 1文法的形式定義 2 2文法 3 規(guī)則 重寫(xiě)規(guī)則 產(chǎn)生式 生成式 形如 或 或 的有序?qū)?其中 某字母表V的V 中的一個(gè)符號(hào)串 左部 V 中的一個(gè)符號(hào)串 右部 定義 一個(gè)文法是一個(gè)四元組G VN VT S P VN 非終結(jié)符集 非空 VT 終結(jié)符集 非空 VN VT S 識(shí)別符號(hào)或開(kāi)始符號(hào) S VN 且至少在一條規(guī)則中作為左部出現(xiàn) P 規(guī)則 產(chǎn)生式 的集合 用V表示VN VT 稱(chēng)G的字母表或詞匯表 4 文法 2 2 1文法的形式定義 2 2文法 G S 0S1或G S S 0S1或G S 0S1 01S 01S 01注意 左部相同的產(chǎn)生式可合并 用 表示 或 簡(jiǎn)化表示 只寫(xiě)出規(guī)則 產(chǎn)生式 且第一條規(guī)則的左部是開(kāi)始符號(hào) 用 括起的或大寫(xiě)字母表示非終結(jié)符 不用 括起的或小寫(xiě)字母表示終結(jié)符 文法G也常寫(xiě)成G S 方括號(hào)中的S為開(kāi)始符號(hào) 例2 6 有一文法G VN VT S P 其中 VN S VT 0 1 開(kāi)始符號(hào)是SP S 0S1 S 01 2 2 1文法的形式定義 2 2文法 例2 7 文法G VN VT S P 為 VN VT student computer sister English I you he am is are have study a an the 開(kāi)始符號(hào)是P student computer sister English I you he am is are have study a an the 2 2 1文法的形式定義 2 2文法 例2 8 FORTRAN語(yǔ)言中對(duì)標(biāo)識(shí)符的規(guī)定是字母開(kāi)頭 長(zhǎng)度小于等于8的字母數(shù)字串 則標(biāo)識(shí)符的規(guī)則可以描述為 1 BNF表示法巴科斯 諾爾范式 巴科斯范式 采用四個(gè)元符號(hào)描述文法 或 2 擴(kuò)展的BNF表示法增加三對(duì)元符號(hào) 1 表示符號(hào)串t的多次重復(fù) n為重復(fù)的最小次數(shù) m為重復(fù)的最大次數(shù) 省略n m表示t可以重復(fù)0到任意多次 2 2 2文法的表示方法 2 2文法 2 用于提取產(chǎn)生式的公共因子 從而可以簡(jiǎn)化產(chǎn)生式 若有文法規(guī)則A x 1 x 2 x n表示為A x 1 2 n 例2 9 文法規(guī)則S 0S1 01簡(jiǎn)化為S 0 S1 1 或S 0S 0 1或S 0 S 1 3 t 表示符號(hào)串t可選 即可有可無(wú) 例2 10 C程序設(shè)計(jì)語(yǔ)言的條件語(yǔ)句的文法規(guī)則BNF表示 if if else 擴(kuò)展BNF表示 if else 2 2 2文法的表示方法 2 2文法 3 語(yǔ)法圖表示法 例2 11 C語(yǔ)言條件語(yǔ)句的語(yǔ)法圖 2 2 2文法的表示方法 2 2文法 終結(jié)符 非終結(jié)符 例2 13 對(duì)文法G S 0S1S 01有直接推導(dǎo)序列 S 0S1 00S11 000111 定義 如 是文法G VN VT S P 的一條規(guī)則 V 若有符號(hào)串v w滿(mǎn)足v w 則稱(chēng)v 應(yīng)用規(guī)則 直接產(chǎn)生w 或稱(chēng)w是v的直接推導(dǎo) 反過(guò)來(lái)稱(chēng)w直接歸約到v 記作v w 1 推導(dǎo)和歸約 2 2 3相關(guān)概念 2 2文法 定義 如果存在直接推導(dǎo)序列 v w0 w1 w2 wn w則稱(chēng)v推導(dǎo) 產(chǎn)生 出w 推導(dǎo)長(zhǎng)度為n 反過(guò)來(lái)稱(chēng)w歸約到v 記作v w 如果有v w 或v w 則記作v w 2 2 3相關(guān)概念 2 2文法 例2 15 推導(dǎo)S 0S1 00S11 000111 定義 文法G VN VT S P 若符號(hào)串x可由開(kāi)始符號(hào)S推導(dǎo)出 S x 則稱(chēng)x是G的一個(gè)句型 若x僅由終結(jié)符組成 則稱(chēng)x為G的一個(gè)句子 2 句型和句子 句型 句子 2 2 3相關(guān)概念 2 2文法 注意 句型和句子都必須由開(kāi)始符號(hào)S推出 定義 文法描述的語(yǔ)言是該文法的所有句子的集合 記作L G 集合形式表示 L G S VT 例2 16 文法G S 0S1S 01描述的語(yǔ)言 L G 0n1n n 1 3 形式語(yǔ)言 2 2 3相關(guān)概念 2 2文法 例2 17 有文法G A A 0RA 01R A1 定義 若有文法G1 G2 它們描述的語(yǔ)言相同 即L G1 L G2 則稱(chēng)兩文法G1和G2等價(jià) 描述的語(yǔ)言L(fǎng) G 0n1n n 1 4 文法的等價(jià)性 2 2 3相關(guān)概念 2 2文法 2 2 3相關(guān)概念 2 2文法 5 遞歸規(guī)則和遞歸文法 遞歸文法 含有遞歸規(guī)則的文法稱(chēng)遞歸文法 遞歸規(guī)則 形如P 1P 2的規(guī)則稱(chēng)遞歸規(guī)則 若 1 則稱(chēng)左遞歸規(guī)則 若 2 則稱(chēng)右遞歸規(guī)則 P 1P 2的遞歸稱(chēng)間接遞歸 含間接遞歸的文法也是遞歸文法 2 3文法的分類(lèi)和化簡(jiǎn) 2 3 1文法的分類(lèi) 2 3 2兩個(gè)定理 2 3 3文法的化簡(jiǎn) 2 3文法的分類(lèi)和化簡(jiǎn) 1 0型文法 無(wú)限制文法或短語(yǔ)文法 2 3 1文法的分類(lèi) 定義2 7設(shè)G VN VT P S 如果它的每個(gè)產(chǎn)生式 滿(mǎn)足 VN VT 且 至少含有一個(gè)非終結(jié)符 則G是一個(gè)0型文法 結(jié)論0型文法的能力相當(dāng)于圖靈機(jī) 它所定義的語(yǔ)言為0型語(yǔ)言 任何0型語(yǔ)言都是遞歸可枚舉的 反之 遞歸可枚舉集也必定是一個(gè)0型語(yǔ)言 可由圖靈機(jī)來(lái)識(shí)別 2 3文法的分類(lèi)和化簡(jiǎn) 定義2 8設(shè)G VN VT P S 如果它的每個(gè)產(chǎn)生式 滿(mǎn)足 僅S 除外 則G是一個(gè)1型文法 另一種描述 文法的產(chǎn)生式形如 1A 2 1 2其中A VN VN VT 且 例2 18 1型文法G S S xSYZ xYZyZ yzxY xyZY YZyY yyzZ zz 2 1型文法 上下文有關(guān)文法 2 3 1文法的分類(lèi) 2 3文法的分類(lèi)和化簡(jiǎn) 3 2型文法 上下文無(wú)關(guān)文法 例2 19 2型文法G S S ET P T PF i E E T E TP F F P 定義2 9設(shè)G VN VT P S 如果它的每個(gè)產(chǎn)生式 中的 是一個(gè)非終結(jié)符 則G是一個(gè)2型文法或上下文無(wú)關(guān)文法 2 3 1文法的分類(lèi) 2 3文法的分類(lèi)和化簡(jiǎn) 4 3型文法 正規(guī)文法或正則文法 例2 20 3型文法G S S aAA aAA aS aA dAA d 定義2 10設(shè)G VN VT P S 如果它的每個(gè)產(chǎn)生式均形如A aB或A a其中A B VN a VT 2 3 1文法的分類(lèi) 2 3文法的分類(lèi)和化簡(jiǎn) 描述句法 描述詞法 VN aB a 2 3文法的分類(lèi)和化簡(jiǎn) 2 3 1文法的分類(lèi) 定理2 1 含有A 的文法產(chǎn)生的語(yǔ)言也可由不含A 的另一個(gè)文法產(chǎn)生 S 除外 定理2 2 若存在一個(gè)上下文有關(guān)文法G 則必存在另一個(gè)上下文有關(guān)文法G1 使得L G1 L G 且G1的開(kāi)始符號(hào)不出現(xiàn)在任何產(chǎn)生式的右邊 在使用上下文無(wú)關(guān)文法描述語(yǔ)言時(shí)不限制 產(chǎn)生式的使用 2 3文法的分類(lèi)和化簡(jiǎn) 2 3 2兩個(gè)定理 文法應(yīng)沒(méi)有多余的或有害的規(guī)則 化簡(jiǎn) 1 刪除形如A A的產(chǎn)生式 2 刪除不可到達(dá)的文法符號(hào)及其相應(yīng)的產(chǎn)生式 3 刪除不可終止的非終結(jié)符及其相應(yīng)的產(chǎn)生式 例2 21 文法G S aS W UU aV bV acW aW W是不可終止的V是不可到達(dá)的 化簡(jiǎn)后的文法G S aS UU a 2 3 3文法的化簡(jiǎn) 2 3文法的分類(lèi)和化簡(jiǎn) 1 語(yǔ)法樹(shù) 2 4文法的二義性 2 3文法的二義性 定義 語(yǔ)法樹(shù)是一棵數(shù)據(jù)結(jié)構(gòu)意義上的 樹(shù) 滿(mǎn)足四個(gè)條件 1 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記 字母表V的一個(gè)符號(hào) 2 根的標(biāo)記是S 文法的開(kāi)始符號(hào) 3 若一個(gè)結(jié)點(diǎn)n至少有一個(gè)它自身除外的子孫 且有標(biāo)記A 則A必在VN中 是非終結(jié)符 4 若標(biāo)記為A的結(jié)點(diǎn)n的直接子孫從左到右的次序是結(jié)點(diǎn)n1 n2 nk 其標(biāo)記分別為A1 A2 Ak 則A A1A2 Ak必是文法產(chǎn)生式集P中的一個(gè)產(chǎn)生式 對(duì)給定文法G 它的任何句型均能構(gòu)造與之相關(guān)的語(yǔ)法樹(shù) 2 4文法的二義性 2 3文法的二義性 i i i的語(yǔ)法樹(shù) 例2 22 對(duì)算術(shù)表達(dá)式文G E iE E EE E EE E i i i 的推導(dǎo)過(guò)程可以是 1 E E E E E E i E E i i E i i i 2 E E E E i E E i E i i i i i 3 E E E E i E E i i E i i i i 2 4文法的二義性 2 3文法的二義性 可見(jiàn) 1 一棵語(yǔ)法樹(shù)表示了一個(gè)句型的多種可能的不同推導(dǎo)過(guò)程 但未必是所有的 2 一個(gè)句型未必只有一棵語(yǔ)法樹(shù) 最左推導(dǎo) 在推導(dǎo)的任何一步 是句型 都是對(duì) 中的最左非終結(jié)符進(jìn)行替換 最右推導(dǎo) 在推導(dǎo)的任何一步 是句型 都是對(duì) 中的最右非終結(jié)符進(jìn)行替換 也稱(chēng)規(guī)范推導(dǎo) 推出的句型稱(chēng)規(guī)范句型 例如最左推導(dǎo) E E E i E i E E i i E i i i最右推導(dǎo) E E E E E E E E i E i i i i I 顯然 一棵語(yǔ)法樹(shù)表示的最左 右 推導(dǎo)是唯一的 2 4文法的二義性 2 3文法的二義性 i i i的語(yǔ)法樹(shù) 定義 若一個(gè)文法存在某個(gè)句子 它對(duì)應(yīng)兩棵 或以上 不同的語(yǔ)法樹(shù) 或它有兩個(gè)不同的最左 右 推導(dǎo) 則該文法是二義的 具有二義性 若產(chǎn)生某一上下文無(wú)關(guān)語(yǔ)言的每個(gè)文法均是二義的 則說(shuō)該語(yǔ)言先天二義 例2 23 與例2 22等價(jià)的非二義文法G E T E TT F T FF E i 愿望 文法非二義 2 4文法的二義性 2 3文法的二義性 ThankYou