I'm creating the structure of a parse tree
and am currently ambivalent as to whether
N nodes should be allowed for the number
of children or whether it should increase
dynamically. What are some thoughts
on this? Restriction or no restriction?

--
j0mbolar

j0mbolar wrote:
> I'm creating the structure of a parse tree
> and am currently ambivalent as to whether
> N nodes should be allowed for the number
> of children or whether it should increase
> dynamically. What are some thoughts
> on this? Restriction or no restriction?
>
> --
> j0mbolar

No restriction. A restriction is trouble waiting to happen.

Furthermore, all you need is TWO nodes. Any time a nonterminal has more
than two grammar symbols on its right hand side in a production, create
a "special" parent node for gs 2 and 3 and make this the child of the
starter node.

a := b c d

would become the tree structure (as an outline)

1.  a
1.1 b
1.2 special
1.2.1 c
1.2.2 d

Edward G. Nilges, author of Build Your Own .Net Language and Compiler,
Apress 2004.

j0mbolar wrote:
> I'm creating the structure of a parse tree
> and am currently ambivalent as to whether
> N nodes should be allowed for the number
> of children or whether it should increase
> dynamically. What are some thoughts
> on this? Restriction or no restriction?

You don't need to make it very complicated as Ed mentioned.

You can implement everything using pairs if you like, just a left and
right value.  If more than two values are needed, you just put a pair
in the right value.  You just need to come up with a type for the
elements of the pair that can hold a token or another pair.  This way
there need be no restriction.

There are other ways to do it.

Rob Thorpe wrote:
> j0mbolar wrote:
> 
>> I'm creating the structure of a parse tree
>> and am currently ambivalent as to whether
>> N nodes should be allowed for the number
>> of children or whether it should increase
>> dynamically. What are some thoughts
>> on this? Restriction or no restriction?
> 
> You don't need to make it very complicated as Ed mentioned.
> 
> You can implement everything using pairs if you like, just a left
> and right value.  If more than two values are needed, you just put
> a pair in the right value.  You just need to come up with a type
> for the elements of the pair that can hold a token or another pair. 
> This way there need be no restriction.
> 
> There are other ways to do it.

EeYup.  All you need is a car and a cdr.

-- 
"The power of the Executive to cast a man into prison without
 formulating any charge known to the law, and particularly to
 deny him the judgement of his peers, is in the highest degree
 odious and is the foundation of all totalitarian government
 whether Nazi or Communist." -- W. Churchill, Nov 21, 1943

CBFalconer wrote:
> Rob Thorpe wrote:
> > j0mbolar wrote:
> >
> >> I'm creating the structure of a parse tree
> >> and am currently ambivalent as to whether
> >> N nodes should be allowed for the number
> >> of children or whether it should increase
> >> dynamically. What are some thoughts
> >> on this? Restriction or no restriction?
> >
> > You don't need to make it very complicated as Ed mentioned.
> >
> > You can implement everything using pairs if you like, just a left
> > and right value.  If more than two values are needed, you just put
> > a pair in the right value.  You just need to come up with a type
> > for the elements of the pair that can hold a token or another pair.
> > This way there need be no restriction.
> >
> > There are other ways to do it.
>
> EeYup.  All you need is a car and a cdr.

Gimme a car, a pack of Camels, and a bottle of Jack Daniel's and you
have a compiler.

Chap here is using Lisp terminology for the left and right branch in a
binary tree too which all n-ary trees may be reduced. The terminology
is based on registers found in, I believe, the old IBM 709 mainframe
where John McCarthy of Stanford implemented Lisp the first time.

You don't even need an explicit tree. See my <shamelessPlug> book,
Build Your Own .Net Language and Compiler Apress 2004 (I wanted to call
it Build Your Own Goddamn .Net Language and Compiler but Apress
wouldn't let me) </shamelessPlug>.

Here, the implicit "parse tree" is not a data structure but simply the
path of actions taken by a recursive descent parser which emits code
for a fantasy machine.

Computer science classes sometimes convince the tyro that he "must"
create a Data Structure of great pomp with the result that more cycles
are spent in the care and feeding of the Data Structure than in getting
work done. The nifty thing about computers is they don't care.

Of course, had I wanted to do more with the parse, a parse tree would
have been required (I had a parse tree in an early version of the
compiler). But in an OO language it should NOT be a data structure, it
should be an object.

Furthermore, it should not be thought of, IMO, as a tree at all.
Instead, it should be a "node" with properties that lead to other
nodes. In philosophical terms it should be a Leibnizian monad which
mirrors the world: Weltspiegelnde.

I discovered it was death to "factor" the Tree as a Node "collection".
A Tree, I found, is a Node because a Node's mission in life is to have
children and to honor, in a Confucian sense, its ancestors. OK, a Tree
is a Node with no ancestors, like the Yellow or Huang emperor of myth.

I'm not smoking anything. Just as Confucius (Kong Fu Zu) reduced a
man's life to the Rites, merely honoring his parents and taking care of
his children, this took care of all-under-heaven, including the
ancestors because Confucius saw that it is meaningless to honor the
ancestors (by burning joss in graveyards) if you go home and beat up
the old man and the old lady. He seems to have seen that the RECURSIVE
structure of family relations means that atomic household decency takes
care, recursively, of what was for him the hierarchy of family and the
nation.

Hmm, contrast this to socialist planning which in fact may have in
China and Russia used large and unwieldly computer models. I think old
Deng realized that he only had to say to heads of families "to get rich
is glorious" to start a recursive procedure. Of course, the results
(environmental pollution, pitched battles in Guangzhou between peasants
and police, a corrupt Party and a trashed environment) are by no means
perfect.

The paradox is that once the false legends of programming depart, such
as the need to always create clap trap in the form of data structures,
real mythos returns to code.
>
> --
> "The power of the Executive to cast a man into prison without
>  formulating any charge known to the law, and particularly to
>  deny him the judgement of his peers, is in the highest degree
>  odious and is the foundation of all totalitarian government
>  whether Nazi or Communist." -- W. Churchill, Nov 21, 1943