Exercises for the Compiler Design Course

  1. What is the Chomsky hierarchy of languages ? Why do we use Regular Expressions instead of Context Free Grammars to describe tokens ? 4

  2. (a) What are some advantages of high level languages over assembly languages? Why is translation to machine language from HLL more complicated than from assembly language?     3 + 3
    (b) What are the advantages of assembly languages over high level languages?     3

  3. (a) What are the major stages in the process of compilation?     5
    (b) What do you understand by cross-compilation?     3

  4. Suppose in a programming language the word if is reserved keyword, and all other strings of alphabetic characters are identifiers. Draw a transition diagram for recognising these two classes of words. Represent the transition diagram in the form of a transition table.     3 + 4

  5. What is "flex"?     3

  6. What is lex (or flex) used for ? Write the regular expression that describes a word that has a sequence of hexadecimal digits followed by a dot and then another sequence of hexadecimal digits. The word may optionally have a hyphen as a prefix. Give two examples of such words.     2 + 2 + 1

  7. What does parsing mean in the context of compilers?   3

  8. Write context free grammar for a single statement for defining simple scalar variables (not arrays, structures, or unions) in C language. What are the tokens that may be returned by the lexical analyser during analysis of such a statement?     3 + 2
  9. Describe the syntax for a variable definition statement in C language for simple scalar variables using Context Free Grammar. Give the rightmost derivation sequence for the statement -     4 + 2
    short a, count, *p;

  10. (a) Using a simple example show that a regular grammar can be represented as a context free grammar.     5
    (b) Write the leftmost and rightmost derivations, and draw the parse-tree for the string -     6
    id id + id * id ^

    with the grammar

    E -> E T + | T
    T -> T F * | F
    F -> F P ^ | P
    P -> E | id

  11. Describe the syntax for a variable definition statement in C language for simple scalar variables using Context Free Grammar. Give the rightmost derivation sequence for the statement-     4 + 2
    short a, count, *p;
  12. What do you understand by ambiguity of a grammar?     2
  13. (a) Using a small example briefly explain ambiguous grammar. If the ambiguity is removed by rewriting the grammar, will the unambiguous grammar recognise exactly the same language as the ambiguous grammar?     3 + 2
    (b) What is the significance of left-most or right-most derivations while using an unambiguous grammar?     2

  14. What is operator precedence parsing? Give an example of a grammar that is unambiguous but not an operator precedence grammar.   3 + 2

  15. (a) What are the different precedence relations used in operator precedence parsing? Draw the operator precedence table for the following grammar-     2 + 4
    E -> E * T | T
    T -> T + F | F
    F -> (E) | id
    (b) What do you understand by left-recursion and left-factoring? How are they relevant in top-down parsing?     3 + 3

  16. (a) Construct the operator precedence parsing table for parsing simple arithmetic expressions involving addition, subtraction, multiplication, division and exponentiation assuming the usual precedence and associativity of the operators. [Use ^ as the operator for exponentiation.] Briefly explain each of the important steps in the process.     4 + 2
    (b) Depict the parsing action (stack content, remaining input) sequence of the above parser for the input string -     5
    20 + 30 * 6 ^ 5
  17. How does left recurssion create problem in top down parsing. Explain with a small example. How would you eliminate left recurssion in the grammar -      S -> S,i | i     ?     4 + 3

  18. (a) Briefly describe the algorithm of predictive parsing ? How is the use of stack in top-down different from that in bottom-up parsing ?     5 + 3
    (b) Briefly describe the method of recursive descent parsing.     5

  19. Consider the following grammar where E is the start symbol:
    E -> TE'
    E' -> +E | Ø
    T -> FT'
    T' -> T | Ø
    F -> PF'
    F' -> *F' | Ø
    P -> (E) | a | Ø

    ( Ø means the empty string )
    (a) Compute FIRST and FOLLOW for each non-terminal of the above grammar.     4
    (b) Construct the predictive parsing table for the grammar.     4
    (c) Is the grammar LL(1)? Why?     2

  20. Consider the following grammar G where E is the start symbol-
    E    ->    E + T   |   T
    T    ->    T * F   |   F
    F    ->    ( E )   |   id
    (a) Is G un-ambiguous? Why?     1 + 2
    (b) Why is G not suitable for recurssive descent parsing? Rewrite G as G' to make it suitable.     1 + 2
    (c) Compute FIRST and FOLLOW for each non-terminal of G'.     4
    (d) Construct the predictive parsing table for the grammar G'.     3
    (e) Why or why not is the grammar G' LL(1)?     2

  21. Construct the sets of LR(0) and the SLR parsing table for the grammar     4 + 5
    F    ->    id ( P );
    P    ->    P & id | id
  22. Write the C program statement to define the data structures for storing a grammar given in BNF, and to represent LR(0) items.     4

  23. Consider the following grammar where S is the start symbol:
    S -> ictSeS | ictS | a
    (a) Compute FOLLOW for each non-terminal of the above grammar.     3
    (b) Construct the canonical collection of LR(0) items for the grammar.     4
    (c) Is the grammar SLR(1)? Why?     2

  24. What are shift-reduce and reduce-reduce conflicts? 4

  25. (a) Construct the set of LR(0) items for the grammar given below and construct the SLR parsing table for it. Is the grammar LR(0) ?     8 + 2
    T -> B | { L }
    L -> T L | B
    B -> a | b
    (b) Depict the parsing action (stack content, remaining input, action) sequence of the above parser for the input string -     3
    { a { b a } }
  26. Consider the grammar-
    S -> i c t { S } e S | i c t S | a = a P a
    P -> + | *
    (a) List all the LR(0) item sets for the grammar.     4
    (b) Construct the SLR(1) parsing table.     5
    (c) Is the grammar SLR(1)? Is the grammar unambiguous?     3

  27. (a) How is canonical LR parsing different from LALR parsing?     3
    (b) What is yacc?     2

  28. How is canonical LR parsing method different from SLR parsing? What would you say about their respective language recognition power?     3 + 2

  29. What does the UNIX utility YACC do ? What is the essential part (that must be present) in the input to YACC?     3 + 2

  30. What do you understand by ambiguity of a grammar?     2

  31. Why is it sometimes useful to use an ambiguous grammar for parsing instead of a rewriting the grammar to remove ambiguity? How is it possible to ambiguous grammar for parsing?     3 + 2

  32. What is the difference between error detection and error recovery? Describe a simple method for error recovery for syntax errors.     3 + 4

  33. What are some of the errors that a compiler should detect? What course of action should the compiler take when it detects an error?     3 + 3

  34. Which of the following expressions have l-values? Which have r-values:
    1. A[I+1]
    2. *A
    3. &A
    4. &(*A)
    5. *(&A)

  35. (a) Present a suitable format for Intermediate Code that may be generated by a compiler. Using that format express the following source code segment in the intermediate code form -     3 + 3
    x = a + 30 * 6;
    y = square( x );
    (b) Briefly describe the different types of storage requirements of a program and how a compiler may handle each of these requirements.     3 + 4

  36. Write the outline of the semantic actions for translation that may be associated with the production for the common if-construct -
    S -> iCtSeS 4 + 2
    Why may we rewrite the production to incorporate the semantic actions?

  37. What is syntax directed translation?     3

  38. (a) Consider the following grammar for arithmatic expressions-
    E -> E + T | T
    T -> T * F | F
    F -> (E) | id
    Write the semantic actions for a syntax-directed translation scheme for converting input expressions into intermediate code in three-address code notation.     8
    (b) Using a simple example, show the need for back patching during intermediate code generation by syntax directed translation.     5

  39. (a) What does a compiler do to facilitate linking?     3
    (b) Why do programming languages provide the macro feature despite the procedure call mechanism ? What do you understand by conditional expansion during macro processing?    4 + 2

  40. Why is a symbol table used by a compiler ? Give a possible format of a symbol table record used by a compiler and state why you would use either an array, a hash table, or any other data structure to keep these records.     5

  41. Describe a scheme to create a symbol table for processing programs in a block-structured language in multiple passes.     5

  42. In a block-structured language, when there are multiple symbols with the same string, how can hashing be used to locate the appropriate symbol table record for a particular symbol? Describe using block diagram.     5

  43. (a) What is an activation record and why is it used ? Why are activation records maintained in a stack ?     4 + 2
    (b) What does an activation record contain? What kind of program data is allocated in an activation record? Why is indirection used for some data objects in the activation record?     2 + 2 + 2

  44. Why is code optimization done by compilers but not by assemblers ?     4

  45. What are some of the optimisations that can be performed by a compiler ? Which kind of optimisation is more effective inside loops - space optimisation or time optimisation ? Why ?     5 + 2

  46. (a) What are basic blocks and flow graphs? Identify the basic blocks and draw the flow graph for the following three-address code segment-     2 + 3 + 2
    (1) PROD = 0
    (2) I = 1
    (3) T1 = 04 * I
    (4) T2 = addr(A) - 4
    (5) T3 = T2[T1]
    (6) T4 = addr(B) - 4
    (7) T5 = T4[T1]
    (8) T6 = T3 * T5
    (9) PROD = PROD + T6
    (10) I = I + 1
    (11) if I <= 20 goto (3)

    (b) What is a Directed Acyclic Graph and what are its uses?     2 + 2

  47. (a) What do the register descriptor contain? How are these useful in code generation?     2 + 2
    (b) Give an example to show how reordering of intermediate code statements can improve code generation.     3