高級(jí)語言及其語法描述.pptVIP

第2章高級(jí)語言及其語法描述 2 1編譯程序需要重點(diǎn)考慮的程序語言特性2 2符號(hào)和符號(hào)串2 3上下文無關(guān)文法2 4語法樹和二義性2 5形式語言介紹 2 1編譯程序需要重點(diǎn)考慮的程序語言特性 1 標(biāo)識(shí)符與名字 標(biāo)識(shí)符 字母打頭的字母數(shù)字串 名字 用標(biāo)識(shí)符表示的 帶有類型 值域的程序語言對象 高級(jí)語言之間的差異也是在這里體現(xiàn)的 例 aa 標(biāo)識(shí)符realaa 名字 實(shí)型變量 值域 運(yùn)算確定 2 名字的定義 影響 目標(biāo)程序的執(zhí)行效率的高低 能否靜態(tài)分配存儲(chǔ)空間 能否作靜態(tài)語義檢查 例 intaaaa 12 3 類型錯(cuò)誤 靜態(tài)語義檢查 全程變量 主程序中定義 局部變量 過程 函數(shù) 分程序 對象中定義 影響 3 變量的作用域 存儲(chǔ)空間能否復(fù)用 變量重名時(shí)的實(shí)現(xiàn)方法 如 采用最小作用域原則 4 語義 同一語句 在不同的語言中的含義可能不同 例 數(shù)組A 1 3 1 4 訪問 A 2 3 Pascal 按行分配 FORTRAN 按列分配 a23地址 a11地址 7 訪問 a23地址 a11地址 6 5 支持的數(shù)據(jù)類型 類型中允許的運(yùn)算 基本數(shù)據(jù)類型 整型 實(shí)型 布爾 字符 字符串 復(fù)雜數(shù)據(jù)類型 數(shù)組 記錄 結(jié)構(gòu) 指針 集合 類 6 支持的語句 分支 循環(huán) 過程 函數(shù) 7 存儲(chǔ)空間分配方式 靜態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配 函數(shù) 允許遞歸調(diào)用時(shí) 每一次調(diào)用需要一片數(shù)據(jù)區(qū)動(dòng)態(tài)數(shù)組動(dòng)態(tài)創(chuàng)建對象用戶可動(dòng)態(tài)申請 釋放數(shù)據(jù)空間 2 2符號(hào)和符號(hào)串 字母表 元素的非空 有窮集合 符號(hào) 字母表中的元素 例1 V a b c 字母表 V符號(hào) a b c例2 單詞符號(hào)集 if then begin 標(biāo)識(shí)符 字母表 單詞符號(hào)集符號(hào) if then begin 標(biāo)識(shí)符 3 符號(hào)串 符號(hào)組成的任何有窮序列 不包括任何符號(hào)的符號(hào)串稱為空串 空字 記為 注 符號(hào)串中符號(hào)的順序是重要的 例1 V a b c 符號(hào)串 a b c ab ba cc aab 其中 ab ba例2 單詞符號(hào)集 if then begin 標(biāo)識(shí)符 程序 由上述符號(hào)構(gòu)成的一個(gè)符號(hào)串但 任一符號(hào)串不一定是合法的程序 編譯研究 什么樣的符號(hào)串是合法的程序 4 串的長度 設(shè) 是字母表V中的符號(hào)串 的長度 中符號(hào)的個(gè)數(shù) 記為 5 串的聯(lián)結(jié) 設(shè) 是字母表V中的符號(hào)串 聯(lián)結(jié) 是指 將 放在 之后形成的符號(hào)串 記為 例 V a b c 且有 ab bca則 abbca bcaab 2 5特別 0 6 符號(hào)串集合 由符號(hào)串構(gòu)成的集合 記為 A x x A 7 符號(hào)串集合的乘積 若A B是V上的符號(hào)串集合 A B的乘積定義為 AB A B 例 若 A ab ba B ca acb 則 AB abca abacb baca baacb A A A 8 符號(hào)串的方冪 對任意符號(hào)串 0 1 2 n n 1 n 0 例 ab則 0 1 ab 2 abab 3 ababab 例 V a b c V0 長度 0的符號(hào)串的集合V1 a b c 長度 1的符號(hào)串的集合V2 aa ab ac ba bb bc ca cb cc 長度 2的符號(hào)串的集合V3 aaa aab aac aba abb abc 長度 3的符號(hào)串的集合V100長度 100的符號(hào)串的集合Vn長度 n的符號(hào)串的集合 9 集合V的方冪 對任意集合V V0 V1 V V2 VV V3 VVV Vn VVn 1 n 0 10 集合的閉包 設(shè)V為集合 V V1 V2 V3 Vn 正閉包V V0 V1 V2 V3 Vn 閉包兩種閉包之間的關(guān)系 V V0 V V VV V V 兩個(gè)集合的乘積 2 3上下文無關(guān)文法 1 產(chǎn)生式 產(chǎn)生規(guī)則 簡稱規(guī)則 一個(gè)有序?qū)?A 通常寫作 A 或A A 符號(hào) 稱為產(chǎn)生式左部 符號(hào)串 稱為 產(chǎn)生式右部 或 產(chǎn)生式的候選式 產(chǎn)生式的書寫方式稱為 BNF范式若有產(chǎn)生式 A 1A 2 A n寫成 A 1 2 n 候選式 2 文法G S 產(chǎn)生式的非空有窮集合 S是一個(gè)符號(hào) 它至少要在一條產(chǎn)生式中作為左部出現(xiàn) 稱為識(shí)別符號(hào)或開始符號(hào) 出現(xiàn)在產(chǎn)生式左部和右部中的所有符號(hào)形成字母表V 例 G E E E T TT T F FF i E V E T F i 產(chǎn)生式 識(shí)別符號(hào)或開始符號(hào) 3 非終結(jié)符號(hào) 給定文法G 把作為產(chǎn)生式左部出現(xiàn)的那些符號(hào)稱為非終結(jié)符號(hào) 或語法實(shí)體 所有非終結(jié)符號(hào)匯集成 非終結(jié)符號(hào)集 記為 VN 例 G E E E T TT T F FF i E V E T F i VN E T F 左部 4 終結(jié)符號(hào) 給定文法G 產(chǎn)生式中不屬于VN的那些符號(hào)稱為終結(jié)符號(hào) 所有終結(jié)符號(hào)匯集成 終結(jié)符號(hào)集 記為 VT 由定義知 V VN VT VN VT 例 G E E E T TT T F FF i E V E T F i VN E T F VT i 5 上下文無關(guān)文法的形式定義 上下文無關(guān)文法是一個(gè)四元組G S VN VT P S 其中 VN 非終結(jié)符號(hào)集合VT 終結(jié)符號(hào)集合P 產(chǎn)生式集合S 文法的識(shí)別符號(hào) 開始符號(hào) 6 直接推導(dǎo) 直接歸約 令G為文法 為符號(hào)串 若 A 是一個(gè)產(chǎn)生式 稱 A 直接推導(dǎo)出 或 直接歸約為 A 記為 A 例 G E E E E E E E E E i推導(dǎo) E E E E E E E E E i E E i i E i E E E i E i i E i 7 推導(dǎo) 歸約 若存在一個(gè)直接推導(dǎo)序列 1 2 3 n稱 1可以出推導(dǎo) n 或 n可歸約為 1記為 1 n 推導(dǎo)步驟 0步 讀作 號(hào)推導(dǎo)出 或 即 例 G E E E E E E E E E i從E E到i i i的幾種可能推導(dǎo) E E E E E i E E i i E i i iE E E i E E i E i i i i iE E E E E E E i E i i i i iE E E E E E i E E i i i i i 8 最左推導(dǎo) 最右推導(dǎo) 推導(dǎo)中若每一步直接推導(dǎo) 替換的都是符號(hào)串的最左非終結(jié)符 稱為最左推導(dǎo) 替換的都是符號(hào)串的最右非終結(jié)符 稱為最右推導(dǎo) 說明 例 G E E E E E E E E E iE E E E E E i E E i i E i i i 只要符號(hào)串中有產(chǎn)生式的左部符號(hào) 就能從該符號(hào)串推導(dǎo)出新的符號(hào)串 即 推導(dǎo)過程未結(jié)束 非終結(jié) 所以左部符號(hào)稱為非終結(jié)符號(hào)Non terminalsymbol符號(hào)串中沒有產(chǎn)生式的左部符號(hào)了 那么推導(dǎo)過程就必須終結(jié) 所以不在產(chǎn)生式的左部出現(xiàn)的符號(hào)稱為終結(jié)符號(hào)Terminalsymbol故 非終結(jié)符集 VN終結(jié)符集 VT 9 句型 句子 令G S 為一文法 如果符號(hào)串 是由文法的開始符號(hào)推導(dǎo)出來的 即 S 則稱 是句型 若S 且 VT 則稱 是句子 即 僅由終結(jié)符號(hào)構(gòu)成的句型稱為句子 例 G E E E E E E E E E iE E E E E E i E E i i E i i i句型 E E E E E E i E E i i E i i i句子 i i i 例 G1 E E E E E E E E E iL G1 E 帶有 擴(kuò)號(hào)等運(yùn)算的算術(shù)表達(dá)式 說明 句型集 VN VT 即 句型集是符號(hào)串集的子集L G S VT 即 語言是終結(jié)符號(hào)串集的子集句子是由文法決定的 不同的文法可以產(chǎn)生相同的語言 即 G1 S G2 S 但L G1 S L G2 S 則稱文法G1 S G2 S 等價(jià) G1 E G2 E 但L G1 E L G2 E 稱 文法G1 E G2 E 等價(jià) 即 不同的文法 可以產(chǎn)生相同的語言 例 G1 E E E E E E E E E iL G1 E 帶有 擴(kuò)號(hào)等運(yùn)算的算術(shù)表達(dá)式 G2 E E E T E T TT T F FF E iL G2 E 帶有 擴(kuò)號(hào)等運(yùn)算的算術(shù)表達(dá)式 例 G S S bAA aA a句子 S bA baS bA baA baaS bA baA baaA baaa S bA baA baaA baa aA baa a L G S ban n 1 例 G S S PQP aPb abQ Qc 句子 S PQ abQ abS PQ aPbQ aaPbbQ a ab bS PQ a ab bQc a ab bc c L G S anbncm n 1 m 0 2 4語法樹和二義性 1 語法樹 用圖表示一個(gè)句型的推導(dǎo)過程 通常表示成一棵倒立的樹 樹根表示文法開始符號(hào) S A a1a2a3 an 若有直接推導(dǎo) A a1a2 an 則從結(jié)點(diǎn)A出發(fā) 劃出n個(gè)分支 指向n個(gè)結(jié)點(diǎn) a1 a2 an 語法樹末端結(jié)點(diǎn) 再?zèng)]有分支從中向下射出的結(jié)點(diǎn) 從左向右遍歷語法樹末端結(jié)點(diǎn) 形成該樹表示的句型 例 G E E E T TT T F FF i E i i i推導(dǎo)過程 E E T T T T F T F F T i F T i i T i i F i i i末端結(jié)點(diǎn) i i i語法樹對應(yīng)的句型 i i i 2 子樹 由語法樹的某個(gè)結(jié)點(diǎn) 子樹根 連同從它向下射出的部分組成的 子樹的末端結(jié)點(diǎn)形成一個(gè)短語 相對于子樹根 子樹 i1 F2 i1 T3 i2 F1 i1 i2 T2 i1 i2 E2 i3 F3 i3 T1 i1 i2 i3 E1 總結(jié) 例 G E E E T TT T F FF i E 句型 T F F推導(dǎo)1 E E T T T T T F T F F推導(dǎo)2 E E T E T F E F F T F F推導(dǎo)3 E E T E T F T T F T F F 對于每個(gè)語法樹 至少存在一個(gè)推導(dǎo) 對于每個(gè)推導(dǎo) 都有一個(gè)對應(yīng)的語法樹 若不同的推導(dǎo)產(chǎn)生相同的語法樹 稱這些推導(dǎo)是等價(jià)的 3 二義性 句子的二義性 若文法G中 某一個(gè)句子有兩棵不同的語法樹 稱該句子是二義的 例 G E E E E E E E E E i句子 i i i如 2 3 4 語法樹1 2 3 4 20 2 3 4 14 語法樹2 句子二義性的等價(jià)定義若文法G中 某一個(gè)句子存在兩個(gè)不同的最左推導(dǎo) 稱該句子是二義的 若文法G中 某一個(gè)句子存在兩個(gè)不同的最右推導(dǎo) 稱該句子是二義的 例 G E E E E E E E E E i句子 i i 最左推導(dǎo) E E E i E i i最右推導(dǎo) E E E E i i i 誤解 有兩個(gè)不同的推導(dǎo) 就是二義的句子 文法的二義性 如果一個(gè)文法包含有一個(gè)二義性的句子 稱該文法是二義的 說明 文法的二義性是由句子決定的 不是由句型決定的 例 G E E T iT T T T T存在句型 T T T 對應(yīng)兩棵語法樹 語法樹1 但 該文法只有一個(gè)句子 i 文法是無二義的 語法樹2 文法的二義問題 不可判定的 即 不存在一種算法 能在有限的步驟內(nèi)判定文法二義 原因 句子是無限的 判定了N個(gè)句子無二義 可能第N 1個(gè)句子就是二義的 目前的做法 找一組充分條件 滿足條件的文法就是無二義的 如 算符優(yōu)先文法就是無二義文法 語言的二義性 一般不提判定標(biāo)準(zhǔn) 原因 一個(gè)語言可能由多個(gè)等價(jià)的文法定義 即 G1 S G2 S 但可能 L G1 S L G2 S 對一個(gè)語言 可能存在無二