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

Groups > comp.compilers > #2906

Re: Some questions about recursive descent?

Show all headers | View raw

Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> 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:
<https://people.inf.ethz.ch/wirth/CompilerConstruction/CompilerConstruction1.pdf>.
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/

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