pa2_grammar.dos

To help you in writing an LL grammar, we have developed a tool to analyze a grammar and determine if

/*
 * This is a LL(1) grammar for part of Iota.  It does not yet handle the
 * following constructs:
 *      1. If statements
 *      2. Expression statements (i.e., stmt_expr)
 *      3. Binary and unary operator precedence
 *
 * The grammar only recognizes the module portion of the language
 * (i.e., .mod files).  Interfaces are up to you.
 *
 * This grammar file can be fed to Iota.util.LLAnalyze to check if it is LL(1):
 *      java Iota.util.LLAnalyze < pa2_grammar.txt
 */
%start Module

%token AND
%token ARRAY
%token COLON
%token COMMA
%token DIV
%token DOT
%token ELSE
%token EQ
%token EQEQ
%token FALSE
%token GT
%token ID
%token IF
%token INTEGER
%token LBRACKET
%token LENGTH
%token LPAREN
%token LT
%token MINUS
%token MOD
%token NEW
%token NOT
%token OR
%token PLUS
%token RBRACKET
%token RETURN
%token RPAREN
%token SEMI
%token STRING
%token TIMES
%token TRUE
%token USES
%token WHILE

%%

Module
        : Uses Defs
        ;

Uses
        : USES Use UsesContinued
        |
        ;

UsesContinued
        : COMMA Use UsesContinued
        |
        ;

Use
        : ID UseContinued
        ;

UseContinued
        : EQ ID DOT ID
        | DOT ID
        ;

Defs
        : Def Defs
        |
        ;

Def
        : ID DefContinued
        ;

DefContinued
        : COLON Type
        | LPAREN Formals RPAREN OptType EQ Expr
        ;

OptType
        : COLON Type
        |
        ;

Formals
        : Formal FormalsContinued
        |
        ;

FormalsContinued
        : COMMA Formal FormalsContinued
        |
        ;

Formal
        : ID COLON Type
        ;

Type
        : ID
        | ARRAY LBRACKET Type RBRACKET
        ;

Expr
        : UnaryExpr ExprContinued
        ;

ExprContinued
        : BinaryOp Expr
        |
        ;

BinaryOp
        : PLUS
        | MINUS
        | TIMES
        | DIV
        | MOD
        | AND
        | OR
        | EQEQ
        | LT
        | GT
        ;

UnaryExpr
        : UnaryOp UnaryExpr
        | Constructor
        | PrimaryExpr
        ;

UnaryOp
        : MINUS
        | NOT
        | LENGTH
        ;

Constructor
        : NEW Type LBRACKET Expr RBRACKET LPAREN Expr RPAREN
        ;

PrimaryExpr
        : Constant
        | ID OptArgs OptSubscripts
        | StmtExpr OptSubscripts
        ;

Constant
        : STRING
        | INTEGER
        | TRUE
        | FALSE
        ;

StmtExpr
        : LPAREN Stmt /* something else goes here */ RPAREN
        ;

Subscripts
        : LBRACKET Expr RBRACKET OptSubscripts
        ;

OptSubscripts
        : LBRACKET Expr RBRACKET OptSubscripts
        |
        ;

Args
        : LPAREN OptExprs RPAREN
        ;

OptExprs
        : Exprs
        |
        ;

Exprs
        : Expr ExprsContinued
        ;

ExprsContinued
        : COMMA Expr ExprsContinued
        |
        ;

OptArgs
        : Args
        |
        ;

/*
 * Expression statements are split into 3 cases to disambiguate expression
 * statements, initializers, and assignments, all of which can start with an
 * ID or LPAREN token.
 *
 *     1. IdentExprOrStmt matches statements that begin with ID.
 *        These can include simple expressions that begin with ID, assignments,
 *        or variable declarations.
 *     2. ParenExprOrStmt matches statements that begin with LPAREN.
 *        These include simple expressions that begin with LPAREN and
 *        assignments.
 *     3. ExprNoAssign matches all other expression statements.
 */
Stmt
        : IdentExprOrStmt
        | ParenExprOrStmt
        | ExprNoAssign
        | IF LPAREN Expr RPAREN Stmt /* you need to handle ELSE, too */
        | WHILE LPAREN Expr RPAREN Stmt
        | RETURN OptExpr
        ;

OptExpr
        : Expr
        |
        ;

IdentExprOrStmt
        : ID IdentExprOrStmtContinued
        ;

IdentExprOrStmtContinued
        : BinaryOp Expr
        | Subscripts BinaryOpOrOptAssign
        | Args OptSubscriptsBinaryOpOrAssign
        | Assign
        | COLON Type OptAssign
        |
        ;

ParenExprOrStmt
        : StmtExpr ParenExprOrStmtContinued
        ;

ParenExprOrStmtContinued
        : BinaryOp Expr
        | Subscripts BinaryOpOrOptAssign
        |
        ;

BinaryOpOrOptAssign
        : BinaryOp Expr
        | OptAssign
        ;

OptSubscriptsBinaryOpOrAssign
        : Subscripts BinaryOpOrOptAssign
        | BinaryOpOrOptAssign
        ;

Assign
        : EQ Expr
        ;

OptAssign
        : Assign
        |
        ;

ExprNoAssign
        : UnaryExprNoAssign ExprNoAssignContinued
        ;

ExprNoAssignContinued
        : BinaryOp Expr
        |
        ;

UnaryExprNoAssign
        : UnaryOp UnaryExpr
        | Constructor
        | Constant
        ;