Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to output the AST built using ANTLR?

I'm making a static analyzer for C. I have done the lexer and parser using ANTLR in which generates Java code.

Does ANTLR build the AST for us automatically by options {output=AST;}? Or do I have to make the tree myself? If it does, then how to spit out the nodes on that AST?

I am currently thinking that the nodes on that AST will be used for making SSA, followed by data flow analysis in order to make the static analyzer. Am I on the right path?

like image 619
Raphael Avatar asked Feb 08 '11 09:02

Raphael


People also ask

Can ANTLR generate AST?

ANTLR helps you build intermediate form trees, or abstract syntax trees (ASTs), by providing grammar annotations that indicate what tokens are to be treated as subtree roots, which are to be leaves, and which are to be ignored with respect to tree construction.

What is the AST output?

An AST is usually the result of the syntax analysis phase of a compiler. It often serves as an intermediate representation of the program through several stages that the compiler requires, and has a strong impact on the final output of the compiler.

What does ANTLR generate?

ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files.


Video Answer


1 Answers

Raphael wrote:

Does antlr build the AST for us automatically by option{output=AST;}? Or do I have to make the tree myself? If it does, then how to spit out the nodes on that AST?

No, the parser does not know what you want as root and as leaves for each parser rule, so you'll have to do a bit more than just put options { output=AST; } in your grammar.

For example, when parsing the source "true && (false || true && (true || false))" using the parser generated from the grammar:

grammar ASTDemo;  options {    output=AST;  }  parse   :  orExp   ;  orExp   :  andExp ('||' andExp)*   ;  andExp   :  atom ('&&' atom)*   ;  atom   :  'true'   |  'false'   |  '(' orExp ')'   ;  // ignore white space characters Space   :  (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;}   ; 

the following parse tree is generated:

enter image description here

(i.e. just a flat, 1 dimensional list of tokens)

You'll want to tell ANTLR which tokens in your grammar become root, leaves, or simply left out of the tree.

Creating AST's can be done in two ways:

  1. use rewrite rules which look like this: foo : A B C D -> ^(D A B);, where foo is a parser rule that matches the tokens A B C D. So everything after the -> is the actual rewrite rule. As you can see, the token C is not used in the rewrite rule, which means it is omitted from the AST. The token placed directly after the ^( will become the root of the tree;
  2. use the tree-operators ^ and ! after a token inside your parser rules where ^ will make a token the root, and ! will delete a token from the tree. The equivalent for foo : A B C D -> ^(D A B); would be foo : A B C! D^;

Both foo : A B C D -> ^(D A B); and foo : A B C! D^; will produce the following AST:

enter image description here

Now, you could rewrite the grammar as follows:

grammar ASTDemo;  options {    output=AST;  }  parse   :  orExp   ;  orExp   :  andExp ('||'^ andExp)* // Make `||` root   ;  andExp   :  atom ('&&'^ atom)* // Make `&&` root   ;  atom   :  'true'   |  'false'   |  '(' orExp ')' -> orExp // Just a single token, no need to do `^(...)`,                              // we're removing the parenthesis. Note that                             // `'('! orExp ')'!` will do exactly the same.   ;  // ignore white space characters Space   :  (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;}   ; 

which will create the following AST from the source "true && (false || true && (true || false))":

enter image description here

Related ANTLR wiki links:

  • Tree construction
  • Tree parsing
  • Tree construction facilities

Raphael wrote:

I am currently thinking that the nodes on that AST will be used for making SSA, followed by data flow analysis in order to make the static analyzer. Am I on the right path?

Never did anything like that, but IMO the first thing you'd want is an AST from the source, so yeah, I guess your on the right path! :)

EDIT

Here's how you can use the generated lexer and parser:

import org.antlr.runtime.*; import org.antlr.runtime.tree.*; import org.antlr.stringtemplate.*;  public class Main {   public static void main(String[] args) throws Exception {     String src = "true && (false || true && (true || false))";     ASTDemoLexer lexer = new ASTDemoLexer(new ANTLRStringStream(src));     ASTDemoParser parser = new ASTDemoParser(new CommonTokenStream(lexer));     CommonTree tree = (CommonTree)parser.parse().getTree();     DOTTreeGenerator gen = new DOTTreeGenerator();     StringTemplate st = gen.toDOT(tree);     System.out.println(st);   } } 
like image 126
Bart Kiers Avatar answered Oct 04 '22 23:10

Bart Kiers