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