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

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