CS5031 - Jan 98 - Pete Jinks - Section A Answer each section in a separate book. Answer 3 questions. 1. a) The following Yacc-like grammar describes a boolean expression (exp) consisting of operators "&", "|", "!", brackets "(" and ")", constants 'true' and 'false', and identifiers. exp : or_part | exp '|' or_part ; or_part : and_part | or_part '&' and_part ; and_part : not_part | '!' not_part ; not_part : identifier | 'true' | 'false' | '(' exp ')' ; Show how the expression a | b | ! c & d & ( ! e | f ) would be recognised by this grammar by giving the complete parse tree for it, including all intermediate nodes. You should assume that there is a lexical analyser recognising the identifiers (a, b, c, d, e, and f) and operators and discarding spaces etc. [4 marks] b) Construct one or more grammar rules that recognise a series of expressions, as described in part (a), separated by semicolons ";". [2 marks] c) Write Lex and Yacc code to recognise an expression as described in part (a). Identifiers are as defined in C. Any white space (space, tab or newline) separates tokens and should otherwise be ignored. You should report any unexpected characters as errors. You should not try to evaluate or translate the expressions. You do not need to give code for common routines such as yywrap, yyerror and main. [8 marks] d) Modify your Lex and Yacc code to build parse trees. Remember to give any %union etc. declarations necessary in your Yacc code, as well as modifying the actions in both your Lex and Yacc code. You may assume the existance of any suitable C functions, but you must describe what such functions do. [6 marks] 2. The phases of a typical compiler are lexical, syntactic and semantic analysis, and code generation and optimisation. Explain in detail how the following fragment of ANSI C code is processed in each phase. You should include a description of any intermediate forms or other data structures it may be transformed into, such as lexemes, parse trees and the dictionary. [15 marks] Give the equivalent ARM or MIPS code for the following fragment of ANSI C code, but as if every use of 'float' had been replace by 'int' i.e. only using integer operations. [5 marks] enum {a=1, b=2, c=3}; float f (int a, e) { float c, d; if (a < 0) a = a + e; d = a + c; c = e - d + b; return c + b * d; } Section B = Questions 3 and 4, written by Peter Capon, about Operating Systems