2.3 节的练习
2.3.1
构建一个语法制导翻译方案,该方案把算数表达式从中缀表达式翻译成前缀表达式。
解答
产生式:
expr -> expr + term | expr - term | termterm -> term * factor | term / factor | factorfactor -> digit | (expr)
翻译方案:
expr -> {print("+")} expr + term | {print("-")} expr - term | termterm -> {print("*")} term * factor | {print("/")} term / factor | factorfactor -> digit {print(digit)} | (expr)
2.3.2
构建一个语法制导翻译方案,该方案把算数表达式从后缀表达式翻译成中缀表达式。
解答
产生式:
expr -> expr expr + | expr expr - | expr expr * | expr expr / | digit
翻译方案:
expr -> expr {print("+")} expr + | expr {print("-")} expr - | {print("(")} expr {print(")*(")} expr {print(")")} * | {print("(")} expr {print(")/(")} expr {print(")")} / | digit {print(digit)}
疑问
参考答案是:
E -> {print("(")} E {print(op)} E {print(")"}} op | digit {print(digit)}
起初我的答案也是这样,但发现括号冗余比较严重,才改成现在的解答。虽然在多级优先级运算中,其实只能减少最低优先级运算的括号,不过看起来在这样的情况下还是能节约比较多括号的。这个解法正确否?
2.3.3
构建一个将整数翻译成罗马数字的语法制导翻译方案。
解答
辅助方法:
repeat(sign, times) // 将 sign 重复 times 次输出,如 repeat('a',2) = 'aa'
翻译方案:
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('X', 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}
2.3.4
构建一个将罗马数字翻译成整数的语法制导方案。
解答
产生式:
romanNum -> thousand hundred ten digitthousand -> M | MM | MMM | ε hundred -> smallHundred | C D | D smallHundred | C MsmallHundred -> C | CC | CCC | εten -> smallTen | X L | L smallTen | X CsmallTen -> X | XX | XXX | εdigit -> smallDigit | I V | V smallDigit | I XsmallDigit -> I | II | III | ε
翻译方案:
romanNum -> thousand hundred ten digit {romanNum.v = thousand.v || hundred.v || ten.v || digit.v; print(romanNun.v)}thousand -> M {thousand.v = 1} | MM {thousand.v = 2} | MMM {thousand.v = 3} | ε {thousand.v = 0} hundred -> smallHundred {hundred.v = smallHundred.v} | C D {hundred.v = smallHundred.v} | D smallHundred {hundred.v = 5 + smallHundred.v} | C M {hundred.v = 9}smallHundred -> C {smallHundred.v = 1} | CC {smallHundred.v = 2} | CCC {smallHundred.v = 3} | ε {hundred.v = 0}ten -> smallTen {ten.v = smallTen.v} | X L {ten.v = 4} | L smallTen {ten.v = 5 + smallTen.v} | X C {ten.v = 9}smallTen -> X {smallTen.v = 1} | XX {smallTen.v = 2} | XXX {smallTen.v = 3} | ε {smallTen.v = 0}digit -> smallDigit {digit.v = smallDigit.v} | I V {digit.v = 4} | V smallDigit {digit.v = 5 + smallDigit.v} | I X {digit.v = 9} smallDigit -> I {smallDigit.v = 1} | II {smallDigit.v = 2} | III {smallDigit.v = 3} | ε {smallDigit.v = 0}
疑问
参考答案和我的解法有一个显著的区别,如下:
LowHundreds → ε { LowHundreds.val = 0; } | C { LowHundreds.val = 100; } | CC { LowHundreds.val = 200; } | CCC { LowHundreds.val = 300; }
所以他的最后一步获得翻译后的数字是用的加法:
RomanNumeral → Thousands Hundreds Tens Ones { RomanNumeral.val = Thousands.val + Hundreds.val + Tens.val + Ones.val; printf(“%d\n”, RomanNumeral.val;) }
看起来我的解法因为使用了更少的0而节约了一些空间,其他也没看出什么坏处,是这样?
2.3.5
构建一个将后缀表达式翻译成前缀表达式的语法制导翻译方案。
解答
产生式:
expr -> expr expr op | digit
翻译方案:
expr -> {print(op)} expr expr op | digit {print(digit)}