Project 1

CSC 4101 – Programming Languages

Due March 2^nd, 2006

Implement a lexical analyzer and parser in C, C++, or Java for the illustrative language FOO which is defined below.

The Input Language   The parser's input language is Input where:

Input --> Token*
Token --> AlphaOther AlphaOtherNumeric* | Delimiter | Operator | Int

The lexical analyzer recognizes keywords, delimiters (parentheses, commas, semicolons), primitive operations, identifiers, and numbers.

Adjacent tokens must be separated by whitespace (a non-empty sequence of spaces, tabs, and newlines) unless one of the tokens is a delimiter or operator. In identifying operators, the lexical analyzer chooses the longest possible match. Hence, <= is interpreted as a single token rather than < followed by =.

Lower --> a | b | c | d | ... | z
Upper --> "A" | "B" | "C" | "D" | ... | "Z"
Other --> ? | _
Digit --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Alpha --> Upper | Lower
AlphaOther --> Alpha | Other
AlphaOtherNumeric --> AlphaOther | Digit
Delimiter --> ( | ) | [ | ] | , | ;
Operator --> "+" | - | ~ | "*" | / | = | != | < | > | <= | >= | & | "|" | :=

FOO: The set of legitimate FOO phrases is the subset of the potential inputs consisting of the expressions Exp defined by the following grammar:

Expressions

Exp  --> Term { Binop Exp }
 | if Exp then Exp else Exp
 | Def+  
 
Term --> Unop Term
 | Factor { ( ExpList ) }
 | Null
 | Int
 | Bool
Factor --> ( Exp ) | Id
ExpList --> { PropExpList }
PropExpList --> Exp | Exp , PropExpList
IdList --> { PropIdList }
PropIdList --> Id | Id , PropIdList

Definitions

Def  --> Id := Assign ; 
Assign  --> Exp | ( IdList ) 
 

Primitive Constants, Operators, and Operations

Null --> null
Bool --> true | false
Unop --> Sign | ~
Sign --> "+" | -
Binop --> Sign | "*" | / | = | != | < | > | <= | >= | & | "|"

Identifiers

Id --> AlphaOther {AlphaOther | Digit}*

Please note that Id does not contain the keywords if, then, else, null, true, and false.

Numbers

Int --> Digit+
 
 
Some Clarifications:

• A symbol in the FOO language always starts with a capital letter. Therefore, Symbol is a symbol in the FOO language, whereas literal is the actual text "literal".
• A phrase P enclosed in braces { P } is optional, i.e. both P and the empty string match.
• A phrase P followed by a * is iterated zero or more times, e.g. Def* means the concatenation of zero or more Def phrases:
  Def
  Def Def
  and so on, as well as the empty string.
• A phrase P followed by a + is iterated one or more times, e.g. Def+ means the concatenation of one or more Def phrases:
  Def
  Def Def
  and so on, but not the empty string.
• If a phrase P enclosed in braces { P } is followed by a * or +, the braces are simply denote grouping: the enclosed phrase is iterated as specified by the * or + symbol. For example, { A B }* is matched by zero or more concatenations of A B: A B
  A B A B
  and so on, as well as the empty string but not A or A B A.
• If something that is interpreted as part of the FOO language should be interpreted literally as part of the language we are describing, it will be enclosed in quotes. Therefore, "A" is the actual letter "A", not the symbol A in the meta language, and P"*" is the phrase P followed by an actual asterisk, and does not mean that the phase P should be repeated zero or more times, as described above.

Your program should:

1) It should scan the input and break it into tokens. If a token is not recognized, it should give an error message (Scanning Error) and display the unrecognized token. If all tokens are recognized, it should complete the scanning successfully (with a success message), and display all recognized tokens (one token per line).

2) It should parse the input and check if it is within the grammar of the language. If not, it should display an error message (Parsing Error) with the line(s) breaking the grammar.

Teamwork: You are strongly encouraged to do this assignment with a team of two. When you submit your assignment, indicate the composition of your team (names and email addresses) in your README file.

If you cannot find a partner and would like one, send an email to kosar@lsu.edu and I will try to find one for you. Teams of more than two members are not permitted. You are free to do the assignment alone if you prefer so.

Testing and Submitting Your Program:

You can test your code with these sample programs.

Before submitting your code:

1) Create a folder with your last name.

2) Copy all of the source code, makefiles, and executables required to compile & run your code into this directory (in a well organized manner).

3) Create a README file that:

• gives the names and email addresses of both team members,
• outlines the organization of your program, and
• specifies what testing process you used to confirm the correctness of your program.

4) Your test data files should be stored in the same directory.

Each procedure or method in your program should include a short comment stating precisely what it does. For routines that parse a particular form of program phrase, give grammar rules describing that form.

To submit your program, make sure that everything that you want to submit is located in the directory with your last name. Zip that directory and send it as a single file to the TA (gschof1@lsu.edu) and CC to the Professor (kosar@lsu.edu). As the subject line, put “Project 1 by your name (& your partner’s name)”.