Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: anton@mips.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.compilers Subject: Re: Some questions about recursive descent? Date: Tue, 01 Mar 2022 08:01:24 GMT Organization: Institut fuer Computersprachen, Technische Universitaet Wien Lines: 50 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-03-001@comp.compilers> References: <22-02-021@comp.compilers> <22-02-024@comp.compilers> <22-02-026@comp.compilers> <22-02-027@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="41624"; mail-complaints-to="abuse@iecc.com" Keywords: parse, LL(1) Posted-Date: 01 Mar 2022 17:38:47 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:2906 Johann 'Myrkraverk' Oskarsson writes: >So I was wondering if people who create /recursive descent/ parsers for >production compilers use such a table as an intermediary step, or not. Gray doesn't. For finding out about conflicts, it just looks at the nodes involved. E.g., for a|b, it produces a warning if both a and b can produce epsilon, if the first sets of a and b are not disjoint, and if a|b may produce epsilon and its first set and its follow set are not disjoint. >I don't know Forth, so I haven't done much more than take a cursory look >at the Gray manual; but it certainly wouldn't surprise me if people used >a skeleton generator, from [E]BNF grammar, and then filled in the >details later. Gray is not a skeleton generator. It takes an RRPG (regular right part grammar, similar to EBNF) with actions, and produces an executable parser (i.e., not as source code). You then run that parser, you do not fill in the details later; you provide all the details in the source code before you generate the parser. BTW, an updated version of Wirth's book that I mentioned is available online for free: . The sections of interest to you seem to be Section 4.1 and 7.2, probably also 7.3. >[ [...] In my experience most people writing RD parsers do this >informally, e.g., to deal with left recursion in expressions you know >that you eat the first token, then peek at the next token and eat it >if you're in the correct rule, otherwise return and let the caller >deal with it. If this seems like more trouble than it's worth, now >you know why we use parser generators. -John] Or you start with EBNF or RRPG where you can express repetition without recursion, so left recursion is rare. I happen to look at Exercise 7.2 at this moment, which suggests another way to deal with difficulties: |7.2. Where is the Oberon syntax not LL(1), that is, where is a |lookahead of more than one symbol necessary? Change the syntax in such |a way that it satisfies the LL(1) property. - anton -- M. Anton Ertl anton@mips.complang.tuwien.ac.at http://www.complang.tuwien.ac.at/anton/