To observe four levels of precedence, an arithmetic grammar needs to have four subparsers. Each of these subparsers handles operators of a common precedence, delegating interpretation of other operators to other subparsers. You can use the words expression , term , factor , and phrase to denote the four subparsers. To begin, you can define expression as observing the lowest level of precedence. expression = expression '+' term expression '' term term; This rule suffers from left recursion, but it properly recognizes all pluses and minuses to the left of a term before adding or subtracting the term . To remove the left recursion, it helps to abbreviate the rule e = e '+' t e '-' t t; and look at what an e might generate. For example: e => e '+' t => e '-' t '+' t => e '+' t '-' t '+' t ... => e ('+' t '-' t)* => t ('+' t '-' t)* As a pattern, e generates another e followed by 0 or more ( '+' t ) or ( '-' t ) sequences, until you generate a plain t , using the third alternate choice for e . You can describe this same pattern, avoiding left recursion, as e = t ('+' t '-' t)*; Or, unabbreviated : expression = term ('+' term '-' term)*; Using the same logic, you can define term to recognize multiplication and division as follows : term = factor ('*' factor '/' factor)*; To recognize exponents, associating them to the right, you can define factor as factor = phrase '^' factor phrase; Notice that this definition requires exponentiation of phrase to occur only after recognition of the factor to the right of the exponent sign. Thus, if a factor contains another exponent sign, the definition calls for a parser to recognize it first, and exponentiation associates to the right. There is no left recursion to remove in this rule, so it is fine as written. The last rule the grammar needs is for phrase , which defines the highest level of precedence: phrase = '(' expression ')' Num; Putting the rules together, the grammar is expression = term ('+' term '-' term)*; term = factor ('*' factor '/' factor)*; factor = phrase '^' factor phrase; phrase = '(' expression ')' Num; This grammar recognizes properly formed arithmetic expressions. The next step in designing an arithmetic parser is to determine how to use assemblers to evaluate expressions as the parser recognizes them. |