编译原理复习例题.doc

编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。但要求至少要按照作业题的范围复习。)一 选择题1编译的各阶段工作都涉及 。A词法分析 B表格管理 C语法分析 D语义分析2 型文法也称为正规文法。A 0 B 1 C 2 D 33 文法不是LL(1)的。A递归 B右递归 C2型 D含有公共左因子的4文法EE+E|E*E|i的句子i*i+i*i有 棵不同的语法树。A 1 B 3 C 5 D 75文法 SaaS|abc 定义的语言是 。Aa2kbc|k0 Bakbc|k0 Ca2k-1bc|k0 Dakakbc|k06若B为非终结符，则 Aa.Bb 为 。A移进项目 B归约项目 C接受项目 D待约项目7同心集合并可能会产生新的 冲突。 A二义 B移进/移进 C移进/归约 D归约/归约8代码优化时所依据的是 。A语法规则 B词法规则 C等价变换规则 D语义规则9表达式a-(-b)*c的逆波兰表示（为单目减）为 。Aa-bc* Babc*- Cab- Dabc-*10过程的DISPLAY表是用于存取过程的 。A非局部变量 B嵌套层次 C返回地址 D入口地址二 填空题1词法分析阶段的任务式从左到右扫描 字符流 ，从而逐个识别 一个个的单词 。2对于文法GE：ET|E+T TF|T*F FPF|P P(E)|i，句型T+T*F+i的句柄是 。3最右推导的逆过程称为 规范归约 ，也称为 最左归约 。4符号表的每一项是由名字栏和 两个栏目组成。在目标代码生成阶段，符号表是 的依据。三 判断题（认为正确的填“T”，错的填“F”）【 】1同心集的合并有可能产生“归约/归约”冲突。【 】2一个文法所有句子的集合构成该文法定义的语言。【 】3非终结符可以有综合属性，但不能有继承属性。【 】4逆波兰表示法表示表达式时无需使用括号。【 】5一个有穷自动机有且只有一个终态。【 】6若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。四 解答题1给定文法G和句型(T+F)*i+T, G: EE+T | T TT*F | F F(E) | i （1）画出句型的语法树； （2）写出句型的全部短语、简单短语和句柄。解：（略）2设有文法G：SS+S|S*S|i|(S)。（1）对于输入串i+i*i 给出一个最左推导；（2）该文法是否是二义性文法？请证明你的结论。解：（1）i+i*i的最左推导：S = S+S = i+S = i+S*S = i+i*S = i+i*i （2）该文法是二义性的。因为对于句子i+i*i可以画出两棵语法树（语法树略）。3给出语言ambmcn|m1,n0的上下文无关文法（2型）。解： G: SAB|A AaAb|abBcB|c4给出语言akbmcn|k,m,n1的正规文法（3型）。解： G: AaA|aB BbB|bCCcC|c5将文法G改写成等价的正规文法（3型）。 G: SdAB AaA|aBbB|b解： G: SdA AaA|aBBbB|b6构造一文法产生任意长的a，b串，使得 |a|b|2|a|其中，“|a|”和“|b|”分别表示串中的字符a和b的个数。解：b的个数在a的个数和其2倍之间，串的结构形如aSBS和BSaS，其中B为1或2个b。故得文法 G: SaSBS|BSaS|Bb|bb7设有字母表a，b上的正规式R=(ab|a)*。（1）构造R的相应有限自动机；解：0123baa-+（2）构造R的相应确定有限自动机；解：将（1）所得的非确定有限自动机确定化ab-01131221+3ab-+013123+12312313+13123012aaba-+（3）构造R的相应最小确定有限自动机；解：对（2）得到的DFA化简，合并状态0和2 为状态2：12aab-+（4）构造与R等价的正规文法解：令状态1和2分别对应非终结符B和AG: AaB|a| BaB|bA|a|b|可化简为：G: AaB| BaB|bA|8写出如图所示的自动机描述的语言的正规式1324babab-+0aa+解：abb*|abb*aa*b|aaa*b9写出在a,b上，不以a开头，但以aa结尾的字符串集合的正规式（并构造与之等价的最简DFA）。解：依题意，“不以a开头”，则必以b开头，又要“以aa结尾”，故正规式为：b(a|b)*aa（构造与之等价的最简DFA，此略）10写一个LL(1)文法G，使其语言是L(G)= ambnc2n | m=0,n0 并证明文法是LL(1)。解：文法G（S）：S aS | EE bEE Ecc | ccSelect(S aS)Select (S E)= Select(E Ecc)Select (E cc) =故文法为LL(1)的11将文法G改写成等价的LL(1)文法，并构造预测分析表。 G：SS*aT|aT|*aT T+aT|+a（编写递归下降子程序）解：消除左递归后的文法G: SaTS|*aTSS*aTS|T+aT|+a提取左公因子得文法G:SaTS|*aTSS*aTS|T+aTTT|Select(SaTS)=aSelect(S*aTS)=*Select(SaTS)Select(S*aTS)=Select(S*aTS)=*Select(S)=Follow(s)=#Select(S*aTS)Select(S)= Select(T+aT)=+Select(TT)=First(T) =+Select(T )=Follow(T)=*,#Select(TT)Select(T)= 所以该文法是LL(1)文法。预测分析表：*+a#SSTa, NTST, NSSTa, N, PTTa, NT, PT, P, Pa, N#OK（递归下降子程序，略）12对文法GS: S aSb | PP bPc | bQcQ Qa | a构造简单优先关系表。该文法是否是简单优先文法？解：简单优先关系矩阵如下：SabPQcS=a=b= =Q=c由于矩阵中有元素存在多种优先关系，故不是简单优先文法。13考虑文法 G: S AS | b A SA | a（1）构造文法的可归前缀图（活前缀的DFA）；（2）判断文法是否是LR(0)文法，并说明理由。解：（1）可归前缀图（2）因为存在冲突，所以不是LR(0)文法。14文法G及其LR分析表如下，请给出对串dada#的分析过程。G: S VdBV eV B aB BdaB 状态ACTIONGOTOdea#SBV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5解：对输入串dada#的分析过程步骤状态栈符号栈剩余输入符号动作1234567890020240245024602467024678024601#V#Vd#Vda#VdB#VdBd#VdBda#VdB#Sdada#dada#ada#da#da#a#用V 归约移进移进用B a归约移进移进用B Bda 归约用S VdB 归约接受15对传值、传地址和传名3种参数传递方法分别写出下列程序的输出：void p(int x, int y, int z) y *= 3;z += x;void main() int a=5, b=2;p(a*b,a,a);printf(“%dn”, a);这些参数传递机制如何实现？解：（1）传值 5； （2）传地址 25； （3）传名 45（参数传递机制，略）16将下面程序划分为基本块，并画出其程序流图。b := 1b := 2if w = x goto L2e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y = z goto L4haltL4:g := g + 1h := 8goto L1解：（1）基本块： （2）程序流图b := 11423765b := 2if w = x goto L2（1）e := bgoto L2（2）L1:goto L3（3）L2:c := 3b := 4c := 6（4）L3:if y = z goto L4（5）halt （6）L4:g := g + 1h := 8goto L1（7）- 8 -