In this assignment, you will use top-down parsing rather than bottom-up parsing
ID: 3794980 • Letter: I
Question
In this assignment, you will use top-down parsing rather than bottom-up parsing
Consider Boolean expressions, with the following operations: and, or, and not
(standard associativity and precedence), brackets are allowed.
Part 1. Write an S-attributed syntax directed translation for Boolean expressions
with the following tokens:
true, false, and brackets, which can be used to evaluate these expressions.
Then, write an L-attributed translation resulting from removing left recursion.
Examples:
true and not false
not false or (false and not false and true or false)
are both correct, and evaluate to true,
but 1 and true is invalid.
Explanation / Answer
We have the following rules for a boolean expression
E --> E or E
E --> E and E
E --> not E
E --> (E)
E --> true
E --> false
S-attributed SDT for boolean expression
Production Semantic Actions
E --> E1or E 2 E.value = (E1.value || E2.value)
E --> E1and E2 E.value = (E1.value && E2.value)
E --> not E 1 E.value = ~ (E1.value)
E --> (E1) E.value = E1.value
E --> true E.value = true
E --> false E.value = false
L-attributed SDT for boolean expression
Production Semantic Actions
E --> not E1 {E'.value = ~ E1.value}
E' {E.value = E'.value}
E --> (E1) {E'.value = E1.value}
E' {E.value = E'.value}
E --> true {E'.value = true}
E' {E.value = E'.value}
E --> false {E'.value = false}
E' {E.value = E'.value}
E' --> or E {E1'.value = E'.value || E.value}
E1' {E.value = E1'.value}
E' --> and E {E1'.value = E'.value && E.value}
E1' {E.value = E1'.value}
E' --> {// Do nothing}