假有以下之文法產生規則： S→aBc B→bXb B→bX X→a X→ab (a). 字串“ababc”是否可由以上文法產生？ (b)

Presentation on theme: "假有以下之文法產生規則： S→aBc B→bXb B→bX X→a X→ab (a). 字串“ababc”是否可由以上文法產生？ (b)"— Presentation transcript:

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

2 根據題目之文法產生規則，寫出以下敘述的推導方法。 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

3 請解釋下列名詞： (1) 關鍵字(key word) (2) 保留字(reserved word) (3) 懸置指標(dangling pointer) (4) 懸置標記引用(dangling label reference)

4 就下列定義的貝氏正式(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

5 設有一語言以EBNF (Extended Backus-Naur Form)規則式定義如下：
<bin-num> :: = [<digit>] <three-ones>[<digit>] 　　<three-ones> :: = 111 　　<digit> :: = 0 | 1 | 0 <bin-num> | 1 <bin-num> 請指出以下四個式子，何者符合上述的文法規定： (1) (2) (3) (4)

6 一個EBNF(Extended Backus-Naur Form)規則定義如下：
<sequence>::= A{B|C} [D] (1) 請列出所有由1個、2個或3個字元所構成合乎上述文法規定之述句(sentence)。 (2) 請將上述EBNF規則定義，轉換成BNF規則定義。

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

8 就下列文法示，如果下列字串屬於該文法所定義之語言，寫出其剖析樹(parse tree)，或指出其不屬於該語言。
文法： <S>－> <A>a<B>b <A>－> <A>b│b <B>－> a<B>│a 字串： (一) bbbaab (二) aaabba

9 就下列定義的貝式正式(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

10 根據以下的語法規則，請問運算式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|. ..

11 (一) 列出一個Grammar之四個主要構成份子(essential components)
(二) 一般常用什麼方式來描述程式語言之語法(syntax)？

12