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

Groups > comp.compilers > #2901

Re: Some questions about recursive descent?

Show key headers only | View raw

On 2/27/22 8:02 PM, Johann 'Myrkraverk' Oskarsson wrote:

> My first question is: how are production recursive descent parsers con-
> structed?

I think that most parsers are hand made, from a well suited (EBNF...)
grammar.

But also have a look at the many tools found by "LL(1) parser
generator". I don't think that all these tools are/have been used to
generate compilers for a couple of new programming languages.

I've explored and modified CoCo/R many years ago. After I understood the
principles I wrote my essential parsers for OPL and C manually, based on
the fine patterns of that Compiler Compiler.


> Second question: why are recursive descent parsers I've come across
> always using globals and construct code and/or the parse tree as side
> effects, rather than, say, return the parse tree to the caller?

Don't think only of programming language compilers if you ask for a
parser. There exist many use cases for parsers like pretty printer, CSV,
RNA or other data deciphering. Not all such "compilers" need a
(complete) parse tree but interpret the parser output differently,
depending on the compilation target.


>      Is this something to do with /synthesized attributes/ that [Holub]
> talks about?  Where the recursive descent parser routines return values
> to the caller, or is this maybe just a tradition that no one bothers to
> change?

One of the nasties disadvantages of commonly used formal grammars are
the specific attributes or similar decoration for a specific compiler.
This makes it hard to use a verified grammar for construction of a tool
other than the one the grammar writer had in mind, maybe a different
compiler implementation language or framework. So one use case of a
parser generator were a decoration remover or converter from some
grammar. This were my most important argument *against* embedding the
parse tree generation into the parser.

Another very interesting experiment was cooperation between Quinn Tyler
Jackson's MetaS parser program, written in C++, and my parse tree
generator, written in Delphi.


> Now, to give these questions a bit of context, as a practice, I wanted
> to create a recursive descent parser for the first programming exercise
> in [Salomon] but found out the hard way that it's not so trivial to
> figure out /how/.

Parser generators can be too picky WRT minor problems of a grammar, like
the famous dangling else. Most practical solution then is a reduced
grammar without the problematic parts and full or partial manual parser
implementation.

DoDi

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