Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Christopher F Clark Newsgroups: comp.compilers Subject: RE: Some questions about recursive descent Date: Mon, 28 Feb 2022 15:40:37 +0200 Organization: Compilers Central Lines: 50 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-02-025@comp.compilers> References: <22-02-021@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="1706"; mail-complaints-to="abuse@iecc.com" Keywords: parse, LL(1) Posted-Date: 28 Feb 2022 10:57:34 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:2903 I'll start with the most important response first. It should definitely be possible to return the generated syntax tree from a procedure implementing a parser rule (for a non-terminal) in a recursive descent compiler. In fact, it surprises me that you say that's not the normal case. It's *almost* the definition of recursive descent. One calls the function implementing some non-terminal and the non-terminal consumes its input, building internally a representation of that input (as a single structure, i.e. an AST node) and returns that structure to the caller, so that the caller can do the same. Each call makes a new rooted tree (that identifies what kind of tree it is, i.e. what non-terminal it represents) and it is used by the caller as part of the larger tree containing it. Now, I supposed it *could* make sense not to make that the return value for the function implementing the non-terminal, but it certainly is a natural value to return. More on that after I talk about tables. It is possible to implement LL (as was as LR and precedence and other) parsers as parser tables. Recursive descent doesn't generally do so. It implements that parser as code, specifically nested function calls, with some (generally, but not necessarily) small amount of logic to determine which variant (alternative) of a non-terminal is being processed. This logic is what uses the result of the first (and follow) functions to determine based upon the initial tokens which alternative matches the input. This is generally done without parsing tables. Using parsing tables generally suggests you are implementing a different parsing methodology than recursive descent, even if you are doing so only as a subroutine within a recursive descent parser. The parts not using the tables are the recursive descent part. The part using the table is an embedded parsing technology within an otherwise recursive descent framework. Ok, back to the question of what a recursive descent parser's routine implementing the parsing of a non-terminal should be. In an Object-oriented world, it would be reasonable for it to return an "object" representing the non-terminal, with methods/member functions that get you the sub-parts, evaluate attributes, etc. Another reasonable return value, comes from the Rust world, it could be a "result type", where it is either the non-terminal as discussed before, or an error. (Result). However, in the non-error case, you generally want each parsing rule to return the root non-terminal of the AST is parsed. -- ****************************************************************************** Chris Clark email: christopher.f.clark@compiler-resources.com Compiler Resources, Inc. Web Site: http://world.std.com/~compres 23 Bailey Rd voice: (508) 435-5016 Berlin, MA 01503 USA twitter: @intel_chris ------------------------------------------------------------------------------