Re: Hybrid LR and LL parser tools?

Dennis Brueni <brueni@csgrad.cs.vt.edu> writes:
>So naturally the question follows:
>
> "What tools exist for generating hybrid parsers automatically?"
>
>From the limited number of things I know, correct me if I am wrong, yacc
>produces LR(1) parsers, pccts produces LR(k), ell produces LL(1), lalr
>produces LR(1), etc. I know of no parser generater which will produce a
>hybrid parser as I describe above.


There is another approach to "hybrid" LR-LL parsers which you might want
to consider. Suppose that we view a parser as mostly LR (or LALR) but make
specific exceptions where we need LL characteristics. Then the task
becomes simply one of identifying where we need information about a
current production before its reduction. In particular, the "feature" of
LL which is so important is that it identifies the production at the point
of entry. (This is also the reason that it is so difficult to get grammars
to be LL(1)).


Even Yacc has a primitive form of this capability in the form of embedded
compound statements. To convert a Yacc grammar from LR (LALR) to quasi-LL,
for each production:
    X -> alpha ;
substitute:
    X -> {} alpha ;
where the compound statement pushes local variables onto a stack for use
by the reduce actions of the nonterminals in alpha. You can be even more
sophisticated by adding actions before each nonterminal which copy
specific values into the local variables much like the actual parameters
in LL-style function calls as well as adding arbitrary side effects
between elements. In LADE, these features are captured in inherited
attributes.


Such an approach will create conflicts only where the grammar is not
LL(1). Moreover, in practice, we can improve this situation by more
judicious placement of the initializing compound statement. For example,
it may be that moving the compound statement one or more elements to the
right will remove the conflict at the expense of not having access to the
context during those initial nonterminal reductions. Also, the use of
regular expressions to combine different productions into one can remove
conflicts (as well as redundencies) between actions. For example:
    X -> {} alpha {} beta {} delta |
              {} alpha {} delta ;
is guaranteed to contain a conflict between the productions but:
    X -> {} alpha [{} beta] {} delta ;
does not suffer this problem (and avoids repeating the code for alpha
and delta).


What is missing at this point is the difference between LL(1) and LL(k).
Since an LL(k) parser scans ahead, it may know the context before a
similar LL(1) parser. An LR(k)-based parser with the above capability
would be the equivalent but, again, we can do better.


This time, view the parser as mostly LR (LALR) (1) but with specific
exceptions for situations of ambiguity where it is LR (LALR) (k) or,
better yet, LR (LALR) (*). LADE, for example, allows grammars to contain
tests on nonterminal reductions. There are basically two types of tests
that are generally performed: semantic tests, tests of information by
semantic analysis; and forward parse tests, parsing ahead looking for a
particular pattern and then returning to the original point with the
result of the test. Even for a language as screwed-up as C++, a few
judiciously placed tests can remove all conflicts.


In general, before you create a "hybrid" parser generator, be sure of what
it is you want from each of the constituent models of parsing. In the case
of LADE, I believe that we have captured the best of all.


--

Return to the comp.compilers page.
Search the comp.compilers archives again.