Implicit rules for associativity are defined for a language so that evaluating expressions involving operations at the same level of precedence can determine the order of operation. Left to right expression evaluation is commonly found in most programming languages. This means that the expression a / b / c is treated as (a / b) / c. If we were to fill in values for a, b and c, the expression, 30 / 6 / 2 , would be treated as (30 / 6) / 2 which yields 2.5. On the other hand if the implicit rule was right to left expression evaluation, the expression 30 / 6 / 2 , would be treated as 30 / (6 / 2) which yields 10.

Precedence adds yet another level of complexity to the issue. Precedence rules define the order in which operators of different precedence levels are evaluated. These rules are based on the hierarchy of operator priorities. Operators with higher priorities are evaluated first. The expression 5 + 2 * 3 + 4 will yield very different results depending on the language’s associativity and precedence rules. The expression yields 25 if the language has no operator precedence and associativity is strictly left to right. The expression yields 19 if the language has no operator precedence and associativity is strictly right to left. However, if the multiplication operator (*) has a higher precedence (or priority) than the addition operator (+), left to right associativity yields 15 as does right to left associativity.

In the previous SPoc lab right to left evaluation with no precedence was implemented to evaluate expressions. This lab requires you to examine two other possibilities and explain their implementation in terms of associativity and precedence with respect to expression evaluation This will neither affect the parsing of a SPoc program or the execution of SPoc programs. However, these modifications will affect how expressions are evaluated in the environment. You must examine the contents of files A.spoc, B1.spoc, and B2.spoc (each containing an alternative parse-expression function) to discover the associativity and precedence rules encoded in those different versions of parse-expression.

Run the following two SPoc programs and record the different outputs displayed with your current parse-expression implementation, with A.spoc’s parse-expression inserted in place of your current parse-expression, with B1.spoc’s parse-expression inserted, and with B2.spoc’s parse-expression inserted. After recording eight sets of output, explain the associativity and precedence rules for each of the three implementations. You may need to construct additional tests to uncover the difference between B1 and B2 .

Once you have discovered the rules followed for each of the existing parse-expressions, write a new parse-expression with yet a different combination of associativity and precedence rules applied. (Likely, some form of right to left with precedence.) Then show two more sets of output, one for each of the following programs.

program expression1
declare d $
begin
  d = ( 4 + 3 * 5 - 2 ) $
  print d $
end

program expression2
declare d $
begin
  d = ( 4 - 3 * 1 - 2 ) $
  print d $
end