《编译原理》复习题-吉林大学.doc

编译原理复习题1语言2LL(1)文法3上下文无关文法CFG（Context Free Grammar）组成4在仅由字母表中的3个字符组成的简单字母表S=a,b,c中，求最多包括了一个b的所有串的集合5举例说明符号串的正闭包 6标号部分的语义错误7实现高级语言程序的途径有哪几种？它们之间的区别？8什么是可规约活前缀？举一例说明。9中间代码优化的种类 10给出活动记录空间结构?并给出各部分的存储对象？11文法可分为几类；各举一例。12Display表的作用？13当实参为变量，形参分别为变参和值参时，传参的区别。14语法错误类别15词法错误校正 16词法分析器的任务 17语法分析树（简称分析树）18确定有限自动机的组成 19中间代码基本块的划分20设有表达式A*(B*C-A) B+C*D (1) 写出逆波兰式(后缀式)中间代码。 (2) 写出三元式中间代码。 (3) 写出多元式中间代码。 (4) 画出树。21判断字符串anbn（n 0）是否可用确定自动机识别？如果能，则画出自动机，否则说明原因。22散列式全局符号表的组织结构和具体实现23类型等价有按名等价和按结构的等价，试同其实现有什么主要区别？24属性文法的定义25编译程序按功能分为哪几个阶段？各个阶段的主要功能？ 26给出描述非0数字作为开始符的奇数字符串的正则表达式或正则式。27求条件语句:if E then S1 else S2对应的程序流图: 28对如下文法：GS ：S a b S | a a B | a d B b b B | b 分别给出句子abaabbb和ad的句柄29有如下文法，给出每个产生式的Predict集。P begin S end S id := E ; S | l E n | id30设对偶表（L，N）分别表示程序在当前位置的层数和偏移量，确定下面程序段中括号部分的内容。假设系统规定整型(int)变量占1个单元，实型(real)变量占2个单元。(L, N) Type at = array of 1.10 of int;() var x ：real;() function f ( ( ？,M) var a: at,() b: at, () var x: real ) : int31有如下文法： GS：S ( L ) | a L S P P , S P | l 给出该文法的动作文法打印每个a的嵌套深度。例如（a，（a），（a）打印1，2，2。32 给定下面源程序，写出词法分析后的TOKEN表示： begin var x: real； var j: integer； read (j)； j:= j + ( j*20 )； x:= j-1； write( 2*j + x ) end 33试写出上述程序的目标程序。 begin var x: real； var j: integer； read (j)； j:= j + ( j*20 )； x:= j-1； write( 2*j + x ) end34写出下面表达式的代码生成过程；a*a+b*c+b35在仅由字母表中的3个字符组成的简单字母表S=a,b,c中，考虑在这个字母表上的仅包括一个b的所有串的集合，求其正则表达式 36Pascal程序段，试问词法分析阶段能发现哪些词法错误？ if a=1. then b: =1.0 else c: =1; a: =bc+d;37写出识别下列正则表达式定义的单词的DFA：(a|bc)*d)+38构造一个DFA，它接受的符号串集合等于正则表达式(ab*c)|(abc*) 所示的字符串集合。要求先构造NFA，其次转换成DFA，最后加以极小化 。39文法G =( + , * , i , ( , ) , E , E , P ), 其中P为：E iE E + EE E * EE ( E ) 给出句型 i * i + i的两颗语法树 :40求文法的first()、follow集合E TE E +TE| T FT T *FT | F (E)|id41假设有文法: Z aBaB bB | c 写出其递归子程序。42已知如下文法，求其消除公共前缀后的等价文法Stm id:=ExpStm id (ExpL)ExpL ExpExpL Exp, ExpL43说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。最后给出该文法的LL（1）分析表。 GA：A B e B B b | a 44判断如下文法是否是LR(1)文法，若不是，说明理由，是则画出它的LR状态图，并给出它的LR(1)分析表。 GS：S a | b | (T) T TeS | S 45已知如下文法，求其预测分析表1. E TE 5. T *FT2. E +TE 6. T 3. E 7. F id4. T FT 8. F (E)46已知如下文法，画出可归前缀图、goto表、action表，句子id+id$的分析过程SE $EE+TETTidT( E )47已知如下文法，画出其可归前缀图，action、goto表，写出句子aab=b#的分析过程。Z SS L=R | RL aR | bR L48以下文法中哪些不是LR(0)？ 为什么？(a) QSL $ SL SL； S SLS S null(b) Q SL $ SL S；SL SL S SL null(c) Q SL $ SL SL；SL SL S Snull(d) Q L $ SL null SLtail SLtail SLtail ；SL49有如下的类型定义： at = ARRAY 1.10 OF ARRAY1.100 OF integer; rt = RECORD x : real ; a : at; CASE u : boolean OF false: ( k : integer); true : ( y: rea