Only answer if you know this, otherwise you will get a downvote. No Spamming please!! In C,
Question:
Only answer if you know this, otherwise you will get a downvote. No Spamming please!!
In C, C++ or Python:Implement the recursive-descend parser for the language no of 1s = no of 0s. The grammar for this language is provided below. Prepare a framework of tests demonstrating that your code works properly. The code you submit should include your tests. You can use and change the recursive descend parser code for balanced parenthesis given below.
Grammar:
recursive descend parser code for balanced paranthesis:
(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.