Exercise 6: Bottom-up evaluator

Using the bottom-up parser from the samples directory, complete BottomUpEval.hs by satisfying all TODOs. Submit your Haskell solution to esubmit.

Hints

• Start by revising the functions so they always return a constant value, say 99, so the code loads and it is obvious where you added the number.
• Fix production_rhs_at_top so it correctly matches the right hand side of a production against the match stack. Whether or not you need to call reverse depends on details of how you wrote your code, and you can change other parts of the file to get this to work. In most cases this can be done in a line or two, but it is fine if your solution is longer.
• Fix apply_action to evaluate the action against the values on the match stack. Again, you may need reverse or you may not depending on other details in your implementation. Test that eval simpleBinaryNumberGrammar "1" returns a 1.
• Fix the action for the production bits → bits bit to compute the correct value. Note the argument to this function is a list of numbers with the first number being the value of the other bits and the second being the value of the single bit.
• If you are curious, binary.g4 and binary.py implement ANTLR versions of this grammar and the intended actions.
• Write the grammar for exprGrammar as discussed in the file. When you are finished, eval simpleBinaryNumberGrammar "10110" would return 22 and eval exprGrammar "3*(1+5*2+3)" would return 42.
• If you are having difficulty picturing some piece of data, you can use trace to display values before computing results. For example, if you add

          import Debug.Trace
  

  at the top of your file and then define apply_action as

          apply_action action stack_elements = trace (show stack_elements) 0
  

  then every time apply_action is executed, the system will show what was passed as the second parameter. trace takes two arguments: a string to print and a value, and it returns the value as its result.
• To test your code, :load your file in ghci and type

          eval simpleBinaryNumberGrammar "101"
  

  When your solution is fully implement, it will return a 5. To test the expression processor:

          eval exprGrammar "3+4*5"
  

  This will return 23.
• If necessary, change your file name to BottomUpEval.hs, add the line

          module BottomUpEval where
  

  at the top. (If you got the file on Thursday, this might have been done for you.) Submit your file to esubmit as problem "ex6eval". Esubmit has have a file with main already loaded (Ex6Main.hs, if you're interested in viewing it). Esubmit will execute the main and capture the output.