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

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

2 1形式語言 第2章形式語言和文法 2 4文法的二義性 2 3文法的分類和化簡(jiǎn) 2 2文法 2 1形式語言 2 1 1語言的概念 2 1 2語言的定義方式 語言 符號(hào)串的集合 元素 符號(hào)串 該語言的一個(gè)句子 字母表 符號(hào)串中符號(hào)的來源 句子的構(gòu)成 按一定規(guī)則 程序設(shè)計(jì)語言 程序的集合句子 程序 一個(gè)或長(zhǎng)或短的字符串 字母表 固定的字符集 語言可以使用的所有符號(hào) 編程時(shí)必須遵循一定的規(guī)則 語法規(guī)則和語義規(guī)則 語言的描述工具 文法 2 1 1語言的概念 2 1語言 1 什么是語言 1 有窮字母表一個(gè)元素的非空有窮集合 其中的元素也稱符號(hào) 每個(gè)語言均有一固定的字母表 例 C語言的字母表由基本字符集 字母 數(shù)字 括號(hào) 專用字符 保留字 int long if struct static typedef sizeof 等組成 2 1 1語言的概念 2 1語言 2 符號(hào)串的相關(guān)概念和術(shù)語 通常用V 或其他大寫字母表示 例如V 0 1 a b c d e 等 2 符號(hào)串字母表中的符號(hào)組成的任何有窮序列 相關(guān)術(shù)語 長(zhǎng)度 符號(hào)串中符號(hào)的個(gè)數(shù) 符號(hào)串x的長(zhǎng)度表示為 x x m 0 空符號(hào)串 無任何符號(hào)的串 簡(jiǎn)稱空串 用 表示 0省略寫法 z x z xz x 2 1 1語言的概念 2 1語言 例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語言的概念 2 1語言 方冪 符號(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語言的概念 2 1語言 4 符號(hào)串的集合若集合A中的所有元素都是某字母表上的符號(hào)串 則稱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語言的概念 2 1語言 閉包 若指定字母表 則 表示 上的所有有窮長(zhǎng)的串的集合 0 1 2 n 稱為集合 的閉包 1 2 n 稱為集合 的正閉包 成立的等式 0 若符號(hào)串x是 的元素 則表示為x 否則x 2 1 1語言的概念 2 1語言 語言的句子個(gè)數(shù)有限 枚舉語言的句子有很多甚至是無窮多個(gè) 給出一些規(guī)則說明這個(gè)語言的句子的組成結(jié)構(gòu) 規(guī)則 文法規(guī)則 2 1 2語言的定義方式 2 1語言 例2 5 文法規(guī)則 student English computer I you he am is are have study a an the 文法規(guī)則的作用 1 嚴(yán)格定義了一個(gè)語言的句子的結(jié)構(gòu) 2 用適當(dāng)條數(shù)的規(guī)則描述了一個(gè)語言的全部句子 2 1 2語言的定義方式 2 1語言 2 2文法 2 2 1文法的形式定義 2 2 2文法的表示方法 2 2 3相關(guān)概念 2 2文法 表示語言中的語法單位的符號(hào) 常用尖括號(hào) 括起 一個(gè)非終結(jié)符一般可以推導(dǎo)出終結(jié)符串 一個(gè)語言可使用的所有非終結(jié)符組成的集合稱為非終結(jié)符集 用VN表示 1 終結(jié)符 不可分割的符號(hào)串 是組成句子的最基本的單位 一個(gè)語言允許使用的所有終結(jié)符組成的集合稱為終結(jié)符集 用VT表示 2 非終結(jié)符 2 2 1文法的形式定義 2 2文法 3 規(guī)則 重寫規(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)或開始符號(hào) S VN 且至少在一條規(guī)則中作為左部出現(xiàn) P 規(guī)則 產(chǎn)生式 的集合 用V表示VN VT 稱G的字母表或詞匯表 4 文法 2 2 1文法的形式定義 2 2文法 G S 0S1或G S S 0S1或G S 0S1 01S 01S 01注意 左部相同的產(chǎn)生式可合并 用 表示 或 簡(jiǎn)化表示 只寫出規(guī)則 產(chǎn)生式 且第一條規(guī)則的左部是開始符號(hào) 用 括起的或大寫字母表示非終結(jié)符 不用 括起的或小寫字母表示終結(jié)符 文法G也常寫成G S 方括號(hào)中的S為開始符號(hào) 例2 6 有一文法G VN VT S P 其中 VN S VT 0 1 開始符號(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 開始符號(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語言中對(duì)標(biāo)識(shí)符的規(guī)定是字母開頭 長(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可選 即可有可無 例2 10 C程序設(shè)計(jì)語言的條件語句的文法規(guī)則BNF表示 if if else 擴(kuò)展BNF表示 if else 2 2 2文法的表示方法 2 2文法 3 語法圖表示法 例2 11 C語言條件語句的語法圖 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滿足v w 則稱v 應(yīng)用規(guī)則 直接產(chǎn)生w 或稱w是v的直接推導(dǎo) 反過來稱w直接歸約到v 記作v w 1 推導(dǎo)和歸約 2 2 3相關(guān)概念 2 2文法 定義 如果存在直接推導(dǎo)序列 v w0 w1 w2 wn w則稱v推導(dǎo) 產(chǎn)生 出w 推導(dǎo)長(zhǎng)度為n 反過來稱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可由開始符號(hào)S推導(dǎo)出 S x 則稱x是G的一個(gè)句型 若x僅由終結(jié)符組成 則稱x為G的一個(gè)句子 2 句型和句子 句型 句子 2 2 3相關(guān)概念 2 2文法 注意 句型和句子都必須由開始符號(hào)S推出 定義 文法描述的語言是該文法的所有句子的集合 記作L G 集合形式表示 L G S VT 例2 16 文法G S 0S1S 01描述的語言 L G 0n1n n 1 3 形式語言 2 2 3相關(guān)概念 2 2文法 例2 17 有文法G A A 0RA 01R A1 定義 若有文法G1 G2 它們描述的語言相同 即L G1 L G2 則稱兩文法G1和G2等價(jià) 描述的語言L G 0n1n n 1 4 文法的等價(jià)性 2 2 3相關(guān)概念 2 2文法 2 2 3相關(guān)概念 2 2文法 5 遞歸規(guī)則和遞歸文法 遞歸文法 含有遞歸規(guī)則的文法稱遞歸文法 遞歸規(guī)則 形如P 1P 2的規(guī)則稱遞歸規(guī)則 若 1 則稱左遞歸規(guī)則 若 2 則稱右遞歸規(guī)則 P 1P 2的遞歸稱間接遞歸 含間接遞歸的文法也是遞歸文法 2 3文法的分類和化簡(jiǎn) 2 3 1文法的分類 2 3 2兩個(gè)定理 2 3 3文法的化簡(jiǎn) 2 3文法的分類和化簡(jiǎn) 1 0型文法 無限制文法或短語文法 2 3 1文法的分類 定義2 7設(shè)G VN VT P S 如果它的每個(gè)產(chǎn)生式 滿足 VN VT 且 至少含有一個(gè)非終結(jié)符 則G是一個(gè)0型文法 結(jié)論0型文法的能力相當(dāng)于圖靈機(jī) 它所定義的語言為0型語言 任何0型語言都是遞歸可枚舉的 反之 遞歸可枚舉集也必定是一個(gè)0型語言 可由圖靈機(jī)來識(shí)別 2 3文法的分類和化簡(jiǎn) 定義2 8設(shè)G VN VT P S 如果它的每個(gè)產(chǎ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文法的分類 2 3文法的分類和化簡(jiǎn) 3 2型文法 上下文無關(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型文法或上下文無關(guān)文法 2 3 1文法的分類 2 3文法的分類和化簡(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文法的分類 2 3文法的分類和化簡(jiǎn) 描述句法 描述詞法 VN aB a 2 3文法的分類和化簡(jiǎn) 2 3 1文法的分類 定理2 1 含有A 的文法產(chǎn)生的語言也可由不含A 的另一個(gè)文法產(chǎn)生 S 除外 定理2 2 若存在一個(gè)上下文有關(guān)文法G 則必存在另一個(gè)上下文有關(guān)文法G1 使得L G1 L G 且G1的開始符號(hào)不出現(xiàn)在任何產(chǎn)生式的右邊 在使用上下文無關(guān)文法描述語言時(shí)不限制 產(chǎn)生式的使用 2 3文法的分類和化簡(jiǎn) 2 3 2兩個(gè)定理 文法應(yīng)沒有多余的或有害的規(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文法的分類和化簡(jiǎn) 1 語法樹 2 4文法的二義性 2 3文法的二義性 定義 語法樹是一棵數(shù)據(jù)結(jié)構(gòu)意義上的 樹 滿足四個(gè)條件 1 每個(gè)結(jié)點(diǎn)都有一個(gè)標(biāo)記 字母表V的一個(gè)符號(hào) 2 根的標(biāo)記是S 文法的開始符號(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)的語法樹 2 4文法的二義性 2 3文法的二義性 i i i的語法樹 例2 22 對(duì)算術(shù)表達(dá)式文G E iE E EE E EE E i i i 的推導(dǎo)過程可以是 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文法的二義性 可見 1 一棵語法樹表示了一個(gè)句型的多種可能的不同推導(dǎo)過程 但未必是所有的 2 一個(gè)句型未必只有一棵語法樹 最左推導(dǎo) 在推導(dǎo)的任何一步 是句型 都是對(duì) 中的最左非終結(jié)符進(jìn)行替換 最右推導(dǎo) 在推導(dǎo)的任何一步 是句型 都是對(duì) 中的最右非終結(jié)符進(jìn)行替換 也稱規(guī)范推導(dǎo) 推出的句型稱規(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 顯然 一棵語法樹表示的最左 右 推導(dǎo)是唯一的 2 4文法的二義性 2 3文法的二義性 i i i的語法樹 定義 若一個(gè)文法存在某個(gè)句子 它對(duì)應(yīng)兩棵 或以上 不同的語法樹 或它有兩個(gè)不同的最左 右 推導(dǎo) 則該文法是二義的 具有二義性 若產(chǎn)生某一上下文無關(guān)語言的每個(gè)文法均是二義的 則說該語言先天二義 例2 23 與例2 22等價(jià)的非二義文法G E T E TT F T FF E i 愿望 文法非二義 2 4文法的二義性 2 3文法的二義性 ThankYou