(1) Compiler operates in various phases each phase transforms the source program from one representation to another. Every phase takes inputs from its previous stage and feeds its output to the next phase of the compiler. Now construct different compilation phases for the following expression: sum = (a + b) / c d - b * 10 Note: Here replace character with power (^) if your Student ID is odd, or replace character with minus (-) if your Student ID is even

2. (a) The KMP algorithm preprocess the pattern P by computing a failure function f that indicates the largest possible shift s using previously performed comparisons. Specifically, the failure function f(j) is defined as the length of the longest prefix of P that is a suffix of P[i . . j]. Here the Palindrome strings are defined as follows: Sk = Sk-2Sk-1 Sk-1Sk-2 where k > 2 Consider that the base values S1 and S2 are the last two digits of your Students ID respectively. For example, if your student ID is 19202103327, then S1 = 2 and S2 = 7. Now construct the failure function for S3 and S4

(b) Describe the context free grammar and ambiguity. Design a context free grammar for the string (id+id)*id which will be ambiguous for the given string and hence show by left most and right most derivation that both gives the same result. After then remove its ambiguity. (3)

(a) In recursive descent parsing, the parser may have more than one production to choose from for a single instance of input, whereas in predictive parser (no backtracking), each step has at most one production to choose. Now consider the following grammar: S E E T | E + T T F | T * F | x | y F 2 | 3 Show the simulation of Recursive Descent Parsing using the above grammar for the input string: x + y * 3.

(b) Consider the following CFG (Context Free Grammar) X X+Y | Y Y Y * Z | Z Z ( X ) | k | Show panic mode error recovery made by non-recursive predictive parser using the above grammar for the input string: )k*+k