Re: Generating a simple hand-coded like recursive descent parser

Pascal Bourguignon wrote:


> The main idea of the recursive descent parser, is that you can select
> the production rule from the first terminal.


Provided you have a LL(1) grammar. What should be right for BASIC
languages...


But I'd structure the grammar in a different way:


> k1 --> "clear"
> k2 --> "clear" "local"
> k3 --> "clear" "local" "mode"
k --> "clear" [ "local" [ "mode" ] ]


> l1 --> "local"
> l2 --> "local" "mode"
l --> "local" [ "mode" ]


> d1 --> "def" "fn" <function name> [ "(" <paramater list> ")" ]
> d2 --> "def" "fn" <function name> "=" <expression>
> d3 --> "def" "fn" <function name> "USING" <functionPointer>
d --> "def" "fn" <function name> [ ... ]


EBNF better supports grammars for LL languages, because it can reflect
the parser structure very well:


if token = "local" then
      if nextToken = "mode" then ... else ...
else
      Error...


The same for {...} repetitions, which translate into while loops.


This way it's possible to hand-craft an recursive descent parser from a
well-formed EBNF grammar. The use of additional tools can be reduced to
formal grammar checks, and to the generation of the FIRST and FOLLOW
sets, from which the procedure tree can be generated either
automatically or manually.


In so far I don't understand (and can't encourage) the way you bloat a
formal grammar first, only to produce the effectively same procedure
structure that could be expressed in EBNF immediately.


Problems IMO can arise only from an inappropriate grammar design, which
might not be LL(1), where a LL(1) grammar is feasable. Unfortunately I
don't know of a tool, that would take an arbitrary grammar, and would
transform it into a LL(1) grammar if ever possible:


> My example Recursive Descent Parser Generator doesn't normalize the
> grammar in such a way, so you'd have to make sure to write the grammar
> such as the first set of each non-terminal group is disjoint.
>
> It would be better to use a parser generator that did this grammar
> normalization (there is a simple algorithm to do this normalization).


Can you give a reference, please?


CoCo/R will report an LL(1) error for a dangling else or other
constructs, which in fact do not prevent the construction of an correct
recursive descent parser.




> Therefore I wouldn't bother with expecting a readable generated
> parser. Table driven parsers are well known and work well and
> efficiently.


You omit one important step in the development of an parser:


In the first place the user has to supply a grammar that *exactly*
reflects the given language!


In this development stage a table driven parser cannot assist in finding
eventual errors in a grammar. The parser generator will either produce
an parser, for a different language, or will report formal errors, which
typically are not related to the error in the language/grammar
transformation. And debugging an table driven parser for such errors is
a nightmare :-(




Even if e.g. CoCo will not produce parsers for many simple languages,
due to LL(1) errors, it will give pointers to the places, where the
grammar deserves a redesign. Then an according modification of an EBNF
grammar is much easier to perform, because the grammar reflects the
formally or informally given language description much closer, and with
less bloat, than a LR(k) BNF grammar.


That's why I suggest to try, at least, to develop an EBNF LL grammar in
the first place, until that grammar seems to reflect the intended
language. Having reached this milestone, the developer can decide
whether to follow this road, and to produce an recursive descent LL
parser, either manually or automatically, or to switch to an LR parser,
if the language is inappropriate for LL parsing at all.




IMO this point was never honored appropriately in the discussion about
recursive descent and table driven parsers. Table driven parsers are
fine, provided that a grammar already exists, or the developer is free
to design a very new language. But in cases, where a language is not
described by a formal (BNF) grammar, an according existing compiler most
probably was *not* based on an table driven parser. Then I don't see any
reason, to favour an table driven parser for that language. A recursive
descent parser instead will allow to implement exactly the same hacks,
which possibly have been inserted in the original compiler for that
language.


DoDi

Return to the comp.compilers page.
Search the comp.compilers archives again.