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

第1頁,第二章 程序設(shè)計語言設(shè)計概述,2.1 表示與抽象 2.2 設(shè)計目標 2.3 設(shè)計準則 2.4 規(guī)格說明,第2頁,2.1 表示與抽象,表示是人為制造的符號組合以表達我們需要表達的意思。 程序是程序設(shè)計語言表示的計算 float n; /n 是浮點數(shù)變量 sqrt(n) ; /對n取平方根 同一程序的高級語言表示、經(jīng)翻譯后的匯編碼表示、機器碼表示就是該程序在不同抽象層次上的表示。,第3頁,2.1 表示與抽象,程序在不同抽象層次表示的關(guān)系 例：x = x + 1在機器碼上就有兩種方法。,從內(nèi)存代表x的地址中取出 值放在運算器中。 加1，將結(jié)果放于某臨時單元。 將臨時單元內(nèi)容做類型檢查（必要時轉(zhuǎn)換）并放入x中。,從內(nèi)存代表x的地址中取出 值放在運算器中。 加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ù)學模型 模擬模型,程序世界 以程序世界術(shù)語 表示描述模型,機器世界 以機器的術(shù)語 實現(xiàn)程序,圖2-1 計算機解題的四個世界,第5頁,2.2 PL設(shè)計目標,定義一組能表示某種范型的特征集，每個特征有嚴格定義并可在機器上高效實現(xiàn)，程序員可靈活運用這些特征表達它所希望的任何計算。,模型有力 Model Power 語義清晰 Semantic Clarity 移植性好 Portability 可讀性好 Readability,方便 Convenience 簡單 Simplicity 高效 Efficiency 靈活性 Flexibility,第6頁,2.3 設(shè)計準則,頻度準則 越常用越簡單 方便、可讀 結(jié)構(gòu)一致 程序結(jié)構(gòu)和計算的邏輯結(jié)構(gòu)一致 可讀、方便 局部性 Locality 只有全局變量Basic 不鼓勵全局變量Pascal,C 無全局變量函數(shù)式 Java 詞法內(nèi)聚 Lexical Coherence 變量在使用處就近聲明 （Pascal聲明和語句嚴格分開）,(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)自動找出安全漏洞，不能彌補也要支持 安全性強類型，即每個計算操作運算之前類型必須確定 C 留給程序員 過程參數(shù)不檢查 一般不安全,第8頁,續(xù),正交性和正規(guī)性(Orthogonality & Regularity) 正交: 每個語言特征都是獨立的, 增減不影響其它 正規(guī): 每一約定或規(guī)則無一例外 不正規(guī)：數(shù)組不能作返回值, 不能賦值 函數(shù)不能做參數(shù) 不正交不正規(guī),第9頁,續(xù),數(shù)據(jù)隱藏 (Data hiddening) 封裝,以名字封裝內(nèi)部數(shù)據(jù)設(shè)計者可見使用者不可見 局部性不一定封裝，如： Do l0 I=1,10,2 當I=7時 GOTO 20 10 CONTINUE 20 . R=I 可以,此時R=7.0,. . .,第10頁,續(xù),抽象表達 抽取因子、遞歸表達、高層模塊名、 常量名=常量表達式（易于維護） 先抽象再修飾具體（如同自然語言） static const int maxlndex=MAX_LENGTH_1 MATHLIB.TRIANG COS(X) 可移植性 力圖不依賴環(huán)境 預(yù)定義機制、預(yù)處理程序,第11頁,形式語法：以形式結(jié)構(gòu)規(guī)則的語言元素組合規(guī)則 微語法 詞法 Lexicon 宏語法 定義特征的規(guī)則,2.4 程序設(shè)計語言規(guī)格說明 語言參考手冊,2.4.1 語法規(guī)格說明,第12頁,T是終結(jié)符號串的有限集。N是非終結(jié)符號串的有限集。 TN = ，即它們是不相交的。S是起始符號串， SN。 P是產(chǎn)生式， 一般形式是: ，(TN)* “”表示左端可推導(dǎo)出右端， 如， ， 則可寫為：| 如果產(chǎn)生式將語言的非終結(jié)符中的每一個標記都推得為終結(jié)符號， 則這一組產(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個 這勢必造成產(chǎn)生式臃腫， 如果寫成： | | ,續(xù),第14頁,續(xù),Chomsky的四種文法 產(chǎn)生式 左符號集右符號集 由左符號集推導(dǎo)出右符號集 0型文法 (NT)+，(NT)* 遞歸可枚舉語言 圖靈機可以識別 1型文法 A B ,(NT)*， AN， B(NT)+ 上下文相關(guān)文法上下文敏感語言 線性有界自動機可識別 2型文法 A (NUT)*, AN 上下文無關(guān)文法語言 非確定下推自動機可識別,第15頁,續(xù),3型文法 ABB T*, A,BN 正則文法 正則語言 有限自動機可以識別 可消除右端非終法符 P可以成為終結(jié)符表達式 例： N=S,R,Q, T=a,b,c P=SRa，SQ，RQb，Qc 則有 SRaQbacba|SQc RQbcb Qc 簡單語言用 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個 左遞歸 右遞歸尾遞歸,第17頁,2.4.1.3 BNF 和EBNF,BNF： :=代替 BNF表達能力同EBNF 指示非終結(jié) 終結(jié)符直接寫出(或黑體) 或者 有擴充： 括號內(nèi)容是可選的 括號內(nèi)容可重復(fù)0至多次 或擴充： C+ Kleene加 C可重復(fù)1至多次 C* Kleene星 C可重復(fù)0至多次,第18頁,續(xù),BNF示例 := | := + |- | := | | , := +|- := | := + := | ,第19頁,EBNF： 左端取消, 空白加- 減少遞歸表示再加(,),., 盡量用正則表達式 終結(jié)符號加 號或黑體,續(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)生的表達式尋找語句相同的結(jié)構(gòu)匹配。每一步都產(chǎn)生下一個可能的源符號串，找到再往下走。 “由底向上”釋義則相反，它先查找源代碼的各個符號串，看它能否匹配歸結(jié)為產(chǎn)生式左邊的非終結(jié)符，如果有含混則向前多讀入k個符號串，為此歸約下去，一個短語一個短語，最后到達起始符號串，歸約的過程就形成了釋義樹。,第24頁,begin x ：= 17 ； writeIn ( x ) end,標識符,變量標識符,變量訪問,無符號常量,完整變量,無符號數(shù),無符號整數(shù),因子,項,簡單表達式,表達式,過程標識符,標識符,變量標識符,完整變量,變量訪問,因子,項,簡單表達式,表達式,write參數(shù),writeln參數(shù)表,賦值語句,簡單語句,語句,過程語句,簡單語句,語句,語句序列,復(fù)合語句,第25頁,2.4.2 語義規(guī)格說明,操作語義:每一動作的凈效果 指稱語義: 語義函數(shù)（語法特征） 語義域上的值 用輔助函數(shù)表征的值 用函數(shù)的數(shù)學模型只看最后效果，不考慮操作過程 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 (c,l)=l tailof empty_list = empty_list lengthof empty_list = 0 lengthof cons (c,l)=succ (length of l) end specification,代數(shù)語義：把語義模型的集合看成是一個代數(shù)結(jié)構(gòu)，模型簇 對應(yīng)為代數(shù)系統(tǒng) 用代數(shù)方法描述數(shù)據(jù)類型 A=(V, Op),第28頁,2.4.3 上下文規(guī)格說明,限定程序短語的良構(gòu)規(guī)則 簡化語法語義形式化 使上下文無關(guān)文法得以使用,