陳維魁 博士 wkchen@pchome.com.tw 儒林圖書公司 第二章 程式語言的語法 陳維魁 博士 wkchen@pchome.com.tw 儒林圖書公司

大綱 基本定義 文法四要素 文法的分類 正規文法分類 B.N.F. 文法 剖析樹 模擬兩可的文法 懸置else問題 描述程式語言語法的方式 語意的描述 精選習題

基本定義 字元集 一組有限符號的集合稱之為字元 集 字元集有二類 ASCII Code Set EBCDIC Code Set

基本定義 ASCII Code Set American Standard Code for Information Interchange 的縮寫 標準的 ASCII Code 有7個位元 可表示 27 = 128 種不同的字元 一般使用在 IBM PC 及Apple II上 現今使用的 ASCII Code 已經擴充為8個位 元，稱之為 ASCII-8

基本定義 EBCDIC Code Set Extended Binary Code Decimal Interchange Code 的縮寫 可表示 28=256 種不同的字元 一般使用在IBM 360及FACOM機器上

基本定義 字串(String) 定義 字串的長度 S=t1t2...tn， ti  T 其中 T 為字元集 n=4 則 S 可能為 abcd，ABCD，AEFG 等等 字串的長度 設 S=t1t2...tn則 S 的長度可表為│S│=n S 的長度為 n

基本定義 字串的連接 設 p 與 q 為二字串且 p=m1m2…mu ，q=n1n2…nv p‧q=m1m2...mun1n2...nv 表示二字串的連接且│p‧q│=u+v p‧q 字串的長度為 u+v

基本定義 空字串 通常以 “ε” 表示空字串，且│ε│=0， 有時空字串也可以 “”表示

基本定義 T＊ 由 T 中的字元所組成任意長度 的字串的集合 實例 假設 T={p，q} 則Ｔ＊ ={ε，p，q，pp，qq，pq，qp，pppp...}

基本定義 語言 (Language) 若 L 為一語言，則 L 是Ｔ＊ 的一組子集合(subset) T是字元集合 實例 假設 T={p，q} 則 L 可為 {p，pq，qp，...}或 {ppp，qqq，pqp，qpq，...} 等等 只要是Ｔ＊ 的子集合即可

基本定義 語言的乘積(product) 範例 L1 與 L2 的乘積 L1={p，q} L2={m，n，mn，nm} L1‧L2={a‧b│a  L1，b  L2} 範例 L1={p，q}　L2={m，n，mn，nm} L1‧L2={pm，pn，pmn，pnm，qm，qn， qmn，qnm}

基本定義 語言 L 的次方 (Power) 定義 範例 Lo={ε} Ln=L‧Ln-1 假設 L={p，pq，q} L0={ε} ， L1=L，L2=L‧L，….

基本定義 L*的定義 L* 又稱“Kleene Closure of L” L 做任意次乘積(product) 的集合 L*=L0L1L2...Ln...

基本定義 L+ 的定義 又稱為“Transitive Closure of L” L+=L1L2L3...Ln...

文法四要素 T 終端符號 表示不能再以其他符號來替代 N 非終端符號 表示可以再以其他符號來替代 而N與T須具以下的關係：N∩T=Ø

文法四要素 S starting symbol 起始符號 從事文法推演之步驟由S開始 P production rule 文法產生規則

文法的分類 Type 0 Type 1 Type 2 Type 3 無任何限制 Context sensitive grammar Context free grammar Type 3 正規文法 (regular grammar)

正規文法分類 右線性正規文法 左線性正規文法 right linear regular grammar 文法產生規需滿足 AuB or A  u，其中 A,BN，u  T 左線性正規文法 left linear regular grammar 文法產生規則需滿足 uAB or A  u，其中 A,BN，u  T

B.N.F. 文法 B.N.F. grammar Backus Naur Form grammar type 2 grammar context-free grammar

B.N.F.文法符號 “::=” “{}” “〔〕” “∣” ”< >” 表示“定義為” 表示出現0次,1次,... 表示出現0次或1次 “∣” 表示“OR” ”< >” 表示非終端符號

範例練習 <expr>::=<expr>+<expr> <expr>::=id 請推出 a+b*c-(d+e)/f

剖析樹 (parse tree) 定義 根據語言的 B.N.F. 描述,將運算式轉換成相對應的樹狀結構,則稱此樹狀結構為剖析樹

練習 <assign>-><id>:=<expr> <id>->A|B|C <expr>-><id>+<expr> <expr>-><id>*<expr> <expr>->(<expr>) <expr>-><id> 請推導 A:=B*(A+C)

範例 Using the following B.N.F. grammar to construct a parse tree for the statement below A:=B DIV 10 + C×D <assign>::=id:=<exp> <exp>::=<term>∣<exp>+<term>∣<exp>-<term> <term>::=<factor>∣<term>×<factor>∣<term> DIV <factor> <factor>::=id∣int∣(<exp>)

推導過程 <assign> ::= id := <exp> := <exp> + <term> := <term> + <term> := <term> DIV <factor> + <term> := <factor> DIV <factor> + <term> := id DIV <factor> + <term> := id DIV int + <term> :=id DIV int + <term> * <factor> :=id DIV int + <factor> * <factor> := id DIV int + id * <factor> := id DIV int + id * id

剖析樹

範例練習 S::=AxSy|uB A::=v| ε B::=zS| ε 建構 AxuzSy 並畫出剖析樹

練習 <assign>-><id>=<expr> <id>->A|B|C <expr>-><expr>+<term>|<term> <term>-><term>*<factor>|<factor> <factor>->(<expr>)|<id> A=A*(B+C*B)

練習 <S>-><A>a<B>b <A>-><A>b|b <B>->a<B>|a 1 baab 5 bbaabb 2 bbbab 6 bbaaaa 3 bbaaaaa 4 bbaab

模擬兩可的文法 根據語言的 B.N.F. 描述,對同一句子(sentence)可繪出二個或二個以上不同的剖析樹,則稱此語言的文法是模擬兩可的 ambiguous grammar -(背起來) 根據語言的 B.N.F. 描述,對同一句子(sentence)可繪出二個或二個以上不同的剖析樹,則稱此語言的文法是模擬兩可的

模擬兩可的文法 Draw 2 different parse tree for id+id+id, using the grammar E→E+E∣id 對id+id+id可畫出二個不同的剖析樹如下 故此文法是模擬兩可的

模擬兩可的文法 Is the following grammar ambiguous? Describe your response carefully? S→aSbS∣bSaS∣ε 如 abab 1. S 2. S a S b S a S b S b S a S ε a S b S ε ε ε ε

練習 <assign>-><id>:=<expr> <id>->A|B|C <expr>-><expr>+<expr> <expr>-><expr>*<expr> <expr>->(<expr>) <expr>-><id> 推導A:=B+C*A 兩棵剖析樹

解決模擬兩可的問題方法 運算子優先順序 讓*優先於+ 運算子結合性 左結合性:由左向右運算 右結合性:由右向左運算

範例 <assign>-><id>:=<expr> <id>->A|B|C <expr>-><expr>+<term>|<term> <term>-><term>*<factor>|<factor> <factor>->(<expr>)|<id>

先定義的優先順序愈低 <expr>-><expr>+<term>中的<expr>在左手邊，是左結合性 從上頁規則推導 A:=B+C*A A:=B+C+A

練習 請證明下列文法是模擬兩可的 <S>-><A> <A>-><A>+<A>|<id> <id>->a|b|c

懸置else問題 dangling else (懸置else)的意義 若有一敘述如下: if 條件A then if 條件B then E1 else E2   則 else 將無法確定要與第一個或第二個 if 結合這種現象,就是所謂的 dangling else 問題

例如 <if_stmt>->IF<expr>then<stmt> |If<expr>then<stmt>else<stmt> <stmt>-><if_stmt>|S1|S2 <expr>->X=0|Y=0 推IF X=0 THEN IF Y=0 THEN S1 ELSE S2 產生兩棵剖析樹

懸置else問題 各種語言解決 dangling else 的方法 近代高階程式語言 多利用”最接近未結合原則”來解決此問題 PASCAL 利用begin-end作為分界，來解決懸置else問題 If …then begin if ….then ….else ….end ALGOL 60 ALGOL 68 利用if...fi作為分界，來解決懸置else的問題 If …then if … then ...else …fi fi 近代高階程式語言 多利用”最接近未結合原則”來解決此問題 If …if… <執行>; else <執行> If… {if …<執行>;}else <執行>;

描述程式語言語法的方式 B.N.F.法 語法圖(Syntax Diagram) 推移圖(Transition Diagram) 請參考sec. 2-4之敘述 語法圖(Syntax Diagram) 推移圖(Transition Diagram)

語法圖 ：表示非終端符號 :表示終端符號 P::=Q1│Q2│‧‧‧│Qn 　

語法圖 P::=Q1 Q2‧‧‧Qn P::={Q} 代表0 or 1 or 2 ……

推移圖 1+0+對應的推移圖 1+代表至少一次1到無窮次1 其中S0為起始狀態，而S2為終止狀態

推移圖 10*1+對應的推移圖 0*代表可能0次到無窮次 其中S0為起始狀態，而S2為終止狀態

推移圖 10*110*1 對應的推移圖 其中S0為起始狀態，而S4為終止狀態

範例練習 1+0*110*1+ 對應的推移圖 1+0*1*1+0*1+ 對應的推移圖 1+0*1*1+0*1+ 0*1*對應的推移圖

語意的描述 靜態語意(static semantics) 動態語意(dynamic semantics) 解釋型語意(interpretive semantics) 公理型語意(axiomatic semantics) 符號型語意(denotational semantics)

靜態語意 意義 作法 範例 屬性文法(attribute grammar) 由於有許多語言規則沒有辦法單純的用BNF文法來做一個描述，因此必需要用其他的規則來加以處理 作法 在程式執行之前或語言處理器翻譯時處理 範例 變數必須先宣告再引用 屬性文法(attribute grammar) 屬性文法是一種可以描述靜態語意之方法，加入 1屬性: 附屬於文法符號，與變數類似，可以指定值給他們 2語意函數:附屬於語法規則，描述屬性值如何計算之函數 3述詞函數:附屬於語法規則，用於語法和語意之檢查

動態語意 解釋型語意(interpretive semantics) 公理型語意(axiomatic semantics) 符號型語意(denotational semantics)

解釋型語意 意義 又稱為操作型語意(operational semantics) ,在本方法中定義抽象機器(abstract machine)，此抽象機器可支援一組簡單的操作並提供一些簡單的資料結構供使用。通常以暫存器或記憶體位置來表示計算機執行的狀態 作法 語言的語意在此類型中，被定義成為如何將程式轉換成在抽象機器上執行的碼 範例 如PL/1語言的維也納定義語言(Vienna Definition Language)

公理型語意 意義 作法 公理型語意提供數學規則來表示程式執行之結果。 對於程式語言的每個語法單元均提供一個數學規則來定義。也就是利用數學推論來証明程式的正確性

符號型語意 意義 符號型語意利用數學函數來定義程式。 作法 syntax entity  object

精選習題 請解釋下列名詞： 剖析樹(parse tree)的樹葉節點是否有特殊意義 關鍵字(key word) 保留字(reserved word) 懸置指標(dangling pointer) 懸置標記引用(dangling label reference) 剖析樹(parse tree)的樹葉節點是否有特殊意義

Ans (1) 關鍵字：具有特殊意義的字，但使用者可以重新定義。 (1) 關鍵字：具有特殊意義的字，但使用者可以重新定義。 (2) 保留字：具有特殊意義的字，但不能由使用者所重新定義者。如Pascal語言中的begin、end、var、type、const、case、repeat、until、while、if、then及else等等，另外使用Reserved word具有數項優點；如可提高程式的可讀性，並可提高Compiler搜尋Symbol table的速度，最重要的是可便利程式的除錯。至於其缺點則是程式設計師必須花費額外的功夫來記憶Reserved word，且程式的擴充性將降低。 (3) 懸置指標：指標變數指到一個已經不存在的記憶體空間稱此現象為懸置指標。 (4) 懸置標記引用：欲用一個已經離開其Scope的label便可稱為懸置標記引用。 終端符號是剖析樹的樹葉節點(leaf nodes)

Q 假有以下之文法產生規則： S→aBc B→bXb B→bX X→a X→ab (a) 字串“ababc”是否可由以上文法產生？ (b) 以上文法產生規則是否是ambiguous？ (c) 寫出以上文法產生規則所定義之所有字串。

Ans (a) “ababc”可由以上文法產生規則導出。 (b) 以上文法產生規則是ambiguous，理由如下： 以“ababc”為例，可得以下二種推導方式： (a) S→aBc→abXbc→ababc (b) S→aBc→abXc→ababc 因此，得證。 (c) 所有的可能推導方式如下： (a) S→aBc→abXbc→ababc (b) S→aBc→abXbc→ababbc (c) S→aBc→abXc→ababc (d) S→aBc→abXc→abac 所有可能之string為ababc、ababbc及abac三種。

練習 根據題目之文法產生規則，寫出以下敘述的推導方法。 A pretty book had a happy Mary <sentence>::= <noun phrase><verb phrase> <noun phrase>::= <article><adjective><name>∣<article> <adjective > <noun> <verb phrase>::= <verb>∣<verb><noun phrase> <name>::= John∣Mary <noun>::= book∣peanut∣friend <adjective>::= happy∣pretty∣tasty <article>::= a∣the <verb>::= ate∣loved∣had

Ans

Q 就下列定義的貝氏正式(BNF)，寫出剖析下列運算式(expression)後所得的剖析樹(parsing tree)，或指出其為語法錯誤(syntax error)。 貝式正式: <ep>::=<ep><op><tt>∣<tt> <op>::=＋∣* <tt>::=<cc>∣<ll><nn> <cc>::=T∣F <nn>::=0∣1 <ll>::=I∣J∣K∣L∣M∣N 運算式 (1) K1*I0+T*L1+M0*F+M1 (2) L1*(J0+M1)+I1

Ans 語法錯誤：因為BNF語法定義中，並未定義左括號"("與右括號")"，所以無法根據題意的BNF規則將L1*(J0+M1)+Il轉換成相對應的剖析樹。

根據底下的語法，請舉出一個實例，並畫出語法樹(syntax tree)，以說明該語法為模擬兩可之語法(ambiguous grammar)。 　　<exp>::=<exp>+<exp> 　　<exp>::=<exp>*<exp> 　　<exp>::=id

Ans 以id+id+id為例本題之文法規則為模擬兩可之語法

練習 就下列定義的貝式正式(BNF)，寫出剖析下列運算式(expression)後所得的剖析樹(parsing tree)或指出其為語法錯誤(syntax error)。 貝式正式： <ep>::= <tt>*<ep> | <tt> <tt>::= <vv> ^ <tt> | <vv> <vv>::= A | B | C | D 運算式： (a) A ^ B ^ C ^ D (b) A * B * C * D (c) A ^ B * C ^ D (d) A * B ^ C * D (e) A + B * C + D

Ans

Q 根據以下的語法規則，請問運算式9-(24/3+1*2)-2，計算的結果為何？ <expr>::=<mm> | <mm> * <expr> | <mm> / <expr> <mm>::=<it> | <it> + <mm> | <it> - <mm> <it>::=(<expr>) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10|...

Ans

Q & Ans (一) 列出一個Grammar之四個主要構成份子(essential components) (二) 一般常用什麼方式來描述程式語言之語法(syntax)？ (一) 文法四要素： (1) T：終端符號(terminal symbol) (2) N：非終端符號(non-terminal symbol) (3) S：起始符號(start symbol) (4) P：文法產生規則(production rule) (二) 描述程式語言語法的方式： (1) BNF(Backus Naur Form) (2) 語法圖(Syntax diagram) (3) 推移圖(Transition diagram)