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

Groups > comp.compilers > #2860

Re: Are compiler developers light-years ahead of other software development?

Show all headers | View raw

On 2022-01-22, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Kaz Kylheku <480-992-1380@kylheku.com> writes:
>>None of the buzzwords you mentioned related to parsing are needed in
>>building a compiler: grammars, LL, LR, first() function, following()
>>function, parsing tables, etc.
>>
>>All that goes away if you write recursive descent parser. The grammar is
>>then in the documentation and code comments only, and somewhat expressed
>>in its code structure. There is no LR, first or follow, no tables.
>
> As our moderator notes, recursive descent is an implementation
> technique for LL(1) grammars.  Moreover, you need first-sets to
> implement them.  If your grammar is
>
> A -> B|C
>
> your recursive-descent parser becomes:

I touched on this point with "All that goes away if you write recursive
descent parser. The grammar is then in the documentation and code
comments only, and somewhat expressed in its code structure."

So it's not that we don't have a grammar or don't know that it's LL;
perhaps we do. But the tooling doesn't.

> if next_symbol in first(B) then parse_B else parse_C fi

In a given parser, there might be no conscious connection to any such
theoretical entities, even though the theory readily identifies those
elements in the resulting work.

(Kind of like a musician who plays by ear is using certain musical
devices that he might not be able to name, but music scholars can.)
>
> If you want to learn about conflicts in your grammar early on (rather
> than finding it out later by having some input be parsed other than
> intended), you also need follow-sets: if your grammar is
>
> A -> B|epsilon
>
> there is a conflict if "intersection(first(b),follow(A))" (where "U"
> signifies the union) is not empty: if one of the symbols in the
> intersection comes up at the start of an A, do you parse B or not?

You can easily parse both ways and pick one. There are readily available
backtracking techniques, even in blub languages.

Years ago I wrote a C expression parser which did this quite well using
exceptions based on setjmp and longjmp.

(Because it parsed expression shapes outside of any declaration context,
so it woudln't know, say, whether (A)(B) is the expression (B) being
cast to type (A), or function (A) being called with argument (B). The
goal of the parser was to determine whether the expression could have
side effects, with a tri-valued result: no, possibly, yes.)

"Parse expression grammars" formalize this more.

That sort of approach has to be carefully wielded, because you can
get poor performance due to explosion of the search space, with several
levels of speculative parsing.

> Of course, if you are freshly designing a programming language, you
> may be fine with declaring the actual behaviour of the
> redursive-descent parser to be the intended behaviour.  But if you
> have to implement a given grammar, things become more complex.

If you have to implement a given grammar, with any tool or approach,
you need to have, or develop as you go along, a comprehensive regression
test suite, hitting as many of the the corner cases as possible.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Are compiler developers light-years ahead of other software development? Roger L Costello <costello@mitre.org> - 2022-01-16 14:36 +0000
  Re: Are compiler developers light-years ahead of other software development? Philipp Klaus Krause <pkk@spth.de> - 2022-01-16 22:13 +0100
  Re: Are compiler developers light-years ahead of other software development? gah4 <gah4@u.washington.edu> - 2022-01-17 07:14 -0800
  Re: Are compiler developers light-years ahead of other software development? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-01-19 21:33 +0000
  Re: Are compiler developers light-years ahead of other software development? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-01-22 03:01 +0000
    Re: Are compiler developers light-years ahead of other software development? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-01-22 10:43 +0000
      Re: Are compiler developers light-years ahead of other software development? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-01-22 21:38 +0000
    Re: Are compiler developers light-years ahead of other software development? Roger L Costello <costello@mitre.org> - 2022-01-22 12:50 +0000
      Re: Are compiler developers light-years ahead of other software development? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-01-22 21:22 +0000
      Re: Are compiler developers light-years ahead of other software development? Ian Lance Taylor <ianlancetaylor@gmail.com> - 2022-01-22 15:40 -0800
        Re: Are compiler developers light-years ahead of other software development? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-01-23 06:17 +0000

csiph-web