······@speakeasy.net (Robert E. Brown) said, a long time ago (23 Feb 2004)
Original in
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/
ee4264318ae30875/2a849cd76cb3a94e#2a849cd76cb3a94e
> Bison does not currently have a Common Lisp backend. I've talked to the
> maintainers of Bison and they're interested in supporting other
> languages, but nothing much has happened beyond C, C++ and maybe a bit
> of Java. Bison's M4 backend will have to be changed a lot before
> languages that don't look like C can be supported.
>
> However, I've translated the Bison C parser skeleton into Common Lisp,
> and tested it with a couple of simple grammars. If you have a working
> Yacc/Bison grammar for the GNU Octave language, you should be able to
> plug the C parsing tables that Bison generates into the Lisp skeleton
> below to get a working Common Lisp parser.
>
> bob
1. Does anyone know if Robert published this code or would be prepared to
publish it? Otherwise I will probably rewrite it.
2. Looking at the code generated, we see the following case statement.
;; Process the action for this production (in C this is a switch statement)
(case yyn
(4
)
(5
)
(6
(setf yyval (aref yyvs yyvs-index)))
... much more etc
For a large grammar, this case macro will be very large. The only lisp
that handles such a macro efficiently, that I have tested, is GCL. I
have tested with (proclaim '(optimize (speed 3) (debug 0)) and (declare
(fixnum yyn)) or similar to encourage fast code generation.
I am told that at least one of the commercial Lisps also generates good
code for this.
The generated code probably needs to be embedded into the generated parser
to allow the parser state to be updated efficiently, and to allow the many
parser variables to be accessed by the parser actions.
A similar problem exists with those lexical analyzers which have embedded
actions and which are driven by a state table.
Are there any good ways to handle such a situation efficiently, given that
we can't assume a given Lisp implementation will always handle such a case
statement efficiently?
The approach I am currently using involves putting each action in its own
anonymous function. I put the addresses of the functions into an array,
something like this:
(setf (getf aref action-table action-nbr)
#'(lambda () (blah blah blah)))
Then I can do (funcall (aref action-array action-nbr).
The funcalls seem to work fast enough but the compilation times are pretty
bad for the Lisps I tested. Not sure why.
Any thoughts welcome - even if they involve a radical change in approach.
Some other possibilities I have not explored for the reasons given - 1.
Peter Norvig style recursive descent parser with memoization (probably too
slow). 2. Generating code to implement the lexer rather than using a state
table (probably still needs lots of case macros).
Tim Josling
Greetings!
tim Josling <·············@westnet.com.au> writes:
> ······@speakeasy.net (Robert E. Brown) said, a long time ago (23 Feb 2004)
> ;; Process the action for this production (in C this is a switch statement)
> (case yyn
> (4
> )
> (5
> )
> (6
> (setf yyval (aref yyvs yyvs-index)))
> ... much more etc
>
> For a large grammar, this case macro will be very large. The only lisp
> that handles such a macro efficiently, that I have tested, is GCL. I
> have tested with (proclaim '(optimize (speed 3) (debug 0)) and (declare
> (fixnum yyn)) or similar to encourage fast code generation.
>
cvs head also implements typecase in fast C switch form when all the
subtypes are recognizeable number types, at present. Plan to extend
this to array types.
Take care,
--
Camm Maguire ····@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah