1、1,第二章 程式語言的語法,陳維魁 博士.tw儒林圖書公司,2,大綱,基本定義文法四要素文法的分類正規文法分類B.N.F. 文法剖析樹,模擬兩可的文法懸置else問題描述程式語言語法的方式語意的描述精選習題,3,基本定義,字元集一組有限符號的集合稱之為字元 集字元集有二類ASCII Code SetEBCDIC Code Set,4,ascii table,5,基本定義,ASCII Code SetAmerican Standard Code for Information Interchange 的縮寫標準的 ASCII Code 有7個位元可表示 27 = 128 種不同的字元一般使用在
2、IBM PC 及Apple II上現今使用的 ASCII Code 已經擴充為8個位 元，稱之為 ASCII-8,6,基本定義,EBCDIC Code SetExtended 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，AEFG 等等字串的長度設 S=t1t2.tn則 S 的長
3、度可表為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 是 的一組子集合(subset)實例假設 T=p，q 則 L 可為 p，pq，qp，.或 ppp
4、，qqq，pqp，qpq，. 等等只要是 的子集合即可,12,基本定義,語言的乘積(product)L1 與 L2 的乘積L1L2=aba L1，b L2範例L1=p，qL2=m，n，mn，nmL1L2=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 做任意次乘積(product) 的集合L*=L0L1L2.Ln.,15,基本定義,L+ 的定義又稱為“Transi
5、tive Closure of L”L+=L1L2L3.Ln.,16,文法四要素,T終端符號表示不能再以其他符號來替代N非終端符號表示可以再以其他符號來替代而N與T須具以下的關係：NT=,17,文法四要素,Sstarting symbol起始符號從事文法推演之步驟由S開始Pproduction rule文法產生規則,18,文法的分類,Type 0無任何限制Type 1Context sensitive grammarType 2Context free grammarType 3正規文法 (regular grammar),19,正規文法分類,右線性正規文法right linear regul
6、ar 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. grammarBackus Naur Form grammartype 2 grammarcontext-free grammar,21,B.N.F.文法符號,“:=”表示“定義為”“”表示出現0次,1次,.“”表示出現0次或1次“”表示“OR”表示非終端符號,22,範例,Using the following B.N.F. grammar to
7、 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 + * := id DIV int + id * := id DIV int + id * id,24,剖析樹,25,剖析樹 (parse tree),定義根據語言的 B.N.F. 描述,將運算式轉換成相對應的樹
8、狀結構,則稱此樹狀結構為剖析樹,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可畫出二個不同的剖析樹如下,故此文法是模擬兩可的,28,模擬兩可的文法,Is the following grammar ambiguous? Describe your response carefully?
9、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問題,各種語言解決 dangling else 的方法PASCAL利用begin-end作為分界，來解決懸置else問題 ALGOL 60利用begin-end作為分界，來解決懸置else問題ALGOL
10、68利用if.fi作為分界，來解決懸置else的問題 近代高階程式語言多利用”最接近未結合原則”來解決此問題,31,描述程式語言語法的方式,B.N.F.法請參考sec. 2-4之敘述語法圖(Syntax Diagram)推移圖(Transition Diagram),32,語法圖,：表示非終端符號 :表示終端符號 P:=Q1Q2Qn,33,語法圖,P:=Q1 Q2Qn P:=Q,34,推移圖,1+0+對應的推移圖,其中S0為起始狀態，而S2為終止狀態,35,推移圖,10*1+對應的推移圖,其中S0為起始狀態，而S2為終止狀態,36,推移圖,10*110*1 對應的推移圖,其中S0為起始狀態，而
11、S4為終止狀態,37,語意的描述,靜態語意(static semantics)動態語意(dynamic semantics)解釋型語意(interpretive semantics)公理型語意(axiomatic semantics)符號型語意(denotational semantics),38,靜態語意,意義由於有許多語言規則沒有辦法單純的用BNF文法來做一個描述，因此必需要用其他的規則來加以處理 作法在程式執行之前或語言處理器翻譯時處理範例變數必須先宣告再引用屬性文法(attribute grammar)屬性文法是一種可以描述靜態語意之方法,39,動態語意,解釋型語意(interpret
12、ive semantics)公理型語意(axiomatic semantics)符號型語意(denotational semantics),40,解釋型語意,意義又稱為操作型語意(operational semantics) ,在本方法中定義抽象機器(abstract machine)，此抽象機器可支援一組簡單的操作並提供一些簡單的資料結構供使用。通常以暫存器或記憶體位置來表示計算機執行的狀態作法語言的語意在此類型中，被定義成為如何將程式轉換成在抽象機器上執行的碼範例如PL/1語言的維也納定義語言(Vienna Definition Language),41,公理型語意,意義公理型語意提供數學規則來表示程式執行之結果。作法對於程式語言的每個語法單元均提供一個數學規則來定義。也就是利用數學推論來証明程式的正確性,42,符號型語意,意義符號型語意利用數學函數來定義程式。作法syntax entity object,43,精選習題,請解釋下列名詞：關鍵字(key word)保留字(reserved word)懸置指標(dangling pointer)懸置標記引用(dangling label reference)剖析樹(parse tree)的樹葉節點是否有特殊意義,
