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. |