Re: predicate parsing

As a followup to several messages in this thread, I'd like to make a bit
of advertising for the SYNTAX(tm) scanner and parser generator developed
by my colleague Pierre Boullier. It generates bottom-up shift-reduce
parsers. Among the features of SYNTAX relevant to this thread are:


1. A predicate can be applied to any terminal at any place in any rule
RHS. If the predicate fails, the terminal is not recognized. This allows
easy imple- mentation of things like (from Dave Schaumann in message
93-04-086):


var_name : is_var_name ( identifier )
;
type_name : is_type_name( identifier )
;


A predicate can also be applied to a non-terminal. In the (C) code
implementing this predicate, the user has access to all the
parser-maintained information and may even scan ahead in the input string.


Combined with the possibility to execute actions a la Yacc, it allows some
from of semantic predicates and semantic-influenced parsing (although I
don't claim that it's better than PCCTS or LADE, which I know nothing
about).


2. SYNTAX generates parsers for the RLR (Regular LR) class of grammars.
Briefly said, a grammar is RLR if, for each conflicting state in the LR(0)
automaton, you can find a regular language against which you can parse the
sequel of the input string and eventually reach a state in which you can
decide how to resolve the conflict (unbounded lookahead). This was
mentioned as a possible way to resolve ambiguities by Kiong Beng Kee in
message 93-04-104; well, here it is. It is important to
note that RLR languages can still be parsed in linear time w.r.t. the
length of the input string (no backtracking), and SYNTAX actually
implements this. The RLR class of languages includes all deterministic
languages and some non-deterministic ones.


3. SYNTAX-built parsers are very good at error repair; see the following
paper:


@article{bib:error,
        author= {Pierre Boullier and Martin Jourdan},
        title= {A New Error Repair and Recovery Scheme for Lexical
and Syntactic Analysis},
        journal= {Science of Computer Programming},
        volume= 9,
        pages= {271-286},
        year= 1987
}


(issue raised by Simon Huntington, Jon Mauney and Trevor Jenkins).


4. SYNTAX-built parsers are compact (table compression typically > 95%)
and fast (I mean, faster than those built by Yacc!).


I'm sorry that I can't give pointers to the litterature on SYNTAX, because
there is none, apart from the avove paper that *I* wrote. Pierre is good
at developing theories and systems, but he does not seem to understand
that in between it's useful to write papers :-).


SYNTAX is a production-quality system which has been used in various
commercial applications (e.g. the Alsys Ada compiler). However it's free
for public research and teaching institutions (requires a bit of
paperwork, though).


For more details, contact Pierre Boullier (Pierre.Boullier@inria.fr).


Sorry if this sounds too commercial.


Martin Jourdan <Martin.Jourdan@inria.fr>, INRIA, Rocquencourt, France.
        Phone +33-1-39-63-54-35, fax +33-1-39-63-53-30
--

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