《编译原理》复习题.doc

编译原理复习题1词法分析器的任务2编译程序按功能分为哪几个阶段？各个阶段的主要功能？2词法错误校正：3举例说明符号串的正闭包4举例说明符号串的星闭包5确定有限自动机的组成1 给定下面源程序，写出词法分析后的TOKEN表示：beginvar x: real； var j: integer； read (j)； j:= j + ( j*20 )； x:= j-1； write( 2*j + x ) end 2试写出上述程序的目标程序。 beginvar x: real； var j: integer； read (j)； j:= j + ( j*20 )； x:= j-1； write( 2*j + x ) end3 写出下面表达式的代码生成过程；a*a+b*c+b4在仅由字母表中的3个字符组成的简单字母表S=a,b,c中，考虑在这个字母表上的仅包括一个b的所有串的集合，求其正则表达式5在仅由字母表中的3个字符组成的简单字母表S=a,b,c中，求最多包括了一个b的所有串的集合6识别不同进制数的状态图7. Pascal程序段，试问词法分析阶段能发现哪些词法错误？if a=1. then b: =1.0 else c: =1; a: =bc+d;8写出识别下列正则表达式定义的单词的DFA：(a|bc)*d)+9构造一个DFA，它接受的符号串集合等于正则表达式(ab*c)|(abc*) 所示的字符串集合。要求先构造NFA，其次转换成DFA，最后加以极小化 。10语法错误类别11上下文无关文法CFG（Context Free Grammar)组成：12语言： 13语法分析树（简称分析树）14文法G =( + , * , i , ( , ) , E , E , P ), 其中P为：l E il E E + El E E * El E ( E ) 给出句型 i * i + i的两颗语法树 :15求文法的first()、follow集合E TE E +TE| T FT T *FT | F (E)|id16求该文法的predict集合GE ：1. E TE 5. T *FT2. E +TE 6. T 3. E 7. F id4. T FT 8. F (E)17假设有文法: Z aBaB bB | c 写出其递归子程序。18已知如下文法，求其消除公共前缀后的等价文法Stm id:=ExpStm id (ExpL)ExpL ExpExpL Exp, ExpL19已知如下文法，求其消除公共前缀后的等价文法Exp Term+Exp | TermTerm FactorTerm | FactorFactor id | (Exp)20LL(1)文法： 21已知如下文法，求其预测分析表1. E TE 5. T *FT2. E +TE 6. T 3. E 7. F id4. T FT 8. F (E)22归约规范活前缀： 23已知如下文法，画出可归前缀图、goto表、action表，句子id+id$的分析过程SE $ EE+T ET Tid T( E )24设有文法G(C)如下 ：S E # 1 E E+T 2 E T 3 T TP 4 T P 5 P id 6 P (E) 7l 构造G(C)的LR(0)可归前缀图l 构造action、goto表l 写出句子id id+id的分析过程25已知如下文法，画出其可归前缀图，action、goto表，写出句子aab=b#的分析过程。Z SS L=R | RL aR | bR L26以下文法中哪些不是LR(0)？ 为什么？(a) Q -SL $SL -SL； SSL -SS -null(b) Q -SL $SL -S；SLSL -SSL -null(c) Q -SL $SL -SL；SLSL -SS -null(d) Q -SL $SL -null SLtailSLtail -SLtail -；SL27有如下的类型定义： at = ARRAY 1.10 OF ARRAY1.100 OF integer; rt = RECORD x : real ; a : at; CASE u : boolean OF false: ( k : integer); true : ( y: real; b: boolean) END构造类型的内部表示。28符号表的局部化处理29二叉式局部符号表的组织结构和具体实现30散列式全局符号表的组织结构和具体实现31标号部分的语义错误： 32类型等价有按名等价和按结构的等价，试同其实现有什么主要区别？33属性文法的定义34写出表达式a5+i.x + m * z的中间代码。u 其中，i,m:integer; z:real; a:array1.100 of rt; rt = record y:int;x:real end35设有表达式A*(B*C-A) B+C*D(1) 写出逆波兰式(后缀式)中间代码。(2) 写出三元式中间代码。(3) 写出多元式中间代码。(4) 画出树。 36中间代码优化的种类：37中间代码基本块的划分：38求条件语句:if E then S1 else