编译原理习题CH2.3

❖ 题目 2.3.1（Problem 2.3.1）

构造一个语法制导翻译方案（SDT），将中缀表达式翻译为前缀表达式（即运算符在操作数前）。
例如，x - y 的前缀表达为 - x y。
请给出字符串 9 - 5 + 2 和 9 - 5 * 2 的带注释的语法树（annotated parse trees）。

✅ 解答（Answer）

🧩 文法（Grammar）

1
2
3
4
5
6
7
8
9
10
expr   → expr + term
       | expr - term
       | term

term   → term * factor
       | term / factor
       | factor

factor → digit
       | ( expr )

🛠 语法制导翻译方案（Translation Scheme）

1
2
3
4
5
6
7
8
9
10
expr   → {print("+")} expr + term
       | {print("-")} expr - term
       | term

term   → {print("*")} term * factor
       | {print("/")} term / factor
       | factor

factor → digit {print(digit)}
       | ( expr )

🌳 注释语法树示例（Annotated Parse Tree）

  1. 输入：9 - 5 + 2

推导方式（按优先级）：

1
2
3
expr → expr + term
     → expr - term + term
     → digit - digit + digit

前缀翻译输出为：

1
+ - 9 5 2

即：先处理 9 - 5，再加上 2，对应前缀为 + - 9 5 2

  1. 输入：9 - 5 \* 2

推导方式：

1
2
3
4
expr → expr - term
     → digit - term
     → digit - term * factor
     → digit - digit * digit

前缀翻译输出为：

1
- 9 * 5 2

即：先做乘法 5 * 2，再用 9 - (...)，对应前缀为 - 9 * 5 2

✅ 中文解释（Chinese Explanation）

  • 中缀表达式：运算符在两个操作数之间，如 x - y
  • 前缀表达式：运算符在前，如 - x y
  • 我们在语法规则中将打印操作嵌入到左递归结构的前面，确保每当遇到运算符时，它优先输出。
  • 数字 digit 是最基础的，打印时直接输出。

❖ 题目 2.3.2（Problem 2.3.2）

构造一个语法制导翻译方案（SDT），将后缀表达式翻译为中缀表达式（即运算符在中间）。
例如，95-2* 应该翻译为 (9 - 5) * 2。
请给出字符串 95-2* 和 952*- 的带注释语法树。

✅ 解答（Answer）

🧩 文法（Grammar）

1
2
3
4
5
expr → expr expr +
     | expr expr -
     | expr expr *
     | expr expr /
     | digit

🛠 语法制导翻译方案（Translation Scheme）

1
2
3
4
5
expr → expr expr {print("+")} +
     | expr expr {print("-")} -
     | expr expr {print("*")} *
     | expr expr {print("/")} /
     | digit {print(digit)}

或更清晰写法（另一种答案）：

1
2
E → {print("(")} E {print(op)} E {print(")")} op
   | digit {print(digit)}

🌳 注释语法树示例（Annotated Parse Tree）

  1. 输入：95-2*

分析顺序：

1
2
expr → expr expr *  
         ↳ expr expr - （先计算 9 - 5）

对应中缀为：

1
( (9 - 5) * 2 )

输出结果：((9-5)*2)

  1. 输入：952*-

分析顺序：

1
2
expr → expr expr -
         ↳ expr expr * （先计算 5 * 2）

对应中缀为：

1
(9 - (5 * 2))

输出结果：(9-(5*2))

✅ 中文解释（Chinese Explanation）

  • 后缀表达式：操作数先出现，运算符在最后，例如 95-2* 表示 (9 - 5) * 2
  • 我们构造规则时，要先处理两个操作数的翻译，再在后面输出运算符，结合括号实现正确的中缀结构
  • 特别注意括号必须加上，否则顺序可能会出错

📘 Section 2.3 Exercises

❖ 题目 2.3.3（Problem 2.3.3）

Construct a syntax-directed translation scheme that translates integers into Roman numerals.
构造一个语法制导翻译方案，将“十进制整数”转换为“罗马数字”。

✅ 解答（Answer）

🌱 辅助函数（Helper Function）

1
repeat(sign, times) // repeat('X', 3) = 'XXX'

🧩 文法（Grammar）

1
num → thousand hundred ten digit

🛠 语法制导翻译方案（Syntax-Directed Translation）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
num → thousand hundred ten digit
     { num.roman = thousand.roman || hundred.roman || ten.roman || digit.roman;
       print(num.roman) }

thousand → low
     { thousand.roman = repeat('M', low.v) }

hundred → low
     { hundred.roman = repeat('C', low.v) }
        | 4
     { hundred.roman = 'CD' }
        | high
     { hundred.roman = 'D' || repeat('C', high.v - 5) }
        | 9
     { hundred.roman = 'CM' }

ten → low
     { ten.roman = repeat('X', low.v) }
     | 4
     { ten.roman = 'XL' }
     | high
     { ten.roman = 'L' || repeat('X', high.v - 5) }
     | 9
     { ten.roman = 'XC' }

digit → low
     { digit.roman = repeat('I', low.v) }
     | 4
     { digit.roman = 'IV' }
     | high
     { digit.roman = 'V' || repeat('I', high.v - 5) }
     | 9
     { digit.roman = 'IX' }

low → 0 {low.v = 0}
     | 1 {low.v = 1}
     | 2 {low.v = 2}
     | 3 {low.v = 3}

high → 5 {high.v = 5}
      | 6 {high.v = 6}
      | 7 {high.v = 7}
      | 8 {high.v = 8}

🧠 中文解释（Chinese Explanation）

  • 本翻译方案将整数分成 千位、百位、十位、个位 四个部分逐一转换为罗马数字。
  • 使用辅助函数 repeat() 重复打印字母，例如：300 → repeat('C', 3) = CCC
  • 对于 4 和 9 特殊处理，例如 4 → IV, 9 → IX
  • low 表示 0-3，high 表示 5-8，通过 5 + low 或 high.v - 5 构造组合形式

❖ 题目 2.3.4（Problem 2.3.4）

Construct a syntax-directed translation scheme that translates Roman numerals into integers.
构造一个语法制导翻译方案，将“罗马数字”转换为“十进制整数”。

✅ 解答（Answer）

🧩 文法（Grammar）

1
2
3
4
5
6
7
8
romanNum → thousand hundred ten digit
thousand → M | MM | MMM | ε
hundred → smallHundred | CD | D smallHundred | CM
smallHundred → C | CC | CCC | ε
ten → smallTen | XL | L smallTen | XC
smallTen → X | XX | XXX | ε
digit → smallDigit | IV | V smallDigit | IX
smallDigit → I | II | III | ε

🛠 语法制导翻译方案（Translation Scheme）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
romanNum → thousand hundred ten digit
    { romanNum.v = thousand.v + hundred.v + ten.v + digit.v;
      print(romanNum.v) }

thousand → M    {thousand.v = 1000}
         | MM   {thousand.v = 2000}
         | MMM  {thousand.v = 3000}
         | ε    {thousand.v = 0}

hundred → smallHundred          {hundred.v = smallHundred.v * 100}
        | CD                    {hundred.v = 400}
        | D smallHundred        {hundred.v = 500 + smallHundred.v * 100}
        | CM                    {hundred.v = 900}

smallHundred → C   {smallHundred.v = 1}
              | CC {smallHundred.v = 2}
              | CCC{smallHundred.v = 3}
              | ε  {smallHundred.v = 0}

ten → smallTen          {ten.v = smallTen.v * 10}
    | XL                {ten.v = 40}
    | L smallTen        {ten.v = 50 + smallTen.v * 10}
    | XC                {ten.v = 90}

smallTen → X    {smallTen.v = 1}
          | XX  {smallTen.v = 2}
          | XXX {smallTen.v = 3}
          | ε   {smallTen.v = 0}

digit → smallDigit       {digit.v = smallDigit.v}
      | IV               {digit.v = 4}
      | V smallDigit     {digit.v = 5 + smallDigit.v}
      | IX               {digit.v = 9}

smallDigit → I    {smallDigit.v = 1}
            | II  {smallDigit.v = 2}
            | III {smallDigit.v = 3}
            | ε   {smallDigit.v = 0}

🧠 中文解释（Chinese Explanation）

  • 罗马数字采用加法规则（例如 XX = 10 + 10）或“减法规则”如 IV = 5 - 1 = 4。
  • 把罗马数分为千、百、十、个位模块，每个部分独立处理。
  • smallXxx 处理1~3；组合如 IV, IX, XL, XC 等是“减法表示”的特殊值。
  • 所有非终结符最终都传递一个 .v 值代表对应的数值。

📘 Exercise 2.3.5

❖ Problem（题目）

Construct a syntax-directed translation scheme that translates postfix arithmetic expressions into equivalent prefix arithmetic expressions.
构造一个语法制导翻译方案，将后缀算术表达式转换为等价的前缀算术表达式。

✅ Answer（答案）

📌 文法（Grammar）

1
2
expr → expr expr op  
     | digit

解释：

  • expr expr op 是后缀表达式中的标准结构，如 9 5 - 表示 9 - 5
  • digit 是数字，终结符

🛠 语法制导翻译方案（Syntax-Directed Translation Scheme）

1
2
expr → {print(op)} expr expr op  
     | digit {print(digit)}

🧠 中文解释（Chinese Explanation）

💡 思路：

  • 后缀表达式形式：操作数在前，运算符在后，如 9 5 +。
  • 前缀表达式形式：运算符在前，操作数在后，如 + 9 5。
  • 所以转换的关键是：在识别 expr expr op 结构时，先打印运算符，再递归转换两个子表达式。