Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Johann 'Myrkraverk' Oskarsson Newsgroups: comp.compilers Subject: Some questions about recursive descent? Date: Sun, 27 Feb 2022 19:02:59 +0000 Organization: Easynews - www.easynews.com Lines: 73 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-02-021@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="1651"; mail-complaints-to="abuse@iecc.com" Keywords: parse, question Posted-Date: 27 Feb 2022 16:37:05 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Content-Language: en-US Xref: csiph.com comp.compilers:2899 Dear comp.compilers, I am currently reading two compiler books, [Holub] and [Appel], and then [Salomon] for a bit of context below, [Holub] Compiler Design in C, 1990, by Allen Holub [Appel] Modern Compiler Implementation in ML, 2004, by Andrew Appel [Salomon] Assemblers and Loaders, 1993, David Salomon and I have some questions about the construction of recursive descent parsers. If some of my questions are adequately answered in some other publication, reference, preferably with chapter and verse, is welcome. The reason for my questions is that I know production compilers /use/ recursive descent. GCC is probably the most famous example, but Watcom does it too. More below as well. 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. The rest of the book seems to be focused on ML-lex and ML-yacc, which I haven't read yet. I have read more of [Holub] and he explains the theory much better, in fact this seems to be the best theory introduction I remember coming across ever. Yet, that book also does not spend too much effort on rec- ursive descent, and goes on about implementing and using lex and yacc like tools. [Holub] explains the construction/algorithms for FIRST and FOLLOW sets better than [Appel], in my opinion, but I do not recall any more details about said parse table, which seems instrumental in the con- struction of the final recursive descent. [Holub] does mention Q grammars, and how they are very easy to turn into recursive descent. 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? 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? 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/. My first methods were somewhat ad-hoc to create and modify the grammar to be non-left-recursive, which I think was mostly easy due to the assembler being very bare bones, and hence the grammar can be very simple. Then I ran into trouble when I tried to make the parser return the parse tree, rather than construct it with side effects. Granted, some of my problems are from using a programming language, ML, that I'm not familiar with, which I decided to use for another wrinkle in the exercise. If the project is too easy, it just isn't /fun/. The first wrinkle I stumbled upon, when I started to read up on the subject, is that constructing the parse table, as a preliminary step, isn't really explained in [Appel] -- at least not to my satisfaction -- and I found not much better coverage of the subject in [Holub] though certain topics are covered better. In the past, when I've stumbled like this, reading up on the subject has helped a lot, but so far, almost everything I've read seems inade- quate in different ways. Side thought: do any of the mentioned authors read this list? Thanks, -- Johann | email: invalid -> com | www.myrkraverk.com/blog/ I'm not from the Internet, I just work there. | twitter: @myrkraverk