编译原理修改.doc

2010 届推免研究生编译原理试题 1.( 10 分) 构造正则表达式(a|b) * aa的 NFA ,并将其转换为等价的 DFA 。 2.( 12 分)构造接受文法 G:S?(L)|a L? L,S|S 的活前缀的一个 DFA ,即其 LR(0) 状态机。 3.(6 分)设有下列 C 语言的声明: typedef struct { int a; float b; } CELL; CELL f1[100]; 写出本层的符号表和类型表。 4.(8 分)设有如下一 C 程序片段: for(k=1;k<=10;k++) { A=i+10*k; } 写出该程序片段的四元式形式的中间代码。 5.( 14 分)形如 A?ε的产生式为空产生式,试设计一个算法消除文法中的空产生式,并举例说明。该算法可以采用自然语言,流程图或伪代码表示。 2011 届推免研究生编译原理试题(总分 50 分) 1.( 12 分) 构造正则表达式(a|b) * a(a|b)(a|b) 的 NFA ,并将其转换为等价的 DFA 。 2.( 18 分)证明文法 E? E+T|T T? T*F|F F? id|(E) 不是 LL(1) 文法,但是 SLR (1 )文法。 3.( 10 分)设有下列 C 语言的声明: typedef struct { int year; int month; int day; } Birthday; typedef struct { char name; Birthday date; } Student; Student s1; Birthday d1; 设当前层数为 L ,当前偏移量为 off1 ,试写出本层的符号表和类型表。 4.( 10 分)设有如下 C 语言声明: int A[10][5],B[10],C[10]; 把下列赋值语句翻译成四元式中间代码形式 A[i][j]=B[i+j]+C[A[k][m]] 。 1. (20 分) (1) 写出字母表?= {a, b} 上语言 L={w|w中a 的个数是偶数} 的正则表达式,并给出接受该语言的最小状态 DFA 。状态 0 表示已接收了偶数个 a ,状态 1 表示已接收了奇数个 a,0 为终止状态。由于状态 0 是终态,而状态1 不是终态,二者是可区分的,图 1 已经是最小终态的 DFA 。图 1. 正规表达式: (b| ab *a) * (b * ab * ab *) *|b * (注意:直接给出 DFA 即可,不必从正规表达式出发构造?-NFA ,然后再化简?-NFA 。) (2) 构造一个 DFA ,它接收Σ={0,1} 上所有满足如下条件的字符串:每个 1 都有 0 直接跟在右边。并给出该语言的正则表达式。(10 | 0) *2. (20 分) 为下面的语言设计文法: (1)L 1={w|w ?{a,b} * ,且 a 的个数是 b 的个数的两倍} S ?aSaSbS|aSbSaS|bSaSaS| ?(2)L 2={ ww R|w ?{a,b} *,w R 表示 w 的反转( reverse )} S ?aSa|bSb| ?3. (10 分) 设有句型?a ?b ?, 且在此句型的推导过程中用到产生式 A ?a ?, 分别指出 LL(1) 方法和 LR(1) 方法在扫描到此句型的什么位置时决定用此产生