課程名稱︰ 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