課程名稱︰編譯程式設計 課程性質︰系必修 課程教師︰陳俊良 開課學院：電資學院 開課系所︰資訊系 考試日期（年月日）︰2011/04/28 考試時限（分鐘）：120 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Consider the following grammar for questions 1~7. The reference figure in the next page is generated by "bison --graph". 1. ExaminationPreparation -> TheoryForScanner scanner E -> TscP contextFreeGrama Parsers 2. TheoryForScanner -> regularExpression T -> r 3. TheoryForScanner -> null (學過了) T -> null 4. Parsers -> topDownParser BottomUpParsers P -> tB 5. Parsers -> BottomUpParsers topDownParser P -> Bt 6. BottomUpParsers -> MoreBottomUpParsers bottomUpParser B -> Mb 7. MoreBottomUpParsers -> bottomUpParser MoreBottomUpParsers M -> bM 8. MoreBottomUpParsers -> null M -> null 1. Complete the SetSetSet table. (15%) 2. The reference figure has 16 states. How many states does LR(1) state machine have? (5%) 3. Complete the LALR(1) item sets, including non-kernel items. (20%) 4. Are SLR(1) table and LALR(1) table the same? Explain your reason briefly. (2+3%) 5. Is the grammar LL(1)? Explain your reason briefly. (2+3%) 6. Is the grammar LALR(1)? Explain your reason briefly. (2+3%) 7. Is the grammar LR(1)? Explain your reason briefly. (2+3%) 8. Today, many language compliers are written in the languages themselves. For example. GCC is written in C and javac is written in Java. This raises something of a "chicken and eggs" problem. Now, you are asked to create the first C compiler for system NEW. And, you are given a C compiler source written in C for system OLD as well as a C compiler executable for system OLD. Explain how to develop the first C compiler for system NEW efficiently. (20%) 9. Let n be the number of input tokens. What is the time complexity of LR(1) shift-reduce parsing? Explain your reason. [hint: number of push/pop operations] (5+15%) == 圖掃描後補上。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.214.43