Use this information only for good ;  never for evil.  Do  not expose to fire .  Do  not operate heavy equipment after reading, may cause drowsiness . . .  The standard is written in English .  If you have trouble understanding a particular section, read it again and again and again . . ..  Sit up straight.  Eat your vegetables.  Do not mumble. – Pascal Standard ISO 7185:1990

A carelessly planned project takes three times longer to complete than expected; a carefully planned project takes only twice as long. – Golub’s Law

1    General Advice

You should read the description carefully. Multiple readings are recommended. Give yourself time by starting early and taking breaks between readings. You will digest the requirements better.

•  The answers to many of your questions can be found in this document.

•  Do not start coding until you have a complete understanding of the requirements. At the very least, do not start coding a task, until you have a complete understanding of the task’s requirement.

•  Ask for help early. I and the TAs can save you a lot of time if you ask for help early.  You can get help with how to approach the project to make the solution easier and have an easier time implementing it. If you spent too many hours on project 1, you should have asked for help early on. That said, when you ask for help, you should be prepared and you should have done your part.

•  Have fun!

2    Overview

In this project, you are asked to write a C++ program that reads a description of a context free grammar, then, depending on the command line argument passed to the program, performs one of the following tasks (see Section 6.3 for more details on how to run the program with command line arguments):

1. print the list of terminals followed by the list of non-terminals in lexicographic order (dictionary order),

2.  calculate FIRST sets,

3.  calculate FOLLOW sets  ,

4.  left-factor the grammar,

5. eliminate left recursion.

All of these tasks are defined in detail in this document.

We provide you with code to read the command line argument into an integer variable.  Depending on the value of the variable, your program will invoke the appropriate functionality. The rest of the document is organized as follows:

1.  Section 3 describes the input format (this is just syntax with no meaning).

2.  Section 4 describes what the input represents (this is the semantics or meaning of the input).

3.  Section 5 describes what the output of your program should be for each task.  This is the largest section of the document.

4.  Section 6 discusses command line arguments and how you should run and test your program.

5.  Section 7 describes the grading scheme.

6.  Section 8 addresses some potential submission concerns.

Important Note. For this project, there is a timeout that we enforce when testing submissions.

•  Programs that are functionally correct but that take an inordinate amount of time can be timed out before finishing execution.

•  DO NOT IMPLEMENT YOUR CALCULATIONS RECURSIVELY: Write a recursive descent parser for the grammar, but do not do the calculations of the sets recursively.  If you try to invent a new recursive algorithm for calculating FIRST and FOLLOW sets, for example, it risks being timed out, and you will not get credit for test cases for which the program is timed out.

• If you follow the algorithms I covered in class for FIRST and FOLLOW and the algorithms that I cover here for left-factoring and elimination of left recursion, you should have no problem with timeout even if your implementation is not particularly efficient. 

3    Input Format

The following context-free grammar specifies the input format:

The input consists of a rule list.  Each rule has a lefthand side which is an ID, followed by an arrow, followed by either a sequence of zero or more IDs and terminated with the STAR token.  The meaning of the input is explained in the  Semantics section below.

The tokens used in the above grammar description are defined by the following regular expressions:

ID                 =  letter  (letter  +  digit)*

STAR              =  ' * '

HASH              =  #

ARROW            =  ->

digit is the digits from ‘0’ through ‘9’ and letter is the upper and lower case letters ‘a’ through ‘z’ and ‘A’ through ‘Z’. Tokens are space separated and there is at least one whitespace character between any two successive tokens. We provide a lexer  with a getToken() function to recognize these tokens. You should use the provided lexer in you solution. You should not modify  the provided lexer.

4    Semantics

The input represents a context-free grammar. The ID tokens represent the terminal and non-terminals of the grammar. The lexemes of these ID tokens are the names of the terminals and non-terminals of the grammar.  Each grammar Rule starts with a non-terminal symbol (the left-hand side of the rule) followed by ARROW, then followed by either a sequence of zero or more terminals and non-terminals, which represent the right-hand side of the rule. If the right-hand of a rule is empty, then the right hand side represents E.

The set of non-terminals for the grammar is the set of names that appear to the left of an arrow.  Names that do not appear to the left of an arrow are terminal symbols. The start symbol of the grammar is the lexeme of the left hand side of the first rule of the grammar.

Note that the convention of using upper-case letters for non-terminals and lower-case letters for terminals that I typically followed in class does not apply in this project.

4.1    Example

Here is an example input:

decl  ->  idList  colon  ID  *

idList  ->  ID  idList1  *

idList1  ->  *

idList1  ->  COMMA  ID  idList1  *

#

The list of non-terminal symbols in the order in which they appear in the grammar is:

Non-Terminals  =  { decl,  idList,  idList1 }

The list of terminal symbols in the order in which they appear in the grammar is:

Terminals  =  { colon,  ID,  COMMA }

The grammar that this input represents is the following:

decl  →  idList  colon  ID

idList  →  ID  idList1

idList1  →  E

idList1  →  COMMA  ID  idList1

Note that even though the example shows that each rule is on a line by itself, a rule can be split into multiple lines, or even multiple rules can be on the same line. Your should not confuse ID which is the name of a terminal of the input grammar in this example with ID which is a token The following input describes the same grammar as the above example:

decl  ->  idList  colon  ID  *  idList  ->  ID  idList1  *

idList1  ->  *  idList1

->  COMMA  ID  idList1    *        # 

5    Output Specifications:  Tasks  1 – 5

Parsing:  There is no serapate tsak for prasing the ipnut.  Your praesr sohuld porerply prase the ipnut and should ouptut SYNTAX ERROR !!! if the ipnut has a snyatx error, and it should not ouptut SYNTAX ERROR !!! if the input does not have a syntax error. There will be a deduction of 15% if your praser does not parse the input correctly.

Your program should read the input grammar from standard input (which is done by the provided lexer code), and read the requested task number from the first command line argument (as stated earlier, we provide code to read the task number). Then, your program should calculate the requested output based on the task number and print the results in the specified format for each task to standard output (stdout). The following specifies the exact requirements for each task number.

5.1    Task 1:  Printing Terminals and Non-terminals

Task 1 simply outputs the list of terminals in the  order in which they appear in the grammar rules followed by the list of non-terminals in the order in which they appear in the grammar rules.

Example:   For the input grammar

decl  ->  idList  colon  ID  *

idList  ->  ID  idList1  *

idList1  ->  *

idList1  ->  COMMA  ID  idList1  *

#

the expected output for task 1 is:

colon  ID  COMMA    decl  idList  idList1

Example:   Given the input grammar:

decl  ->  idList  colon  ID  *

idList1  ->  *

idList1  ->  COMMA  ID  idList1  *

idList  ->  ID  idList1  *

#

the expected output for task 1 is:

colon  ID  COMMA    decl  idList  idList1

Note that in this example, even though the rule for idList1 is before the rule for idList, idList appears before idList1 in the grammar rules. To be clear, here is the grammar again with the order of each symbol added between parentheses after the first appearance of the symbol.

decl  (1)        ->  idList  (2)  colon  (3)  ID  (4)  *

idList1  (5)  ->  *

idList1         ->  COMMA  (6)  ID  idList1  *

idList            ->  ID  idList1  *

#

5.2    Task 2:  Calculate FIRST Sets

Compute the FIRST sets for all the non-terminal symbols. Then, for each of the non-terminals of the input grammar, in the order in which it appears in the grammar, output one line in the following format:

FIRST(<symbol>)  =  {  <set_items>  }

where <symbol> should be replaced by the non-terminal name and <set_items> should be replaced by a comma-separated list of elements of the set ordered in the following manner.

•  If G belongs to the set, represent it as #.

• If G belongs to the set, it should be listed before any other element of the set.

•  All other elements of the set should be sorted in the order in which they appear in the grammar.

Example:   Given the input grammar:

decl  ->  idList  colon  ID  *

idList  ->  ID  idList1  *

idList1  ->  *

idList1  ->  COMMA  ID  idList1  *

#

the expected output for task 2 is:

FIRST(decl)  =  {  ID  }

FIRST(idList)  =  {  ID  }

FIRST(idList1)  =  {  #,  COMMA  }

5.3    Task 3:  Calculate FOLLOW Sets

Compute the FOLLOW sets for all the non-terminal symbols. Then, for each of the non-terminals of the input grammar, in the order in which it appears in the grammar, output one line in the following format:

FOLLOW(<symbol>)  =  {  <set_items>  }

where <symbol> should be replaced by the non-terminal and <set_items> should be replaced by the comma-separated list of elements of the set ordered in the following manner.

• If EOF belongs to the set, represent it as $.

• If EOF belongs to the set, it should be listed before any other element of the set.

•  All other elements of the set should be sorted in the order in which they appear in the grammar.

Example:   Given the input grammar:

decl  ->  idList  colon  ID  *

idList  ->  ID  idList1  *

idList1  ->  *

idList1  ->  COMMA  ID  idList1  *

#

the expected output for task 3 is:

FOLLOW(decl)  =  {  $  }

FOLLOW(idList)  =  {  colon  }

FOLLOW(idList1)  =  {  colon  }

5.4    Task 4:  Left Factoring

For this task, your program takes as input a grammar G and outputs a new grammar G、that is obtained by left-factoring G. Below, I give a motivation for left factoring, then I present an algorithm for left factoring which is followed by a step by step  example and finally, I specify the output format for this task.

5.4.1    Left factoring introduction

The simple expression grammar that we have seen in class does not technically have a predictive parser. For instance the FIRST sets of T  +  E and T, which are the right hand sides of the rules for E, are not disjoint.

To write the parser, we looked at the common part (prefix) of the two right hand sides, the T, and started with parse_T(). Then, we either stopped or we continued parsing +  E. What we have done is essentially left factoring. We have two rules

E  ->  T  +  E

E  ->  T

and we treated them as E followed by +E or E:

E  ->  T  (    +  E  |   epsilon  )

By factoring the E out, we have implicitly transformed our input grammar into an equivalent grammar that has a predictive parser.  In general, the transformation can be done explicitly and the explicit transformation is called left factoring.  For the example above, the resulting grammar would be:

E  ->  T  E1

E1  ->  +  E  |   epsilon

In general, we can do left factoring whenever two rules for the same non-terminal have righthand sides with a common non-trivial (empty) prefix. The general algorithm for left factoring is given in the next subsection.

It is important to note that, in general, left-factoring by itself is not sufficient to obtain a grammar that has a predictive recursive descent parser but we need to do left factoring if we hope of obtain an equivalent grammar that might have a predictive recursive descent parser.