Week 5 - Parser 2¶
Ambiguity¶
Recap: Ambiguity
A grammar is ambiguous if at least one sentence in the language has more than one parse tree.
Consider the Calc1 grammar:
This grammar accepts 9-5+2, but the expression has two possible parse trees:
Using parentheses to show how the operands are grouped, the two interpretations are (9-5)+2 and 9-(5+2). This is an example of ambiguity.
The second interpretation does not match the usual arithmetic convention. Similarly, we want our parser to give an input a consistent interpretation rather than leave it with multiple possible parse trees.
Operator Associativity¶
When an operand appears between two operators, we need a rule for deciding which operator it groups with first.
The + and - operators are left-associative: when they occur at the same precedence level, we group operations from left to right. For example, in 9-5+2, the operand 5 groups with the - on its left, giving (9-5)+2.
The assignment operator = in C is right-associative. Thus, a=b=c is interpreted as a=(b=c): the middle operand b groups with the = on its right.
Operator Precedence¶
With this grammar, 9+5*2 can have two parse trees, corresponding to (9+5)*2 and 9+(5*2). Declaring all four operators left-associative does not fully resolve the ambiguity: associativity determines grouping among operators at the same precedence level. When an expression contains operators at different levels, we also need to define their precedence.
Saying that * has higher precedence than + means that operands group with multiplication before addition. In both 9+5*2 and 9*5+2, the operand 5 participates in multiplication first. These expressions therefore mean 9+(5*2) and (9*5)+2, respectively.
Resolving Grammar Ambiguity in ANTLR¶
Precedence¶
To give * higher precedence than + in Calc2, place the expr '*' expr alternative before expr '+' expr:
For these left-recursive operator alternatives, ANTLR assigns higher precedence to alternatives that appear earlier. Multiplication therefore binds more tightly than addition.
However, this version also gives * higher precedence than /. ANTLR would parse 1 * 2 / 3 as (1*2)/3, but 1 / 2 * 3 as 1/(2*3).
To give operators the same precedence, group them in a subrule within a single alternative:
Associativity¶
ANTLR treats these operators as left-associative by default. To make an alternative right-associative, add <assoc=right> at its beginning:
grammar Calc2;
expr : expr ('*'|'/') expr
| expr ('+'|'-') expr
| <assoc=right> expr '=' expr
| factor
;
Error Handling¶
A useful compiler should provide informative diagnostics for invalid programs, including the location and nature of each error. Here, we focus on syntax errors, such as a missing semicolon or parenthesis. These differ from semantic problems, such as referencing an undefined variable or accessing an array outside its bounds.
One of ANTLR's strengths is its built-in support for error reporting and recovery. Recovery allows the parser to resume processing the remaining input after an error, rather than stop at the first syntax error.
The following sections briefly introduce ANTLR's default error reporting and recovery, which work without additional implementation on your part. We will then use semantic actions to handle specific error patterns.
ANTLR's Default Error Handling¶
Single-Token Errors¶
Matching tokens is a routine part of parsing. Consider this rule:
The parser matches if, then (, then recursively matches exp, and so on. The following statement is valid: each token and each subrule matches the expected structure.
Now consider a statement with a missing opening parenthesis:
After if, the parser expects ( but encounters x. ANTLR can recover by inserting a missing token if the current input is valid immediately after that token. Here, x can begin exp, so treating ( as missing allows parsing to continue. ANTLR reports the missing token and proceeds with the rest of the statement.
A related recovery technique is deleting an unwanted token:
Here, skipping xyz exposes the expected (. ANTLR reports the unwanted token and continues parsing.
Errors That Require Broader Recovery¶
Some errors cannot be repaired by inserting or deleting a single token. In these cases, the parser discards input tokens until it reaches a token that allows parsing to resume. Such tokens belong to a recovery set, derived from the tokens that can follow the surrounding rules.
Consider the same rule:
and this input:
The parser matches if and ( successfully, but the contents do not form a valid exp. A single-token insertion or deletion cannot repair the expression. The parser can instead consume tokens until it reaches ), which follows exp in this rule. It then resumes parsing the rest of the statement as though it had finished processing the expression.
ANTLR tracks the possible following tokens as it enters rules and uses that information to recover from errors.
Customizing Error Handling¶
Custom Error Messages¶
To customize the format and content of diagnostics, extend BaseErrorListener and override syntaxError. Its parameters provide the information available for constructing your message:
import org.antlr.v4.runtime.BaseErrorListener;
import org.antlr.v4.runtime.RecognitionException;
import org.antlr.v4.runtime.Recognizer;
// recognizer: the parser or lexer that reported the error
// offendingSymbol: the input symbol that caused the error, usually a Token
// line: the line number where the error occurred
// charPositionInLine: the character position within that line
// msg: ANTLR's description of the error
// e: an exception containing further details about the recognition error
public class MyErrorListener extends BaseErrorListener {
@Override
public void syntaxError(Recognizer<?, ?> recognizer, Object offendingSymbol, int line, int charPositionInLine, String msg, RecognitionException e) {
System.err.println(msg);
}
}
Remove the default error listeners before adding your own to avoid duplicate diagnostics:
CalculatorParser calculatorParser = new CalculatorParser(tokens);
calculatorParser.removeErrorListeners();
calculatorParser.addErrorListener(new MyErrorListener());
Semantic Actions¶
A semantic action is a snippet of code embedded in an ANTLR grammar and written in the target language—in our case, Java.
Actions execute when the parser reaches their position in a rule. They let you define custom behavior during parsing: whenever the parser recognizes a particular structure, it can run the Java code you provide.
To add an action, place the code inside braces at the desired position in a rule. ANTLR includes it in the generated parser. An action placed at the end of an alternative appears after the code that matches that alternative.
For example:
When this rule matches an input such as:
it prints hello.
Semantic actions can also provide diagnostics for specific error patterns. Add an alternative that explicitly recognizes a common mistake, then report the error when that alternative matches:
stmt: 'if' '(' exp ')' stmt
| 'if' exp ')' stmt {this.notifyErrorListeners("Missing opening parenthesis");}
;
The second alternative recognizes an if statement with a missing (. The method this.notifyErrorListeners is available in the generated parser. Because the action is embedded directly in that parser, it can call this method and supply the diagnostic message.
To retrieve the starting line of the current rule, use:
Here, $ctx refers to the context object for the current rule. It contains information such as the starting and ending tokens, from which you can obtain source locations and construct your own diagnostics.
Separating Semantic Actions from the Grammar with Listeners and Visitors¶
Semantic actions let a parser run code as soon as it recognizes a particular syntactic structure. Beyond custom error handling, they can support semantic processing.
For example, when the parser recognizes a variable declaration, an action can record the variable in a symbol table. When it later encounters an assignment, another action can check whether the variable has been declared. In principle, this kind of processing can be implemented with actions during parsing.
However, a real language may require a large amount of processing logic. Embedding all of it in the grammar mixes syntax definitions with implementation code, making the file harder to read and maintain. It also makes the grammar harder to reuse for other tasks, because the embedded actions are tied to one particular use.
ANTLR offers two convenient ways to keep this logic separate: listeners and visitors. For a grammar named Spl, the generated Java files include SplVisitor, SplListener, SplBaseVisitor, and SplBaseListener. The first two are interfaces; the latter two are classes that implement those interfaces.
Let us start with SplListener. It defines methods named enterXXX and exitXXX, where XXX corresponds to a rule in the .g4 file. Each rule has an entry callback and an exit callback. During a parse-tree walk, enter runs when the walker reaches the rule's node, and exit runs after it has visited that node's children. Thus, by the time exit runs, the callbacks for all child rules have already run.
For the following grammar:
the diagram shows the order of these callbacks:
Both callbacks receive the same ctx object, which contains the rule's context, including the matched tokens and its child rules.
You might expect more information to be available on exit than on entry, since the child rules must have been processed by then. The key distinction is when the tree is built. Embedded grammar actions run while the parser is building the parse tree. In the listener and visitor workflow described here, processing happens after the parse tree has been built.
By the time we walk the tree, the source has already been parsed, and every rule's children are available—even in an enter callback. In contrast, an action embedded at the beginning of a grammar rule runs before the parser has matched that rule's children, so their contents are not yet known.
Now consider SplVisitor. It provides one visitXXX method per rule, rather than separate entry and exit callbacks. Why is there no need to distinguish between entering and leaving a rule?
The answer lies in who controls the traversal. With a listener and the standard tree walker, callbacks run in a fixed depth-first order: an entry callback before the children and an exit callback afterward. Put an action in enter if it should run before the child actions, or in exit if it should run after them.
Suppose, however, that you want to run a custom operation after processing the first child but before processing the second. The parent rule's entry and exit callbacks do not provide a place to intervene between these child visits or control their order. A visitor gives you that control: within a parent's visit method, you decide which children to visit and when.
- Call
visiton the first child. - Run your custom operation.
- Call
visiton the second child.
A single visitor method therefore gives you control over operations before, between, and after child visits. Separate enter and exit methods are unnecessary because all of those decisions can be made within the same method.
Another difference is that a visitor has a generic type parameter: its visit methods can return values of that type. Listener callbacks return no value. This distinction can help you choose between the two approaches.
A listener is often convenient for static analysis, such as adding declarations to a symbol table and looking up variables in assignments, when you do not need fine control over traversal. A visitor is useful for tasks such as code translation, where each rule may return a result that its parent combines into a larger result.
ANTLR provides default implementations in SplBaseListener and SplBaseVisitor. The base listener's callbacks do nothing, while the base visitor visits child nodes. To add custom behavior, extend the appropriate base class and override only the methods you need.
For operations that apply to every rule, listeners also provide the convenient callbacks enterEveryRule and exitEveryRule.
Building a Visitor or Listener Quickly
Extend the generated XXXBaseVisitor or XXXBaseListener class. These classes already implement the corresponding XXXVisitor and XXXListener interfaces with useful default behavior:
- In
XXXBaseVisitor, eachvisitmethod recursively visits the rule's children by default. - In
XXXBaseListener, eachenterXXXandexitXXXmethod does nothing by default.
Use Java's override mechanism to replace only the methods relevant to your task.
To visit a child rule from a visitor method, use a call such as:
Replace childRule with the child rule's name. The general-purpose visit method dispatches to the appropriate visitor method based on the actual type of the context object passed to it.
ANTLR generates accessors in a parent rule's context class for the child rules and tokens it contains. Rule accessors return rule contexts; token accessors return terminal nodes. When a rule contains multiple occurrences of the same child rule, as in a left-recursive expression or a repeated structure, ANTLR provides both a list accessor and an indexed accessor:
ctx.expr()returns a list of allexprchild contexts.ctx.expr(i)returns theithexprchild context, using a zero-based index and preserving their order in the rule.
For example:
The generated accessors let you distinguish the two operands:
ctx.expr(0)refers to theexpron the left of+.ctx.expr(1)refers to theexpron the right of+.
Use an explicit index when you need a particular occurrence of a child rule.
Labeling Alternatives for Finer Control¶
So far, we have described listener and visitor methods generated for individual rules. Sometimes that level of detail is insufficient because a rule has several alternatives that need different processing.
For example:
exp
: CHAR
| FLOAT
| INT
| ID
| ID DOT ID
| exp LB exp RB
| ID LP RP
| ID LP args RP
| LP exp RP
| MINUS exp
| exp (MUL | DIV) exp
| exp (PLUS | MINUS) exp
| exp (OR | EQ | NE | LT | LE | GT | GE) exp
| exp AND exp
| NOT exp
| exp ASSIGN exp;
To attach different behavior to different alternatives, add an alternative label at the end of each one:
ANTLR then generates separate listener and visitor methods for the labeled alternatives, giving you finer control:
exp
: CHAR # CharLiteral
| FLOAT # FloatLiteral
| INT # IntLiteral
| ID # IdExp
| ID DOT ID # StructMemberAccessExp
| exp LB exp RB # ArrayAccessExp
| ID LP RP # CallExpNoArgs
| ID LP args RP # CallExpWithArgs
| LP exp RP # ParenExp
| MINUS exp # UnaryMinusExp
| exp (MUL | DIV) exp # MulDivExp
| exp (PLUS | MINUS) exp # PlusMinusExp
| exp (OR | EQ | NE | LT | LE | GT | GE) exp # CompareExp
| exp AND exp # AndExp
| NOT exp # NotExp
| exp ASSIGN exp # AssignExp
;
Exercise¶
Extend Calc1 to support multiplication, division, and parentheses in addition to addition and subtraction. Then write a small program that evaluates the sample expressions and produces the output below.
- Complete CalcLab5Visitor.java.
- Consider how you would implement the same functionality with a listener.
Calc1.g4:
grammar Calc1;
root: expr * EOF;
expr :
LPAREN expr RPAREN # aren
| expr (MUL | DIV) expr # mulDiv
| expr (ADD | SUB) expr # addSub
| factor # goFactor
;
factor : INT;
INT : '0' | [1-9][0-9]*;
ADD : '+' ;
SUB : '-' ;
MUL : '*';
DIV : '/';
LPAREN: '(';
RPAREN: ')';
WS : [ \t\r\n]+ -> skip ;
Create CalcLab5Visitor.java in the same directory:
Main.java:
import generated.Calc1.Calc1Lexer;
import generated.Calc1.Calc1Parser;
import org.antlr.v4.runtime.*;
public class Main {
public static void main(String[] args) {
// Create a character stream from a string. To read a file, use CharStreams.fromFileName("path/to/file").
// Supply the input to ANTLR.
CharStream input = CharStreams.fromString("2 + 3 * (5 - 4) / 2\n 3-4/2\n20 /4 -3\n((1+2)*3-5)/2 ");
// Create the lexer.
Calc1Lexer lexer = new Calc1Lexer(input);
// Create the token stream.
CommonTokenStream tokens = new CommonTokenStream(lexer);
// Create the parser.
Calc1Parser parser = new Calc1Parser(tokens);
// Parse from the root rule to obtain the visitor's starting context.
Calc1Parser.RootContext context = parser.root();
CalcLab5Visitor visitor = new CalcLab5Visitor();
for (Calc1Parser.ExprContext expr : context.expr()) {
System.out.printf("%s = %s\n", expr.getText(), visitor.visit(expr));
}
}
}
Expected output: