CS365 Project Assignment 1


In this assignment you are going to write a lexical analyzer for your spreadsheet application.

Your lexer file should be placed in a package named formula and should be named formula.lex. You can derive the tokens for your lexer from the grammar for the formulas.


Formula Grammar

Here is the grammar that describes the syntax for the formulas in your spreadsheet application. You can derive the tokens for your lexer from this grammar. The following grammar uses several conventions:

  1. Nonterminals start with a capital letter
  2. Named terminals, such as id, are bold-faced

Formula -> (id[number|id=RowList] = Exp)+

RowList -> RowRef [, RowRef]*
RowRef -> number | number-number
  1. An id starts with an upper/lowercase letter and is followed by any number of letters, numbers, or _'s.
  2. A number is any string of 0 or more digits, followed by an optional decimal point and 1 or more digits. A number must have at least one digit.
  3. A sample formula involving a cell list might be: grade[i=3-5, 7, 8-9] = midterm[i] * .4 + final[i] * .6 The ids on the left side of the equals sign represent cell references, with the ids denoting the column labels and the numbers denoting the rows. A simple expression such as grade[1] references a single cell whereas a row list allows a formula to be assigned to multiple cells in the same column. In the above example the formula would be assigned to rows 3-5, 7, and 8-9 in the grade column.
Exp -> Exp + Exp | Exp - Exp | Exp * Exp | Exp / Exp | ( Exp ) | -Exp
    |  Exp < Exp | Exp > Exp | Exp <= Exp | Exp >= Exp 
	|  Exp == Exp | Exp != Exp
    |  number | id[number|id]
    |  Exp ? Exp : Exp
    |  sum|min|max(CellList)

CellList -> CellRef (, CellRef)*

CellRef -> id[RowList] | id[id]
  1. ? and : have the highest precedence
  2. * and / have precedence over + and -.
  3. The unary - has precedence over * and /.
  4. * and / have equal precedence and so do + and -.
  5. Operators are left associative.
  6. sum returns the sum of its operands
  7. min returns the minimum value of its operands
  8. max returns the maximum value of its operands
  9. Cell references are designed to allow the user to reference either a number of rows in a single column or a generic row in a single column
  10. The meaning of Exp1 ? Exp2 : Exp3 is the same as: if (Exp1) then Exp2 else Exp3 Exp1 is considered false if it evaluates to 0 and true otherwise. As an example, the expression income < 10000 ? income * .1 : income * .2 will return 500 if income is 5000 and 20000 if income is 100000.


Sample Formulas

Here is a list of sample formulas:

a[2] = 3 b[3] = a[2] c[1] = b[2] * a[1] grade[1] = .3 * (midterm1[1] + midterm2[1]) + .4 * final[1] grade[i=1,3-6,8] = .3 * (midterm1[i] + midterm2[i]) + .4 * final[i] grade[i=1,3-6,8] = weight[1] * (midterm1[i] + midterm2[i]) + weight[2] * final[i] total_hw[i=1-6] = sum(hw1[i], hw2[i], hw3[i]) total_purchases[2] = sum(total[2-6, 8]) tax[3] = income[3] < 20000 ? income[3] * .1 : income[3] * .2