Converting Bison precedence and associativity rules to Antlr

As noted in the Bison guide:

• The associativity of an operator op determines how repeated uses of the operator nest: whether ‘x op y op z’ is parsed by grouping x with y first or by grouping y with z first. %left specifies left-associativity (grouping x with y first) and %right specifies right-associativity (grouping y with z first). %nonassoc specifies no associativity, which means that ‘x op y op z’ is considered a syntax error.%precedence gives only precedence to the symbols, and defines no associativity at all. Use this to define precedence only, and leave any potential conflict due to associativity enabled.
• The precedence of an operator determines how it nests with other operators. All the tokens declared in a single precedence declaration have equal precedence and nest together according to their associativity. When two tokens declared in different precedence declarations associate, the one declared later has the higher precedence and is grouped first.

Associativity

By default, operators in Antlr are left-associative. So, %left associative operators do not require any additional declarations in Antlr.

%left op

=>

e : e op e

An operator declared as %right associative will need to be tagged in Antlr with <assoc=right>.

%right op

=>

e : <assoc=right> e op e

Antlr does not have a %nonassoc declaration. To disallow a non-associative operator in Antlr, a semantic predicate must be used.

%nonassoc op

=>

e : e op e { Input.LA(1) != op }?

Precedence

In Antlr, to make op1 higher precedence than op2, one will need to define the alternative containing op1 before the alternative for op2. In other words, the order of the alternatives of the operators in Antlr is the same as the order of appearance in the Bison grammar.

%left op1
%left op2

=>

e : e op1 e | e op2 e

What are precedence and associativity bound to?

As noted here: “A precedence and associativity is associated with each grammar rule. It is the precedence and associativity of the final token or literal in the body of the rule. If the %prec construction is used, it overrides this default value. Some grammar rules may have no precedence and associativity associated with them.”

Even though precedence and associativity are specified with an operator, the precedence and associativity are associated with a rule as well. Note, this makes sense from an implementation reference: when you see a shift/shift or shift/reduce conflict, you are deciding what to place in the parsing table for the action based on the rule and the lookahead that you see. Crucially, the %prec, %right, %left, %nonassoc clauses can appear within a rule, which overrides any clauses specified elsewhere.

–Ken