1. This question is about lexing, parsing, and CFGS (= context free grammars). (a) For each of the following statements about ASTS (= abstract syntax trees), state whether they are true or false. Correct answers are awarded 2 marks; wrong answers are penalised by 1 mark (to a minimum of O marks for this question). Omitted answers do not contribute positively or negatively to your grade. [14 marks] i. The lexer takes as input a list of tokens, representing a program. ii. The lexer produces an AST from the list of tokens. iii. The token list is produced in the semantic analysis stage. iv. The purpose of the lexing phase is to make it easier to adapt a compiler to new machine architectures (such as moving from Intel to ARM processors). v. The purpose of constructing an AST is to represent the structure of the computer program, to simplify code generation. vi. The purpose of constructing an AST is to allow the compiler to generate faster executable machine code. vii. Dynamically typed languages like Python and Javascript don't need to do lexing and parsing. (b) In this question, we consider CFGs in which we takes to be the initial variable. For each of the following statements, state whether they are true or false. Correct answers are awarded 4 marks; wrong answers are penalised by 1 mark (to a minimum of O marks for this question). Omitted answers do not contribute positively or negatively to your grade. [16 marks! 1. The CFG over the alphabet (0.6.=. +. 1.:) with reductions S + A:SA +2=EA +6=EE+E+E1E+V+V True or talse: the language of this CFG is infinite (meaning: contains infinitely many strings). . The CFG over the alphabet (.)) with reductions $+(5) 5+(55) S-0 True or false: the language of this CFG is precisely the set of non-empty strings over {} with balanced brackets, including e.g. 0.001.00))... ill. The CFG over the alphabet (.)) with reductions 5+(1) S-T(T) 5 + {T{(TXT)) $| 1-5 True or false: the language of this CFG is precisely the set of (possibly empty) strings over {(.)) with balanced brackets, including e.g. 0.0), 1000))... iv. The CFG over the alphabet (a.!} with reductions S+HSHS $ + !!!! S +6 | H+SHS True or false: the CFG is left-recursive. (c) For this question, you are to provide a formal specification of the structure of the reduction relations of a CFG, given that a CFG can itself be described using a sequence of symbols. Consider a context-free grammar G = (A.V, S, X), with alphabet A = {9,6,c), variables V- {P.Q.R.S.T), and start variables. Observe that one may specify the reduction relation x with a string of the following format: A single reduction rule has the format "var) := (string)", where (var) EV, and - (string) is either a single symbol epsilon, or a non-empty string over the set AUV. The set of all reduction rules consists either of just a single reduction rule, or a semicolon-separated list" (rule); (rule); ..." in which each (rule) is a single reduction rule. Write a formal grammar (involving alphabet symbols := epsilon',':', *: 'W.P. 9. etc.) which accepts precisely the strings with the above format, for a CFG G = (AV, S, X) as set out above. (Hint: use notation which distinguishes the rules of the CFG G, from the rules of the formal grammar which you use to describe G.) [20 marks]
