编译原理复习题 (1).doc

编译原理复习题1确定有限自动机的组成2编译程序按功能分为哪几个阶段？各个阶段的主要功能？3词法分析器的任务 4举例说明符号串的正闭包5什么是可规约活前缀？举一例说明。 6词法错误校正7实现高级语言程序的途径有哪几种？它们之间的区别？8举例说明符号串的星闭包。9通过合并LR（1）文法中的同心状态得到的LALR(1)文法可能会产生哪些冲突？一定不会产生哪些冲突？10给出活动记录空间结构?并给出各部分的存储对象？11文法可分为几类；各举一例。12Display表的作用？13当实参为变量，形参分别为变参和值参时，传参的区别。14语法错误类别15上下文无关文法CFG（Context Free Grammar)组成16语言17语法分析树（简称分析树）18LL(1)文法19归约规范活前缀20符号表的局部化处理21二叉式局部符号表的组织结构和具体实现22散列式全局符号表的组织结构和具体实现23标号部分的语义错误24类型等价有按名等价和按结构的等价，试同其实现有什么主要区别？25属性文法的定义26中间代码基本块的划分27中间代码优化的种类28给出描述非0数字作为开始符的奇数字符串的正则表达式或正则式。29判断字符串anbn（n 0）是否可用确定自动机识别？如果能，则画出自动机，否则说明原因。30对如下文法：GS ：S a b S | a a B | a d B b b B | b 分别给出句子abaabbb和ad的句柄31有如下文法，给出每个产生式的Predict集。P begin S end S id := E ; S | l E n | id32设对偶表（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 ) : int33有如下文法： GS：S ( L ) | a L S P P , S P | l 给出该文法的动作文法打印每个a的嵌套深度。例如（a，（a），（a）打印1，2，2。36 给定下面源程序，写出词法分析后的TOKEN表示：beginvar x: real； var j: integer；read (j)；j:= j + ( j*20 )；x:= j-1；write( 2*j + x )end 37试写出上述程序的目标程序。 beginvar x: real； var j: integer；read (j)；j:= j + ( j*20 )；x:= j-1；write( 2*j + x )end38写出下面表达式的代码生成过程；a*a+b*c+b39在仅由字母表中的3个字符组成的简单字母表S=a,b,c中，考虑在这个字母表上的仅包括一个b的所有串的集合，求其正则表达式40在仅由字母表中的3个字符组成的简单字母表S=a,b,c中，求最多包括了一个b的所有串的集合41识别不同进制数的状态图42Pascal程序段，试问词法分析阶段能发现哪些词法错误？ if a=1. then b: =1.0 else c: =1; a: =bc+d;43写出识别下列正则表达式定义的单词的DFA：(a|bc)*d)+44构造一个DFA，它接受的符号串集合等于正则表达式(ab*c)|(abc*) 所示的字符串集合。要求先构造NFA，其次转换成DFA，最后加以极小化 。45文法G =( + , * , i , ( , ) , E , E , P ), 其中P为：E iE E + EE E * EE ( E ) 给出句型 i * i + i的两颗语法树 :46求文法的first()、follow集合E TE E +TE| T FT T *FT | F (E)|id47求该文法的predict集合GE ：1. E TE 5. T *FT2. E +TE 6. T 3. E 7. F id4. T FT 8. F (E)48假设有文法: Z aBaB bB | c 写出其递归子程序。49已知如下文法，求其消除公共前缀后的等价文法Stm id:=ExpStm id (ExpL)ExpL ExpExpL Exp, ExpL19已知如下文法，求其消除公共前缀后的等价文法Exp Term+Exp | TermTerm FactorTerm | FactorFactor id | (Exp)50说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。最后给出该文法的LL（1）分析表。 GA：A B e B B b | a 51判断如下文法是否是LR(1)文法，若不是，说明理由，是则画出它的LR状态图，并给出它的LR(1)分析表。 GS：S a | b | (T) T TeS | S 52已知如下文法，求其预测分析表1. E TE 5. T *FT2. E +TE 6. T 3. E 7. F id4. T FT 8. F (E)53已知如下文法，画出其可归前缀图，action、goto表，写出句子aab=b#的分析过程。Z SS L=R | RL aR | bR L54设有文法G(C)如下 ：S E # 1 E E+T2