Imaginary token
1 posts in topic
Flat View  Flat View

Posted By:   Jason_Yip
Posted On:   Monday, August 26, 2002 07:53 AM

I am very new to ANTLR.. to learn it and build my first parser, I started with the SQL grammar.

However I just don't understand what is going on with the imaginary token. I don't know what it does and why I want to use it. For example:

{ #select_list = #([SELECT_LIST, "select_list"], #select_list); }

What does that mean?

What's more, I don't understand why this semantic predicate will make sense:

( update_clause ) => update_clause

There is nothing to be predicted with the update_clause. Can anybody helps me? Thanks!

Re: Imaginary token

Posted By:   Adam_McClure  
Posted On:   Tuesday, September 3, 2002 10:44 AM

You have three questions here:

  1. What is an imaginary token?

  2. How are tokens used in constructing an AST?

  3. How are semantic predicates evaluated?

I'll take a stab at each one briefly in turn.

1) Imaginary tokens are used to annotate an Abstract Syntax Tree with nodes that can be further manipulated by a treewalker or simply used to better understand the output tree. Imaginary nodes are tokens that do not correspond to a matched token from the input stream. They are added by the AST construction code you define in your grammar file. Steal the Swing-based tree viewer code from the Java grammar to literally see how they change the way you see the output tree.

2) Every parser constructs a default AST with one node and lots (!) of children. If you want a more complex tree you need to get involved in constructing the tree yourself. The statement above:

{ #select_list = #(#[SELECT_LIST, "select_list"], #select_list}; }

can be translated to mean the following: 1) Set the tree returned by this rule (i.e. select_list) to be 2) a new tree with root node imaginary token SELECT_LIST defined in my tokens block for this parser 3) with child node set equal to the rest of the AST nodes auto-generated for this rule. For the definitive treatment, read the documentation on building AST trees.

3) Finally, the semantic predicate works fine because what you are telling ANTLR to do is only match an update_clause rule when it matches. That's right, the parser will only complete the rule when it looks ahead and determines a successful match on update_clause. This technique is commonly used when there are multiple alternatives within a rule that cannot be disambiguated without subsequent parsing. So you set the first alternative to try and match itself. If it fails, the next alternative in the rule will be tried. Only after all the alternatives fail will the parser throw an error. Usually the last alternative is a default match and will bomb out if the input stream doesn't match.

Cheers! :-)

About | Sitemap | Contact