[antlr-interest] What do . (period) and Tokens mean in tree grammars?

Harald M. Müller harald_m_mueller at gmx.de
Sat Dec 29 14:16:13 PST 2007


Sorry that I ask - but I did not find it on the Wiki and not in the ANTLR
book: What do . and Tokens mean in tree grammars?

AFAIK, . means "any complete subtree." - although this seems not to work in
some current builds, if I understood some email of yesterday correctly?

Question number two:
Does a single Token also match a complete tree with this token at the root,
or only a "childless tree" (i.e. the token as a tree node alone)?

Question number three:
What sort of lookahead is used over . ? For example, would the following
work - assume here that the subtrees can be arbitrarily large subconditions
(as is usual in expression trees):

condition : ^(AND . ^(NOT .))	-> ...rewrite1...
	| ^(AND . .)		-> ...rewrite2...
	;

The intention of this is to rewrite an AND tree which has as second child a
tree with a NOT root to rewrite1; whereas all other trees are supposed to be
rewritten as rewrite2.
If ANTLR tree parsing works the way I assume it - namely the whole tree is
flattened to a node sequence, on which "one-dimensional" parsing techniques
(even LL(*)) are applied, then the NOT will be "too far" away even for an
LL(*) analysis, because there will be recursively nested expressions on the
way between the AND and the NOT. However, if ANTLR goes for real
"two-dimensional" parsing, or does some lookahead over arbitrarily large
subtrees (to the readily available "later" children!) - which I would call
"1.5-dimensional lookahead computation/parsing", then the above two patterns
could be disambiguated.

Thanks
Harald
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20071229/470767a3/attachment.html 


More information about the antlr-interest mailing list