Re: problem with C grammar

"A.T.Hofkamp" <a.t.hofkamp@xxxxxx> wrote in message

<the.malfunction@xxxxxxxxxxxxxx> 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
.

Relevant Pages

  • problem with C grammar
    ... I rather would like to let the parser do ... Is there any way to change the grammar such that I can use ... IDENTIFIER instead of TYPE_NAME here without having all those conflicts? ... Parsing and Term Rewriting: Semantics Driven Disambiguation, ...
    (comp.compilers)
  • Re: Is interpret/compile the wrong distinction?
    ... I want the behavior of S" to be: parse a string ... the part performed at parse time: ... Depending on whether we want to have interpretation semantics, ...
    (comp.lang.forth)
  • Re: C99 parser ?
    ... just something which checks syntax and semantics. ... and to learn the syntax and semantics of the C99 standard. ... Sparse (semantic parser) is a project for a C/C++ parser that might be ...
    (comp.compilers)
  • Re: Universal grammar
    ... domain of mathematics. ... One might attempt to pin down this semantics using tree structures ... It is not difficult to write parser that ... logical models for the natural language semantics. ...
    (sci.lang)
  • Re: Is C99 the final C? (some suggestions)
    ... >> Yes it complexifies the parser quite a bit. ... I don't dispute that. ... It depends on the semantics ...
    (comp.lang.c)