Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2904

Re: Some questions about recursive descent?

Show all headers | View raw

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

> Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> writes:
>>My first question is: how are production recursive descent parsers con-
>>structed?  From these two books, and other things I have read in the
>>past, recursive descent is so simple it's mostly just brushed off with
>>an example or two, but there seems to be a whole lot more to it.  For
>>instance, [Appel] mentions a parse table but mostly does not explain how
>>to construct one.
>
> I don't know what such a table would be good for.  My parser generator
> Gray <https://www.complang.tuwien.ac.at/forth/gray.zip>, which
> generates recursive-descent parsers, certainly does not need one.

A parse table for recursive descent/LL(1) simply tells which rule to
expand given the non-terminal currently parsed and the incoming token
type. The building of this table is described in, e.g., the dragon book
(for sure in the 2nd edition).

> The way Gray works is: It computes first and follow sets for all nodes
> in the grammar; follow sets are only used for computing first

You probably mean the reverse (first is used to compute follow).

> sets and for reporting conflicts, first sets are used for deciding how
> to parse. It generates code as follows:
>
> grammar  code
> terminal if sym in first(terminal) then sym=scan(); else syntax_error(); end
> a b      code(a) code(b)
> a|b      if sym in first(a) then code(a); else code(b); end
> a?       if sym in first(a) do code(a); end
> a*       while sym in first(a) do code(a); end
> a+       do code(a) while sym in first(a)
> nonterm  call(function(nonterm))
> action   action

The parsing table embodies all that logic. Parsing works by maintaining
a stack of symbols, and the table indicates what actions need to be
taken (either replace one non-terminal with a rhs on the stack, or match
one input symbol). The algorithm works with any table, and the whole
thing (algorithm+table) is certainly much shorter than generating code
for each and every rule. EBNF constructions like ?/*/+/... have to be
translated first into "regular" rules, but that's trivial pre-processing
(along with left factoring/recursivity elimination).

Building a parse tree in this context is less obvious, because
non-terminal symbols seem to "disappear" during the parsing. The
solution (at least the one I came up with) consists in keeping special
entries on the stack signaling the end of a rhs. Then, special actions
(i.e., "reduce") can be taken when finding these special entries during
parsing, much in the same way as it is done in bottom-up (e.g., LR)
parsing: the "semantic values" of the various symbols can be pushed onto
a separate stack, and you end up with something really similar to
LR-parsing.

-- Alain.
[I think the point is that if you have a table, you have a table driven
LL(1) parser rather than recursive descent in which the grammar is embedded
in the code. -John]

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Some questions about recursive descent? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> - 2022-02-27 19:02 +0000
  Re: Some questions about recursive descent? gah4 <gah4@u.washington.edu> - 2022-02-27 17:13 -0800
  Re: Some questions about recursive descent? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-02-28 06:48 +0100
  Re: Some questions about recursive descent? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-02-28 07:43 +0000
    Re: Some questions about recursive descent? Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-02-28 21:52 +0100
      Re: Some questions about recursive descent? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2022-03-01 01:40 +0000
        Re: Some questions about recursive descent? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-03-01 08:01 +0000
        Re: Some questions about recursive descent? Alain Ketterlin <alain@universite-de-strasbourg.fr> - 2022-03-01 23:13 +0100
        Re: Some questions about recursive descent? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-03-02 05:52 +0100
    Re:Some questions about recursive descent? "Paul Robinson" <xdpascal@xdpascal.com> - 2022-03-05 14:46 -0600
  RE: Some questions about recursive descent Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-02-28 15:40 +0200

csiph-web