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

Groups > comp.compilers > #1128

Re: LL vs LR, was Programming language and IDE design

Show key headers only | View raw

On 2014-03-02, Ivan Godard <ivan@ootbcomp.com> wrote:
> On 3/1/2014 4:03 PM, Hannah wrote:
><snip>
>
>> So the C grammar is not LL(k) for any k, either. You can probably parse
>> that particular part of the C/C++ grammar easily using LR.
>>
>> Hannah.
>
> The standard way to handle this, and many such other cases where a
> formal grammar is not LL, is to introduce a function (in recursive
> descent) or rule (in parser generators) that recognizes "parenthesized
> thingy" and then figure it out later. Yes, that amounts to LR, but you
> only need it in a few specialized places. There's an equivalent trick
> in "DOI=1," in Fortran, where you let the lexer resolve it so the
> parser sees proper lexemes, not characters.

You can parse "anything" with LL(k) with backtracking. What you do is
you try various different parses, in a carefully designed order, until
something matches, with backtracking.

> [C++ is unusually bad, with some parts just plain ambiguous.  In the example
> a few messages back, I gather that the rule is that if you can parse it as a
> declaration, it's a declaration, otherwise it's something else. -John]

Years ago (1999) I wrote a parser for C expression syntax (only the expression
syntax)  as part of a module which could diagnose, at run-time, unsafe uses of
a C macro that contains multiple evaluations:

The source code is here:

http://git.savannah.gnu.org/cgit/kazlib.git/tree/sfx.c

E.g. dumb example:

  #define INCR(A) (SFX_CHECK(A) = (A) + 1)

This SFX_CHECK (actually KAZLIB_SFX_CHECK, for hygiene) expands to code which
produces the value of (A), but also hands the expression "A" to a run-time
checker which answers the question, does the C expression "A" have side
effects?

The answer to the question is "yes, no, or possibly".

(Also, the expression "A" is put into a hash table which caches the
result for next time, so the checking is faster, when turned on.)

If the answer is other than no, then a diagnostic is printed, with the
expression "A", and file name and line number where that macro was
expanded. The diagnostic tells you whether there is a confirmed problem
in that line or just suspicion.

The parser has way to know how a symbol is declared, and so it uses
backtracking techniques.

In fact, an exception library based on setjmp/longjmp is used for some
backtracking returns.  There is logic like, "if parsing it this way throws a
syntax error, try it this way".

For instance, what is "(a)(b)"?  This could be that function a is being
called with argument b.  Or it could be that a is a type, and b is being
cast to that type.

I remember parts of this being somewhat tough to write, but it looks fairly
transparent to me today.  That was about a year before I discovered Lisp.

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

Thread

Re: Programming language and IDE design Martin Ward <martin@gkc.org.uk> - 2013-11-16 15:55 +0000
  Re: Programming language and IDE design Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2013-11-16 19:48 +0100
  Re: Programming language and IDE design George Neuner <gneuner2@comcast.net> - 2013-11-18 19:02 -0500
    Re: Programming language and IDE design "Steven G. Kargl" <sgk@REMOVEtroutmask.apl.washington.edu> - 2013-11-19 15:36 +0000
    Re: Programming language and IDE design George Neuner <gneuner2@comcast.net> - 2013-11-19 12:41 -0500
      Re: Parsing Fortran, was Programming language and IDE design glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-11-19 20:18 +0000
        Re: Parsing Fortran, was Programming language and IDE design glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-11-21 21:22 +0000
    Re: Programming language and IDE design wclodius@earthlink.net (William Clodius) - 2013-11-22 18:27 -0700
    Re: Programming language and IDE design "robin" <robin51@dodo.com.au> - 2013-11-25 10:33 +1100
      Re: Programming language and IDE design Martin Ward <martin@gkc.org.uk> - 2013-12-03 15:15 +0000
        Re: Programming language and IDE design Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2013-12-05 03:35 +0100
    Re: Programming language and IDE design hu47121@usenet.kitty.sub.org (Hannah) - 2014-03-02 00:03 +0000
      Re: LL vs LR, was Programming language and IDE design Ivan Godard <ivan@ootbcomp.com> - 2014-03-01 20:31 -0800
        Re: LL vs LR, was Programming language and IDE design Kaz Kylheku <kaz@kylheku.com> - 2014-03-02 18:41 +0000
      Re: Programming language and IDE design George Neuner <gneuner2@comcast.net> - 2014-03-02 12:21 -0500
  Re: Programming language and IDE design Jonathan Thornburg <jonathan@cobalt.astro.indiana.edu> - 2013-11-19 19:39 +0000

csiph-web