[試題] 96下 薛智文 compiler

[Game73 (艾草)]

課程名稱︰ compiler
課程性質︰ 必修課
課程教師︰ 薛智文
開課學院： 電資學院
開課系所︰ 資訊工程學系
考試日期（年月日）︰ 2008/4/14
考試時限（分鐘）： 180
是否需發放獎勵金： yes , thx
（如未明確表示，則不予發放）

試題 :

Compiler
Name: ________     902 39200 01, Spring 2008  Score: /110/360
ID: ______________     Midterm, April 14th, 9:10 - 12:10

  This is an openbook and open-lecture-note exam. Please do answer in the order
of question number in one answer sheet. You can write in Chinese. Please sign
your name andturn in this paperwith your answer sheet. Good luck.

1. Explain or compare the turns used in Compiler in the following:
(a) DFA-based scanning; NFA-based scanning.[10%]
(b) cycles;useless[10%]
(c) synchronization in error handling [10%]
(d) recursive-descent parser;predictive parser [10%]
(e) lookahead propagation; [10%]
(f) regular expression;context free grammar [10%]

2. Modify the following grammar so that the left most derivation and right
most derivation are the same and is right associative, i.e 2-3-4 = 2-(3-4) =3
[20%]Note that operator precedence / < - , 8-4/2 = 8-4/2 =2
E-> int
E-> E-E
E-> E/E
E-> (E)

3.Explain why LL(1) ≦ LR(1) ? Why SLR(1) and LALR(1) always have the same
number of states[10%]

4.Give an example of a useage of lookahead operators in LEX [10%]
How lookahead operators are inplemented in LEX?[10%]
What does LEX do when multiple rules are matched at the same time for a given
input.

5.Assume A->α·Xβ∈I During LR(0) parsing.why it is the case that
 closure(A->α·Xβ)≦Goto(I,X) not the case closure({A 'αX·β}) = GOTO(I,X). [10%] Use the following
grammar and its LR(0) automaton to show how a GOTO(I, X) is the union of some
closure({ A 'αX ·β})'s. [15%]

E`->E
E ->E+T
T ->T*F
F->(E)|id

6. Assume G is an LR(0) Grammer. Let F'εbe a production that is not currently
 in G. Assume F is a nonterminal that is already in G. Let G* be the new
grammar from G by inserting the new production F->ε.Describe the possible
impacts(in the areas of conflict,expressivepower and parsing complexities)
 of adding this new production[30%]

7. Eliminate left factor and left recursion from the following grammar[30%]
A->Ac|Ad|e|xyC|r
B->k|Ayy|yy|Bw|t
C->Ax|y|id|Cee
D->Auv|Buv|p

8.consider the following grammar with the starting nonterminal E
E->E-T|T
T->T(F)|F
F->F*|id|w|[Q]
Q->a|+E

(a) compute the LR(0) automation[35%]
(b) compute the LR(1) parsing table [35%]
(c) using LR(1) parsing to parse the input id-[+w] [20%]

9.consider the following grammar with E being the starting nonterminal
E->E'TR
E'->TE'T'|(RH)|ε
T->a|b|FFT'
T'->*F(T')|ε
F->char|int|[E]|ε
R->E:T|ε
H->x1|x2

(a) Compute FIRST for all nonterminals [15%]
(b) Compute FIRST for all strings on the right hand side of a production.[20%]
(c) Compute FOLLOW for all nonterminals. [20%]






--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.4.234
推 hips:這課程名稱真的是英文喔? 好奇怪的課@@
推 godhuen:中文叫編譯程式設計  老師也挺奇怪的@@
→ Game73:我修過三次　以前的老師比較好