《第二章程式语言的语法.ppt》由会员分享，可在线阅读，更多相关《第二章程式语言的语法.ppt（43页珍藏版）》请在三一文库上搜索。
1、1,第二章 程式語言的語法,陳維魁 博士 .tw 儒林圖書公司,2,大綱,基本定義 文法四要素 文法的分類 正規文法分類 B.N.F. 文法 剖析樹,模擬兩可的文法 懸置else問題 描述程式語言語法的方式 語意的描述 精選習題,3,基本定義,字元集 一組有限符號的集合稱之為字元 集 字元集有二類 ASCII Code Set EBCDIC Code Set,4,ascii table,5,基本定義,ASCII Code Set American Standard Code for Information Interchange 的縮寫 標準的 ASCII Code 有7個位元 可表示 27
2、= 128 種不同的字元 一般使用在 IBM PC 及Apple II上 現今使用的 ASCII Code 已經擴充為8個位 元，稱之為 ASCII-8,6,基本定義,EBCDIC Code Set Extended Binary Code Decimal Interchange Code 的縮寫 標準的EBCDIC Code有8個位元 可表示 28=256 種不同的字元 一般使用在IBM 360及FACOM機器上,7,基本定義,字串(String) 定義 S=t1t2.tn， ti T 其中 T 為字元集 S 是由 T 中的字元所組成的一串列 n=4 則 S 可能為 abcd，ABCD，AE
3、FG 等等 字串的長度 設 S=t1t2.tn則 S 的長度可表為S=n S 的長度為 n,8,基本定義,字串的連接 設 p 與 q 為二字串且 p=m1m2mu ，q=n1n2nv pq=m1m2.mun1n2.nv 表示二字串的連接且pq=u+v pq 字串的長度為 u+v,9,基本定義,空字串 通常以 “” 表示空字串，且=0， 有時空字串也可以 “”表示,10,基本定義,T 由 T 中的字元所組成任意長度 的字串的集合 實例 假設 T=p，q 則 =，p，q，pp，qq，pq，qp，pppp.,11,基本定義,語言 (Language) 若 L 為一語言，則 L 是 的一組子集合(su
4、bset) 實例 假設 T=p，q 則 L 可為 p，pq，qp，.或 ppp，qqq，pqp，qpq，. 等等 只要是 的子集合即可,12,基本定義,語言的乘積(product) L1 與 L2 的乘積 L1L2=aba L1，b L2 範例 L1=p，q L2=m，n，mn，nm L1L2=pm，pn，pmn，pnm，qm，qn， qmn，qnm,13,基本定義,語言 L 的次方 (Power) 定義 Lo= Ln=LLn-1 範例 假設 L=p，pq，q L0= ， L1=L，L2=LL，.,14,基本定義,L*的定義 L* 又稱“Kleene Closure of L” L 做任意次乘
5、積(product) 的集合 L*=L0L1L2.Ln.,15,基本定義,L+ 的定義 又稱為“Transitive Closure of L” L+=L1L2L3.Ln.,16,文法四要素,T 終端符號 表示不能再以其他符號來替代 N 非終端符號 表示可以再以其他符號來替代 而N與T須具以下的關係：NT=,17,文法四要素,S starting symbol 起始符號 從事文法推演之步驟由S開始 P production rule 文法產生規則,18,文法的分類,Type 0 無任何限制 Type 1 Context sensitive grammar Type 2 Context free
6、 grammar Type 3 正規文法 (regular grammar),19,正規文法分類,右線性正規文法 right linear regular grammar 文法產生規需滿足 AuB or A u，其中 A,BN，u T 左線性正規文法 left linear regular grammar 文法產生規則需滿足 uAB or A u，其中 A,BN，u T,20,B.N.F. 文法,B.N.F. grammar Backus Naur Form grammar type 2 grammar context-free grammar,21,B.N.F.文法符號,“:=” 表示“定義
7、為” “” 表示出現0次,1次,. “” 表示出現0次或1次 “” 表示“OR” ” 表示非終端符號,22,範例,Using the following B.N.F. grammar to construct a parse tree for the statement below A:=B DIV 10 + CD :=id:= :=+- := DIV :=idint(),23,推導過程, := id := := + := + := DIV + := DIV + := id DIV + := id DIV int + :=id DIV int + * :=id DIV int + * := i
8、d DIV int + id * := id DIV int + id * id,24,剖析樹,25,剖析樹 (parse tree),定義 根據語言的 B.N.F. 描述,將運算式轉換成相對應的樹狀結構,則稱此樹狀結構為剖析樹,26,模擬兩可的文法,ambiguous grammar 根據語言的 B.N.F. 描述,對同一句子(sentence)可繪出二個或二個以上不同的剖析樹,則稱此語言的文法是模擬兩可的,27,模擬兩可的文法,Draw 2 different parse tree for id+id+id, using the grammar EE+Eid,對id+id+id可畫出二個不
9、同的剖析樹如下,故此文法是模擬兩可的,28,模擬兩可的文法,Is the following grammar ambiguous? Describe your response carefully? SaSbSbSaS,如 abab 1. S 2. S a S b S a S b S b S a S a S b S ,29,懸置else問題,dangling else 的意義 若有一敘述如下: if 條件A then if 條件B then E1 else E2 則 else 將無法確定要與第一個或第二個 if 結合這種現象,就是所謂的 dangling else 問題,30,懸置else問題
10、,各種語言解決 dangling else 的方法 PASCAL 利用begin-end作為分界，來解決懸置else問題 ALGOL 60 利用begin-end作為分界，來解決懸置else問題 ALGOL 68 利用if.fi作為分界，來解決懸置else的問題 近代高階程式語言 多利用”最接近未結合原則”來解決此問題,31,描述程式語言語法的方式,B.N.F.法 請參考sec. 2-4之敘述 語法圖(Syntax Diagram) 推移圖(Transition Diagram),32,語法圖,：表示非終端符號 :表示終端符號 P:=Q1Q2Qn,33,語法圖,P:=Q1 Q2Qn P:=Q,
11、34,推移圖,1+0+對應的推移圖,其中S0為起始狀態，而S2為終止狀態,35,推移圖,10*1+對應的推移圖,其中S0為起始狀態，而S2為終止狀態,36,推移圖,10*110*1 對應的推移圖,其中S0為起始狀態，而S4為終止狀態,37,語意的描述,靜態語意(static semantics) 動態語意(dynamic semantics) 解釋型語意(interpretive semantics) 公理型語意(axiomatic semantics) 符號型語意(denotational semantics),38,靜態語意,意義 由於有許多語言規則沒有辦法單純的用BNF文法來做一個描述，
12、因此必需要用其他的規則來加以處理 作法 在程式執行之前或語言處理器翻譯時處理 範例 變數必須先宣告再引用 屬性文法(attribute grammar) 屬性文法是一種可以描述靜態語意之方法,39,動態語意,解釋型語意(interpretive semantics) 公理型語意(axiomatic semantics) 符號型語意(denotational semantics),40,解釋型語意,意義 又稱為操作型語意(operational semantics) ,在本方法中定義抽象機器(abstract machine)，此抽象機器可支援一組簡單的操作並提供一些簡單的資料結構供使用。通常以
13、暫存器或記憶體位置來表示計算機執行的狀態 作法 語言的語意在此類型中，被定義成為如何將程式轉換成在抽象機器上執行的碼 範例 如PL/1語言的維也納定義語言(Vienna Definition Language),41,公理型語意,意義 公理型語意提供數學規則來表示程式執行之結果。 作法 對於程式語言的每個語法單元均提供一個數學規則來定義。也就是利用數學推論來証明程式的正確性,42,符號型語意,意義 符號型語意利用數學函數來定義程式。 作法 syntax entity object,43,精選習題,請解釋下列名詞： 關鍵字(key word) 保留字(reserved word) 懸置指標(dangling pointer) 懸置標記引用(dangling label reference) 剖析樹(parse tree)的樹葉節點是否有特殊意義,