Use the same assumptions about the AST and the generated code as for Question 1, including the fact that an expression's operands can be evaluated either left-to-right or right-to-left. Also assume that all operators arc non-commutative and non-associative (i.e., the expression a op b is not equivalent to the expression b op a, and the expression (a op b) op c is not equivalent to the expression a op (b op c)). You are to give a recursive algorithm that works as follows: The input to the algorithm is an expression node in the AST (recall from Question 1 that we are assuming that we only have expressions involving non short-circuited binary operators). The output of the algorithm is the number of registers required to generated code for the whole expression. Note that generating code to evaluate a leaf node requires one register (into which the value of the identifier or literal is loaded).For non-leaf nodes, your algorithm should recursively calculate the number of registers required to generate code for the left operand (leaving the value in a register) and the number of registers required to generate code for the right operand (leaving the value in a register) and then determine the number of registers required for the entire expression represented by the node. In other words, complete the following method: For example, for the expression a - b, the input to the algorithm is the squareroot node of the expression tree. The algorithm will recursively determine that the number of registers required to generate code for each operand is 1 (because each operand is a leaf and thus requires one register). The output of the algorithm for this example should be 2 (because the whole expression can be evaluated using two registers, as illustrated above in Part 1. but it cannot be evaluated using just one register). Use the same assumptions about the AST and the generated code as for Question 1, including the fact that an expression's operands can be evaluated either left-to-right or right-to-left. Also assume that all operators arc non-commutative and non-associative (i.e., the expression a op b is not equivalent to the expression b op a, and the expression (a op b) op c is not equivalent to the expression a op (b op c)). You are to give a recursive algorithm that works as follows: The input to the algorithm is an expression node in the AST (recall from Question 1 that we are assuming that we only have expressions involving non short-circuited binary operators). The output of the algorithm is the number of registers required to generated code for the whole expression. Note that generating code to evaluate a leaf node requires one register (into which the value of the identifier or literal is loaded).For non-leaf nodes, your algorithm should recursively calculate the number of registers required to generate code for the left operand (leaving the value in a register) and the number of registers required to generate code for the right operand (leaving the value in a register) and then determine the number of registers required for the entire expression represented by the node. In other words, complete the following method: For example, for the expression a - b, the input to the algorithm is the squareroot node of the expression tree. The algorithm will recursively determine that the number of registers required to generate code for each operand is 1 (because each operand is a leaf and thus requires one register). The output of the algorithm for this example should be 2 (because the whole expression can be evaluated using two registers, as illustrated above in Part 1. but it cannot be evaluated using just one register)
