Compiler Design

Relevant Course: Compiler Design

Relevant Department: Computer Science and Engineering

Relevant Semester: Semester 5 or 6 in 8 semester program 

Pre- requisite : Programming Languages,Data Structure and Algorithms,Computer Architecture & Discrete Structure or Theory of computation

 Course Description and Outline

1. Grammars for Programming Language constructs : sample grammars for following lingistic constructs found in languages such as C, C , Java :

  • Declaration processing – scalar data types; derived data types arrays, pointers, functions, class
  • Assignment; expressions involving common operators on integers, chars, strings, floats; complex     expressions involving other operators (unary, bits, logical, etc)
  • Control statements : if-then-else, switch, loops, break, continue, function calls, etc.
  • Function definitions

2. Basics of LR Parsers :

  • Principles of Bottom-up parsing, context free grammar, rightmost derivation and parse trees
  • Structure of a LR parser : parsing table, stack, driver routine; FIRST and FOLLOW  information
  • Illustration of working of a manually constructed LR parser
  • LR(0) item, states of an LR() automaton, relation between and LR automaton and parsing table
  • key concepts of viable prefixes and valid items, conflicts in LR parser : shift-reduce and reduce-       reduce

3. LALR(1) Parser construction

  • LALR(1) items, lookaheads attached, split of SLR(1) states based on lookahead,
  • Properties of LALR(1) parser : size advantage of SLR; as powerful as canonical LR(1) with respect to shift-reduce conflicts; wit respect to reduce-reduce conflicts - less powerful than LR(1) but better   than SLR(1); proof outlines only
  • Manual construction of a few LALR(1) parsers for small grammars

4. Using YACC for generating Parsers

  • YACC syntax for writing CFGs – purpose of the different sections; skip LEX hence hardcoded tokens only
  • Generating a parser using YACC : how to read the important generated files – y.output;y.tab.c;         y.tab.h
  • Correlate the LALR(1) automaton with the concepts learned; interpret the conflicts, if any.
  • Use the generated parser to parse sample inputs.
  • Using the debugging option to show the parser working in ints entire glory.

5. Tutorial on the problem solving aspects including writing grammars, constructing few states of a parser, FIRST and FOLLOW sets, given a state write viable prefixes corresponding to it, given a viable prefix write all the items of the associated state.

6. Experiments on YACC as detailed in Item 4 above.

  

Schedule for Lecture Delivery

Session 1 : 13-Oct-2015  (2-4 PM)

Session 2 : 15-Oct-2015  (2-4 PM)

Session 3 :19-Oct-2015  (2-4 PM)

Teacher Forum

Slides For Session 1

Video - 1

Video - 2

Video - 3 

Video - 4

Forum for Session 1

Forum for Session 1

Forum not available

Quiz - I

Quiz - I 

Quiz not avilable

Assignment

The problems given in this document are targeted to students for testing  their understanding of the concepts and skills learned during the lectures on this session. The following points may be considered while  using  this document.

  • While a few problems may be solved as part of  the lecture sessions under the supervision of the instructor, by and large these problems are designed as take home assignments. 
  • The operators in C with their attributes, given in the following table, are referred to in various problems of this document. 
  • While the tutorial problems refer to C / C language features, a student may replace it by any other programming language in which s/he is more comfortable.  

P1.  This problem is to encourage  you to make your own observations about the compiler that you frequently use. You may write programs with errors introduced on the same lines as has been used in the first few slides of session 1. Write a program in a programming language of your choice for which a compiler is available. Introduce one or two errors in the program. Compile the program and examine the errors reported. Justify each error reported by the compiler.  Identify from the list of errors, all the parsing errors justifying why you think such errors were detected by the  parser. 

 P2. Consider the following context free grammar with start symbol with {S, X, M} as nonterminals, S as the start symbol, terminals {a, b, c, d} and the productions given below.

(a) Construct FIRST( ) and FOLLOW () sets for all nonterminals. 

(b) For the sentence, b b b d c a a, construct a rightmost derivation and a parse tree. 

(c) For the sentence, b b b d c a a, construct a leftmost derivation and a parse tree. 

P3. Write a grammar that can generate a single declaration statement of a built-in type of C/C , for example, short, int, char, long , long long, for both signed and unsigned forms. Sample example sentences are given below for your reference.

 

(a) Using your grammar, draw a parse tree for the sentence :        signed long long n1, n2, n3, n4, n5;

 (b) Construct a rightmost derivation for the sentence given in part (a) above. 

P4. Write a grammar that can generate one or more  declaration statements of a built-in type of C/C , as given in P3 above. Also add the types, float, double, long double to the set of types. Sample example sentences are given below for your reference.

Your grammar should be able to generate  the following set of declarations.

              float x;

             unsigned int num1, num2, num3;

             signed long long n1, n2, n3, n4, n5;

             long double d1, d2;

 Using your grammar, draw a parse tree for the set of declarations given above.

 P5.  Compile the following program, given in column1, observe the errors and answer the questions given.

P6. Write a grammar that can generate a single declaration statement with or without initialization. An example of a declaration of both kinds are given below.

 Uninitialized declaration :  int a ;

 Initialized declaration (also called as definition) :  int a = 564;

 Similar to P3, your grammar should handle declarations of built-in types of C/C , for example, short, int, char, long , long long, for both signed and unsigned forms.           

(a)  Consider the sentence given below. Construct a parse tree for this sentence using your grammar.

                  signed  short  s1, s2 = 1024, , s3 = 32, s4, s5;

 (b) Construct a rightmost derivation for the sentence given in part (a) above.

 P7. Write a grammar that can generate a single declaration statement for scalars and arrays for built-in types of C/C .  Provide for declaration of single to multi-dimensional arrays.  Sample examples of such declarations are given below. Note that arrays are declared only and not initialized, but scalars may or may not be initialized.

 Consider the following string that is expected to be generated through your grammar.

 Construct a parse tree for the sentence using your grammar.

             int a[100], b[10, 20], c[2], num1 = 0, d[5, 10, 5, 10, 10], num2 ;

 P8. Do Problem 7  but now using the array declaration syntax used in languages such as C / C .

 Consider the following string that is expected to be generated through your grammar.

 Construct a parse tree for the sentence using your grammar.

             int a[100], b[10][20], c[2], num1 = 0, d[5][10][5][10][10], num2 ;

 P9.  Construct a parse tree for the following expression in C/C language :

  

 (a) Given that a has the value 5 initially, use your parse tree to determine the value of a after evaluation of the expression. Show the value at each node of the parse tree.

 (b) Write a program to compute the value of the assignment to a given in this question. Verify that your parse tree AND/OR evaluation is correct of the expression is correct with respect to the value(s) produced by the program.

P10. Write an unambiguous expression grammar for the following operators from C {=, =, *=, /=, | |, &&, binary , binary -} and operands as tokens num and id.

(a) Construct FIRST and FOLLOW sets for your grammar.

(b) Parse the sentence given in P9 using your grammar.

P11. Consider the set of  operators of C {=, =, ||,  &&, ==, !=, <, <=, >, >=, binary } and operand set = {num , id }.

(a) Write an unambiguous expression grammar for the operator and operand set  as given in this problem.

(b) For the string given below,

            a = b = a < 5 || a b  >= 16  && a == b != a 2 != b a

construct a  parse tree  using your grammar.

 (c) Assume initial values of a and b as 5 and -2 respectively.  Evaluate the expression using the parse tree of part (b) and show the value at each node of the parse tree. Write a program and verify that your parse tree AND/OR evaluation is correct.

P12. Consider the set of  operators {=, | |,  &&, ==, !=, binary , binary –,  *, /, %, unary -} and operand set as {num, id }. The * is the multiplicative operator.

 (a) Write an unambiguous expression grammar for the operator and operand set  as given in this problem.

 (b) Construct an expression that uses all the operators and operands at least once and is syntactically valid.  Create a parse tree for your expression using your grammar.

 (c) Assume initial values for all identifiers used in your expression of part (b). Evaluate the expression using these initial values and the parse tree of part (b) and show the value at each node of the parse tree. Write a program and verify that your parse tree AND/OR evaluation is correct.

P13. Consider the set of  operators {=, | |,  &&, ==, !=, <<, >>, bitwise and &, bitwise xor ^, bitwise or |, bitwise not ~, logical not !} and operand set as {num ,id }.  

 (a) Write an unambiguous expression grammar for the operator and operand set  as given in this problem.

 (b) Construct an expression that uses all the operators and operands at least once and is syntactically valid.  Create a parse tree for your expression using your grammar.

 (c) Assume initial values for all identifiers used in your expression of part (b). Evaluate the expression using these initial values and the parse tree of part (b) and show the value at each node of the parse tree. Write a program and verify that your parse tree AND/OR evaluation is correct.

P14. Consider the set of  operators {=, ,- -, dereference *, address of &,  ==, !=, binary , binary -, multiplicative *, multiplicative /} and operand set = {num ,id }.  

 Do parts(a), (b) and (c) as given in P13 for this operator and operand combination.

 P15. Consider the set of  operators {=, , - - , dereference *, address of &,  ==, !=, binary , multiplicative *, array reference [ ] and ternary ? : } and operand set = {num ,id }.  

 Do parts(a), (b) and (c) as given in P13 for this operator and operand combination.

 P16. Consider the following context free grammar G1 with 6 terminals {id   ,   (   )  ;  num }. The nonterminals are {S, P, A, T} and G1 has 5 production rules as given below.

      

(a)  Construct and report the FIRST() and FOLLOW() sets for all nonterminals.

 (b)  For the sentence given below construct a rightmost derivation and its corresponding  parse tree.

                        id ( id , num, id , num );

(c)  Write another grammar G2 such  that G2 is not right recursive such that L(G1) = L(G2).

(d)  Identify the  PL feature that is captured by this grammar.

P17. Consider the following CFG with start symbol E, the only non terminal, and 2 terminals {id -  } and the following 3 rules.

                           

(a) Consider the string  10 - 3 - 2 - 7. Can this string be generated from the given grammar? If the answer is YES, show a parse tree for this sentence and also find the result of this expression using this parse tree. If your answer is NO, explain the point of error with reasons.

(b) How many other valid parse trees are possible for the string of part (a) ? Evaluate all the parse trees and show the results of the expression using each tree. Justify your answer.

 P18.  Consider the following ambiguous grammar for generating nested if-then-else control structures. The grammar uses a single non terminal S and 4 terminals { if  a   c  then  else }. The terminal a denotes statements other than if then else statements.

(a) Consider the sentence: 

 

                         if  c then  if c  then   if c  then  a else a  else  if c then a

 Construct as many distinct parse trees as possible when the grammar is used to parse this sentence.

 (b) Consider another grammar for generating nested if-then-else constructs as given below. 

Construct as many possible distinct parse trees with this grammar for the same string as that of part (a).

 (c) In the grammar given in part(b), the rule for a has been attached with M. What happens if instead of this rule, the following options are used ? Comment in each case, whether the resulting grammar is correct for generating all valid nested if-then-else statements.

 

 P19. We wish to generate program fragments of the following form. The constructs involve declarations of scalars and arrays, assignment statements involving scalars and arrays. Use all the grammar writing skills developed in earlier problems to construct an unambiguous grammar for generating such sentences. The programming language is not C/C for this  question. A single data type integer may be used for this problem.

                           integer  a [10] [20];

                          integer  b [10] [20];

                          integer i; 

                          integer j;

                          i = 10; j = 16;

                          b[i][ j 2] = a [i-1] [j 1] a [i 1] [j – 2];

 

P20. Consider the following grammar given below which was meant for control structures in some programming language. The start symbol is A; the terminals are denoted in bold. The non-terminal S is for representing different statements in the language. The nont erminal C is supposed to generate a block of statements, B is for generating some  boolean expressions and E for generating arithmetic expressions. The terminal relop denotes the set of relational operators { <, <=, >, >=, ==, !=}; terminals true and false are the constants of the boolean type.

The grammar given above was supposed to parse program fragments of the form given below.

 

  if ( a < b) then

                   begin

                      a = b c;

                      while ( a <= b) do begin  a = c d end;

                      a = b

                   end

              else     begin  c = c d end  ;

 

(a) Argue whether grammar given will serve its intended purpose. In case your answer is no, report all possible problems with this grammar with justifications.

(b) Write an unambiguous grammar, equivalent in spirit to that given in this problem, so that program fragments of the desired structure are generated by it.

 

 

Assignment not available

Solutions

Page view resticted for students

Slides For Session 2

Video - 1

Video - 2

Video - 3

Video - 4

Video - 5

Forum For Session 2

Forum For Session 2

Forum not available

Quiz - II

Quiz - II

Quiz not avilable

Slides for Session 3

Video - 1

Video - 2

Video - 3

Video- 4

Video- 5

Video- 6

Forum for Session 3

Forum for Session 3

Forum not available

Quiz III

Quiz III

Quiz not avilable

Proctored Quiz

Proctored Quiz

Quiz not avilable

Table of Contents