In C++, Python or Java: Implement the recursive-descend parser of FCS section 11.6 constructing parse trees of the grammar of balanced parentheses (FCS figure 11.25; students are allowed to use directly the code of FCS section 11.6). After constructing a parse tree your algorithm should compute its height and list all labels in pre-order and post-order. Demonstrate with examples that your code operates properly.

(1) ? epsilon

(2) ? ( )

Figure 11.25

#define FAILED NULL

typedef struct NODE *TREE;

struct NODE {

char label;

TREE leftmostChild, rightSibling;

};

TREE makeNode0(char x);

TREE makeNode1(char x, TREE t);

TREE makeNode4(char x, TREE t1, TREE t2, TREE t3, TREE t4);

TREE B();

TREE parseTree; /* holds the result of the parse */

char *nextTerminal; /* current position in input string */

void main()

{

nextTerminal = "()()"; /* in practice, a string

of terminals would be read from input */

parseTree = B();

}

TREE makeNode0(char x)

{

TREE root;

root = (TREE) malloc(sizeof(struct NODE));

root->label = x;

root->leftmostChild = NULL;

root->rightSibling = NULL;

return root;

}

TREE makeNode1(char x, TREE t)

{

TREE root;

root = makeNode0(x);

root->leftmostChild = t;

return root;

}

TREE makeNode4(char x, TREE t1, TREE t2, TREE t3, TREE t4)

{

TREE root;

root = makeNode1(x, t1);

t1->rightSibling = t2;

t2->rightSibling = t3;

t3->rightSibling = t4;

return root;

}

Fig. 11.27(a). Auxiliary functions for recursive-descent parser.

620 RECURSIVE DESCRIPTION OF PATTERNS

TREE B()

{

(1) TREE firstB, secondB;

(2) if(*nextTerminal == () /* follow production 2 */ {

(3) nextTerminal++;

(4) firstB = B();

(5) if(firstB != FAILED && *nextTerminal == )) {

(6) nextTerminal++;

(7) secondB = B();

(8) if(secondB == FAILED)

(9) return FAILED;

else

(10) return makeNode4(B,

makeNode0((),

firstB,

makeNode0()),

secondB);

}

else /* first call to B failed */

(11) return FAILED;

}

else /* follow production 1 */

(12) return makeNode1(B, makeNode0(e));

}

Fig. 11.27(b). Function to construct parse trees for strings of balanced parentheses.