推 bztfir :推原PO帥哥 04/29 00:00
課程名稱︰編譯程式設計
課程性質︰系必修
課程教師︰陳俊良
開課學院：電資學院
開課系所︰資訊系
考試日期（年月日）︰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