编译原理复习题.pdfVIP

. 二、概念题 1、设有文法：P→P+Q|Q Q→Q*R|R R→(P)|i （1）证明Q*R+Q+Q 是它的一个句型。（3 分) （2）给出Q*R+Q+Q 的所有短语，直接短语和句柄。(4分) （3）给出句子ｉ+ ｉ* ｉ的最右推导。(4分) （4）给出句子ｉ+ ｉ* ｉ的最左推导。(4分) 2、 设有文法：E→E+T|T T→T*F|F F→(E)|i （1）证明E+T*F 是它的一个句型。（3 分) （2）给出E+T*F 的所有短语，直接短语和句柄。(4分) （3）给出句子ｉ+ ｉ* ｉ的最右推导。(4分) 3、写出表达式 a+b*(c-d)对应的逆波兰式和三元式序列。 答案：逆波兰式： (abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c (2) * b (1) (3) + a (2) 三、词法分析题 给出下面语言的相应文法 n n m m L1={a b a b |n,m≥0} .; . 给出下面语言的相应文法 n n L2={a b c |n≥1, ≥0} 给出下面语言的相应文法 L3={a b c | m,n≥1，n 为奇数，m 为偶数}。 n n m 四、词法分析题 1、构造下面正规式相应的DFA * * * ((0|1) |(11)) （要求：先将正规式转化为NFA，再将NFA 确定化，最小化） 2、构造下面正规式相应的DFA * 1(0|1) 101 3、构造一个DFA，它接受 ={a，b}上所有包含 ab 的字符串。 （要求：先将正规式转化为NFA，再将NFA 确定化，最小化） 4、构造与正规式 b(a|b)*ba 等价的 DFA 五、语法分析题 1、对下面的文法 G: Expr→- Expr Expr→(Expr)|Var ExprTail ExprTail→- Expr| ε Var→id VarTail VarTail→(Expr) |ε （1）构造LL(1)分析表。（12 分） （2）给出对句子 id—id((id))的分析过程。（8 分） .; . 2、对下面的文法 G: E→TE’ E’→+E| ε T→FT’ T’→T| ε F→PF’ F’ →*F’|ε P→(E)|a|b|∧ （1）计算这个文法的每个非终结符的FIRST 和 FOLLOW。（8 分） （2）证明这个文法是LL(1)的。（6 分） （3）构造它的预测分析表。（6 分） 3、已知文法 G[S] 为： S->a|(T) T->T,S| ①消除文法 G[S]中的左递归，得文法G´[S]。 ② 文法 G´[S]是否为 LL(1)的？若是，给出它的预测分析表。 4、对下面的文法 G:   a T | a T |  a T T   a T |  a (1) 消除该文法的左递归和提取左公因子； (2) 构造各非终结符的 FIRST 和 FOLLOW 集合； (3) 构造该文法的 LL(1)分析表，并判断该文法是否是 LL(1)的。 5、文法 G(S)及其 LR 分析表如下，请给出串 baba#的分析过程。 (1) S → DbB (2) D → d (3) D → ε (4) B → a (5) B → Bba (6) B → ε LR 分析表 ACTION GOTO b D a