Sale!

Programming Assignment 01 Lexical and Syntax Analyzer

$33.00

Category:
5/5 - (2 votes)

Programming Assignment 01

1. Introduction

The goal of this assignment is to have you write a lexical and syntax analyzer for a hypothetical programming language (roughly based on Pascal). The input of your program is a source code written in the programming language’s grammar. If the source code is syntactically correct your program should display a generated parse tree. An appropriate error message should be provided otherwise.

The expectation for this programming assignment is that you will be coding a complete parser from scratch using Scala. You can choose between the two approaches discussed in class: top-down or bottom-up. You are not allowed to base your project on any parser generator software like YACC or Java CC, for example.

2. Grammar

Below is the grammar for the Pascal-like programming language specified using EBNF notation. Assume that this PL is case-sensitive.

program = ´program´ identifier body ´.´
identifier = letter { ( letter | digit ) }
body = [ var_sct ] block
var_sct = ´var´ var_dcl { ´;´ var_dcl }
var_dcl = identifier { identifier } ´:´ type
type = ´Integer´ | ´Boolean´
block = ´begin´ stmt { ´;´ stmt } ´end´
stmt = assgm_stmt | read_stmt | write_stmt | if_stmt | while_stmt | block
assgm_stmt = identifier ´:=´ expr
read_stmt = ´read´ identifier
write_stmt = ´write´ ( identifier | literal )
if_stmt = ´if´ bool_expr ´then´ stmt [ ´else´ stmt ]
while_stmt = ´while´ bool_expr ´do´ stmt
expr = arithm_expr | bool_expr
arithm_expr = arithm_expr ( ´+´ | ´-´ ) term | term
term = term ´*´ factor | factor
factor = identifier | int_literal
literal = int_literal | bool_literal
int_literal = digit { digit }
bool_litreal = ´true´ | ´false´
bool_expr = bool_literal | arithm_expr ( ´>´ | ´>=´ | ´=´ | ´<=´ | ´<´ ) arithm_expr
letter = ´a´ | ´b´ | ´c´ | ´d´ | ´e´ | ´f´ | ´g´ | ´h´ | ´i´ | ´j´ | ´k´ | ´l´ | ´m´ | ´n´ | ´o´ | ´p´ | ´q´ | ´r´ | ´s´ | ´t´ | ´u´ | ´v´ | ´w´ | ´x´ | ´y´ | ´z´ | ´A´ | ´B´ | ´C´ | ´D´ | ´E´ | ´F´ | ´G´ | ´H´ | ´I´ | ´J´ | ´K´ | ´L´ | ´M´ | ´N´ | ´O´ | ´P´ | ´Q´ | ´R´ | ´S´ | ´T´ | ´U´ | ´V´ | ´W´ | ´X´ | ´Y´ | ´Z´
digit = ´0´ | ´1´ | ´2´ | ´3´ | ´4´ | ´5´ | ´6´ | ´7´ | ´8´ | ´9´

3. Tests

For testing purposes, 15 source files are provided (get them from https://github.com/thyagomota/20FCS3210). The expected output for each of the tests is provided next.

program Source1

var x1 x2 y: Integer

begin

read x1;
read x2;
y := x1 + x2;
write y

end.
program
program
identifier: ‘Source1’
body
var_sct
var
var_dct
identifier: ‘x1’
identifier: ‘x2’
identifier: ‘y’
:
type
Integer
block
begin
stmt
read_stmt
read
identifier: ‘x1’
;
stmt
read_stmt
read
identifier: ‘x2’
;
stmt
assgm_stmt
identifier: ‘y’
:=
expr
arithm_expr
term
factor
identifier: ‘x1′
term’
arithm_expr’
+
term
factor
identifier: ‘x2′
term’
arithm_expr’
;
stmt
write_stmt
write
identifier: ‘y’
end
.

program Source2

var
s: Integer;
i: Integer;
acc: Integer

begin

read s;
i := 1;
acc := 0;
while i <= s do
begin
acc := acc + i;
i := i + 1
end

end. program
program
identifier: ‘Source2’
body
var_sct
var
var_dct
identifier: ‘s’
:
type
Integer
;
var_dct
identifier: ‘i’
:
type
Integer
;
var_dct
identifier: ‘acc’
:
type
Integer
block
begin
stmt
read_stmt
read
identifier: ‘s’
;
stmt
assgm_stmt
identifier: ‘i’
:=
expr
arithm_expr
term
factor
int_literal: ‘1’
term’
arithm_expr’
;
stmt
assgm_stmt
identifier: ‘acc’
:=
expr
arithm_expr
term
factor
int_literal: ‘0’
term’
arithm_expr’
;
stmt
while_stmt
while
bool_expr
arithm_expr
term
factor
identifier: ‘i’
term’
arithm_expr’
<=
arithm_expr
term
factor
identifier: ‘s’
term’
arithm_expr’
do
stmt
block
begin
stmt
assgm_stmt
identifier: ‘acc’
:=
expr
arithm_expr
term
factor
identifier: ‘acc’
term’
arithm_expr’
+
term
factor
identifier: ‘i’
term’
arithm_expr’
;
stmt
assgm_stmt
identifier: ‘i’
:=
expr
arithm_expr
term
factor
identifier: ‘i’
term’
arithm_expr’
+
term
factor
int_literal: ‘1’
term’
arithm_expr’
end
end
.

program Source3

var
x: Integer;
y: Integer;
result: Boolean

begin

read x;
read y;
if x > y then
result := true
else
result := false;
write result

end. program
program
identifier: ‘Source3’
body
var_sct
var
var_dct
identifier: ‘x’
:
type
Integer
;
var_dct
identifier: ‘y’
:
type
Integer
;
var_dct
identifier: ‘result’
:
type
Boolean
block
begin
stmt
read_stmt
read
identifier: ‘x’
;
stmt
read_stmt
read
identifier: ‘y’
;
stmt
if_stmt
if
bool_expr
arithm_expr
term
factor
identifier: ‘x’
term’
arithm_expr’
>
arithm_expr
term
factor
identifier: ‘y’
term’
arithm_expr’
then
stmt
assgm_stmt
identifier: ‘result’
:=
expr
bool_expr
bool_literal
true
else
stmt
assgm_stmt
identifier: ‘result’
:=
expr
bool_expr
bool_literal
false
;
stmt
write_stmt
write
identifier: ‘result’
end
.

source4.pas Syntax Analyzer Error: identifier expected!
source5.pas Syntax Analyzer Error: begin expected!
source6.pas Syntax Analyzer Error: colon expected!
source7.pas Syntax Analyzer Error: assignment expected!
source8.pas Syntax Analyzer Error: type expected!
source9.pas Syntax Analyzer Error: do expected!
source10.pas Syntax Analyzer Error: relational operator expected!
source11.pas Syntax Analyzer Error: period expected!
source12.pas Syntax Analyzer Error: identifier or (int) literal expected!
source13.pas Syntax Analyzer Error: then expected!
source14.pas Syntax Analyzer Error: end expected!
source15.pas Syntax Analyzer Error: EOF expected!

Please be aware that those tests are far from being comprehensive. The instructor reserves the right to run other tests on your code if deemed necessary. You are encouraged to create other tests on your own.

4. Deliverables and Submission

All of the source code that you use for this project must be zipped in a file named src.zip and submitted through Canvas. I only accept zip format (no Z, RAR, or any other format).

Each source code MUST have a comment section in the beginning with the name(s) of the author(s) of the project. You are allowed to work together with another classmate. Teams of more than two students will NOT be accepted (NO exceptions). Only one of the members of the team needs to submit on Canvas.

5. Rubric

This programming assignment is worth 100 points, distributed in the following way:

+3 command-line validation
+32 lexical analyzer works as expected
+5 tokens match specification
+2 recognizes EOF
+3 recognizes identifiers
+3 recognizes literals
+5 recognizes special words
+2 recognizes assignment operator
+3 recognizes arithmetic operator
+3 recognizes relational operators
+2 recognizes logical operators
+3 recognizes punctuators
+1 raises exception with proper error message when it fails
+60 syntax analyzer works as expected
+10 grammar used matches specification
+10 parser shows appropriate error messages
+10 parse tree is built correctly
+2 for each source input test that passes all tests
+5 submission follows instructions (student names identified in a comment section, zip format,)

PlaceholderProgramming Assignment 01 Lexical and Syntax Analyzer
$33.00
Open chat
Need help?
Hello
Can we help?