Re: Grammars and parse trees.

What you are talking about is a Context-Free Grammar, this is defined
by a grammar G=(V,T,S,P) if all productions in P have the form A->x,
where A is an element of V and x is an element of (V U T)*. Thus V is
defined as a set of variables, T is defined as a set of terminals, S
is the starting Variable and P is a set of productions for this
grammar. Consider the following grammar bellow:


[consider & to be theta (or the empty string)
Also note this example is case sesitive]


G=(V,T,S,P) : V={A,B}, T={a,b,c}, S=A, P={A->aAc|bBc|&,B->bBc|&}


Therefor the string "abcc" would be in this grammar.
A->aBc->abBcc->abcc
This would also produce the following Derivation Tree:
    A
a B c
  bBc
    &


This grammar produces the language L = {a^n b^m c^(n+m)} where spaces are
used only for readability and ^m or ^n etc. are used as mathematical
exponent symbols and are not part of the language. As can be seen the
alphabet used is {a,b,c}*


As you can see the set of variables and the terminals are the nodes in
the tree and only the terminals are the leaves.


For ease of use the above grammar in Backus-Naur form is:
<a's> ::= a <a's> c | b <b's> c | &
<b's> ::= b <b's> c | &


For your question let us use the grammar in Backus-Naur form:
<T> ::= <T>^<T> | A | B
This would give you the following derivation tree below:
                                          <T>
                              <T> ^ <T>
                                    A ^ A
This tree is correct for the given string of "A^A".
If when implementing you code you use a tree structure of objects to relize
your given tree then your grammar may change just a little to give you the
following grammar:
<non-terminal> ::= <non-terminal> ^ <non-terminal> | <terminal>
<terminal> ::= A | B
using this grammar then the non-terminal object be used to contain other
nonterminal objects and terminal objects. When you travese the tree you can
then tell where a terminal may be by traversing the structure from left to
right or right to left depending on preference.


I hope that this has helped you with your problems. I am not an expert on
grammars yet but the class I am currently taking on Automata & Formal
Languages Theory is helping. The book we are using is "An Introduction To
Formal Languages and Automata" second edition by Peter Linz Library of
Congress Catalog Number: 95-80417 or ISBN 0-7637-0296-X. You can also look
at my web page that I hope sometime in the next few months I will be putting
information on formal languages on. This will depend on how busy I am such
that I am a RA at my University and time is scarce.
http://www.wiu.edu/users/mucm9


Immanuel Litzroth wrote in message 99-04-011...
>My question is about the conceptual interpretation of parse trees. ...
>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).

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