Grammars and parse trees.

Immanuel Litzroth <>
1 Apr 1999 00:58:48 -0500

          From comp.compilers

Related articles
Grammars and parse trees. (Immanuel Litzroth) (1999-04-01)
Re: Grammars and parse trees. (Chris Matthew) (1999-04-06)
| List of all articles for this month |

From: Immanuel Litzroth <>
Newsgroups: comp.compilers
Date: 1 Apr 1999 00:58:48 -0500
Organization: Compilers Central
Keywords: parse

My question is about the conceptual interpretation of parse trees.
lets say the following grammar is given over an alphabet {^,A,B} and a
production (T is start symbol and only nonterminal)
T ::= T ^ T | A | B.
A parse tree for an expression should be a tree (right!?) and my
question is what the collection of nodes is that tree is defined
over. It cannot be the the strings consisting of terminals since that
would make it impossible to produce a parse tree for A ^ A (no way to
distinguish between the first and the second A).
My guess is you have to rewrite the string you want to parse to label
the terminals with the positions they occur in. But only the terminals
that can appear as leaves of the parse tree have to be changed.
Has anybody some comment on this (or a pointer to some theory).
[Grammars can generally have arbitrary numbers of each terminal in a
sentence. If you care which is which (sometimes you do, sometimes you
don't) you have to tag them, typically outside the parser. -John]

Post a followup to this message

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