Re: OT: Recursive descent parsers

From: Paul (nath5573_at_uidaho.edu)
Date: 06/22/04 

Date: Tue, 22 Jun 2004 01:41:16 -0700
To: William Bland <news123@abstractnonsense.com>

Look into the structure of lex and yacc(flex/bison).
The man pages are not too bad.

If you are familiar with automata theory and computability, a technical
book on parsing should bring you up to speed easily.

There are three general questions:
-> lexical analysis (is this string in the set of permissable words, and
is it [keyword|identifier|etc]?)

->syntactical anlysis (is this string of words in the grammar of this
language or can it be transformed into the grammar of this language?
(here is where bnf shows up)

->semantic analysis (assigning meaning to each construct in the grammar)
This is "annotated grammar"

Look into the compiler book by Aho, if you can find it.

William Bland wrote:
> 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.

Relevant Pages

  • Re: ANTLR Target for Ruby
    ... I'm in the process of migrating a YACC grammar to ANTLR. ... However, since the rest of the project is written in Ruby, I'd like to ... LALR) parsers or is there just extra overhead that you need at parse time ...
    (comp.lang.ruby)
  • 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: Ruby Parser Combinator
    ... build complex Grammar productions by combining Grammars. ... def initialize ... class Code < SimpleGrammar ... This way you can build lexers, parsers, ...
    (comp.lang.ruby)
  • A Grammar Writing Question
    ... ordered-choice grammar wouldn't result in an equal or better match to ... parsers that process them. ... statement of the language (usually acknowledged to not be quite be the ... take a look at the examples and ask yourself - if a compiler failing ...
    (comp.compilers)
  • 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)