Re: [Q] Encapsulated parsers

Bob Collins asked:
> Does anyone know of any research on what I call
> encapsulated parsers, which consists of
> 1. a single parse routine that accepts
> 2. a. a set of parse tables,
> b. a synthesize semantics routine, and
> c. semantic routines to disambiguate
> grammar conflicts at runtime
> as parameters,
> 3. so that the parser can be called multiply
> in code with different parameters to parse
> the same input in different ways.


To which our estemed moderator noted that C++-ized yaccs might do
that. I'd like to flush out the details of that (as I understand
them).


For example, the tool I am most familiar with, Yacc++(r) and the
Language Objects Library, has the parsing routine(s) in the library
code. The routine(s) match requirements 1, 2a, 2b, & 3. Placing the
code in the library and the tables and semantic routines in the
derived user class were part of the object-oriented approach the
product took. In fact, one of the tutorial examples, MULTIPLE to be
exact, shows how to write an application which does exactly what you
ask (except for the 2c requirement).


As to your 2c requirement, run-time diasambiguation of conflicts,
there are fewer projects that have attempted that. Kjell Post wrote a
couple years back about having built a system that did that.


Part of the reason run-time disambiguation is not commonly done, is
that in most LR tools the disambiguation gets folded into the tables.
You need at least one table entry with two or more distinct
alternative actions for each point you do run-time disambiguation.
Your parser generator must also generate the right follow-on states
for each distinct action. The different follow-on states may also
change the conflicts for other states (the ones they are lookahead
for).


Another alternative approach, semantic predicates ala PCCTS and ANTLR,
would have the same effect as run-time disambiguation. Semantic
predicates are on the short-list of projects for Yacc++ (It already
has syntactic predicates.), mostly waiting on the time to flesh out
the exact interface of specifying when a predicate is "true". The
Btyacc (backtracking yacc) tool has a feature that works kind of like
semantic predicates, when the generated parser is disambiguating a
conflict at runtime by using backtracking, the action code can tell
the parser when to abandon (accept, or both, I don't recall precisely)
certain branches as matching.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : cfc@world.std.com
Compiler Resources, Inc. CompuServe : 74252,1375
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------
Web Site in Progress: Web Site : http://world.std.com/~compres

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