Writing a parser in lisp...

[Camm Maguire]

Greetings! Is lisp well suited to this? Especially in comparison to
flex/bison, which I already know?

I've found:

http://www.pipeline.com/~hbaker1/Prag-Parse.html

Are there any other good examples?

Take care,
--
Camm Maguire ca...@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah

[Raymond Wiker]

Camm Maguire <ca...@enhanced.com> writes:

> Greetings! Is lisp well suited to this? Especially in comparison to
> flex/bison, which I already know?
>
> I've found:
>
> http://www.pipeline.com/~hbaker1/Prag-Parse.html
>
> Are there any other good examples?

Zebu, probably.

--
Raymond Wiker Mail: Raymon...@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60

Try FAST Search: http://alltheweb.com/

[Peter Seibel]

Camm Maguire <ca...@enhanced.com> writes:

> Greetings! Is lisp well suited to this? Especially in comparison to
> flex/bison, which I already know?
>
> I've found:
>
> http://www.pipeline.com/~hbaker1/Prag-Parse.html
>
> Are there any other good examples?

I wrote a parser generater based on Baker's paper. It is not 100% soup
yet but I'm planning/hoping to finish it off and include it in my
book. For the moment you can see a version of it at:

<http://www.gigamonkeys.com/lisp/>

The file parser.lisp is the main parser generator and java-lexer.lisp
is a grammar that uses it to tokenize Java source code.

-Peter

--
Peter Seibel pe...@javamonkey.com

Lisp is the red pill. -- John Fraser, comp.lang.lisp

[Jeff Dalton]

Camm Maguire <ca...@enhanced.com> writes:

> Greetings! Is lisp well suited to this? Especially in comparison to
> flex/bison, which I already know?

I've found it fairly easy to write recursive-descent parsers
in Lisp, not using a "compiler-compiler" / parser-generator,
but using a small libraary of functions such as zero-or-more
that make it easier to handle common cases.

Some fragments, from different parsers:

(defun <conditions-clause> ()
(cons 'conditions
(one-or-more #'<condition-statement>
:separator '|,|
:until '|;|)))

(defun <definition> ()
(unless *allow-definitions*
(syntax-error
"Definitions are not allowed in the scope of local
declarations."))
(token-case
((variable) (<variable-definition>))
((parameter) (<parameter-definition>))
((constant) (<constant-definition>))
((function) (<function-definition>))
((method) (<method-definition>))
((generic) (<generic-definition>))
((structure) (<structure-definition>))
((class) (<class-definition>))
(t
(syntax-error "Illegal definition type \"~S\"." (token)))))

I use a version of the "S-algol error recovery scheme" described
in the book _Recursive Descent Compiling_ by A. J. T. Davie and R.
Morrison (Ellis Horwood, 1981), which in turn comes from a scheme
developed by D. A. Turner for a SASL compiler.

It works reasonably well and is very easy to implement.

Here's an example. Suppose the syntax of an "if" statement is
"if <expression> then <statement> fi". The procedure for parsing
an "if" will include code like the following:

(setq test (expression))
(must-be 'then)
(setq consequent (statement))
(must-be 'fi)

Suppose the expression parses without error but the "then" is missing
or misspelled. must-be will report that as an error and set the
special variable *recovering* to true. While *recovering* is true,
syntax errors aren't reported. The next call to must-be,
(must-be 'fi) will notice that *recovering* is true and hence
will discard tokens until it finds a fi. It then sets
*recovering* to false.

There's also a must-satisfy. For example:

(defun <variable> ()
(must-satisfy #'name-p "a valid variable name"))

If too much (or too little) is discarded in some common case, it will
often be possible to add some special-purpose processing for that case
while still using the general method for the rest. The zero-or-more
and one-or-more functions do some things of that sort.

-- jd

[Petter Gustad]

Camm Maguire <ca...@enhanced.com> writes:

> Greetings! Is lisp well suited to this? Especially in comparison to
> flex/bison, which I already know?

I've used meta and zebu. Meta is very impressive because it's so
simple and elegant. But the grammars are a little difficult to
maintain. Zebu on the other hand is a more classical parser generator.
Lately I've moved more towards Zebu. It's powerful, but I wish I it
had a more expandable lexical analyzer.

Petter

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?