Description
Assignment – 4: Parser for tinyC
1 Preamble – tinyC
This assignment follows the phase structure grammar specification of C language from the International Standard ISO/IEC 9899:1999 (E). To keep the assign- ment within our required scope, we have chosen a subset of the specification as given below. We shall refer to this language as tinyC.
The lexical specification of tinyC, also taken and abridged from the Standard, has already been discussed in Assignment 3.
The phase structure grammar specification is written using the common notation of language specifications as discussed in the last assignment.
2
Phrase Structure Grammar of C 1. Expressions
primary-expression: identifier
constant string-literal
( expression )
postfix-expression: primary-expression
postfix-expression [ expression ] postfix-expression ( argument-expression-listopt ) postfix-expression . identifier
postfix-expression − > identifier postfix-expression ++
postfix-expression −−
( type-name ) { initializer-list }
( type-name ) { initializer-list , }
argument-expression-list: assignment-expression
argument-expression-list , assignment-expression unary-expression:
postfix-expression
++ unary-expression
−− unary-expression unary-operator cast-expression sizeof unary-expression sizeof ( type-name )
unary-operator: one of &*+-~!
cast-expression: unary-expression
( type-name ) cast-expression multiplicative-expression:
cast-expression
multiplicative-expression ∗ cast-expression multiplicative-expression / cast-expression multiplicative-expression % cast-expression
1
additive-expression: multiplicative-expression
additive-expression + multiplicative-expression
additive-expression − multiplicative-expression shift-expression:
additive-expression
shift-expression << additive-expression shift-expression >> additive-expression
relational-expression: shift-expression
relational-expression relational-expression relational-expression relational-expression
equality-expression: relational-expression
< shift-expression > shift-expression <= shift-expression >= shift-expression
equality-expression == relational-expression
equality-expression ! = relational-expression AND-expression:
equality-expression
AND-expression & equality-expression exclusive-OR-expression:
AND-expression
exclusive-OR-expression ˆ AND-expression inclusive-OR-expression:
exclusive-OR-expression
inclusive-OR-expression | exclusive-OR-expression logical-AND-expression:
inclusive-OR-expression
logical-AND-expression && inclusive-OR-expression logical-OR-expression:
logical-AND-expression
logical-OR-expression || logical-AND-expression conditional-expression:
logical-OR-expression
logical-OR-expression ? expression : conditional-expression assignment-expression:
conditional-expression
unary-expression assignment-operator assignment-expression assignment-operator: one of
= *= /= %= += -= <<= >>= &= ^= |=
expression: assignment-expression
expression , assignment-expression constant-expression:
conditional-expression
2. Declarations
declaration:
declaration-specifiers init-declarator-listopt ;
declaration-specifiers:
storage-class-specifier declaration-specifiersopt type-specifier declaration-specifiersopt type-qualifier declaration-specifiersopt function-specifier declaration-specifiersopt
init-declarator-list: init-declarator
init-declarator-list , init-declarator init-declarator:
declarator
declarator = initializer
2
storage-class-specifier:
extern static auto register
type-specifier:
void char short
int
long float double signed unsigned
Bool Complex Imaginary
enum-specifier specifier-qualifier-list:
type-specifier specifier-qualifier-listopt
type-qualifier specifier-qualifier-listopt enum-specifier:
enum identifieropt { enumerator-list } enum identifieropt { enumerator-list , } enum identifier
enumerator-list: enumerator
enumerator-list , enumerator enumerator:
enumeration-constant
enumeration-constant = constant-expression type-qualifier:
const restrict volatile
function-specifier:
inline
declarator:
pointeropt direct-declarator
direct-declarator: identifier
( declarator )
direct-declarator [ type-qualifier-listopt assignment-expressionopt ] direct-declarator
[ static type-qualifier-listopt assignment-expression ] direct-declarator [ type-qualifier-list static assignment-expression ] direct-declarator [ type-qualifier-listopt * ]
direct-declarator ( parameter-type-list )
direct-declarator ( identifier-listopt )
pointer:
* type-qualifier-listopt
* type-qualifier-listopt pointer type-qualifier-list:
type-qualifier
type-qualifier-list type-qualifier parameter-type-list:
parameter-list
parameter-list , … parameter-list:
parameter-declaration
parameter-list , parameter-declaration
3
parameter-declaration: declaration-specifiers declarator declaration-specifiers
identifier-list: identifier
identifier-list , identifier type-name:
specifier-qualifier-list initializer:
assignment-expression { initializer-list }
{ initializer-list , }
initializer-list:
designationopt initializer
initializer-list , designationopt initializer designation:
designator-list = designator-list:
designator
designator-list designator designator:
[ constant-expression ] . identifier
3. Statements
statement: labeled-statement
compound-statement expression-statement selection-statement iteration-statement jump-statement
labeled-statement:
identifier : statement
case constant-expression : statement
default : statement compound-statement:
{ block-item-listopt } block-item-list:
block-item
block-item-list block-item block-item:
declaration
statement expression-statement: expressionopt ;
selection-statement:
if ( expression ) statement
if ( expression ) statement else statement
switch ( expression ) statement iteration-statement:
while ( expression ) statement
do statement while ( expression ) ;
for ( expressionopt ; expressionopt ; expressionopt ) statement for ( declaration expressionopt ; expressionopt ) statement
jump-statement:
goto identifier ;
continue ;
break ;
return expressionopt ;
4
3
1. 2.
3.
4.
External definitions
translation-unit: external-declaration
translation-unit external-declaration external-declaration:
function-definition
declaration function-definition:
declaration-specifiers declarator declaration-listopt compound-statement declaration-list:
declaration
declaration-list declaration
The Assignment
Write a bison specification for defining the tokens of tinyC and generate the required y.tab.h file.
Write a bison specification for the language of tinyC using the above phase structure grammar. Use the flex specification that you had developed for Assignment 3 (if required, you may fix your flex specification).
While writing the bison specification, you may need to make some changes to the grammar. For example, some non-terminals like
argument-expression-listopt
are shown as optional on the right-hand-side as:
postfix-expression:
postfix-expression ( argument-expression-listopt )
One way to handle them would be to introduce a new non-terminal, argument-expression-list-opt, and a pair of new productions:
argument-expression-list-opt: argument-expression-list
ε
and change the above rule as:
postfix-expression:
postfix-expression ( argument-expression-list-opt )
Names of your .l and .y files should be asgn4 roll.l and asgn4 roll.y respectively. The .y or the .l file should not contain the function main(). Write your main() (in a separate file asgn4 roll.c) to test your lexer and parser.
Prepare a Makefile to compile the specifications and generate the lexer and the parser.
Prepare a test input file asgn4 roll test.c that will test all the rules that you have coded.
Prepare a tar-archive with the name asgn4 roll.tar containing all the files and upload to Moodle.
