On Thu, May 13, 2004 at 01:01:12PM -0500, Abhijit A. Mahabal wrote:
: I have been thinking the following about what larry said earlier. Is this
: what you meant, larry?
:
: $grammar = q{
: class_defn: "class" block .. etc (normal top-down stuff)
: ...
: term: { call Parse::Yapp or something }
: }
Er, I've never used Parse::Yapp, so I couldn't say. I'd tend to roll
my own operator precedence parser anyway.
: What I mean by that weird pseudocode is that everything happens in a
: parse-recdescent parser, except that the production of some non-terminals
: calls into a bottom-up parser. That part seems trivially doable. What I
: need to figure out is how the bottom-up parser can relinquish control to
: the top-down parser if it hits a block or such.
The bottom up parser doesn't know that it is relinquishing control. It
has to have some kind of tokener/lexer, and that lexer recognizes that it
has a complex term that needs a subparser, calls the parser, and then
returns the subparse as a single token to the bottom-up engine.
: A preliminary thought: A traditional bottom-up parser can take the four
: actions shift, reduce, accept, and error. We will need a fifth: call the
: top down parser. I have not thought through how that happens or if it can
: be done at all. It is the only way that I currently see.
No, you still have the four basic actions. Subparsing is all hidden in
the lexer. As far as the parse is concerned, it's processing a single
token that happens to be something complicated. The only complicated
thing is making sure that all the constructs sub-parsed by the lexer
know when they should terminate. That's trivially easy for bracketed
constructs like blocks. Things get a little tricker for things like
unparenthesized list operators that have to be treated like a left
parenthesis that has no corresponding right parenthesis. Things like
semicolon will be slightly context sensitive: outside brackets, they
terminate the current statement, while inside brackets, they separate
slice terms.
And, of course, the lexer has to be sensitive to whether we're currently
expecting a term or an operator...
: I think I'll try to coax Parse::Recdescent and Parse::Yapp to work
: together. I have never used the latter, but the documentation seems to
: suggest that it can do what Bison can. Or maybe I should write two small
: parsers by hand (one recdescent and the other an operator precedence
: shift/reduce) and make them be nice to each other.
I'd take the latter approach myself, since in any event it will
probably need tweaks that are foreign to whatever tool you choose.
In particular, the fact that Perl 6 uses string comparison rather than
numeric comparison to do precedence levels is going to give almost
any standard tool a hissyfit. (We do that so that the user never has
to specify a precedence level--all levels are specified relative to
an existing operator's precedence level. And with strings, we can
fit as many new precedence levels into the interstices as the user
likes without ever running out of numeric precision.)
Larry
