CS 75 Project 2a: LL(1) Grammar for C--

Convert the context-free C-- grammar into an LL(1) grammar that will be suitable for use in a recursive descent parser. To do this you will need to:

• Eliminate ambiguity by encoding operator precedence
• Eliminate left recursion
• Factor out similarity to enable the use of only one token of lookahead

Run update75 to get the file cs75/projects/2a/LL1grammar. Put your converted grammar into this file.

• Does a C-- program have to have at least one function declaration? Yes.

• Does a block in a C-- program have to have at least one statement? Yes.

• Does an if statement in a C-- program have to have an else? Yes. However, if you don't need to do any computation in the else, you can simply put a semicolon.

• Can an if statement in a C-- program contain multiple statements within the then and else? Yes, because according to the C-- grammar, the then and else bodies are statements, and a statement can go to a block.

• In C--, can you combine a variable declaration with an assignment? No. It is not valid to do: int c = 4;.

• According to the C-- grammar, it is legal to write: !5 || 1. What does this evaluate to? In C-- (and C), the integer 0 is considered to be false, and any other value is considered to be true. When an expression evaluates to true it generally returns 1. So this would evaluate to 1.

• The terminals of the LL(1) grammar should be the tokens generated by your lexical analyzer.

• The precedence of C-- operators from lowest to highest is:
  • assignment (=)
  • or (||)
  • and (&&)
  • equal, not equal (==, !=)
  • less than, less than or equal, greater than, greater than or equal (<, <=,>, >=)
  • addition, subtraction (+, -)
  • multiplication, division (*, /)
  • not, unary minus (!, -)
  • parentheses ()

• There is one portion of the C-- grammar that is difficult to convert into an LL(1) format and it occurs in some expressions involving the assignment operator. The difficulty is in determining if the expression on the left side of an assignment is a valid lvalue (or storage location) at parse time.
  
  For example, these are all valid C-- expressions:

  • a[i];            // a[i] is not an lvalue here

  • a[i] = x;        // a[i] is an lvalue here

  • x = 8 + (y = 6); // y is an lvalue and (y=6) returns the value 6

  These are invalid C-- expressions:

  • a[i] + b[i] = x; // a[i]+b[i] is not a valid lvalue 

  • x = 8 + y = 6;   // 8+y is not a valid lvalue, but + has higher precedence than =

  Correctly handling these cases is hard, but very easy to do in the next phase of the compiler. Therefore it is OK if your LL(1) grammar incorrectly accepts strings like:

  a[i] + b[i] =
  8;

  Later you can ensure that any expression appearing on the left side of an assignment expression is a valid lvalue.

• You should test your LL(1) grammar by hand to verify that its rules can correctly parse some very small C-- programs. For example, try some programs with zero, one, or two global variable declarations, and one or two small functions:

  int x;
  char y;
  
  int double(int value) {
    return value*2;
  }
  
  int main() {
     int z; 
  
     read x;
     z = double(x);
     write z;
  }
  

  Be sure that you have not altered the productions in such a way as to change the language that is recognized.

• I encourage you to compute the FIRST and FOLLOW sets of your converted grammar. Using these you can verify that your gammar is indeed LL(1) based on the rules given at the bottom of page 223 in the text book (with explanation that continues on page 224).

Home Page