程序設(shè)計(jì)語(yǔ)言基礎(chǔ).ppt

《程序設(shè)計(jì)語(yǔ)言基礎(chǔ).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《程序設(shè)計(jì)語(yǔ)言基礎(chǔ).ppt（49頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第2章程序語(yǔ)言基礎(chǔ)知識(shí)2 1程序設(shè)計(jì)語(yǔ)言基礎(chǔ)知識(shí)2 2編譯系統(tǒng)基本原理2 2 1文法2 2 2文法分析2 2 3詞法分析2 3C語(yǔ)言基礎(chǔ) 2 1程序設(shè)計(jì)語(yǔ)言概述低級(jí)語(yǔ)言 面向機(jī)器的語(yǔ)言 面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言 C Java Smalltalk 程序設(shè)計(jì)語(yǔ)言邏輯程序設(shè)計(jì)語(yǔ)言 Prolog 高級(jí)語(yǔ)言函數(shù)式的語(yǔ)言 Lisp 命令式程序設(shè)計(jì)語(yǔ)言 C Pascal 科學(xué)計(jì)算語(yǔ)言 Fortran 邏輯式語(yǔ)言是一類(lèi)以形式邏輯為基礎(chǔ)的語(yǔ)言 其代表就是建立關(guān)系理論和一階謂詞理論基礎(chǔ)上的Prolog 邏輯式語(yǔ)言有很強(qiáng)的推理能力 用于開(kāi)發(fā)專(zhuān)家系統(tǒng) 自然語(yǔ)言理解等 函數(shù)式語(yǔ)言是一類(lèi)以演算為基礎(chǔ)的語(yǔ)言 其基本概念來(lái)自為人工智能而設(shè)計(jì)的Lisp語(yǔ)言 這里所謂的函數(shù)跟數(shù)學(xué)中的函數(shù)概念是類(lèi)似的 命令式語(yǔ)言命令式語(yǔ)言又稱過(guò)程式語(yǔ)言 它是一種基于動(dòng)作的語(yǔ)言 所有的計(jì)算被看成工作序列 例 語(yǔ)言不是面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言 A JavaB C C SmalltalkD Fortran 2 2編譯系統(tǒng)基本原理2 2 1編譯原理基本知識(shí)語(yǔ)言處理程序分為兩個(gè)大類(lèi) 翻譯程序和解釋程序 翻譯程序 把用某種程序設(shè)計(jì)語(yǔ)言書(shū)寫(xiě)的程序翻譯成等價(jià)的機(jī)器語(yǔ)言 ?？键c(diǎn)1 程序編譯過(guò)程一般情況 編譯程序的流程如下圖所示 源程序 詞法分析 語(yǔ)法分析 語(yǔ)義分析 中間代碼生成 代碼優(yōu)化 目標(biāo)代碼生成 目標(biāo)程序 注意 并非所有的編譯程序都分成這幾個(gè)處理階段 有些編譯程序并不需要生成中間代碼 有些編譯程序不進(jìn)行代碼優(yōu)化 有些最簡(jiǎn)單的編譯程序在語(yǔ)法分析的同時(shí)產(chǎn)生目標(biāo)指令代碼 例 軟設(shè)2008年5月上午試題20 編譯器對(duì)高級(jí)語(yǔ)言源程序的處理過(guò)程可以劃分為詞法分析 語(yǔ)法分析 語(yǔ)義分析 中間代碼生成 代碼優(yōu)化 目標(biāo)代碼生成等幾個(gè)階段 其中 并不是每種編譯器都必需的 A 詞法分析和語(yǔ)法分析B 語(yǔ)義分析和中間代碼生成C 中間代碼生成和代碼優(yōu)化D 代碼優(yōu)化和目標(biāo)代碼生成 2 2編譯系統(tǒng)基本原理2 2 2文法1 文法定義文法G定義為四元組 VN VT P S 其中 1 VN為非終結(jié)符號(hào) 或語(yǔ)法實(shí)體 或變量 集 2 VT為終結(jié)符號(hào)集 3 P為產(chǎn)生式 也稱規(guī)則 的集合 4 S稱為識(shí)別符號(hào)或開(kāi)始符號(hào) 它是一個(gè)非終結(jié)符 一般約定 第一條產(chǎn)生式的左部是開(kāi)始符號(hào) 識(shí)別符號(hào) 一般情況 大寫(xiě)字母表示非終結(jié)符 小寫(xiě)字母表示終結(jié)符 例 文法G VN VT P S 其中VN S VT 0 1 P S 0S1 S 01 總結(jié) 一個(gè)文法定義的語(yǔ)言是終結(jié)符號(hào)串的集合 這些終結(jié)符號(hào)串應(yīng)能從文法的起始符號(hào)出發(fā)推導(dǎo)出來(lái) 2 稱為集合 的閉包 0 1 2 n 其中 n表示 的方冪 假設(shè) 是個(gè)符號(hào)串 n表示把 自身連接n次得到的符號(hào)串 例如 AB 求 0 1 2 n 其中 0 表示不包含任何符號(hào)的符號(hào)串 即空符號(hào)串 其長(zhǎng)度為0 1 AB 2 ABAB 定義 設(shè)G S 是一文法 如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來(lái)的 即有S x 則稱x是文法G S 的句型 若x僅有終結(jié)符號(hào)組成 即S x x屬于VT 則稱x為G S 的句子 2 2 3文法分析1 文法的類(lèi)型 1 0型文法 2 1型文法或上下文有關(guān)文法 3 2型文法或上下文無(wú)關(guān)文法 1 0型文法定義 設(shè)G VN VT P S 為一文法 如果它的每個(gè)產(chǎn)生式a b是這樣一種結(jié)構(gòu) a屬于 VN VT 且至少含有一個(gè)非終結(jié)符 而b屬于 VN VT 則G是一個(gè)0型文法 對(duì)0型文法產(chǎn)生式的形式作某些限制 就是1型 2型 3型文法 2 1型文法或上下文有關(guān)文法定義 設(shè)G VN VT P S 為一文法 若P中的每一個(gè)產(chǎn)生式a b均滿足 b a 僅僅S 除外 則G是1型文法或上下文有關(guān)文法 3 2型文法或上下文無(wú)關(guān)文法定義 設(shè)G VN VT P S 為一文法 若P中的每一個(gè)產(chǎn)生式a b滿足 a是一非終結(jié)符 b屬于 VN VT 則此文法為2型文法或上下文無(wú)關(guān)文法 例 文法G E i P E 其中P為 E iE E EE E EE E 今后 對(duì) 文法 一詞若無(wú)特別說(shuō)明 則均指上下文無(wú)關(guān)文法 例 2007年下半年上午第50 程序語(yǔ)言的大多數(shù)語(yǔ)法現(xiàn)象可用上下文無(wú)關(guān)文法描述 對(duì)于一個(gè)上下文無(wú)關(guān)文法G N T P S 其中N是非終結(jié)符號(hào)的集合 T是終結(jié)符號(hào)的集合 P是產(chǎn)生式集合 S是開(kāi)始符號(hào) 令集合V N T 那么G所描述的語(yǔ)言是的集合 A 從S出發(fā)推導(dǎo)出的包含V中所有符號(hào)的串B 從S出發(fā)推導(dǎo)出的僅包含T中符號(hào)的串C N中所有符號(hào)組成的串D T中所有符號(hào)組成的串 例 2009年上半年上午第50 設(shè)某語(yǔ)言的語(yǔ)法規(guī)則用上下文無(wú)關(guān)文法G N T P S 表示 其中N是非終結(jié)符號(hào)的集合 T是終結(jié)符號(hào)的集合 P是產(chǎn)生式集合 S是開(kāi)始符號(hào) 令V N T 那么符合該語(yǔ)言的句子是 A 從S出發(fā)推導(dǎo)的 僅包含T中符號(hào)的符號(hào)串B 從N中符號(hào)出發(fā)推導(dǎo)的 僅包含T中符號(hào)的符號(hào)串C 從S出發(fā)推導(dǎo)的 包含V中符號(hào)的符號(hào)串D 從N中符號(hào)出發(fā)推導(dǎo)的 包含V中符號(hào)的符號(hào)串 2 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù) 推導(dǎo)樹(shù) 語(yǔ)法樹(shù)或推導(dǎo)樹(shù) 是一種描述上下文無(wú)關(guān)文法的句型推導(dǎo)的直觀方法 通過(guò)語(yǔ)法樹(shù) 可以得到文法G的句型 從下面的例子說(shuō)明語(yǔ)法樹(shù)的構(gòu)造 例 G S A a b P S 其中P為 1 S aAS 2 A SbA 3 A SS 4 S a 5 A ba構(gòu)造G的語(yǔ)法樹(shù) 注意 如果在推導(dǎo)的任何一步 都是對(duì)其中的最左 最右 非終結(jié)符進(jìn)行替換 則稱這種推導(dǎo)為最左 最右 推導(dǎo) 例 軟設(shè)2008年5月上午試題21 已知某文法G S S 0S0S 1 從S推導(dǎo)出的符號(hào)串可用 n 0 描述 A 010 nB 0n10nC 1nD 01n0 例 2008年下半年上午第50 設(shè)某上下文無(wú)關(guān)文法如下 S 11 1001 S0 SS 則該文法所產(chǎn)生的所有二進(jìn)制字符串都具有的特點(diǎn)是 A 能被3整除B 0 1出現(xiàn)的次數(shù)相等C 0和1的出現(xiàn)次數(shù)都為偶數(shù)D 能被2整除 例 2008年下半年上午第48 給定文法G S 及其非終結(jié)符A FIRST A 定義為 從A出發(fā)能推導(dǎo)出的終結(jié)符號(hào)的集合 S是文法的起始符號(hào) 為非終結(jié)符 對(duì)于文法G S S L aL L S S其中 G S 包含的4個(gè)終結(jié)符號(hào)分別為 a 則FIRST S 的成員包括 48 A aB a C a 和 D a 和 2 2 4詞法分析考點(diǎn)1 詞法分析的功能詞法分析階段的主要功能如下 1 識(shí)別出源程序中意義獨(dú)立的最小詞法單位 單詞 并且確定其類(lèi)型 例如表示符 關(guān)鍵字 操作符還是數(shù)字等 2 刪除無(wú)用的空格 回車(chē)和其它與輸入介質(zhì)有關(guān)的無(wú)用符號(hào)以及程序注釋 3 報(bào)告分析時(shí)的錯(cuò)誤 經(jīng)過(guò)詞法分析后 源程序就轉(zhuǎn)換為單詞串 例 軟設(shè)2005年11月上午試題27 編譯程序進(jìn)行詞法分析時(shí)不能 A 過(guò)濾源程序中的注釋B 掃描源程序并識(shí)別句號(hào)C 指出出錯(cuò)的行號(hào)D 查出拼錯(cuò)的保留字 考點(diǎn)2 正規(guī)式和正規(guī)集 正規(guī)式和正規(guī)集正規(guī)式 用正規(guī)表達(dá)式 簡(jiǎn)稱正規(guī)式 可表示程序語(yǔ)言的單詞 正規(guī)集 正規(guī)式表示的集合稱為正規(guī)集 例 令 a b 上的正規(guī)式和相應(yīng)的正規(guī)集的例子有 正規(guī)式正規(guī)集a a a b a b ab ab a a aa 任意個(gè)a的串 a b a b aa ab ba bb 所有a b組成的串 a b a b aa bb 正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則 表正規(guī)文法到正規(guī)式的轉(zhuǎn)換規(guī)則 例 2007年下半年上午第48 正則表達(dá)式1 0 01 表示的集合元素的特點(diǎn)是 A 長(zhǎng)度為奇數(shù)的0 1串B 開(kāi)始和結(jié)尾字符必須為1的0 1串C 串的長(zhǎng)度為偶數(shù)的0 1串D 不包含字串011的0 1串 例 2009年上半年上午第49 由a b構(gòu)造且僅包含偶數(shù)個(gè)a的串的集合用正規(guī)式表示為 A a a b B b ab a C a ba b D a b aa 考點(diǎn)3 自動(dòng)機(jī)有窮自動(dòng)機(jī)分為兩類(lèi) 1 確定的有窮自動(dòng)機(jī) DeterministicFiniteAutomata 2 不確定的有窮自動(dòng)機(jī) NondeterministicFiniteAutomata 1 確定的有窮自動(dòng)機(jī) DFA 一個(gè)確定的有窮自動(dòng)機(jī) DFA M是一個(gè)五元組 M K f S Z 其中 1 K是一個(gè)有窮集 它的每個(gè)元素稱為一個(gè)狀態(tài) 2 是一個(gè)有窮字母表 它的每個(gè)元素稱為一個(gè)輸入字符 所以也稱 為輸入符號(hào)字母表 3 f是轉(zhuǎn)換函數(shù) 是在K K上的映像 即 如f ki a kj ki屬于K kj屬于K 表示當(dāng)前狀態(tài)為ki 輸入字符在a時(shí) 將轉(zhuǎn)換為下一個(gè)狀態(tài)kj 4 S屬于K S是唯一的一個(gè)初態(tài) 5 Z包含與K Z是一個(gè)終態(tài)集 終態(tài)也稱為可接受狀態(tài)或結(jié)束狀態(tài) 例 DFAM S U V Q a b f S Q 其中f定義為 f S a Uf V a Uf S b Vf V b Qf U a Qf Q a Qf U b Vf Q b Q請(qǐng)畫(huà)出該DFA的狀態(tài)轉(zhuǎn)換圖 補(bǔ)充 對(duì)于 中的任何一個(gè)串t 若存在一條從某一初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的道路 且這條道路上所有弧的標(biāo)記符依序連接成的串等于t 則稱t可為DFAM所識(shí)別 讀出或接受 若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn) 則空字可為M所識(shí)別 接受 2 不確定的有窮自動(dòng)機(jī) NFA 一個(gè)不確定的有窮自動(dòng)機(jī) NFA M是一個(gè)五元組 M K f S Z 其中 1 K是一個(gè)有窮集 它的每個(gè)元素稱為一個(gè)狀態(tài) 2 是一個(gè)有窮字母表 它的每個(gè)元素稱為一個(gè)輸入字符 3 f是轉(zhuǎn)換函數(shù) 是從K K上子集的映像 4 S屬于K S是一個(gè)非空的初態(tài)集 5 Z包含與K Z是一個(gè)終態(tài)集 例2 一個(gè)NFAM 0 1 2 3 4 a b f 0 2 4 其中f定義為 f 0 a 0 3 f 2 b 2 f 0 b 0 1 f 3 a 4 f 1 b 2 f 4 a 4 f 2 a 2 f 4 b 4 請(qǐng)畫(huà)出該NFA的狀態(tài)轉(zhuǎn)換圖 補(bǔ)充 對(duì)于 中的任何一個(gè)串t 若存在一條從某一初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的道路 且這條道路上所有弧的標(biāo)記符依序連接成的串等于t 則稱t可為NFAM所識(shí)別 讀出或接受 例2中的NFAM所能識(shí)別的是那些含有相繼兩個(gè)a或相繼兩個(gè)b的串 自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換過(guò)程如圖所示 對(duì)于代之對(duì)于代之對(duì)于代之 1 2 3 R1 R2 1 3 R1R2 1 2 1 2 3 1 2 1 3 R1 R2 R1R2 R3 R1 R2 R1 R3 R2 例 2006年下半年上午第45 46 下圖是一有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖 該自動(dòng)機(jī)所識(shí)別語(yǔ)言的特點(diǎn)是 1 等價(jià)的正規(guī)式為 2 1 A 由符號(hào)a b構(gòu)成且包含偶數(shù)個(gè)a的串B 由符號(hào)a b構(gòu)成且開(kāi)頭和結(jié)尾符號(hào)都為a的串C 由符號(hào)a b構(gòu)成的任意串D 由符號(hào)a b構(gòu)成且b的前后必須為a的串 2 A a b aa B a a b aC a b D a ba a 例 2009年上半年上午第48 下圖所示有限自動(dòng)機(jī)的特點(diǎn)是 A 識(shí)別的0 1串是以0開(kāi)頭且以1結(jié)尾B 識(shí)別的0 1串中1的數(shù)目為偶數(shù)C 識(shí)別的0 1串中0后面必須是1D 識(shí)別的0 1串中1不能連續(xù)出現(xiàn) 例 2008年上半年上午第50 某確定性有限自動(dòng)機(jī) DFA 的狀態(tài)轉(zhuǎn)換圖如下圖所示 令d 0 1 2 9 則以下字符串中 能被該DFA接受的是 A 3857B 1 2E 5C 123 67D 0 576E10 例 2008年上半年上午第48 有限自動(dòng)機(jī) FA 可用于識(shí)別高級(jí)語(yǔ)言源程序中的記號(hào) 單詞 FA可分為確定的有限自動(dòng)機(jī) DFA 和不確定的有限自動(dòng)機(jī) NFA 若某DFAD與某NFAM等價(jià) 則 A DFAD與NFAM的狀態(tài)數(shù)一定相等B DFAD與NFAM可識(shí)別的記號(hào)相同C NFAM能識(shí)別的正規(guī)集是DFAD所識(shí)別正規(guī)集的真子集D DFAD能識(shí)別的正規(guī)集是NFAM所識(shí)別正規(guī)集的真子集 2 3C語(yǔ)言基礎(chǔ)?？键c(diǎn) 參數(shù)傳遞方式參數(shù)傳遞有兩種方式 傳值方式和傳引用方式 傳值調(diào)用 以傳值調(diào)用方式進(jìn)行參數(shù)傳遞時(shí) 是將實(shí)參的值傳遞給形參 然后執(zhí)行被調(diào)用的函數(shù) 被調(diào)用的函數(shù)執(zhí)行時(shí)對(duì)形參的修改不影響實(shí)參的值 引用調(diào)用 以引用調(diào)用方式進(jìn)行參數(shù)傳遞時(shí) 是將實(shí)參的地址傳遞給形參 然后執(zhí)行被調(diào)用的函數(shù) 被調(diào)用的函數(shù)執(zhí)行時(shí)對(duì)形參的修改將反映在對(duì)應(yīng)實(shí)參變量中 例 函數(shù)f g 的定義如下所示 調(diào)用函數(shù)f時(shí)傳遞給形參a的值為1 若采用傳值 callbyvalue 的方式調(diào)用g c 則函數(shù)f的返回值為 1 若采用傳引用 callbyreference 的方式調(diào)用g c 則函數(shù)f的返回值為 2 f 形式參數(shù)a g 形式參數(shù)b 供選擇的答案 1 A 7B 5C 4D 3 2 A 3B 4C 5D 7 例 2007年上半年上午第49 函數(shù)t f 的定義如下所示 若調(diào)用函數(shù)t時(shí)傳遞給x的值為3 并且調(diào)用函數(shù)f 時(shí) 第一個(gè)參數(shù)采用傳值 callbyvalue 方式 第二個(gè)參數(shù)采用傳引用 callbyreference 方式 則函數(shù)t的返回值為 A 35B 24C 22D 11