CS 3723: Tiny® Language

	CS 3723 Programming Languages
Tiny® Language

Description: Much of the design is based on a requirement that each token be a single non-whitespace character. The idea is to make various elementary parts of the compiler unnecessary, such as the scanner and the symbol table. While relatively simple to implement, these can be distracting and confusing even in a modest compiler project.

Grammar for Tiny® language

M  --->  { S } '$'
S  --->  I  |  W  |  A  |  P  |  C  |  G
I  --->  '[' E '?' { S } ':' { S } ']'  |  '[' E '?' { S } ']'
W  --->  '{' E '?' { S } '}'
A  --->  lower-case '=' E ';'
P  --->  '<'  E  ';'
G  --->  '>'  lower-case ';'
C  --->  '<'  upper-case ';'
E  --->  T {('+' | '-') T}
T  --->  U {('*' | '/' | '%') U}
U  --->  F '^' U | F
F  --->  '(' E ')'  |  lower-case  |  digit

Here "lower-case" stands for a single lower-case letter, and "upper-case" stands for a single upper-case letter. For a more colorful grammar (in a slightly different form), see colorful grammar.

This grammar (and the language it defines) doesn't have any regular reserved words (key words), but the upper-case letters 'B', 'T', and 'N' are reserved.

Just to help with understanding, below on the left is the intuitive meaning of each of the above non-terminals. The table on the right gives the input/output statements.

Symbol	Meaning
M	Main Program
S	Statement
I	If-Then-[Else] Statement
W	While Statement
A	Assignment Statement
P	Put or Print (integer)
C	Print Character
G	Get (integer)
E	Expression (logical or arith)
T	Term
U	(Hmmm. Ugly Term?)
F	Factor

Statement	Meaning
< expression ;	print an expression
< B ;	print a blank
< N ;	print a newline
< T ;	print a tab
> lower-case ;	read into variable

Notice that the languge uses [ ] for an if-then-else statement, because this notation is often used in BNF for an optional item, while the { } is used for a while statement because in the BNF { } is used for zero or more repetitions. It might be confusing that { } are used othe as terminal symbols (inside quotes) and as meta-symbols.

Semantics: The basic assignment is to be implemented using MIPS assembly code and 32-bit integers, with all integer arithmetic. It is relatively simple to beef this up to 64-bit floating point numbers, and this contains the previous integer implementation as a special case, since 64-bit floats do exact 51-bit integer operations.

Extensions: There is an extension of Tiny® to the Small® language, which includes relational operators, boolean values and operators, and functions and parameters. At the least this extension will be discussed in class.

Revision date: 2013-02-10. (Please use ISO 8601, the International Standard.)