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

《北航研究生課程程序語(yǔ)言設(shè)計(jì)原理教程第02章.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《北航研究生課程程序語(yǔ)言設(shè)計(jì)原理教程第02章.ppt（28頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第1頁(yè),第二章 程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)概述,2.1 表示與抽象 2.2 設(shè)計(jì)目標(biāo) 2.3 設(shè)計(jì)準(zhǔn)則 2.4 規(guī)格說(shuō)明,第2頁(yè),2.1 表示與抽象,表示是人為制造的符號(hào)組合以表達(dá)我們需要表達(dá)的意思。 程序是程序設(shè)計(jì)語(yǔ)言表示的計(jì)算 float n; //n 是浮點(diǎn)數(shù)變量 sqrt(n) ; //對(duì)n取平方根 同一程序的高級(jí)語(yǔ)言表示、經(jīng)翻譯后的匯編碼表示、機(jī)器碼表示就是該程序在不同抽象層次上的表示。,第3頁(yè),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頁(yè),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,,指令集,,,,,,,客觀世界 問(wèn)題抽象,,模型世界 數(shù)學(xué)模型 模擬模型,,程序世界 以程序世界術(shù)語(yǔ) 表示描述模型,,機(jī)器世界 以機(jī)器的術(shù)語(yǔ) 實(shí)現(xiàn)程序,,圖2-1 計(jì)算機(jī)解題的四個(gè)世界,第5頁(yè),2.2 PL設(shè)計(jì)目標(biāo),定義一組能表示某種范型的特征集，每個(gè)特征有嚴(yán)格定義并可在機(jī)器上高效實(shí)現(xiàn)，程序員可靈活運(yùn)用這些特征表達(dá)它所希望的任何計(jì)算。,模型有力 Model Power 語(yǔ)義清晰 Semantic Clarity 移植性好 Portability 可讀性好 Readability,方便 Convenience 簡(jiǎn)單 Simplicity 高效 Efficiency 靈活性 Flexibility,第6頁(yè),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 無(wú)全局變量函數(shù)式 Java 詞法內(nèi)聚 Lexical Coherence 變量在使用處就近聲明 （Pascal聲明和語(yǔ)句嚴(yán)格分開(kāi)）,((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頁(yè),續(xù),語(yǔ)法一致性 GO TO (L1, L2, …, Ln), I I={1n} GO TO N, (L1, L2, …, Ln) ASSIGN Li TO N N={L1.Ln} 安全性Security 語(yǔ)言—編譯系統(tǒng)自動(dòng)找出安全漏洞，不能彌補(bǔ)也要支持 安全性→強(qiáng)類型，即每個(gè)計(jì)算操作運(yùn)算之前類型必須確定 C 留給程序員 過(guò)程參數(shù)不檢查 一般不安全,第8頁(yè),續(xù),正交性和正規(guī)性(Orthogonality & Regularity) 正交: 每個(gè)語(yǔ)言特征都是獨(dú)立的, 增減不影響其它 正規(guī): 每一約定或規(guī)則無(wú)一例外 不正規(guī)：數(shù)組不能作返回值, 不能賦值 函數(shù)不能做參數(shù) 不正交→不正規(guī),第9頁(yè),續(xù),數(shù)據(jù)隱藏 (Data hiddening) 封裝,以名字封裝內(nèi)部數(shù)據(jù)設(shè)計(jì)者可見(jiàn)使用者不可見(jiàn) 局部性不一定封裝，如： Do l0 I=1,10,2 當(dāng)I=7時(shí) GOTO 20 10 CONTINUE 20 …. R=I 可以,此時(shí)R=7.0,. . .,第10頁(yè),續(xù),抽象表達(dá) 抽取因子、遞歸表達(dá)、高層模塊名、 常量名=常量表達(dá)式（易于維護(hù)） 先抽象再修飾具體（如同自然語(yǔ)言） static const int maxlndex=MAX_LENGTH_1 MATHLIB.TRIANG COS(X) 可移植性 力圖不依賴環(huán)境 預(yù)定義機(jī)制、預(yù)處理程序,第11頁(yè),形式語(yǔ)法：以形式結(jié)構(gòu)規(guī)則的語(yǔ)言元素組合規(guī)則 微語(yǔ)法 詞法 Lexicon 宏語(yǔ)法 定義特征的規(guī)則,2.4 程序設(shè)計(jì)語(yǔ)言規(guī)格說(shuō)明 ——語(yǔ)言參考手冊(cè),2.4.1 語(yǔ)法規(guī)格說(shuō)明,第12頁(yè),T是終結(jié)符號(hào)串的有限集。N是非終結(jié)符號(hào)串的有限集。 T∩N = Φ，即它們是不相交的。S是起始符號(hào)串， S∈N。 P是產(chǎn)生式， 一般形式是:α→β α，β∈(T∪N)* “→”表示左端可推導(dǎo)出右端， 如α→β， α→Υ， α→δ則可寫為：α→β|Υ|δ 如果產(chǎn)生式將語(yǔ)言的非終結(jié)符中的每一個(gè)標(biāo)記都推得為終結(jié)符號(hào)， 則這一組產(chǎn)生式集即為該語(yǔ)言的全部文法。,2.4.1.1 文法 文法 產(chǎn)生符合語(yǔ)法的語(yǔ)言（句子集合）規(guī)則，如： G=(S,N,T,P) S∈N,T∩N=Φ*,第13頁(yè),整數(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頁(yè),續(xù),Chomsky的四種文法 產(chǎn)生式 左符號(hào)集→右符號(hào)集 由左符號(hào)集推導(dǎo)出右符號(hào)集 0型文法 α→β α∈(N∪T)+，β∈(N∪T)* 遞歸可枚舉語(yǔ)言 圖靈機(jī)可以識(shí)別 1型文法 α A β→αBβ α,β∈(N∪T)*， A∈N， B∈(N∪T)+ 上下文相關(guān)文法上下文敏感語(yǔ)言 線性有界自動(dòng)機(jī)可識(shí)別 2型文法 A→α α∈(NUT)*, A∈N 上下文無(wú)關(guān)文法語(yǔ)言 非確定下推自動(dòng)機(jī)可識(shí)別,第15頁(yè),續(xù),3型文法 A→αB｜Bα α∈T*, A,B∈N 正則文法 正則語(yǔ)言 有限自動(dòng)機(jī)可以識(shí)別 可消除右端非終法符 P可以成為終結(jié)符表達(dá)式 例： N={S,R,Q}, T={a,b,c} P={S→Ra，S→Q，R→Qb，Q→c} 則有 S→Ra→Qba→cba|S→Q→c R→Qb→cb Q→c 簡(jiǎn)單語(yǔ)言用 3型，匯編，詞法子語(yǔ)言 最常用 2型 0、1型無(wú)法判定二義性, 不常用,,0,,,,1,,2,,3,第16頁(yè),2.4.1.2 上下文無(wú)關(guān)文法,文法的遞歸表示法 →0｜1｜2｜3|4|5|6|7|8｜9 → 一位數(shù) → 二位數(shù) →. n 位數(shù) n個(gè) →｜ 左遞歸 右遞歸尾遞歸,第17頁(yè),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頁(yè),續(xù),BNF示例 ::= | ::= + |- | ::= | | , ::= [ +|-] ::= { | } ::= + ::= { | },,第19頁(yè),EBNF： 左端取消, 空白加‘-’ 減少遞歸表示再加‘(’,‘)’,‘.’, 盡量用正則表達(dá)式 終結(jié)符號(hào)加‘ ’號(hào)或黑體,續(xù),第20頁(yè),續(xù),program ::= ； .. program-heading ::= program [ ( )]. program-parameters ::= . identifier-list ::= {， } . program-block ::= . block ::= . variable-declaration-part ::= [var ； { ； }]. variable-declaration ::= ； . statement-part ::= compound-statement.,第21頁(yè),compound-statement ::= begin end. statement-sequence ::= {； }. statement::=[ ：](|). simple-statement ::= | | | . structured-statement ::= | | | .,續(xù),第22頁(yè),2.4.1.4 語(yǔ)法圖,同EBNF 取消[ ] 以→短路表示 { } 以→迥環(huán)表示,,非終結(jié)符,走向,,,,復(fù)合語(yǔ)句,;,,,,,,,,,,begin,,end,,語(yǔ)句,,,,,,終結(jié)符,終結(jié)符,,,,,,,,,,第23頁(yè),2.4.1.5 語(yǔ)法分析,語(yǔ)法規(guī)格說(shuō)明定義了該語(yǔ)言程序合法的特征和語(yǔ)句。語(yǔ)言處理器則通過(guò)語(yǔ)法分析接受合法的程序，這就叫做程序釋義（Parsing a Program）,釋義過(guò)程是產(chǎn)生式生成句子的逆過(guò)程。,語(yǔ)法分析的算法可歸為兩類： “自頂向下” 釋義則從文法的起始符開(kāi)始，按可能產(chǎn)生的表達(dá)式尋找語(yǔ)句相同的結(jié)構(gòu)匹配。每一步都產(chǎn)生下一個(gè)可能的源符號(hào)串，找到再往下走。 “由底向上”釋義則相反，它先查找源代碼的各個(gè)符號(hào)串，看它能否匹配歸結(jié)為產(chǎn)生式左邊的非終結(jié)符，如果有含混則向前多讀入k個(gè)符號(hào)串，為此歸約下去，一個(gè)短語(yǔ)一個(gè)短語(yǔ)，最后到達(dá)起始符號(hào)串，歸約的過(guò)程就形成了釋義樹(shù)。,第24頁(yè),begin x ：= 17 ； writeIn ( x ) end,標(biāo)識(shí)符,變量標(biāo)識(shí)符,變量訪問(wèn),無(wú)符號(hào)常量,完整變量,無(wú)符號(hào)數(shù),無(wú)符號(hào)整數(shù),因子,項(xiàng),簡(jiǎn)單表達(dá)式,表達(dá)式,過(guò)程標(biāo)識(shí)符,標(biāo)識(shí)符,變量標(biāo)識(shí)符,完整變量,變量訪問(wèn),因子,項(xiàng),簡(jiǎn)單表達(dá)式,表達(dá)式,,,,,,,write參數(shù),writeln參數(shù)表,賦值語(yǔ)句,簡(jiǎn)單語(yǔ)句,語(yǔ)句,過(guò)程語(yǔ)句,簡(jiǎn)單語(yǔ)句,語(yǔ)句,語(yǔ)句序列,復(fù)合語(yǔ)句,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,第25頁(yè),2.4.2 語(yǔ)義規(guī)格說(shuō)明,操作語(yǔ)義:每一動(dòng)作的凈效果 指稱語(yǔ)義: 語(yǔ)義函數(shù)（語(yǔ)法特征） →語(yǔ)義域上的值 用輔助函數(shù)表征的值 用函數(shù)的數(shù)學(xué)模型只看最后效果，不考慮操作過(guò)程 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頁(yè),2.4.2 語(yǔ)義規(guī)格說(shuō)明,公理語(yǔ)義：從程序的前題推導(dǎo)出結(jié)論 前題 f1, f2, ., fn 結(jié)論 f0 f1:{p}S{q}公式也是定理 {p},{q}前后置斷言, S語(yǔ)句集 x=a and y=b 只要前提為真結(jié)論亦為真 t:=x; x:=x+y; y:=t x=a+b and y=a,第27頁(yè),續(xù),specification LISTS sorts List NATURALS formal sort Component Operations empty_list : List cons(_，_) : Component,List→List 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ù)語(yǔ)義：把語(yǔ)義模型的集合看成是一個(gè)代數(shù)結(jié)構(gòu)，模型簇 對(duì)應(yīng)為代數(shù)系統(tǒng) 用代數(shù)方法描述數(shù)據(jù)類型 A=(V, Op),第28頁(yè),2.4.3 上下文規(guī)格說(shuō)明,限定程序短語(yǔ)的良構(gòu)規(guī)則 簡(jiǎn)化語(yǔ)法語(yǔ)義形式化 使上下文無(wú)關(guān)文法得以使用,