OT: Recursive descent parsers

From: William Bland (news123_at_abstractnonsense.com)
Date: 06/22/04 

Date: Tue, 22 Jun 2004 03:50:33 GMT

Yet another rather off topic question, posted here because Lisp hackers
know everything ;-)

I missed out on a formal computing education, as I was busy doing pure
mathematics, so I never learned about parsers. This has become important
recently because I need to write one at work (unfortunately in Java rather
than Lisp, where it'd be much easier). I already know how to write it, and
I *think* it's what you'd call a "recursive descent parser", but every
time I try to read an article on parsers I get bogged down in the BNF,
which I don't find easy to read at all.

Basically the structure I'm thinking of for my parser is a top-level
function that dispatches on the first character it reads, and calls a
bunch of helper functions, something like:

(defun read-stuff ()
  (let ((c (peek-char)))
    (cond ((char= c #\Space)
           (read-char)
           (read-stuff))
          ((char= c #\()
           (read-char)
           (read-list))
          ((digit-char-p c)
           (read-number))
          (t
           "ERROR!"))))

(defun read-list ()
  (let ((c (peek-char)))
    (cond ((char= c #\))
           (read-char)
           nil)
          (t
           (cons (read-stuff) (read-list))))))

(defun read-number ()
  (read-number-helper 0))

(defun read-number-helper (acc)
  (let ((digit (- (char-code (read-char))
                  (char-code #\0))))
    (setf acc (+ (* 10 acc) digit))
    (if (digit-char-p (peek-char))
        (read-number-helper acc)
        acc)))

but, of course, I'll have to write it in Java (yuck!). I write parsers
this way just because I can't imagine any other way to write them (well, I
suppose I can, but they wouldn't be pretty). I'd be interested to know
though:

1) is this a "normal" way to write a parser? I've seen similar things in
Lisp books, so I know I'm not the *only* person who writes them this way,
but do other people write them like this (e.g. when people write parsers
for languages like Java)?

2) is this what people mean when they say "recursive descent parser"?

Cheers,
        Bill. 

-- 
Dr. William Bland.
It would not be too unfair to any language to refer to Java as a
stripped down Lisp or Smalltalk with a C syntax.   (Ken Anderson).

Relevant Pages

  • Re: simple lisp interpreter
    ... by users is _still_ Lisp syntax. ... What I mean exactly is any sexpr syntax that conforms to ... discussing the properties of the reader absent readmacros. ... I don't know any parsers that take pointers to complex object structures as ...
    (comp.lang.lisp)
  • Re: simple lisp interpreter
    ... by users is _still_ Lisp syntax. ... discussing the properties of the reader absent readmacros. ... its program texts can fall into some less powerful class of parsers. ... The question of whether ISLISP is LLmight be worth wondering ...
    (comp.lang.lisp)
  • Re: Benefits of Dynamic Typing
    ... > people who are turned off by s-expression syntax don't spend their time ... > writing macro packages or parsers to translate other syntaxes into Lisp; ... > they just don't use Lisp. ...
    (comp.lang.functional)
  • Re: OT: Recursive descent parsers
    ... > Yet another rather off topic question, posted here because Lisp hackers ... > time I try to read an article on parsers I get bogged down in the BNF, ... > but, of course, I'll have to write it in Java. ... Principles, Techniques and Tools", by Alfred V. Aho, ...
    (comp.lang.lisp)
  • Re: jython lacks working xml processing modules?
    ... > I'm trying to parse an xml file with jython (not through java parsers ... It's quite likely that your documents contained namespaces. ... parser supported in jython is "xmlproc", ... Use a Java SAX2 parser, write a jython ContentHandler for it, build ...
    (comp.lang.python)