課程名稱︰ 編譯程式設計
課程性質︰ 大三下系必修
課程教師︰ 薛智文
開課學院： 電資學院
開課系所︰ 資工系
考試日期（年月日）︰ 2009/04/16
考試時限（分鐘）： 200
是否需發放獎勵金： 是
（如未明確表示，則不予發放）
試題 :
1. Explain or compare the following terms used in Compiler in your own words:
(a) viable prefix; handle [10%]
(b) synchronization in error handling [10%]
(c) top down parsing; bottom up parsing [10%]
(d) language; grammar [10%]
2. Modify the following grammar so that the leftmost derivation and rightmost
derivation are the same and is left associative, i.e. 2-3-4=(2-3)-4=-5.[20%]
Note that operator precedence / < -, i.e. 8-4/2=(8-4)/2=2.
E -> int
E -> E-E
E -> E/E
E -> (E)
3. Explain why LL(1) 包含於 LR(1)? [10%] Why SLR(1) and LALR(1) always have the
same number of states. [10%]
4. Give an example of a usage of lookahead operator in LEX. [10%] Hoow look-
ahead operators are implemented in LEX? [10%] What does LEX do when multiple
rules are matched at the same time for a given input? [10%]
5. Eliminate left factors and left recursions from the following grammar. [30%]
S -> Sc | Sd | eA | xyB | r
A -> y | Syy | yy | Aw | t
B -> Sx | y | id | Bee
6. Consider the following grammar with the starting nonterminal E.
E -> E-E | T
T -> T(F) | F
F -> .F | id | w | [Q]
Q -> a | +E
(a) Compute its LR(0) automaton. [20%]
(b) Compute its LR(1) parsing table. [20%]
(c) Using LR(1) parsing to parse the input id-[+.w]
7. Consider the following grammar with E being the starting nonterminal. Note
that int, x1, x2 are terminals.
E -> E'TR
E' -> T'E' | (HR) | ε
T -> a | b | FFT'
T' -> *FT' | ε
F -> int | [E] | ε
R -> E:T | ε_
H -> x1 | x2
(a) Compute FIRST for all nonterminals. [20%]
(b) Compute FIRST for all strings on the right hand side of a production.
[20%]
(c) Compute FOLLOW for all nonterminals. [20%]
8. Consider the following grammar, is it LL(1)? Why? [10%] Write a parsing
table for it. [10%]
S -> Xa | Yb
X ->ε
Y -> ε
9. For a language if 2 symbols {a, b} recognized by a NFA with two states
{0, 1}, what is the DFA of the same language with the maximum state? Find
the transition diagram of the DFA and its regular expression. [20%]
10. Are the FIRST or FOLLOW of the same nonterminals the same after left
factors removing? Why? [10%]
註: 開書考, 滿分300
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.76.145
※ 編輯: edwardhw 來自: 118.168.76.145 (04/16 18:56)