Re: problem with C grammar

"Ira Baxter" <idbaxter@semdesigns.com>
3 Jun 2006 18:55:27 -0400

          From comp.compilers

Related articles
problem with C grammar the.malfunction@googlemail.com (the.malfunction@googlemail.com) (2006-05-26)
Re: problem with C grammar ik@unicals.com (Ivan A. Kosarev) (2006-05-26)
Re: problem with C grammar DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-05-30)
Re: problem with C grammar cfc@shell01.TheWorld.com (Chris F Clark) (2006-05-30)
problem with C grammar a.t.hofkamp@tue.nl (A.T.Hofkamp) (2006-05-30)
Re: problem with C grammar rsc@swtch.com (Russ Cox) (2006-05-30)
Re: problem with C grammar idbaxter@semdesigns.com (Ira Baxter) (2006-06-03)
Re: problem with C grammar hebisch@math.uni.wroc.pl (Waldek Hebisch) (2006-06-03)
Re: problem with C grammar mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-06-05)
| List of all articles for this month |

From: "Ira Baxter" <idbaxter@semdesigns.com>
Newsgroups: comp.compilers
Date: 3 Jun 2006 18:55:27 -0400
Organization: NewsGuy - Unlimited Usenet $19.95
References: 06-05-078 06-05-082 06-05-092
Keywords: C, parse
Posted-Date: 03 Jun 2006 18:55:27 EDT

"A.T.Hofkamp" <a.t.hofkamp@tue.nl> wrote in message
>
> <the.malfunction@googlemail.com> wrote
>
> If you dislike the idea of having the syntactical phase and semantical phase
> intertwined, you may want to use a parser that delivers a parse forest
(that
> is, all parse trees derivable from the grammar for your input) instead of
a
> single tree. In the (seperate) semantical phase you can then decide which
> trees of the forest you should use.
>
> Two approaches that do this are
>
> 1. T.A. Wagner and S.L. Graham, Incremental analysis of real programming
> languages. In proceedings of 1997 ACM SIGPLAN conference om Programming
> language design and implementation, pages 31--43, ACM Press 1997
>
> 2. P. Klint and E. Visser, Using filters for the disambiguation of
> context-free grammars, In G. Pighizzini and P. San Pietro, editors Proc.
> ASMICS Workshop on Parsing Theory, pages 1--20, Milano Italy, 1994, Tech
Rep
> 126-1994, Dipartimento di Scienze dell'Informazione, Universit\`a di
Milano.
>
> Of the latter, there is also an implementation, described in
>
> M.G.J. van den Brand, S. Klusener, L. Moonen, and J.J. Vinju. Generalized
> Parsing and Term Rewriting: Semantics Driven Disambiguation, in:
Proceedings
> of Third Workshop on Language Descriptions, Tools and Applications
(LDTA'2003)
> (eds. B.R. Bryant and J. Saraiva), volume 82 of Electronic Notes in
> Theoretical Computer Science, Elsevier, 2003.


The DMS Software Reengineering Toolkit implements a variation of the
1. above, using a tightly integrated attribute evaluator. In
particular, it uses a GLR parsing engine to produce a parse DAG with
embedded ambiguities and shared subterms (this is a property of good
GLR parsers). So-called "Semantical" information is really just an
inference of facts from the syntax tree (sometimes even from the
ambiguous part, many langauges have rules to the effect that "if xxx
is ambiguous, then the meaning is yyy").


It is quite effective to encode such inferences as an attribute-value
computation. The DMS attribute evaluators allow the specification of
such computations in a typical functional-program form, but unusually
allows side effects. One special side effect is the signaling of
"semantic errors", which cause branches under and ambiguity node to be
automatically eliminated. Combining name and type resolution with the
signalling of semantcial errors deletes the "wrong subtrees" of
ambiguities.


We use this in most of our langauge front ends, and it
works beautifully for C++.




--
Ira Baxter, CTO
www.semanticdesigns.com


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.