There is one common situation where the rules given above for resolving conflicts are not sufficient. This is in the parsing of arithmetic expressions. Most of the commonly used constructions for arithmetic expressions can be naturally described by the notion of precedence levels for operators, together with information about left or right associativity. It turns out that ambiguous grammars with appropriate disambiguating rules can be used to create parsers that are faster and easier to write than parsers constructed from unambiguous grammars. The basic notion is to write grammar rules of the form expr : expr OP expr and expr : UNARY expr for all binary and unary operators desired. This creates a very ambiguous grammar with many parsing conflicts. You specify as disambiguating rules the precedence or binding strength of all the operators and the associativity of the binary operators. This information is sufficient to allow yacc to resolve the parsing conflicts in accordance with these rules and construct a parser that realizes the desired precedences and associativities. The precedences and associativities are attached to tokens in the declarations section. This is done by a series of lines beginning with the keywords or yacc %left, %right, %nonassoc, followed by a list of tokens. All of the tokens on the same line are assumed to have the same precedence level and associativity; the lines are listed in order of increasing precedence or binding strength. Thus %left '+' '-' %left '' '/' describes the precedence and associativity of the four arithmetic operators. and are left + - associative and have lower precedence than and which are also left associative. The keyword /, %right is used to describe right associative operators. The keyword %nonassoc is used to describe operators, like the operator .LT. in FORTRAN, that may not associate with themselves. That is, because A .LT. B .LT. C is invalid in FORTRAN, .LT. would be described with the keyword %nonassoc in yacc. As an example of the behavior of these declarations, the description %right '=' %left '+' '-' %left '' '/' %% expr : expr '=' expr
There is one common situation where the rules given above for resolving conflicts are not sufficient. This is in the parsing of arithmetic expressions. Most of the commonly used constructions for arithmetic expressions can be naturally described by the notion of precedence levels for operators, together with information about left or right associativity. It turns out that ambiguous grammars with appropriate disambiguating rules can be used to create parsers that are faster and easier to write than parsers constructed from unambiguous grammars. The basic notion is to write grammar rules of the form expr : expr OP expr and expr : UNARY expr for all binary and unary operators desired. This creates a very ambiguous grammar with many parsing conflicts. You specify as disambiguating rules the precedence or binding strength of all the operators and the associativity of the binary operators. This information is sufficient to allow yacc to resolve the parsing conflicts in accordance with these rules and construct a parser that realizes the desired precedences and associativities. The precedences and associativities are attached to tokens in the declarations section. This is done by a series of lines beginning with the yacc keywords %left, %right, or %nonassoc, followed by a list of tokens. All of the tokens on the same line are assumed to have the same precedence level and associativity; the lines are listed in order of increasing precedence or binding strength. Thus %left '+' '-' %left '' '/' describes the precedence and associativity of the four arithmetic operators. + and - are left associative and have lower precedence than and /, which are also left associative. The keyword %right is used to describe right associative operators. The keyword %nonassoc is used to describe operators, like the operator .LT. in FORTRAN, that may not associate with themselves. That is, because A .LT. B .LT. C is invalid in FORTRAN, .LT. would be described with the keyword %nonassoc in yacc. As an example of the behavior of these declarations, the description %right '=' %left '+' '-' %left '' '/' %% expr : expr '=' expr
compiler_design_manual.docx