Skip to content

answer6.md

Latest commit

 

History

History
544 lines (382 loc) · 12.1 KB

answer6.md

File metadata and controls

544 lines (382 loc) · 12.1 KB
  1. 写出如下语法制导定义中的继承属性和综合属性。 S → D1 . D2 { S.v := D1.v+D2.v; D1.f : =1; D2.f :=2-D2.l } D → D1 B { D1.f := 2D.f; B.f : = D.f; D.v := D1.v+B.v; D.l := D1.l +1 } D → B { D.l := 1 ; D.v := B.v ; B.f := D.f } B → 1 { B.v := B.f } B → 0 { B.v := 0 } 说明: D1 和 D2 为 D 的不同出现; D1 . D2 中的 . 是小数点; S.v 中的 . 用于表明 v 是 S 的一个属性。

解答：

在给定的语法制导定义中，我们需要区分综合属性（Synthesized Attributes）和继承属性（Inherited Attributes），并解释它们的作用。

1. 综合属性：

综合属性是从子节点的属性计算得到的，即从语法树的子节点向上传递。

  • S.v：在产生式 S → D1 . D2 中，计算得来： [ S.v = D1.v + D2.v ] 解释：S.v 是由其子节点 D1 和 D2 的属性综合而成的，所以是综合属性。

  • D.v：在产生式中，根据子节点的属性计算：

    • 对于 D → D1 B： [ D.v = D1.v + B.v ]
    • 对于 D → B： [ D.v = B.v ] 解释：D.v 取决于其子节点 D1、B 或仅 B 的属性，是综合属性。

  • D.l：表示 D 的长度，也是综合属性：

    • 对于 D → D1 B： [ D.l = D1.l + 1 ]
    • 对于 D → B： [ D.l = 1 ] 解释：D.l 是基于子节点的长度计算得到的，是综合属性。

  • D1.v、D1.l、D2.v、D2.l： 解释：D1 和 D2 是非终结符 D 的实例，其属性 v 和 l 也是通过子节点综合得到的，因此是综合属性。

  • B.v：

    • 对于 B → 1： [ B.v = B.f ]
    • 对于 B → 0： [ B.v = 0 ] 解释：B.v 是由自身或其子节点的属性计算得来，是综合属性。

2. 继承属性：

继承属性是从父节点或兄弟节点传递下来的，即从语法树的父节点向下传递。

  • D.f： 解释：D.f 是由父节点传递给 D 的属性，用于计算子节点的属性，因此是继承属性。

  • D1.f、D2.f：

    • 在产生式 S → D1 . D2 中： [ \begin{cases} D1.f = 1 \ D2.f = 2 - D2.l \end{cases} ] 解释：D1.f 和 D2.f 是由父节点 S 赋值的，用于传递给子节点 D1 和 D2，所以是继承属性。

  • B.f：

    • 在产生式 D → D1 B 中： [ B.f = D.f ]
    • 在产生式 D → B 中： [ B.f = D.f ] 解释：B.f 是由父节点 D 传递给子节点 B 的属性，因此是继承属性。

  • D1.f（在 D → D1 B 中）： [ D1.f = 2 \times D.f ] 解释：D1.f 继承自父节点 D，用于进一步传递或计算，是继承属性。

3. 属性解释：

  • f 属性（继承属性）：

    • 用于在节点间传递系数或参数，影响子节点的计算。
    • 例如，D.f 被传递给 D1.f 和 B.f，影响它们的计算。

  • v 属性（综合属性）：

    • 表示节点的值，通过计算子节点的值得到。
    • 例如，S.v 是 D1.v 和 D2.v 的和。

  • l 属性（综合属性）：

    • 表示节点的长度或层次，通过计算子节点的长度得到。
    • 例如，D.l 是 D1.l 加上 1。

4. 综合属性和继承属性的作用：

  • 综合属性：

    • 用于从下往上计算属性值，汇总子节点的信息。
    • 适合表示语法分析中自底向上的计算，如求值、类型检查等。

  • 继承属性：

    • 用于从上往下传递信息，将父节点的参数或环境传递给子节点。
    • 适合表示需要上下文信息的计算，如作用域、参数传递等。

总结：

在上述语法制导定义中，综合属性主要用于计算节点的值和长度，继承属性用于在节点间传递参数或影响子节点的计算。通过综合属性和继承属性的协同工作，实现了对语法结构的完整语义描述。

  1. 为文法 E → (L) | a L → L, E | E 写一个语法制导定义，要求输出括号的对数。

解答：

为了计算输入中括号的对数，我们需要为给定的文法编写一个语法制导定义（SDD），使用属性来累计括号对的数量。

给定文法：

  1. E → ( L )
  2. E → a
  3. L → L , E
  4. L → E

设计属性：

  • 对于每个非终结符 E 和 L，我们定义一个综合属性 count，表示该节点对应的子树中括号对的数量。
  • 终结符 a 不产生括号对，其 count 值为 0。

语法制导定义：

  1. E → ( L )

    语义动作：

    E.count = L.count + 1;

    解释：

    • 当前产生式引入了一对括号，因此在 L 的括号对数量基础上加 1。

  2. E → a

    语义动作：

    E.count = 0;

    解释：

    • 终结符 a 不包含括号对，计数为 0。

  3. L → L , E

    语义动作：

    L.count = L1.count + E.count;

    注意：

    • 这里需要区分左侧的 L 和右侧的 L，因此用 L1 表示左侧的 L。

    解释：

    • L 的括号对数量为左侧 L1 和右侧 E 的括号对数量之和。

  4. L → E

    语义动作：

    L.count = E.count;

    解释：

    • L 的括号对数量等于其子节点 E 的括号对数量。

完整的语法制导定义：

1. E → ( L )
   {
     E.count = L.count + 1;
   }

2. E → a
   {
     E.count = 0;
   }

3. L → L1 , E
   {
     L.count = L1.count + E.count;
   }

4. L → E
   {
     L.count = E.count;
   }

示例解析：

让我们通过一个示例输入来说明这个语法制导定义是如何工作的。

示例输入：

( a , ( a ) , a )

对应的语法树：

          E
          |
        ( L )
          |
      -----------------
      |       |       |
     L1       ,       E
     |                |
     E              ( L )
     |                |
     a                E
                      |
                      a

计算过程：

  1. 最内层的 E → a

    E.count = 0;

  2. L → E

    L.count = E.count = 0;

  3. E → ( L )

    E.count = L.count + 1 = 0 + 1 = 1;

  4. 左侧的 E → a

    E.count = 0;

  5. L1 → E

    L1.count = E.count = 0;

  6. 中间的 L → L1 , E

    L.count = L1.count + E.count = 0 + 1 = 1;

  7. 最外层的 E → ( L )

    E.count = L.count + 1 = 1 + 1 = 2;

结果：

  • 整个输入的括号对数为 E.count = 2。

总结：

通过为每个非终结符定义综合属性 count，并在语义动作中累加括号对的数量，我们成功地编写了一个语法制导定义来计算输入中的括号对数。

备注：

  • 属性类型： 这里使用的都是综合属性，值从子节点向父节点传递。
  • 计算逻辑： 在处理 E → ( L ) 时，括号对数加 1；在处理 L → L1 , E 时，累加左右部分的括号对数。

扩展：

如果需要在语法分析的过程中输出括号对数，可以在开始符号的语义动作中打印 E.count 的值。

S → E
{
  输出 "括号对数："，E.count;
}

这样，当整个输入被成功解析后，会输出括号的总对数。

结论：

通过上述语法制导定义，我们成功地实现了对给定文法的括号对数计算，满足题目要求。

  1. 为如下文法写一个 S-属性的语法制导定义，用 E 的综合属 性 val 给出下面文法中 E 产生的二进制数的十进制值。例如， 输入 101.101 时，E.val=5.625。 E -> L . R | L L -> L B | B R -> B R | B B -> 0 | 1

解答：

要为给定的文法编写一个 S-属性（仅使用综合属性）的语法制导定义，使得非终结符 E 的综合属性 E.val 能够计算输入的二进制数对应的十进制值。

给定文法：

  1. E → L . R
  2. E → L
  3. L → L B
  4. L → B
  5. R → B R
  6. R → B
  7. B → 0
  8. B → 1

设计思路：

  • 整数部分（左侧 L）：

    • 从左到右处理二进制位，逐位计算十进制值。
    • 使用综合属性 L.str 存储整数部分的二进制字符串。
    • 定义函数 str_to_int(s) 将二进制字符串转换为十进制整数。

  • 小数部分（右侧 R）：

    • 从左到右处理小数部分的二进制位，逐位计算十进制值。
    • 使用综合属性 R.str 存储小数部分的二进制字符串。
    • 定义函数 str_to_frac(s) 将二进制小数字符串转换为十进制小数。

  • 终结符 B：

    • B.val 为对应的数字 0 或 1。
    • B.digit 为字符形式的 '0' 或 '1'，用于构建字符串。

语法制导定义（SDD）：

  1. B → 0

    B.digit := '0';

  2. B → 1

    B.digit := '1';

  3. L → B

    L.str := B.digit;

  4. L → L1 B

    L.str := L1.str || B.digit;

    说明：|| 表示字符串连接。

  5. R → B

    R.str := B.digit;

  6. R → B R1

    R.str := B.digit || R1.str;

    **说明：**小数部分从左到右处理，需要保持顺序。

  7. E → L

    E.intStr := L.str;
E.fracStr := "";
E.val := str_to_int(E.intStr);

    **说明：**当没有小数部分时，小数字符串为空，E.val 仅为整数部分的值。

  8. E → L . R

    E.intStr := L.str;
E.fracStr := R.str;
E.val := str_to_int(E.intStr) + str_to_frac(E.fracStr);

    说明：E.val 为整数部分和小数部分之和。

辅助函数定义：

  • 函数 str_to_int(s)：

    def str_to_int(s):
    value = 0
    for c in s:
        value = value * 2 + int(c)
    return value

    **说明：**逐位将二进制字符串转换为十进制整数。

  • 函数 str_to_frac(s)：

    def str_to_frac(s):
    value = 0.0
    factor = 0.5
    for c in s:
        value += int(c) * factor
        factor /= 2
    return value

    **说明：**逐位将二进制小数字符串转换为十进制小数。

示例计算：

输入：101.101

解析步骤：

  1. 处理整数部分 L：

    • L → L1 B
      • L1.str = '10', B.digit = '1'
      • L.str = '10' || '1' = '101'

  2. 处理小数部分 R：

    • R → B R1
      • B.digit = '1', R1.str = '01'
      • R.str = '1' || '01' = '101'

  3. 计算 E.val：

    • E.intStr = '101'
    • E.fracStr = '101'
    • E.val = str_to_int('101') + str_to_frac('101')

  4. 计算整数部分：

    • str_to_int('101'):
      • 初始值：value = 0
      • 处理 '1'：value = 0 * 2 + 1 = 1
      • 处理 '0'：value = 1 * 2 + 0 = 2
      • 处理 '1'：value = 2 * 2 + 1 = 5
      • 整数部分值：5

  5. 计算小数部分：

    • str_to_frac('101'):
      • 初始值：value = 0.0, factor = 0.5
      • 处理 '1'：value += 1 * 0.5 = 0.5, factor = 0.25
      • 处理 '0'：value += 0 * 0.25 = 0.5, factor = 0.125
      • 处理 '1'：value += 1 * 0.125 = 0.625, factor = 0.0625
      • 小数部分值：0.625

  6. 最终结果：

    • E.val = 5 + 0.625 = 5.625

解释：

  • 综合属性：

    • 所有属性都是综合属性，从子节点向父节点传递。
    • B.digit：表示当前位的字符 '0' 或 '1'。
    • L.str、R.str：累积的二进制字符串。
    • E.intStr、E.fracStr：整数和小数部分的二进制字符串。
    • E.val：最终计算的十进制值。

  • 处理顺序：

    • 整数部分从左到右处理，符合二进制数的位权重。
    • 小数部分也从左到右处理，但需要注意位权重是负指数，使用 factor 控制。

  • 函数作用：

    • str_to_int(s)：将二进制整数部分转换为十进制。
    • str_to_frac(s)：将二进制小数部分转换为十进制。

总结：

通过以上的 S-属性语法制导定义，我们成功地为给定的文法编写了一个能够计算二进制数对应十进制值的方案。所有属性都是综合属性，符合 S-属性文法的要求。