CS365 Project Assignment 1
In this assignment you are going to write a lexical analyzer for your
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.
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:
- Nonterminals start with a capital letter
- Named terminals, such as id, are bold-faced
Formula -> (id[number|id=RowList] = Exp)+
RowList -> RowRef [, RowRef]*
RowRef -> number | number-number
- An id starts with an upper/lowercase letter and is followed
by any number of letters, numbers, or _'s.
- 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.
- 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 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
CellList -> CellRef (, CellRef)*
CellRef -> id[RowList] | id[id]
- ? and : have the highest precedence
- * and / have precedence over + and -.
- The unary - has precedence over * and /.
- * and / have equal precedence and so do + and -.
- Operators are left associative.
- sum returns the sum of its operands
- min returns the minimum value of its operands
- max returns the maximum value of its operands
- 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
- 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.
Here is a list of sample formulas:
a = 3
b = a
c = b * a
grade = .3 * (midterm1 + midterm2) + .4 * final
grade[i=1,3-6,8] = .3 * (midterm1[i] + midterm2[i]) + .4 * final[i]
grade[i=1,3-6,8] = weight * (midterm1[i] + midterm2[i]) + weight * final[i]
total_hw[i=1-6] = sum(hw1[i], hw2[i], hw3[i])
total_purchases = sum(total[2-6, 8])
tax = income < 20000 ? income * .1 : income * .2