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

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