From: John Max Skaller (skaller_at_[hidden])
Date: 2001-05-28 16:57:27
joel de guzman wrote:
> Yet, trivial applications does not necessitate the need for ASTs. That's
> the reason for the existence of simplified semantic Action(s) in Spirit.
No. You need 'executable' statements to actually build ASTs.
Otherwise, the parser has to build a parse tree, which is then
processed to produce an AST. The latter process is fragile,
since it must map parse tree nodes, which must be named after
the production they represent. So there is a strong reason
to put the rules that map the concrete syntax to abstract
syntax _inside_ the grammar, and build the AST directly
when parsing. Which _requires_ syntax directed translation
rules, that is, 'semantic actions'.
This need is much less for a meta-grammar like EBNF,
where the productions can more directly represent abstract
syntax. The metagrammar isn't cluttered with dummy
productions for iteration, options, etc. So, if you have
a high enough level 'grammar', decoupling the semantic
actions becomes more viable.
In the Felix parser, a lot of the semantic
actions do nothing but build lists for T* forms, etc.
The Vyper parser, OTOH, was a nightmare!
Vyper is a Python interpreter [it executes AST's directly]
Trying to model the simple Python metagrammar as
an LL(1) grammar proved impossible. The actual parser reads a
doctored token stream which is built by something
like 10 pre-processing passes. Trickery is used
for some nasty cases (especially trailing commas).
The problem here is NOT performance: the thing
is lightning fast, despite all the passes over the
token stream. The problem is that the whole apparatus
is fragile: it took longer to get right than the
-- John (Max) Skaller, mailto:skaller_at_[hidden] 10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850 checkout Vyper http://Vyper.sourceforge.net download Interscript http://Interscript.sourceforge.net
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk