Design Patterns discussion

["Robert Allan Schwartz" <notbob AT tessellation.com>]

> 2) The Related Patterns section of the Builder (p. 106) says that a
> Composite is what the builder often builds. Fine enough for "simple"
> composites (where parts are simply appended to the composite, as in the
> RTF example given in the book).
> But I do not quite see how a builder can build a tree structure such as
> parse trees, which are built bottom-up. The description given in the
> book (Implementation section, p. 101) of how this is achieved doesn't
> help me much:
>
> "[...] the builder would return child nodes to the director, which then
> would pass them back to the builder to build the parent nodes".

Suppose you have the following grammar:

sentence ::= noun_phrase verb_phrase ".";

noun_phrase ::= article noun;

article ::= "a" | "an" | "the";

noun ::= "boy" | "ball";

verb_phrase ::= verb noun_phrase;

verb ::= "threw";

The Builder's Director would "parse" the sentence "the boy threw the ball."
as follows:

"the" ==> parse_article("the") { push "the" on the stack; }

"boy" ==> parse_noun("boy") { push "boy" on the stack; }

==> parse_noun_phrase() { pop 2 objects off the stack; use those values to
initialize and push a "noun_phrase" object on the stack; }

"threw" ==> parse_verb("threw") { push "threw" on the stack; }

"the" ==> parse_article("the") { push "the" on the stack; }

"ball" ==> parse_noun("ball") { push "ball" on the stack; }

==> parse_noun_phrase() { pop 2 objects off the stack; use those values to
initialize and push a "noun_phrase" object on the stack; }

==> parse_verb_phrase() { pop 2 objects off the stack; use those values to
initialize and push a "verb_phrase" object on the stack; }

"." ==> parse_sentence() { pop 2 objects off the stack; use those values to
initialize and push a "sentence" object on the stack; }

The parse_XXX() methods are sent by the Director to the Builder. The Builder
maintains the stack. The Director eventually calls get_result() from the
Builder, to pop the "sentence" object, leaving the stack empty.

Does that help?

Robert