《龙书》后缀转前缀表达式翻译方案正确性咨询

网上方案的错误确认 #

你找到的网上方案确实存在错误，具体分析如下：

方案内容 #

生产式：

expr -> expr expr op | digit

翻译方案：

expr -> {print(op)} expr expr op | digit {print(digit)}

错误原因 #

1. 动作位置逻辑错误：该方案在未读取到运算符op的情况下就执行print(op)，不符合语法制导翻译的基本规则——只有当产生式右部的符号全部匹配完成后，才能使用对应的符号属性。
2. 输出顺序错误：以测试用例95-2*（对应前缀*-952）为例，该方案的执行顺序会先处理95-输出-95，再处理2输出2，最后遇到*时输出*，最终得到-95*2，完全颠倒了运算符和操作数的顺序，违背了后缀转前缀的核心逻辑（后缀A B op应转换为前缀op A B）。

你的方案分析与问题点 #

你设计的方案通过拆分expr（加减）、term（乘除）、fact（原子）的层级来处理运算符优先级，能正确处理测试的两个用例，但存在几个需要修正的问题和未覆盖的边缘情况：

方案代码整理 #

Exercise 2.3.5
(postfix 1 and 2 is used just to differ production instances)

root -> expr

expr -> expr1 term + expr2 | 
    expr1 term - expr2 | 
    term

term -> term fact * term |
    term fact / term |
    term

fact -> digit | 
    expr | 
    e

digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Translation scheme:

root -> expr { root.value = expr.prefix; print(root.value) }

expr -> expr1 term + expr2 { 
    expr.prefix = expr2.op || '+' || expr1.prefix || term.prefix || expr2.digits, 
    expr.op = '+',
    expr.digits = expr1.digits || term.digits || expr2.prefix   
}
expr -> expr1 term - expr2 { 
    expr.prefix = expr2.op || '-' || expr1.prefix || term.prefix || expr2.digits, 
    expr.op = '-',
    expr.digits = expr1.digits || term.digits || expr2.prefix   
}
expr -> term {
    expr.prefix = term.prefix,
    expr.op = term.op,
    expr.digits = term.digits 
}

term -> term1 fact * term2 {
    term.prefix = term2.op || '*' || term1.prefix || fact.prefix || term2.digits, 
    term.op = '*',
    term.digits = term1.digits || fact.digits || term2.prefix   
}
term -> term1 fact / term2 {
    term.prefix = term2.op || '/' || term1.prefix || fact.prefix || term2.digits, 
    term.op = '/',
    term.digits = term1.digits || fact.digits || term2.prefix   
}
term -> fact {
    term.prefix = fact.prefix,
    term.op = fact.op,
    term.digits = fact.digits 
}

fact -> digit {
    fact.prefix = e,
    fact.op = e,
    fact.digit = digit.value
}
fact -> expr {
    fact.prefix = expr.prefix,
    fact.op = expr.op,
    fact.digit = expr.digit
}
fact -> e {
    fact.prefix = e,
    fact.op = e,
    fact.digit = e
}

digit -> 0 { digit.value = 0 }
digit -> 1 { digit.value = 1 }
digit -> 2 { digit.value = 2 }
digit -> 3 { digit.value = 3 }
digit -> 4 { digit.value = 4 }
digit -> 5 { digit.value = 5 }
digit -> 6 { digit.value = 6 }
digit -> 7 { digit.value = 7 }
digit -> 8 { digit.value = 8 }
digit -> 9 { digit.value = 9 }

存在的问题 #

1. 文法与后缀表达式结构不匹配：后缀表达式的核心结构是「操作数1 操作数2 运算符」，但你的产生式如expr -> expr1 term + expr2不符合该结构，会导致解析逻辑混乱，无法正确对应后缀表达式的语法规则。
2. 单数字表达式处理错误：当输入为单数字（如5）时，fact->digit设置fact.prefix = e（空），最终root.value为空，无法输出正确的前缀5。
3. 冗余产生式：fact -> e（空产生式）没有实际意义，后缀表达式不存在空原子，反而会导致解析错误。
4. 变量名不一致：fact的属性是digit（单数），但expr和term的属性用digits（复数），会导致属性传递错误。
5. 结合性未正确处理：对于连续同优先级运算符（如后缀95-3-，对应前缀--953），当前方案的逻辑无法保证正确的结合顺序。

修正建议 #

正确的后缀转前缀语法制导翻译应基于后缀表达式的文法，结合属性传递实现：

1. 采用符合后缀结构的文法：

expr -> expr expr '+' | expr expr '-' | term
term -> term term '*' | term term '/' | fact
fact -> digit

2. 为每个非终结符添加prefix属性，语义动作在归约时拼接前缀：

expr -> expr1 expr2 '+' { expr.prefix = '+' || expr1.prefix || expr2.prefix }
expr -> expr1 expr2 '-' { expr.prefix = '-' || expr1.prefix || expr2.prefix }
expr -> term { expr.prefix = term.prefix }

term -> term1 term2 '*' { term.prefix = '*' || term1.prefix || term2.prefix }
term -> term1 term2 '/' { term.prefix = '/' || term1.prefix || term2.prefix }
term -> fact { term.prefix = fact.prefix }

fact -> digit { fact.prefix = digit.value }

digit -> '0' { digit.value = '0' }
...
digit -> '9' { digit.value = '9' }

该方案通过自底向上归约时拼接前缀，能正确处理所有后缀表达式，包括你测试的用例和边缘情况。

内容的提问来源于stack exchange，提问作者Artyom Vorontsov