logo资料库

编译原理第五章习题答案.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.11M 资料格式：doc 举报 版权申诉
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页，剩余部分请下载后查看
    5.3 节的练习
    5.3.1
    解答
    5.3.2 !
    解答
    5.3.3 !
    5.4 节的练习
    5.4.1
    解答
    5.4.2
    5.4.3 ！
    解答
    5.4.4 ！
    解答
    5.4.5
    解答
    5.4.6
    5.4.7
    5.4.6 和 5.4.7 的解答
    5.5 节的练习
    5.5.1
    5.5.2
    5.5.3
    5.5.4
    5.5.5
    5.5.6
    5.2 节的练习 5.2.1 图 5-7 中的依赖图的全部拓扑顺序有哪些 解答 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ], [ 1, 2, 3, 5, 4, 6, 7, 8, 9 ], [ 1, 2, 4, 3, 5, 6, 7, 8, 9 ], [ 1, 3, 2, 4, 5, 6, 7, 8, 9 ], [ 1, 3, 2, 5, 4, 6, 7, 8, 9 ], [ 1, 3, 5, 2, 4, 6, 7, 8, 9 ], [ 2, 1, 3, 4, 5, 6, 7, 8, 9 ], [ 2, 1, 3, 5, 4, 6, 7, 8, 9 ], [ 2, 1, 4, 3, 5, 6, 7, 8, 9 ], [ 2, 4, 1, 3, 5, 6, 7, 8, 9 ] 算法见 5.2.1.js 5.2.2 对于图 5-8 中的 SDD，给出下列表达式对应的注释语法分析树：   int a, b , c float w, x, y, z 解答
    int a, b, c 5.2.3 假设我们有一个产生式 A -> BCD。A, B, C, D 这四个非终结符号都有两个属性，综合 属性 s 和继承属性 i。对于下面的每组规则，指出（1）这些规则是否满足 S 属性定 义的要求（2）这些规则是否满足 L 属性定义的要求（3）是否存在和这些规则一致的 求值过程？     A.s = B.i + C.s A.s = B.i + C.s , D.i = A.i + B.s A.s = B.s + D.s ! A.s = D.i , B.i = A.s + C.s , C.i = B.s , D.i = B.i + C.i 解答  否， ？  否， 是  是， 是  否， 否 5.2.4 ！ 这个文法生成了含“小数点”的二进制数： S -> L.L|L L -> LB|B B -> 0|1 设计一个 L 属性的 SDD 来计算 S.val，即输入串的十进制数值。比如，串 101.101 应 该被翻译为十进制数 5.625。 解答 产生式 语法规则
    1) S -> L_1.L_2 L_1.isLeft = true L_2.isLeft = false S.val = L_1.val + L_2.val 2) S -> L L.isLeft = true S.val = L.val L_1.isLeft = L.isLeft L.len = L_1.len + 1 L.val = L.isLeft ? L_1.val * 2 + B.val : L_1.val + B.val * 2^(-L.len) L.len = 1 L.val = L.isLeft ? B.val : B.val/2 B.val = 0 B.val = 1 3) L -> L_1B 4) 5) 6) L -> B B -> 0 B -> 1 其中：    isLeft 为继承属性，表示节点是否在小数点的左边 len 为综合属性，表示节点包含的二进制串的长度 val 为综合属性 5.2.5 ！！ 为练习 5.2.4 中描述的文法和翻译设计一个 S 属性的 SDD。 解答 1) 2) 3) 4) 5) 6) 产生式 语法规则 S -> L_1.L_2 S.val = L_1.val + L_2.val/L_2.f S -> L S.val = L.val L -> L_1B L -> B B -> 0 B -> 1 L.val = L_1.val*2 + B.val L.f = L_1.f * 2 L.val = B.val L.f = 2 B.val = 0 B.val = 1
    5.2.6 ！！ 使用一个自顶向下的语法分析文法上的 L 属性 SDD 来实现算法 3.23。这个算法把一 个正则表达式转换为一个 NFA。假设有一个表示任意字符的词法单元 char，并且 char.lexval 是它所表示的字符。你可以假设存在一个函数 new()，该函数范围一个新 的状态页就是一个之前尚未被这个函数返回的状态。使用任何方便的表示来描述这个 NFA 的翻译。 5.3 节的练习 5.3.1 下面是涉及运算符 + 和整数或浮点运算分量的表达式的文法。区分浮点数的方法是 看它有无小数点。 E -> E + T | T T -> num.num | num 给出一个 SDD 来确定每个项 T 和表达式 E 的类型 扩展这个得到的 SDD，使得它可以把表达式转换成为后缀表达式。使用一个 单目运算符 intToFloat 把一个整数转换为相等的浮点数。 解答 1. 2. 1. 产生式 语法规则 1) E -> E_1 + T E.type = E_1.type === float || T.type === float ? float : int 2) E -> T E.type = T.type
    产生式 语法规则 3) T -> num.num T.type = float 4) T -> num T.type = int 5.3.2 ! 给出一个 SDD，将一个带有 + 和 * 的中缀表达式翻译成没有冗余括号的表达式。 比如因为两个运算符都是左结合的，并且 * 的优先级高于 +，所以 ((a*(b+c))*(d)) 可翻译为 a*(b+c)*d 解答 几个属性设置：     wrapped: 表达式最外层是否有括号。 precedence: 令 +，*，() 和单 digit 的优先级分别为 0，1，2，3。 如 果表达式最外层有括号，则为去掉括号后最后被计算的运算符的优先级，否则为表 达式最后被计算的运算符的优先级。 expr: 表达式。 cleanExpr: 去除了冗余括号的表达式。 产生式 语法规则 1) L -> En L.cleanExpr = E.wrapped ? E.cleanExpr : E.expr 2) E -> E_1 + T E.wrapped = false E.precedence = 0 E.expr = E_1.expr || "+" || T.expr E.cleanExpr = (E_1.wrapped ? E_1.cleanExpr : E_1.expr) || "+" || (T.wrapped ? T.cleanExpr :
    产生式 语法规则 T.expr) E.wrapped = T.wrapped 3) E -> T E.precedence = T.precedence E.expr = T.expr E.cleanExpr = T.cleanExpr 4) T -> T_1 * F T.wrapped = false T.precedence = 1 T.expr = T_1.expr || "*" || F.expr T.cleanExpr = (T_1.wrapped && T_1.precedence >= 1 ? T_1.cleanExpr : T_1) || * || (F.wrapped && F.precedence >= 1 ? F.cleanExpr : F.expr) 5) T -> F T.wrapped = F.wrapped T.precedence = F.precedence T.expr = F.expr T.cleanExpr = F.cleanExpr 6) F -> (E) F.wrapped = true F.precedence = E.precedence F.expr = "(" || E.expr || ")" F.cleanExpr = E.expr F.wrapped = false F.precedence = 3 F.expr = digit F.cleanExpr = digit 7) F -> digit 5.3.3 !
    给出一个 SDD 对 x*(3*x+x*x) 这样的表达式求微分。表达式中涉及运算符 + 和 * 、变量 x 和常量。假设不进行任何简化，也就是说，比如 3*x 将被翻译为 3*1+0*x。 5.4 节的练习 5.4.1 我们在 5.4.2 节中提到可能根据语法分析栈中的 LR 状态来推导出这个状态表示 了什么文法符号。我们如何推导这个信息？ 解答 见算法 4.44 5.4.2 改写下面的 SDT: A -> A {a} B | A B {b} | 0 B -> B {c} A | B A {d} | 1 使得基础文法变成非左递归的。 5.4.3 ！ 下面的 SDT 计算了一个由 0 和 1 组成的串的值。它把输入的符号串当做正二进制 数来解释。 B -> B_1 0 {B.val = 2 * B_1.val} | B_1 1 {B.val = 2 * B_1.val + 1} | 1 {B.val = 1}
    改写这个 SDT，使得基础文法不再是左递归的，但仍然可以计算出整个输入串的相 同的 B.val 的值。 解答 提取左公因子 B -> B_1 digit {B.val = 2 * B_1.val + digit.val} | 1 {B.val = 1} digit -> 0 {digit.val = 0} | 1 {digit.val = 1} 在形如 A = A a | b 的左递归产生式中， a 为 digit {B.val = 2 * B_1.val + digit.val}， b 为 1 消除左递归后得 B -> 1 {A.i = 1} A A -> digit {A_1.i = 2 * A.i + digit.val} A_1 {A.val = A_1.val} | ε {A.val = A.i} digit -> 0 {digit.val = 0} | 1 {digit.val = 1} 5.4.4 ！ 为下面的产生式写出一个和例 5.19 类似的 L 属性 SDD。这里的每个产生式表示一 个常见的 C 语言那样的控制流结构。你可能需要生成一个三地址语句来跳转到某个 标号 L，此时你可以生成语句 goto L。 1. 2. 3. S -> if ( C ) S_1 else S_2 S -> do S_1 while ( C ) S -> '{' L '}'; L -> L S | ε 请注意，列表中的任何语句都可能包含一条从它的内部跳转到下一个语句的跳转指 令，因此简单地为各个语句按顺序生成代码是不够的。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料