Faster parser driver for yacc?
Kathy Harris
Has anyone experimented with modifying or rewriting the "yaccpar"
file (the main driver of yacc generated parsers) in order to
create a faster parser in the resulting y.tab.c program?
Does anyone have any guidelines on how the structure of the input grammar
will affect the efficiency of the resulting parser (eg, number of
levels of non-terminal, etc.)?
Kathy Harris
Hewlett Packard Systems Software Operation
Ft. Collins, Colorado
Dale Worley
> will affect the efficiency of the resulting parser (eg, number of
> levels of non-terminal, etc.)?
Avoid productions like
a : b ;
if possible. It helps to use precedence rules with an ambiguous
grammar. Thus you can write things like
expr : expr '+' expr
| expr '*' expr
| '-' expr
| '(' expr ')'
;
and use precedence rules to sort things out. This avoids alot of
nonterminals whose sole purpose is keeping the precedences straight.
Dale
D...@psuvma.bitnet
it was one of the faster parts, so that any minor changes wouldn't effect
speed that much.
dave
D...@psuvma.bitnet
Use left recursion over right recursion to speed it up.
dave
Kathy Harris
> dave
----------
It depends on what you want to use yacc for. In compilers, it's probably
true that the computation involved in code generation makes the parse
time less critical.
However, yacc can be useful as a parser for other types of input languages
where the computation task is not so great and so yacc becomes a large
part of the task. A more efficient yacc parser would make it feasible
to use yacc in more contexts than just compilers.
The application I've been looking at is an assembler that uses yacc to
parse the assembly source. Currently, yyparse is 25%+ of the user time.
I'm looking for ways to speed of the parse phase, and yet not sacrifice
the flexibility (eg, in adding support for new instructions and addressing
types) that is provided by yacc.
kathy harris
{hplabs | ihnp4}!hpfcla!kah
d...@psuvm.bitnet.uucp
Good Point,
I was refering to Yacc in context to compiler's only.
dave