Re: Ambiguous AST ?

"Ira D. Baxter" <>
11 Mar 2002 02:16:29 -0500

          From comp.compilers

Related articles
Ambiguous AST ? (2002-03-09)
Re: Ambiguous AST ? (Ira D. Baxter) (2002-03-11)
Re: Ambiguous AST ? (Joachim Durchholz) (2002-03-11)
Re: Ambiguous AST ? (2002-03-11)
| List of all articles for this month |

From: "Ira D. Baxter" <>
Newsgroups: comp.compilers
Date: 11 Mar 2002 02:16:29 -0500
Organization: Compilers Central
References: 02-03-042
Keywords: syntax
Posted-Date: 11 Mar 2002 02:16:29 EST

Yes, it is quite practical.

Our DMS Software Reengineering Toolkit does exactly this. Parsing
builds trees having special ambiguity nodes with (maximally shared)
subtrees representing the various alternative parses.

We do symbol table creation by running an attribute evaluator over the
parse tree. Special attribute evalution synthesized properties
include ERROR, meaning that this interpretation is semanticcally
wrong. A side-effect of such a signalled property is that the
offending subtree is deleted, leaving behind only
semantically-sensible trees. (Of course, you might have multiple
versions of those, too).

In practice, for well-formed programs, only one subtree remains, and
its ambiguity node is automatically removed. At the end of the symbol
table creation process, you end up with an unambiguous tree, and a
well-formed symbol table.

Ira D. Baxter, Ph.D. CTO Semantic Designs, Inc.

"Nicolás Ojeda Bär" <> wrote in message
> I am writing a front end for something like Pascal. I want to separate
> as much as possible the parsing from the semantic analysis,
> intermediate code, and code generation in order to mantain a clear
> organization.
> Clearly, I want to postpone symbol table creation to a second pass
> over the ast created during parsing (otherwise, i.e. if I were
> creating the symbol tables during parsing, it wouldn't be logical to
> delay e.g. type checking until later). Now, Pascal's syntax is
> semantically ambiguous, in particular one cannot know if a identifier
> in an expression is a variable reference or a function call without
> arguments.
> My question is the following: since I have no way of knowing which
> case it is without symbol table information (which I have not
> collected during parsing time), would it be
> practical/logical/realistic to have an "ambiguous" ast data structure
> (an ast node that doesn't specify which of the two cases I have
> encountered) and then translate that (during semantic analysis) to the
> corresponding data structure (according to the info collected while
> processing the declarations).

Post a followup to this message

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