Bottom-Up Evaluation of S-Attributed Definitions

Key Concepts

• S-Attributed Definitions: Only synthesized attributes; values derived from children nodes.
• Stack Structure: Maintains two arrays:
  • First Array: Stores grammar symbols.
  • Second Array: Stores corresponding attribute values.

Evaluation Process

1. Initialization:

   • Input example: 3 + 4 * 5 n
   • Stack starts empty.

2. Push to Stack:

   • Move first symbol to stack, e.g., 3.
   • Stack: 3 (attribute value is - if none).

3. Reduction Steps:

   • Reduce 3 to F:
     • Prediction used: F -> digit.
     • Stack updates: F with attribute value 3.
   • Continue Reducing:
     • Keep reducing F to T, then E as necessary to accommodate operators like +.
     • Replace E based on the grammar rules.
   • Next Symbol:
     • Reduce 4 to F, then T, and then E to incorporate +.
   • Incorporate Multiplication:
     • Reduce 5 similarly to be able to apply *.

4. Handling Operators:

   • Whenever reducing, always check the remaining input.
   • Keep track of values through the stack:
     • E with value 3, + with no value, T with value 4, etc.

5. Final Reductions:

   • Reduce from E + T to final E and print the result when reaching n.
   • Example Calculation: 3 + (4 * 5) = 23.

Grammar References

• Grammar Rules and Productions:
  • E -> E + T
  • T -> T * F
  • F -> digit

Summary

• The evaluation uses a stack to maintain grammar symbols and their attribute values.
• Reductions are performed based on predictions, with careful consideration of remaining input.
• Final output for the provided input expression is 23.