CS 440 Compiler Design I Instructions

User Manual:

Open the PDF directly: View PDF PDF.
Page Count: 3

DownloadCS 440 Compiler Design I Instructions
Open PDF In BrowserView PDF
Syntax Analyzer for Toy language
Instructions
You are to implement a syntax analyzer for the programming language Toy, as defined in project #1.
You should first design a CFG G for Toy based on the following Backus Normal Form (BNF)
description, and then write a program to (1) create a parsing table for G, and (2) perform a onesymbol lookahead parsing on various input Toy programs and print appropriate parsing actions.
The grammar of Toy is given in a variant of extended BNF. The meta-notation used:
x
X

x*
x+
x+,
|

means that x is a terminal i.e. a token. All terminal names are lowercase.
(in italic) means X is a nonterminal. All nonterminal names are capitalized.
means zero or one occurrence of x, i.e., x is optional
means zero or more occurrences of x
means one or more occurrences of x
a comma-separated list of one or more x’s (commas appear only between x’s)
separates production alternatives

For readability, we represent operators by the lexeme that denotes them, such as + or != as opposed
to the token (_plus, _notequal) returned by the scanner.
1. Program ::= Decl+
2. Decl ::= VariableDecl | FunctionDecl | ClassDecl | InterfaceDecl
3. VariableDecl ::= Variable ;
4. Variable ::= Type id
5. Type ::= int | double | boolean | string | Type [] | id
6. FunctionDecl ::= Type id ( Formals ) StmtBlock | void id ( Formals ) StmtBlock
7. Formals ::= Variable+, | ε
8. ClassDecl ::= class id  < implements id+, > { Field* }
9. Field ::= VariableDecl | FunctionDecl
10. InterfaceDecl ::= interface id { Prototype* }
11. Prototype ::= Type id ( Formals ) ; | void id ( Formals ) ;
12. StmtBlock ::= { VariableDecl* Stmt* }
13. Stmt ::=  ; | IfStmt | WhileStmt | ForStmt | BreakStmt | ReturnStmt | PrintStmt | StmtBlock
14. IfStmt ::= if ( Expr ) Stmt 
15. WhileStmt ::= while ( Expr ) Stmt
16. ForStmt ::= for (  ; Expr ;  ) Stmt
17. BreakStmt ::= break ;
18. ReturnStmt ::= return  ;
19. PrintStmt ::= println ( Expr+, ) ;
20. Expr ::= Lvalue = Expr | Constant | Lvalue | Call | ( Expr ) |
Expr + Expr | Expr – Expr | Expr * Expr | Expr / Expr | Expr % Expr | - Expr |
Expr < Expr | Expr <= Expr | Expr > Expr | Expr >= Expr |
Expr == Expr | Expr != Expr | Expr && Expr | Expr || Expr | ! Expr
readln () | new ( id ) | newarray ( intconstant , Type )
21. Lvalue ::= id | Lvalue [ Expr ] | Lvalue . id
22. Call ::= id ( Actuals ) | id . id ( Actuals )
23. Actuals ::= Expr+, | ε
24. Constant ::= intconstant | doubleconstant | stringconstant | booleanconstant | null
1/3

Operator precedence from highest to lowest:
[.
!*/%
+< <= > >=
== !=
&&
||
=
•
•
•

(array indexing and field selection)
(logical not, unary minus)
(multiply, divide, mod)
(addition, subtraction)
(relational)
(equality)
(logical and)
(logical or)
(assignment)

All binary arithmetic and logical operators are left-associative.
The assignment and relational operators are not associate, which means we cannot chain a
sequence of operators that are on the same precedence level. For example, a < b >= c should not
parse, but a < b == c is allowed.
Parentheses may override precedence and associativity.

For every input Toy program, you should print out a sequence of tokens generated by your first
project (the lexical analyzer), and print out the action (either "shift" or "reduce") decided by your
parser for each token. If the action is "reduce", also print out the production number. For instance,
given the following CFG:
1.
2.
3.
4.
5.
6.

S→aXc
X→bX
X→b
X→Yd
Y→Yd
Y→d

The sample output for string abbbc should be
a [shift]
b [shift]
b [shift]
b [shift]
c [reduce 3][reduce 2][reduce 2][shift]
[reduce 1]
[accept]
and the output for abcd should be
a [shift]
b [shift]
c [reduce 3][shift]
d [reduce 1]
[reject]

2/3

1
2
3
4
5
6
7
8
9

10

11
12
13
14

Input
Expected outcome Program result
void f (double x, double y) { }
int i = 1;
// in function
result = 5.times(4);
// in function
front = in.nextLine();
// in function
front = in.nextLine;
int[][][] super;
a[3][4.5][b] = result = x + y + z;
// in function
for ( ; ; ) x = 1;
// in function
if (h>w) g=h;
else h=g;
double a;
// in class
boolean b;
userDefinedClassType f(){}
double d;
string g(){}
the sample Toy program given in project #1
design your own test case
design your own test case
design your own test case

3/3
Source Exif Data: 
File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.5
Linearized                      : Yes
Author                          : Daisey Sang
Company                         : 
Created                         : D:20181203
Create Date                     : 2019:02:08 10:07:41-08:00
Last Saved                      : D:20190207
Modify Date                     : 2019:02:08 10:07:46-08:00
Source Modified                 : D:20190208180731
Language                        : EN-US
Tagged PDF                      : Yes
XMP Toolkit                     : Adobe XMP Core 5.4-c006 80.159825, 2016/09/16-03:31:08
Metadata Date                   : 2019:02:08 10:07:46-08:00
Creator Tool                    : Acrobat PDFMaker 11 for Word
Document ID                     : uuid:f4121a4f-6d1b-426a-ba39-384ba60420df
Instance ID                     : uuid:73600257-b38e-495c-86d7-f65c54264e7e
Subject                         : 2
Format                          : application/pdf
Title                           : CS 440  Compiler Design I
Creator                         : Daisey Sang
Producer                        : Adobe PDF Library 11.0
Page Layout                     : OneColumn
Page Count                      : 3
EXIF Metadata provided by EXIF.tools

Navigation menu