北航研究生課程程序語言設(shè)計(jì)原理教程第02章.ppt

第1頁,第二章 程序設(shè)計(jì)語言設(shè)計(jì)概述,2.1 表示與抽象 2.2 設(shè)計(jì)目標(biāo) 2.3 設(shè)計(jì)準(zhǔn)則 2.4 規(guī)格說明,第2頁,2.1 表示與抽象,表示是人為制造的符號(hào)組合以表達(dá)我們需要表達(dá)的意思。 程序是程序設(shè)計(jì)語言表示的計(jì)算 float n; /n 是浮點(diǎn)數(shù)變量 sqrt(n) ; /對(duì)n取平方根 同一程序的高級(jí)語言表示、經(jīng)翻譯后的匯編碼表示、機(jī)器碼表示就是該程序在不同抽象層次上的表示。,第3頁,2.1 表示與抽象,程序在不同抽象層次表示的關(guān)系 例：x = x + 1在機(jī)器碼上就有兩種方法。,從內(nèi)存代表x的地址中取出 值放在運(yùn)算器中。 加1，將結(jié)果放于某臨時(shí)單元。 將臨時(shí)單元內(nèi)容做類型檢查（必要時(shí)轉(zhuǎn)換）并放入x中。,從內(nèi)存代表x的地址中取出 值放在運(yùn)算器中。 加1，將結(jié)果放入x地址中。,第4頁,2.1 表示與抽象,兒子10歲女兒8歲母親35歲 幾年后兒女歲數(shù)之和大于等于母親？,u=m-s-d,每人每年增1歲每增 一年比較一次，滿足 條件即所求。,read(m,s,d); u=m-s-d; print(u),read(m,s,d); u=0; while(m+us+d+2u) u+; print(u);,m,s,d,u,指令集,客觀世界 問題抽象,模型世界 數(shù)學(xué)模型 模擬模型,程序世界 以程序世界術(shù)語 表示描述模型,機(jī)器世界 以機(jī)器的術(shù)語 實(shí)現(xiàn)程序,圖2-1 計(jì)算機(jī)解題的四個(gè)世界,第5頁,2.2 PL設(shè)計(jì)目標(biāo),定義一組能表示某種范型的特征集，每個(gè)特征有嚴(yán)格定義并可在機(jī)器上高效實(shí)現(xiàn)，程序員可靈活運(yùn)用這些特征表達(dá)它所希望的任何計(jì)算。,模型有力 Model Power 語義清晰 Semantic Clarity 移植性好 Portability 可讀性好 Readability,方便 Convenience 簡(jiǎn)單 Simplicity 高效 Efficiency 靈活性 Flexibility,第6頁,2.3 設(shè)計(jì)準(zhǔn)則,頻度準(zhǔn)則 越常用越簡(jiǎn)單 方便、可讀 結(jié)構(gòu)一致 程序結(jié)構(gòu)和計(jì)算的邏輯結(jié)構(gòu)一致 可讀、方便 局部性 Locality 只有全局變量Basic 不鼓勵(lì)全局變量Pascal,C 無全局變量函數(shù)式 Java 詞法內(nèi)聚 Lexical Coherence 變量在使用處就近聲明 （Pascal聲明和語句嚴(yán)格分開）,(lambda (x y) (let (x 3.5) (y (+ a 2) (+ (* x y) (+ (* x y) (- x y) (- x y) 3.5 (+ a 2) x.y.(x*y)+(x-y) 3.5 (a+2),第7頁,續(xù),語法一致性 GO TO (L1, L2, , Ln), I I=1n GO TO N, (L1, L2, , Ln) ASSIGN Li TO N N=L1.Ln 安全性Security 語言編譯系統(tǒng)自動(dòng)找出安全漏洞，不能彌補(bǔ)也要支持 安全性強(qiáng)類型，即每個(gè)計(jì)算操作運(yùn)算之前類型必須確定 C 留給程序員 過程參數(shù)不檢查 一般不安全,第8頁,續(xù),正交性和正規(guī)性(Orthogonality & Regularity) 正交: 每個(gè)語言特征都是獨(dú)立的, 增減不影響其它 正規(guī): 每一約定或規(guī)則無一例外 不正規(guī)：數(shù)組不能作返回值, 不能賦值 函數(shù)不能做參數(shù) 不正交不正規(guī),第9頁,續(xù),數(shù)據(jù)隱藏 (Data hiddening) 封裝,以名字封裝內(nèi)部數(shù)據(jù)設(shè)計(jì)者可見使用者不可見 局部性不一定封裝，如： Do l0 I=1,10,2 當(dāng)I=7時(shí) GOTO 20 10 CONTINUE 20 . R=I 可以,此時(shí)R=7.0,. . .,第10頁,續(xù),抽象表達(dá) 抽取因子、遞歸表達(dá)、高層模塊名、 常量名=常量表達(dá)式（易于維護(hù)） 先抽象再修飾具體（如同自然語言） static const int maxlndex=MAX_LENGTH_1 MATHLIB.TRIANG COS(X) 可移植性 力圖不依賴環(huán)境 預(yù)定義機(jī)制、預(yù)處理程序,第11頁,形式語法：以形式結(jié)構(gòu)規(guī)則的語言元素組合規(guī)則 微語法 詞法 Lexicon 宏語法 定義特征的規(guī)則,2.4 程序設(shè)計(jì)語言規(guī)格說明 語言參考手冊(cè),2.4.1 語法規(guī)格說明,第12頁,T是終結(jié)符號(hào)串的有限集。N是非終結(jié)符號(hào)串的有限集。 TN = ，即它們是不相交的。S是起始符號(hào)串， SN。 P是產(chǎn)生式， 一般形式是: ，(TN)* “”表示左端可推導(dǎo)出右端， 如， ， 則可寫為：| 如果產(chǎn)生式將語言的非終結(jié)符中的每一個(gè)標(biāo)記都推得為終結(jié)符號(hào)， 則這一組產(chǎn)生式集即為該語言的全部文法。,2.4.1.1 文法 文法 產(chǎn)生符合語法的語言（句子集合）規(guī)則，如： G=(S,N,T,P) SN,TN=*,第13頁,整數(shù)的產(chǎn)生式表示法： 設(shè)0|1|2|3|4|5|6|7|8|9 則 一位數(shù)是整數(shù) 兩位數(shù)也是 n位數(shù)也是 n個(gè) 這勢(shì)必造成產(chǎn)生式臃腫， 如果寫成： | | ,續(xù),第14頁,續(xù),Chomsky的四種文法 產(chǎn)生式 左符號(hào)集右符號(hào)集 由左符號(hào)集推導(dǎo)出右符號(hào)集 0型文法 (NT)+，(NT)* 遞歸可枚舉語言 圖靈機(jī)可以識(shí)別 1型文法 A B ,(NT)*， AN， B(NT)+ 上下文相關(guān)文法上下文敏感語言 線性有界自動(dòng)機(jī)可識(shí)別 2型文法 A (NUT)*, AN 上下文無關(guān)文法語言 非確定下推自動(dòng)機(jī)可識(shí)別,第15頁,續(xù),3型文法 ABB T*, A,BN 正則文法 正則語言 有限自動(dòng)機(jī)可以識(shí)別 可消除右端非終法符 P可以成為終結(jié)符表達(dá)式 例： N=S,R,Q, T=a,b,c P=SRa，SQ，RQb，Qc 則有 SRaQbacba|SQc RQbcb Qc 簡(jiǎn)單語言用 3型，匯編，詞法子語言 最常用 2型 0、1型無法判定二義性, 不常用,0,1,2,3,第16頁,2.4.1.2 上下文無關(guān)文法,文法的遞歸表示法 0123|4|5|6|7|89 一位數(shù) 二位數(shù) . n 位數(shù) n個(gè) 左遞歸 右遞歸尾遞歸,第17頁,2.4.1.3 BNF 和EBNF,BNF： :=代替 BNF表達(dá)能力同EBNF 指示非終結(jié) 終結(jié)符直接寫出(或黑體) 或者 有擴(kuò)充： 括號(hào)內(nèi)容是可選的 括號(hào)內(nèi)容可重復(fù)0至多次 或擴(kuò)充： C+ Kleene加 C可重復(fù)1至多次 C* Kleene星 C可重復(fù)0至多次,第18頁,續(xù),BNF示例 := | := + |- | := | | , := +|- := | := + := | ,第19頁,EBNF： 左端取消, 空白加- 減少遞歸表示再加(,),., 盡量用正則表達(dá)式 終結(jié)符號(hào)加 號(hào)或黑體,續(xù),第20頁,續(xù),program := ； . program-heading := program ( ). program-parameters := . identifier-list := ， . program-block := . block := . variable-declaration-part := var ； ； . variable-declaration := ； . statement-part := compound-statement.,第21頁,compound-statement := begin end. statement-sequence := ； . statement:= ：(|). simple-statement := | | | . structured-statement := | | | .,續(xù),第22頁,2.4.1.4 語法圖,同EBNF 取消 以短路表示 以迥環(huán)表示,非終結(jié)符,走向,復(fù)合語句,;,begin,end,語句,終結(jié)符,終結(jié)符,第23頁,2.4.1.5 語法分析,語法規(guī)格說明定義了該語言程序合法的特征和語句。語言處理器則通過語法分析接受合法的程序，這就叫做程序釋義（Parsing a Program）,釋義過程是產(chǎn)生式生成句子的逆過程。,語法分析的算法可歸為兩類： “自頂向下” 釋義則從文法的起始符開始，按可能產(chǎn)生的表達(dá)式尋找語句相同的結(jié)構(gòu)匹配。每一步都產(chǎn)生下一個(gè)可能的源符號(hào)串，找到再往下走。 “由底向上”釋義則相反，它先查找源代碼的各個(gè)符號(hào)串，看它能否匹配歸結(jié)為產(chǎn)生式左邊的非終結(jié)符，如果有含混則向前多讀入k個(gè)符號(hào)串，為此歸約下去，一個(gè)短語一個(gè)短語，最后到達(dá)起始符號(hào)串，歸約的過程就形成了釋義樹。,第24頁,begin x ：= 17 ； writeIn ( x ) end,標(biāo)識(shí)符,變量標(biāo)識(shí)符,變量訪問,無符號(hào)常量,完整變量,無符號(hào)數(shù),無符號(hào)整數(shù),因子,項(xiàng),簡(jiǎn)單表達(dá)式,表達(dá)式,過程標(biāo)識(shí)符,標(biāo)識(shí)符,變量標(biāo)識(shí)符,完整變量,變量訪問,因子,項(xiàng),簡(jiǎn)單表達(dá)式,表達(dá)式,write參數(shù),writeln參數(shù)表,賦值語句,簡(jiǎn)單語句,語句,過程語句,簡(jiǎn)單語句,語句,語句序列,復(fù)合語句,第25頁,2.4.2 語義規(guī)格說明,操作語義:每一動(dòng)作的凈效果 指稱語義: 語義函數(shù)（語法特征） 語義域上的值 用輔助函數(shù)表征的值 用函數(shù)的數(shù)學(xué)模型只看最后效果，不考慮操作過程 execute C1; C2 env sto = execute C2 env (execute C1 env sto) execute while E do C= let execute_while env sto = if evaluate E env sto = truth_value true then execute_while env (execute C env sto) else sto in execute_while,第26頁,2.4.2 語義規(guī)格說明,公理語義：從程序的前題推導(dǎo)出結(jié)論 前題 f1, f2, ., fn 結(jié)論 f0 f1:pSq公式也是定理 p,q前后置斷言, S語句集 x=a and y=b 只要前提為真結(jié)論亦為真 t:=x; x:=x+y; y:=t x=a+b and y=a,第27頁,續(xù),specification LISTS sorts List NATURALS formal sort Component Operations empty_list : List cons(_，_) : Component,ListList headof_ : List Component tailof_ : List List lengthof_ : List NATURALSs variables c: Component l: List equations headof cons (c,l)=c tailof cons (