Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.misty.com!news.iecc.com!.POSTED!nerds-end From: Kaz Kylheku Newsgroups: comp.compilers Subject: Re: LL vs LR, was Programming language and IDE design Date: Sun, 2 Mar 2014 18:41:00 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 65 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-03-006@comp.compilers> References: <13-11-016@comp.compilers> <13-11-018@comp.compilers> <14-03-003@comp.compilers> <14-03-004@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: miucha.iecc.com 1393846009 99357 64.57.183.58 (3 Mar 2014 11:26:49 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Mon, 3 Mar 2014 11:26:49 +0000 (UTC) Keywords: C, parse, tools Posted-Date: 03 Mar 2014 06:26:49 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:1128 On 2014-03-02, Ivan Godard wrote: > On 3/1/2014 4:03 PM, Hannah wrote: > > >> 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.