uc.bnf

// A grammar for the µC programming language [1].
//
// The content and structure of this document is heavily influenced by the Go
// Programming Language Specification [2] and some parts are therefore governed
// by a BSD-style license [3]. Any original content of this document is hereby
// released into the public domain [4].
//
// References:
//    [1]: https://www.it.uu.se/katalog/aleji304/CompilersProject/uc.html
//    [2]: http://golang.org/ref/spec
//    [3]: http://golang.org/LICENSE
//    [4]: https://creativecommons.org/publicdomain/zero/1.0/

// # Source code representation
//

// ## Characters
//

// An arbitrary ASCII character except null (0x00), new lines (0x0A), carriage
// return (0x0D), apostrophe (0x27), double quote (0x22) and backslash (0x5C).
_ascii_char
	: '\x01' - '\x09'
	| '\x0B' - '\x0C'
	| '\x0E' - '\x21'
	| '\x23' - '\x26'
	| '\x28' - '\x5B'
	| '\x5D' - '\x7F'
;

_ascii_letter : 'a' - 'z' | 'A' - 'Z' ;
_ascii_digit  : '0' - '9' ;

// ## Letters and digits
//

_letter        : _ascii_letter | '_' ;
_decimal_digit : _ascii_digit ;
_decimals      : _decimal_digit { _decimal_digit } ;

// # Lexical elements
//

// ## Comments
//

_line_comment
	: '/' '/' { . } '\n'
	// TODO: Implement proper support for preprocess directive.
	| '#'  { . } '\n'
;
_block_comment : '/' '*' { . | '*' } '*' '/' ;
!comment       : _line_comment | _block_comment ;

// ## Tokens
//

// White space, formed from spaces (0x20), horizontal tabs (0x09), new line
// (line-feed (0x0A) or carriage-return (0x0D)), vertical tabs (0x0B), and form-
// feeds (0x0C) (§6.4), is ignored except as it separates tokens that would
// otherwise combine into a single token.
!whitespace : ' ' | '\t' | '\v' | '\f' | '\r' | '\n' ;

// ## Identifiers
//

ident : _letter { _letter | _decimal_digit } ;

// ## Integer literals
//

int_lit : _decimals ;

// ## Character literals
//

_escaped_char : '\\' 'n' ;
char_lit      : '\'' ( _ascii_char | '"' | _escaped_char ) '\'' ;

// # Syntaxic production rules
//

<< import (
	"github.com/mewmew/uc/ast/astx"
	"github.com/mewmew/uc/token"
) >>

File
	: Decls                             << astx.NewFile($0) >>
;

Decls
	: empty
	| DeclList
;

DeclList
	: Decl                              << astx.NewDeclList($0) >>
	| DeclList Decl                     << astx.AppendDecl($0, $1) >>
;

Decl
	: VarDecl ";"                       << $0, nil >>
	| FuncDecl ";"                      << $0, nil >>
	| FuncDef
	| TypeDef ";"                       << $0, nil >>
;

FuncDecl
	: FuncHeader
;

FuncHeader
	// BasicType : "char" | "int" | "void" ;
	: BasicType ident "(" Params ")"    << astx.NewFuncDecl($0, $1, $2, $3, $4) >>
;

FuncDef
	: FuncHeader BlockStmt              << astx.SetFuncBody($0, $1) >>
;

VarDecl
	: ScalarDecl
	| ArrayDecl
;

ScalarDecl
	// BasicType : "char" | "int" ;
	: BasicType ident                   << astx.NewScalarDecl($0, $1) >>
;

ArrayDecl
	// BasicType : "char" | "int" ;
	: BasicType ident "[" IntLit "]"    << astx.NewArrayDecl($0, $1, $2, $3, $4) >>
	| BasicType ident "[" "]"           << astx.NewArrayDecl($0, $1, $2, 0, $3) >>
;

IntLit
	: int_lit                           << astx.NewIntLit($0, token.IntLit) >>
	| char_lit                          << astx.NewIntLit($0, token.CharLit) >>
;

TypeDef
	: "typedef" Type ident              << astx.NewTypeDef($0, $1, $2) >>
;

BasicType
	// BasicType : "char" | "int" | "void" ;
	: ident                             << astx.NewIdent($0) >>
;

Params
	: empty
	| ParamList
;

ParamList
	: Param                             << astx.NewParamList($0) >>
	| ParamList "," Param               << astx.AppendParam($0, $2) >>
;

Param
	// BasicType : "void" ;
	: Type                              << astx.NewAnonParam($0) >>
	| VarDecl
;

// TODO: Add support for array types.
Type
	: BasicType
;

Stmt
	: MatchedStmt
	| OpenStmt
;

// Thanks to http://www.parsifalsoft.com/ifelse.html for loop statement
// resolvning (while, do, for).

OtherStmt
	: Expr ";"                          << astx.NewExprStmt($0) >>
	| "return" Expr ";"                 << astx.NewReturnStmt($0, $1) >>
	| "return" ";"                      << astx.NewReturnStmt($0, nil) >>
	| BlockStmt
	| ";"                               << astx.NewEmptyStmt($0) >>
;

BlockStmt
	: "{" BlockItems "}"                << astx.NewBlockStmt($0, $1, $2) >>
;

MatchedStmt
	: "if" Condition MatchedStmt
	  "else" MatchedStmt                << astx.NewIfStmt($0, $1, $2, $4) >>
	| "while" Condition MatchedStmt     << astx.NewWhileStmt($0, $1, $2) >>
	| OtherStmt
;

OpenStmt
	: "if" Condition Stmt               << astx.NewIfStmt($0, $1, $2, nil) >>
	| "if" Condition MatchedStmt
	  "else" OpenStmt                   << astx.NewIfStmt($0, $1, $2, $4) >>
	| "while" Condition OpenStmt        << astx.NewWhileStmt($0, $1, $2) >>
;

Condition
	: "(" Expr ")"                      << $1, nil >>
;

BlockItems
	: empty
	| BlockItemList
;

BlockItemList
	: BlockItem                         << astx.NewBlockItemList($0) >>
	| BlockItemList BlockItem           << astx.AppendBlockItem($0, $1) >>
;

BlockItem
	: Decl
	| Stmt
;

Expr
	: Expr2R
;

// Right-associative binary expressions with precedence 2.
//
//    2R: =
Expr2R
	: Expr5L
	// Right-associative.
	| Expr5L "=" Expr2R                 << astx.NewBinaryExpr($0, $1, $2) >>
;

// Left-associative binary expressions with precedence 5.
//
//    5L: &&
Expr5L
	: Expr9L
	| Expr5L "&&" Expr9L                << astx.NewBinaryExpr($0, $1, $2) >>
;

// Left-associative binary expressions with precedence 9.
//
//    9L: == !=
Expr9L
	: Expr10L
	| Expr9L "==" Expr10L               << astx.NewBinaryExpr($0, $1, $2) >>
	| Expr9L "!=" Expr10L               << astx.NewBinaryExpr($0, $1, $2) >>
;

// Left-associative binary expressions with precedence 10.
//
//    10L: < > <= >=
Expr10L
	: Expr12L
	| Expr10L "<" Expr12L               << astx.NewBinaryExpr($0, $1, $2) >>
	| Expr10L ">" Expr12L               << astx.NewBinaryExpr($0, $1, $2) >>
	| Expr10L "<=" Expr12L              << astx.NewBinaryExpr($0, $1, $2) >>
	| Expr10L ">=" Expr12L              << astx.NewBinaryExpr($0, $1, $2) >>
;

// Left-associative binary expressions with precedence 12.
//
//    12L: + -
Expr12L
	: Expr13L
	| Expr12L "+" Expr13L               << astx.NewBinaryExpr($0, $1, $2) >>
	| Expr12L "-" Expr13L               << astx.NewBinaryExpr($0, $1, $2) >>
;

// Left-associative binary expressions with precedence 13.
//
//    13L: * /
Expr13L
	: Expr14
	| Expr13L "*" Expr14                << astx.NewBinaryExpr($0, $1, $2) >>
	| Expr13L "/" Expr14                << astx.NewBinaryExpr($0, $1, $2) >>
;

// Unary expressions with precedence 14.
//
//    14: - !
Expr14
	: Expr15
	| "-" Expr14                        << astx.NewUnaryExpr($0, $1) >>
	| "!" Expr14                        << astx.NewUnaryExpr($0, $1) >>
;

// TODO: Replace function name with expression in call expression. Do the same
// for array names.

// TODO: Replace Expr15 (and similar names) with CastExpr, PostfixExpr, ...
// (from the C11 spec).

// Expressions with precedence 15.
Expr15
	: PrimaryExpr
	| ident "[" Expr "]"                << astx.NewIndexExpr($0, $1, $2, $3) >>
	| ident "(" Args ")"                << astx.NewCallExpr($0, $1, $2, $3) >>
;

// Primary expressions with the highest precedence (§A.2.1).
PrimaryExpr
	: int_lit                           << astx.NewBasicLit($0, token.IntLit) >>
	| char_lit                          << astx.NewBasicLit($0, token.CharLit) >>
	| ident                             << astx.NewIdent($0) >>
	| ParenExpr
;

ParenExpr
	: "(" Expr ")"                      << astx.NewParenExpr($0, $1, $2) >>
;

Args
	: empty
	| ExprList
;

ExprList
	: Expr                              << astx.NewExprList($0) >>
	| ExprList "," Expr                 << astx.AppendExpr($0, $2) >>
;