ANTLR v4 (ANother Tool for Language Recognition)

ANTLR supports dynamic scoping, allowing a rule to access attributes from its invoking rules (rules higher up in the call chain). This is useful for passing context information (like symbol tables) down through the parse tree.

Syntax: Use $ruleName::attributeName to access an attribute of a specific invoking rule.

Important Notes:

• The rule r must be in the current call chain; otherwise, a runtime exception occurs.
• This is different from @members fields. A @members field is local to each invocation (lexical scoping), whereas dynamic scoping allows access to the state of the parent rule's context.
• To walk up the tree manually, you can use $ctx.getParent().

grammar DynScope;
 
prog: block ;
 
block
	/* List of symbols defined within this block */
	locals [ List<String> symbols = new ArrayList<String>() ]
	: '{' decl* stat+ '}'
	{System.out.println("symbols="+$symbols);} 
	;
 
decl: 'int' ID {$block::symbols.add($ID.text);} ';' ;
 
stat: ID '=' INT ';' 
	{ if ( !$block::symbols.contains($ID.text) ) { System.err.println("undefined variable: "+$ID.text); } }
	| block
	; 
 
ID : [a-z]+ ;
INT : [0-9]+ ;
WS : [ \t\r\n]+ -> skip ;

In lexer rules, semantic predicates are used to prune the set of viable rules when the lexer faces ambiguity. Unlike parser predicates (which should be on the left edge of alternatives), lexer predicates are most effective when placed on the right edge of the rule, though they can technically appear anywhere.

When a predicate evaluates to false, the lexer deactivates that rule for the current input, allowing other rules to be selected.

Important Constraints:

• No Side Effects: Lexer predicates cannot depend on side effects from lexer actions within the same rule. This is because actions are only executed after the lexer has positively identified the rule to match, whereas predicates are part of the selection process itself.
• Action Ordering: Lexer actions must appear after predicates in a rule if the action is intended to be part of the rule's successful match.
• Execution Timing: Actions are not executed inline during matching; they are collected and executed en masse after the rule is recognized. Therefore, a predicate cannot rely on a variable incremented by an action in the same rule.

// Example: Using a predicate on the right edge to distinguish a keyword
ENUM: [a-z]+ {getText().equals("enum")}? 
      {System.out.println("enum!");} 
    ;

ID: [a-z]+ {System.out.println("ID " + getText());} 
    ;

An ANTLR grammar file must be named X.g4 to define grammar X. A grammar consists of a header, followed by optional sections like options, import, tokens, channels, and named actions, and finally the rules.

Naming Conventions:

• Parser rules: Must start with a lowercase letter.
• Lexer rules: Must start with an uppercase letter.

Grammar Types:

• Combined Grammar: Defined with grammar Name;. Contains both lexical and parser rules.
• Parser Grammar: Defined with parser grammar Name;. Contains only parser rules.
• Lexer Grammar: Defined with lexer grammar Name;. Contains only lexer rules. Only lexer grammars can contain mode specifications or custom channels specifications.

/** Optional javadoc style comment */
grammar Name; ①
options {...}
import ... ;
 
tokens {...}
channels {...} // lexer only
@actionName {...}
 
rule1 // parser and lexer rules, possibly intermingled
...
ruleN

ANTLR provides two ways to traverse the parse tree for analysis:

Visitors

• Best for: Computing a single synthesized attribute or when you need explicit control over the order of traversal.
• Traversal Pattern: Generally implements a post-order tree walk. You must manually call self.visit(child) within your visit methods to continue the walk.
• Generation: Add the -visitor flag to the antlr4 command.
• Usage: Inherit from the generated Visitor class and call .visit(tree) on the root node.

Listeners

• Best for: Computing both synthesized and inherited attributes.
• Traversal Pattern: Performs an LR tree traversal. The walker calls an enter method when it first encounters a node, and an exit method after all children of that node have been visited.
• Generation: Add the -listener flag to the antlr4 command.
• Usage: Inherit from the generated Listener class and pass your instance to a ParseTreeWalker.walk(listener, tree) call.