6 Apr 1999 22:50:14 -0400

Related articles |
---|

Grammars and parse trees. Immanuel.Litzroth@pandora.be@telenet-ops.be (Immanuel Litzroth) (1999-04-01) |

Re: Grammars and parse trees. c-matthew@wiu.edu (Chris Matthew) (1999-04-06) |

From: | "Chris Matthew" <c-matthew@wiu.edu> |

Newsgroups: | comp.compilers |

Date: | 6 Apr 1999 22:50:14 -0400 |

Organization: | Educational Computing Network |

References: | 99-04-011 |

Keywords: | parse |

X-MimeOLE: | Produced By Microsoft MimeOLE V4.72.3110.3 |

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).*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.