Consider the following expression BNF: ::= * | / |

[answerhappygod]

Consider the following expression BNF:
<expression> ::= <factor> *
<expression> | <factor>
/ <expression> |
<factor>
<factor> :== <term> +
<factor> | <term> - <factor>
| <term>
<term> ::= { <expression>
} | <literal>
<literal> ::= 0|1|2|3|4|5|6|7|8|9
Using recursive
descent, and only recursive
descent, scan expressions that adhere to this BNF to
build their expression tree; an integer valued function is needed
that scans the tree to evaluate the expression represented by the
tree.
Input:
Output:
Need a Python or C++ working program. The algorithm is
mentioned below:
The expression tree will have:
- Operators as internal nodes
- Operands as leaves
To build the tree, we will write functions for each non-terminal
symbol:
- A function called expression (treeType t)
- A function called factor (treeType t)
- A function called term (treeType t)
- A function called literal (treeType t)
We also have a function called gettoken() that reads the next token
in the string.
- We have a global variable variable: token
- Also, whenever a function is called from above, token contains
the first token of the string that the function is supposed to
recognize.
ALGORITHM:
function expression (treeType t)
{ //<expression> ::= <factor> *
<expression> | <factor> /
<expression> | <factor>
treeType factorTree;
factor(factorTree); // factor will return in factorTree the
expression tree for the first factor
if (token=="*")
{ //<expression> ::= <factor>
* <expression>
treeType expTree;
gettoken(token);
expression(expTree);
t.data = "*";
t.left = factorTree;
t.right=expTree;
}
else if (token=="/")
{ //<expression> ::= <factor>
/ <expression>
treeType expTree;
gettoken(token);
expression(expTree);
t.data = "/";
t.left = factorTree;
t.right=expTree;
}
else
{ //<expression> ::=
<factor>
t = factorTree;
}

}
function factor (treeType t)
{ //<factor> :== <term> + <factor>
| <term> - <factor> |
<term>
treeType termTree;
term(termTree); // term will return in termTree the expression tree
for the first term
if (token=="+")
{ //<factor> ::= <term> +
<factor>
treeType factorTree;
gettoken(token);
factor(factorTree);
t.data = "+";
t.left = termTree;
t.right= factorTree;
}
else if (token=="-")
{ //<factor> ::= <term> -
<factor>
treeType factorTree;
gettoken(token);
factor(factorTree);
t.data = "-";
t.left = termTree;
t.right= factorTree;
}
else
{ //<factor> ::= <term>

t = termTree;
}

}
function term (treeType t)
{ //<term> ::= ( <expression> )
| <literal>
if (token=="(")
{ //<term> ::= ( <expression>
)

treeType expTree;
gettoken(token);
expression(expTree);
gettoken(token); // to get rid of the ')'
t = expTree;
}
else
{ // <term> ::= <literal>
literal(t);
}
}
function literal (treeType t)
{
t.data = token;
t.left = none;
t.right = none;
}