I started doing exercise 2.4.5 in Dragon book second edition and found some answers in internet but they seems wrong for me
First of all this is the exercise:
Construct a syntax-directed translation scheme that translates postfix arithmetic expressions into equivalent prefix arithmetic expressions.
Answer from internet:
https://github.com/fool2fish/dragon-book-exercise-answers/blob/master/ch02/2.3/2.3.md
Production:
expr -> expr expr op | digit
Translation scheme:
expr -> {print(op)} expr expr op | digit {print(digit)}
I tried this scheme for two expressions 952*- and 95-2*.
952*- is transformed correctly to prefix expression (952*- => -9*52), but 95-2* not! (95-2* => -95*2, should be 95-2* => *-952)
I constructed my own scheme which seems that works correctly for both cases:
My translation scheme
I used Backus-Naur Form (BNF) in order to implement syntax directed translation with parameters
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 }
Experts! Please let me know is my translation scheme correct? And this internet answer is indeed wrong? Or I just missing something?
Thank you in advance!
I tried to evaluate translation scheme which I found in internet for values 952*-, 95-2* and it seems to be incorrect. In contrast my scheme works good, but I am not sure about other edge cases which my translation scheme may hide.
