[net.lang] Faster parser driver for yacc?

kah@hpfclq.HP.COM (Kathy Harris) (10/04/86)

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

drw@cullvax.UUCP (Dale Worley) (10/07/86)

> 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.)?

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

DMB@PSUVMA.BITNET (10/08/86)

Is the parser Yacc generates really the bottleneck? My understanding was that
it was one of the faster parts, so that any minor changes wouldn't effect
speed that much.


                dave

DMB@PSUVMA.BITNET (10/09/86)

    Use left recursion over right recursion to speed it up.



                                                      dave

kah@hpfclq.HP.COM (Kathy Harris) (10/17/86)

/ hpfclq:net.lang / DMB@PSUVMA.BITNET /  2:00 pm  Oct  8, 1986 /
>Is the parser Yacc generates really the bottleneck? My understanding was that
>it was one of the faster parts, so that any minor changes wouldn't effect
>speed that much.

>                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

dmb@psuvm.bitnet.UUCP (10/20/86)

   Good Point,
         I was refering to Yacc in context to compiler's only.

                                                            dave