編譯原理本科試卷A.doc

姓名 學(xué)號(hào) 學(xué)院 班級(jí) 座位號(hào) ( 密 封 線 內(nèi) 不 答 題 )密封線線_ _ 誠(chéng)信應(yīng)考,考試作弊將帶來(lái)嚴(yán)重后果！ 華南理工大學(xué)期末考試 編譯原理 試卷A注意事項(xiàng)：1. 考前請(qǐng)將密封線內(nèi)填寫清楚； 2. 所有答案請(qǐng)直接答在試卷上； 3考試形式：閉卷； 4. 本試卷共 大題，滿分100分，考試時(shí)間120分鐘。題 號(hào)一二三四五總分得 分評(píng)卷人Note: Whether English or Chinese doesnt impact your score.1. Fill in the blanks (18%)a. Normally, A complier consists of a number of phases. They are Scanner Grammarparser, _Semantic analyzer_, _Source Code Optimizer_, Code Generator, and _target code optimizer _.b. The logical units the scanner generates are called Tokens. For a modern programming language, there are five types of token. They are _Identifier_, _Reserved Words_, _Number_, _, _. c. Based on the following C source code fragmentint gets(char *s) if (s = NULL) printf(“illegal point parameter n”); return -1; return 0;Please answer:a) “int” is a _b) “printf” is a _ c) “s” is a (an) _ d) “= =” is a _ e) “0” is a _d. A grammar G usually includes four components, they are _, _, _, and _.2. (Terms Translation, 12%)Please give a brief explanation to the following terms in compiler science domaina) Compiler b) Source code c) Scanner d) Tokens e) Terminal symbol f) Ambiguous Grammar 3. (Scanning; 20%)(a) (10%) Construct an NFA that recognizes the same language as defined by the following regular expression: (a*ba*b)*ba*(b) (10%) Using the subset construction, convert the NFA into a DFA. abA=0,1,2,5BCB=2BDC=3,6, 7,8EFD=3DFE=3,7, 8EFF=1,2,4,5BC4. (LL parsing; 25%) Consider the following grammar G(S): S-number | ListList - (Seq)Seq - Seq, S | SWhere number and “,” are terminal symbols, and the others symbols are non-terminal.(a) (7%) Please write the left-most derivation for sentence “(4, (34)”(b) 8%Please convert the grammar G into a LL(1) grammar G1 by remove the left recursion.(c) 10%Based on your LL(1) grammar G1, please calculate the FOLLOW set and FIRST set, and build its LL(1) table. 5. (LR parsing; 25%)Consider the following grammar GS: E(L)|a LEL |EWhere a ,” (”，” )” are terminal symbols and the others are non-terminal symbols.(a) 5%. Construct the DFA of LR(0) items of this grammar.(b) 10% Construct the SLR(1) parsing table.(c) 10% Show the parsing stack and the action of a SLR(1) parser for the input string: (a (a a)華南理工大學(xué)期末考試答案 編譯原理 試卷 A1. Fill in the blanks (18%)a. _Grammar_Parser_, _Sematic Analyzer_, _Source Code Optimizer_, _Target Code Optimizer _. b._Reserved Words_, _Identifier_, _Number_, _Operator_, _Special Symbol_c. a) “int” is a _ Reserved Wordb) “printf” is a _Reserved Word c) “s” is a (an) _ Identifier _ d) “= =” is a _ Operator_ e) “0” is a_ Number_ _d. Terminal symbol Non-Terminal symbol, start symbol ,and _Product Rules2. (Terms Translation, 12%)a) Compiler 一種應(yīng)用程序，將源代碼轉(zhuǎn)換為指定的目標(biāo)代碼。b) Source code 文本文件，其中內(nèi)容是按照指定的文法規(guī)則描述特定的算法，c) Scanner 將文本字符串按照詞法規(guī)則，轉(zhuǎn)換為特定的內(nèi)部標(biāo)識(shí)，供編譯器后續(xù)分析。d) Tokens 源文件中最基本的信息單元e) Terminal symbol 文法規(guī)則中不需要產(chǎn)生式定義的符號(hào)f) Ambiguous Grammar 使用不同推導(dǎo)方法，推導(dǎo)出不同語(yǔ)法樹，就稱該文法為二義文法。3. (Scanning; 20%)(a) (10%)(b) (10%)abA=0,1,2,5BCB=2BDC=3,6, 7,8EFD=3DFE=3,7, 8EFF=1,2,4,5BC4. (LL parsing; 25%)(a) (7%)S -List-(Seq)-(Seq,S)-(S,S)-(number, S)-(4,S)-(4,List)-(4,(Seq)-(4,(S)-(4,(number)-(4, (34)(b) (8%) S-number | ListList - (Seq)Seq - S Seq1Seq1-,S Seq1| (c)(10%)FIRSTSETFOLLOWSET(),number$Seqnumber,()S Seq1S Seq1Seq1, , ),S Seq1List($,), ,(Seq)Snumber,($,), ,Lnumber5. (LR parsing; 25%)（a）(5%)(b)(10%)(c) (10%)1234567891011121314151617Parsing stack Input Action$ 0 (a (a a) $ shift1$ 0 ( 1 a (a a)$ shift3 $ 0 ( 1a3 (a a) $ r E-a$ 0(1E4 (a a) $ shift1$ 0(1E4(1 a a) $ shift3$ 0(1E4(1 a 3 a) $ r E-a$ 0(1E4(1E4 a) $ shift3$ 0(1E4(1E4a3 ) $ r E-a$ 0(1E4(1E4E4 )$ r