Re: Some questions about recursive descent?

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

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