| A convention that arises especially in arithmetic relates to associativity. Conventionally, multiplication, division, addition, and subtraction "associate" to the left. A parser must evaluate the leftmost operation first for operations of the same precedence. For example, System.out.println(25 16 - 9); prints . If Java calculated the rightmost subtraction first, the answer would instead be 18 . Exponentiation, on the other hand, conventionally associates to the right. Associating to the right means that a parser must evaluate the rightmost exponentiation first. Thus, 5^3^2 is equal to 5^9 , or 1953125 . If exponentiation associated to the left, like subtraction, then 5^3^2 would equal 125^2 , or 15625 . Java sidesteps the particular point of power precedence by not offering an exponentiation operator. However, in Java the assignment operator " = " and all assignment-with-operation operators, such as " *= ", associate to the right, as does the conditional operator "? = ". Java in a Nutshell [Flanagan] discusses all of Java's operators. Chapter 3, "Building a Parser," uses the reduced arithmetic language Minimath to show where assemblers plug in to a parser. This little language also serves to show associativity problems that can arise in a grammar. Minimath contains arithmetic expressions that contain only the minus operator. For example, Minimath contains {"0.0", "1.2 2.3", "100 90 80 - 70", "47 43 - 41", ...} The following grammar describes this language. // Grammar G1 e = Num '' e Num; // suffers from incorrect associativity! Let's call this grammar G1 . G1 describes all the elements of Minimath, but G1 is problematic because of associativity. For example, consider how this grammar will portray the string "25 “ 16 - 9" . Conventionally, this string is equal to "(25 - 16) - 9" . This convention means that subtraction associates to the left; in other words, the leftmost subtraction should happen first. However, G1 matches this string as "Num - e" , or "25 - e" . This guides a parser for G1 to calculate the value of e and subtract it from 25 , and that gives an incorrect result. Here is an implementation of G1 : package sjm.examples.minimath; import sjm.parse.*; import sjm.parse.tokens.*; import sjm.examples.arithmetic.*; /** * This class uses a problematic grammar for Minimath. For * a better grammar, see class <code>MinimathCompute</code>. * Here, the grammar is: * * <blockquote><pre> * e = Num '-' e Num; * </pre></blockquote> * * Writing a parser directly from this grammar will show * that the associativity is wrong. For example, this * grammar will lead to a parser that calculates the value * of 25 - 16 - 9 as 18. */ public class MiniWrongAssociativity { /** * Demonstrates incorrect associativity. */ public static void main(String args[]) { Alternation e = new Alternation(); Num n = new Num(); n.setAssembler(new NumAssembler()); Sequence s = new Sequence(); s.add(n); s.add(new Symbol('-').discard()); s.add(e); s.setAssembler(new MinusAssembler()); e.add(s); e.add(n); Assembly out = e.completeMatch(new TokenAssembly("25 - 16 - 9")); System.out.println(out.pop() + " // arguably wrong!"); } } This class uses assemblers from sjm.examples.arithmetic to show the results that the grammar leads to. This class prints 18.0 // arguably wrong! To get conventional associativity, you really want this grammar: // Grammar G2 e = e '' Num Num; // suffers from left recursion! This grammar has a new problem, namely left recursion, that the next section addresses. It turns out that you can transform a grammar to avoid left recursion. It is important to fix associativity first because transformation to avoid left recursion does not alter the grammar's associativity. Getting the desirable associativity depends on whether an operator should associate to the right or the left. If a rule needs right association for an operator, then you should write the grammar so that it will first match the rightmost operator in a sequence of like operators. For example, exponentiation should associate to the right; "2 ^ 1 ^ 4" should equal "2 ^ 1" . To achieve this effect, write the grammar as follows : // Grammar G3 e = Num '^' e Num; This grammar matches "2 ^ 1 ^ 4" as "2 ^ e" , which is correct. The conventional value of this string is 2^e , where e is the value of 1^4 . In short, you can use G2 as a template for achieving left associativity in a rule, and G3 as a template for achieving right associativity. Once the associativity of your language is correct, you need to check it for left recursion. | 
