Interpreter Project Flex/Bison

function_header:
FUNCTION IDENTIFIER RETURNS type ‘;’ ;
type:
INTEGER |
CHARACTER ;

optional_variable:
variable |
%empty ;

variable:
IDENTIFIER ‘:’ type IS statement ‘;’ {scalars.insert($1, $5);}; |
IDENTIFIER ‘:’ LIST OF type IS list ‘;’ {lists.insert($1, $7);} ;
list:
‘(‘ expressions ‘)’ {$$ = $2;} ;
expressions:
expressions ‘,’ expression {$1->push_back($3); $$ = $1;} |
expression {$$ = new vector(); $$->push_back($1);}
body:
BEGIN_ statement_ END {$$ = $2;} ;
statement_:
statement ‘;’ |
error ‘;’ {$$ = 0;} ;

statement:
expression |
WHEN condition ‘,’ expression ‘:’ expression {$$ = $2 ? $4 : $6;} |
SWITCH expression IS cases OTHERS ARROW statement ‘;’ ENDSWITCH
{$$ = !isnan($4) ? $4 : $7;} ;
cases:
cases case {$$ = !isnan($1) ? $1 : $2;} |
%empty {$$ = NAN;} ;

case:
CASE INT_LITERAL ARROW statement ‘;’ {$$ = $-2 == $2 ? $4 : NAN;} ;
condition:
condition ANDOP relation {$$ = $1 && $2;} |
relation ;
relation:
‘(‘ condition ‘)’ {$$ = $2;} |
expression RELOP expression {$$ = evaluateRelational($1, $2, $3);} ;
expression:
expression ADDOP term {$$ = evaluateArithmetic($1, $2, $3);} |
term ;

term:
term MULOP primary {$$ = evaluateArithmetic($1, $2, $3);} |
primary ;
primary:
‘(‘ expression ‘)’ {$$ = $2;} |
INT_LITERAL |
CHAR_LITERAL |
IDENTIFIER ‘(‘ expression ‘)’ {$$ = extract_element($1, $3); } |
IDENTIFIER {if (!scalars.find($1, $$)) appendError(UNDECLARED, $1);} ;
%%
void yyerror(const char* message) {
appendError(SYNTAX, message);
}
double extract_element(CharPtr list_name, double subscript) {
vector* list;
if (lists.find(list_name, list))
return (*list)[subscript];
appendError(UNDECLARED, list_name);
return NAN;
}
int main(int argc, char *argv[]) {
firstLine();
yyparse();
if (lastLine() == 0)
cout << "Result = " << result << endl; return 0; } __MACOSX/Project 3 Skeleton Code-2/._parser.y Project 3 Skeleton Code-2/listing.h // CMSC 430 Compiler Theory and Design // Project 3 Skeleton // UMGC CITE // Summer 2023 // This file contains the function prototypes for the functions that produce // the compilation listing enum ErrorCategories {LEXICAL, SYNTAX, GENERAL_SEMANTIC, DUPLICATE_IDENTIFIER, UNDECLARED}; void firstLine(); void nextLine(); int lastLine(); void appendError(ErrorCategories errorCategory, string message); __MACOSX/Project 3 Skeleton Code-2/._listing.h Project 3 Skeleton Code-2/values.cc Project 3 Skeleton Code-2/values.cc // CMSC 430 Compiler Theory and Design // Project 3 Skeleton // UMGC CITE // Summer 2023 // This file contains the bodies of the evaluation functions #include   < string >

#include
 
< cmath >

using
 
namespace
 std
;

#include
 
“values.h”

#include
 
“listing.h”

double
 evaluateArithmetic
(
double
 left
,
 
Operators
 operator_
,
 
double
 right
)
 
{

    
double
 result
;

    
switch
 
(
operator_
)
 
{

        
case
 ADD
:

            result 
=
 left 
+
 right
;

            
break
;

        
case
 MULTIPLY
:

            result 
=
 left 
*
 right
;

            
break
;

    
}

    
return
 result
;

}

double
 evaluateRelational
(
double
 left
,
 
Operators
 operator_
,
 
double
 right
)
 
{

    
double
 result
;

    
switch
 
(
operator_
)
 
{

        
case
 LESS
:

            result 
=
 left 
<  right ;              break ;      }      return  result ; } __MACOSX/Project 3 Skeleton Code-2/._values.cc Required Project 2 Files/scanner.l /* This file contains flex input file */ %{ #include
#include
using namespace std;
#include “listing.h”
#include “parser.tab.h”
%}
%option noyywrap
ws [ \t\r]+
comment “//”.*\n
comment2 “–“.*
line [\n]
id [_A-Za-z]([A-Za-z0-9_])*
digit [0-9]
dec {digit}+
hex_literal “#”({digit}|[A-Fa-f])+
char ‘([^\\]|\\[btnrf])’
punc [\(\),:;]
%%
{ws} { ECHO; }
{comment} { ECHO; nextLine(); }
{line} { ECHO; nextLine(); }
“+” { ECHO; return(ADDOP); }
“-” { ECHO; return(ADDOP); }
“*” { ECHO; return(MULOP); }
“/” { ECHO; return(MULOP); }
“%” { ECHO; return(MODOP); }
“rem” { ECHO; return(REMOP); }
“^” { ECHO; return(EXPOP); }
“~” { ECHO; return(NEGOP); }
“&” { ECHO; return(ANDOP); }
“<" { ECHO; return(RELOP); } "=>” { ECHO; return(ARROW); }
“=” { ECHO; return(RELOP); }
“<>” { ECHO; return(RELOP); }
“>” { ECHO; return(RELOP); }
“>=” { ECHO; return(RELOP); }
“<=" { ECHO; return(RELOP); } "|" { ECHO; return(OROP); } "!" { ECHO; return(NOTOP); } begin { ECHO; return(BEGIN_); } case { ECHO; return(CASE); } character { ECHO; return(CHARACTER); } end { ECHO; return(END); } endswitch { ECHO; return(ENDSWITCH); } function { ECHO; return(FUNCTION); } integer { ECHO; return(INTEGER); } is { ECHO; return(IS); } list { ECHO; return(LIST); } of { ECHO; return(OF); } others { ECHO; return(OTHERS); } returns { ECHO; return(RETURNS); } switch { ECHO; return(SWITCH); } when { ECHO; return(WHEN); } else { ECHO; return(ELSE); } elsif { ECHO; return(ELSIF); } endfold { ECHO; return(ENDFOLD); } endif { ECHO; return(ENDIF); } fold { ECHO; return(FOLD); } if { ECHO; return(IF); } left { ECHO; return(LEFT); } real { ECHO; return(REAL); } right { ECHO; return(RIGHT); } then { ECHO; return(THEN); } reduce { ECHO; return(REDUCE); } endreduce { ECHO; return(ENDREDUCE); } {id} { if (strstr(yytext, "___") || yytext[0] == '_' || yytext[strlen(yytext) - 1] == '_') { appendError(LEXICAL, "Invalid Identifier " + string(yytext)); // Flag invalid identifiers } else { ECHO; return(IDENTIFIER); } } [0-9]*\.[0-9]+([eE][+-]?[0-9]+)? { return(REAL_LITERAL); } {hex_literal} { ECHO; return(HEX_LITERAL); } {dec} { ECHO; return(INT_LITERAL); } {char} { ECHO; return(CHAR_LITERAL); } {punc} { ECHO; return(yytext[0]); } "--".* { /* Ignore comments starting with -- */ } . { ECHO; appendError(LEXICAL, "Invalid Character " + string(yytext)); } %% __MACOSX/Required Project 2 Files/._scanner.l Required Project 2 Files/makefile compile: scanner.o parser.o listing.o g++ -o compile scanner.o parser.o listing.o scanner.o: scanner.c listing.h tokens.h g++ -c scanner.c scanner.c: scanner.l flex scanner.l mv lex.yy.c scanner.c parser.o: parser.c listing.h g++ -c parser.c parser.c tokens.h: parser.y bison -d -v parser.y mv parser.tab.c parser.c cp parser.tab.h tokens.h listing.o: listing.cc listing.h g++ -c listing.cc __MACOSX/Required Project 2 Files/._makefile Required Project 2 Files/listing.cc Required Project 2 Files/listing.cc // This file contains the bodies of the functions that produces the  // compilation listing #include   < cstdio >

#include
 
< string >

#include
 
< queue >

using
 
namespace
 std
;

#include
 
“listing.h”

static
 queue
< string >
 errorQueue
;

static
 
int
 lineNumber
;

static
 string error 
=
 
“”
;

static
 
int
 totalErrors 
=
 
0
;

int
 lexicalErrors 
=
 
0
;

int
 syntaxErrors 
=
 
0
;

int
 semanticErrors 
=
 
0
;

static
 
void
 displayErrors
();

void
 firstLine
()

{

    lineNumber 
=
 
1
;

    printf
(
“\n%4d  ”
,
lineNumber
);

}

void
 nextLine
()

{

    displayErrors
();

    lineNumber
++
;

    printf
(
“%4d  ”
,
lineNumber
);

}

int
 lastLine
()

{

    printf
(
“\n”
);

    displayErrors
();

    printf
(
”   Lexical Errors: %d\n”
,
 lexicalErrors
);

    printf
(
”   Syntax Errors: %d\n”
,
 syntaxErrors
);

    printf
(
”   Semantic Errors: %d\n”
,
 semanticErrors
);

    
if
 
(
totalErrors 
==
 
0
)
 
{

        printf
(
“\nCompiled Successfully\n”
);

    
}

    
return
 totalErrors
;

}

void
 appendError
(
ErrorCategories
 errorCategory
,
 string message
)

{

    string messages
[]
 
=
 
{

        
“Lexical Error: ”
,

        
“Syntax Error: ”
,

        
“Semantic Error: ”
,

        
“Semantic Error: Duplicate Identifier ”
,

        
“Semantic Error: Undeclared ”

    
};

    errorQueue
.
push
(
messages
[
errorCategory
]
 
+
 message
);

    
switch
 
(
errorCategory
)
 
{

        
case
 LEXICAL
:

            lexicalErrors
++
;

            
break
;

        
case
 SYNTAX
:

            syntaxErrors
++
;

            
break
;

        
case
 GENERAL_SEMANTIC
:

        
case
 DUPLICATE_IDENTIFIER
:

        
case
 UNDECLARED
:

            semanticErrors
++
;

            
break
;

    
}

    totalErrors
++
;

}

void
 displayErrors
()

{

while
 
(
!
errorQueue
.
empty
())
 
{

        printf
(
“%s\n”
,
 errorQueue
.
front
().
c_str
());

        errorQueue
.
pop
();
 

    
}

}

__MACOSX/Required Project 2 Files/._listing.cc

Required Project 2 Files/parser.y
/* CMSC 430 Compiler Theory and Design
Project 2 Skeleton
UMGC CITE
Summer 2023
Project 2 Parser */
%{
#include
using namespace std;
#include “listing.h”
int yylex();
void yyerror(const char* message);
%}
%define parse.error verbose
%token IDENTIFIER INT_LITERAL CHAR_LITERAL REAL_LITERAL HEX_LITERAL
%token ADDOP MULOP EXPOP MODOP REMOP ANDOP OROP NOTOP NEGOP RELOP ARROW
%token BEGIN_ CASE CHARACTER ELSE END ENDSWITCH FUNCTION INTEGER IS LIST OF OTHERS
%token RETURNS SWITCH WHEN REAL IF THEN ENDIF ELSIF FOLD LEFT RIGHT ENDFOLD
%token REDUCE ENDREDUCE
%%
function:
function_header optional_variable body ;
function_header:
FUNCTION IDENTIFIER optional_parameters RETURNS type ‘;’ |
error ‘;’ ;
type:
INTEGER |
CHARACTER |
REAL ;

optional_variable:
variable_list |
%empty ;
variable_list:
variable_list variable |
variable;

variable:
IDENTIFIER ‘:’ type IS statement ‘;’ |
IDENTIFIER ‘:’ LIST OF type IS list ‘;’ ;
list:
‘(‘ expressions ‘)’ ;
optional_parameters:
parameters |
%empty;
parameters:
parameters ‘,’ parameter |
parameter;
parameter:
IDENTIFIER ‘:’ type;
expressions:
expressions ‘,’ expression|
expression ;
body:
BEGIN_ statement_ END ‘;’ ;
statement_list:
statement_list statement_ |
statement_;
statement_:
statement ‘;’ |
error ‘;’ ;

statement:
expression |
WHEN condition ‘,’ expression ‘:’ expression |
SWITCH expression IS cases OTHERS ARROW statement ‘;’ ENDSWITCH ;|
IF condition THEN statement_list elsif_statements ELSE statement_list ENDIF |
FOLD direction operator list_choice ENDFOLD ;
elsif_statements:
elsif_statements ELSIF condition THEN statement_list |
%empty;
cases:
cases case_ |
%empty ;
case_:
case ‘;’ |
error ‘;’ ;
case:
CASE INT_LITERAL ARROW statement ;
direction:
LEFT |
RIGHT;
operator:
ADDOP |
MULOP;
list_choice:
list |
IDENTIFIER;
condition:
condition ANDOP logical |
condition OROP logical |
logical;
logical:
NOTOP relation |
relation;
relation:
‘(‘ condition ‘)’ |
expression RELOP expression ;
expression:
expression ADDOP term |
term ;

term:
term MULOP exponentiation |
term MODOP exponentiation |
exponentiation;
exponentiation:
exponentiation EXPOP primary |
primary;
primary:
‘(‘ expression ‘)’ |
NEGOP primary |
INT_LITERAL |
CHAR_LITERAL |
REAL_LITERAL |
HEX_LITERAL |
IDENTIFIER ‘(‘ expression ‘)’ |
IDENTIFIER ;
%%
void yyerror(const char* message) {
appendError(SYNTAX, message);
}
int main(int argc, char *argv[]) {
firstLine();
yyparse();
lastLine();
return 0;
}

__MACOSX/Required Project 2 Files/._parser.y

Required Project 2 Files/listing.h

// This file contains the function prototypes for the functions that produce
// the compilation listing
enum ErrorCategories {LEXICAL, SYNTAX, GENERAL_SEMANTIC, DUPLICATE_IDENTIFIER,
UNDECLARED};
void firstLine();
void nextLine();
int lastLine();
void appendError(ErrorCategories errorCategory, string message);

__MACOSX/Required Project 2 Files/._listing.h

Here is the recommended approach for project 3.

1) Study the skeleton project provided, build it and run it so that you understand how semantic

actions are used to perform the evaluation needed to interpret programs in our language.

2) You should incorporate the new features that are in the skeleton into your version of project 2

and be sure that it builds and runs just as the skeleton did. Then confirm that test cases

test1.txt – test4.txt that were provided as test cases for the skeleton code produce the

correct output. Note that changes are required to both parser.y and scanner.l. You are likely

to get type clash warnings from bison initially. These will be resolved once the entire project is

completed.

3) Make additions as defined by the specification incrementally. Start with adding the code to

evaluate real literals and the hexadecimal integer literals. These changes involve modifications to

scanner.l. There is a predefined C++ function atof that will convert a string containing a real

literal to a double. But you will need to write a function that converts a string containing a

hexadecimal integer to an int. Once you have made these modifications use test5.txt test

them. Shown below is the output that should result when using that test case as

input:

$ ./compile < test5.txt

1 // Function with Arithmetic Expression using Real Literals

2 // and Hexadecimal Integer Literals

3

4 function main returns real;

5 begin

6 .83e+2 + 2.5E-1 + (4.3E2 + #aF2) * .01;

7 end;

Compiled Successfully

Result = 115.57

4) Next, add the code to scanner.l to evaluate character literals that includes both ordinary

character literals and the escape characters. As with the hexadecimal integer literals, you will

need to write a function to perform this conversion. Once you have made this modification use

test6.txt test it. Shown below is the output that should result when using that test case as

input:

1 // Function with Character Literal Escape Characters

2

3 function main returns character;

4 lines: integer is 60;

5 begin

6 when lines < 60, '\n' : '\f';

7 end;

Compiled Successfully

Result = 12

5) Next add the necessary semantic actions for each of the new arithmetic operators. Create

individual test cases to test each new operator. Once you have verified that the operators are

evaluated correctly in those cases, use test7.txt, which will test all of them along with their

precedence. Modifications to scanner.l, parser.y, values.h and values.cc are required

Shown below is

the output that should result when using that

test case as input:

$ ./compile < test7.txt

1 // Tests All Arithmetic Operators

2

3 function main returns integer;

4 begin

5 9 + 2 – (5 + ~1) / 2 % 3 * 3 ^ 1 ^ 2;

6 end;

Compiled Successfully

Result = 5

6). Do the relational operators next. As before it is a good idea to create individual test cases to

test each new operator. Finally the two logical operators | and ! testing each with separate test

cases. Once you have added all the new operators use test8.txt to test them. Shown below is

the output

that should result when using that test case as input:

$ ./compile < test8.txt

1 // Test Logical and Relational Operators

2

3 function main returns integer;

4 begin

5 when !(6 <> 7) & 5 + 4 >= 9 | 6 = 5, 6 + 9 * 3 : 8 – 2 ^ 3;

6 end;

Compiled Successfully

Result = 0

7) The if statement would be a good next step. Study how the when statement is implemented

using the conditional expression operator. A similar approach should be used here. Also study

how the case statements are implemented. The elsif statements should be done in a similar

fashion. Use test9.txt to test it. Shown below is the output that should result when using that

test case as input:

$ ./compile < test9.txt

1 // Function with an If Statement

2

3 function main returns integer;

4 a: integer is 28;

5 begin

6 if a < 10 then

7 1;

8 elsif a < 20 then

9 2;

10 elsif a < 30 then

11 3;

12 else

13 4;

14 endif;

15 end;

Compiled Successfully

Result = 3

To ensure all cases work correctly, modify the value of the variable a, so each case is tested.

8) Test multiple variable declarations next. No modifications should be needed provided you are

using the grammar from project 2. Use test10.txt to confirm that they work correctly. Shown

below is

the output that should result when using that test case as input:

$ ./compile < test10.txt

1 — Multiple Variable Initializations

2

3 function main returns character;

4 b: integer is 5 + 1 – 4;

5 c: real is 2 + 3.7;

6 d: character is ‘A’;

7 begin

8 if b + 1 – c > 0 then

9 d;

10 else

11 ‘\n’;

12 endif;

13 end;

Compiled Successfully

Result = 10

9) Next make the changes necessary for programs that contain parameters. The parameters are in

the command line arguments, argv. The prototoype of main is:

int main(int argc, char *argv[])

Declare a global array, which is dynamically allocated based on argc, at the top of parser.y. In

main convert each command line argument to a double and store it into that global array. The

function atof will do the conversion of a char* to a double. In the semantic action for the

parameter production, retrieve the value of the corresponding parameter from the global array

and store its value in the symbol table.

Use test11.txt and test12.txt to test that change. Shown below is the output that should

result when using both test cases as input:

$ ./compile < test11.txt 6.8

1 // Single Parameter Declaration

2

3 function main a: real returns real;

4 begin

5 a + 1.5;

6 end;

Compiled Successfully

Result = 8.3

$ ./compile < test12.txt 16 15.9

1 // Two parameter declarations

2

3 function main a: integer, b: real returns real;

4 begin

5 if a < #A then

6 b + 1;

7 else

8 b – 1;

9 endif;

10 end;

Compiled Successfully

Result = 14.9

10) Save the fold statement for last. It is likely the most unfamiliar statement. Be sure to read

the description in the requirements on how such statements are evaluated. Creating a new

function in values.cc to evaluate the fold statement is the best approach.

Use test13.txt to test the right fold statement using a list variable.. Shown below is the output

that should result when using that test case as input:

$ ./compile < test13.txt

1 // Test Right Fold

2

3 function main returns integer;

4 values: list of integer is (3, 2, 1);

5 begin

6 fold right – values endfold;

7 end;

Compiled Successfully

Result = 2

Use test14.txt to test the left fold statement using a list literal. . Shown below is the output

that should result when using that test case as input:

$ ./compile < test14.txt

1 // Test Left Fold

2

3 function main returns integer;

4 begin

5 fold left – (3, 2, 1) endfold;

6 end;

Compiled Successfully

Result = 0

11) The final test cases, test15.txt contains all the statements in the language. Shown below is

the output that should result when using that test case as input:

$ ./compile < test15.txt 1 2.5 65

1 // Test that Includes All Statements

2

3 function main a: integer, b: real, c: character returns real;

4 d: integer is when a > 0, #A: #A0;

5 e: list of integer is (3, 2, 1);

6 f: integer is

7 switch a is

8 case 1 => fold left – e endfold;

9 case 2 => fold right – e endfold;

10 others => 0;

11 endswitch;

12 g: integer is

13 if c = ‘A’ & b > 0 then

14 a * 2;

15 elsif c = ‘B’ | b < 0 then

16 (a ^ 2) * 10;

17 else

18 0;

19 endif;

20 begin

21 f + (d – 1) % g;

22 end;

Compiled Successfully

Result = 1

All of the test cases discussed above are included in the attached .zip file.

You are certainly encouraged to create any other test cases that you wish to incorporate in your

test plan. Keep in mind that your compiler should produce the correct output for all syntactically

correct programs, so it is recommended that you choose some different test cases as a part of

your test plan. Your instructor may use a comparable but different set of test cases when testing

your project.

CMSC 430 Project 3

The third project involves modifying the attached interpreter so that it interprets programs for the

complete language.

When the program is run on the command line, the parameters to the function should be supplied

as command line arguments. For example, for the following function header of a program in the

file text.txt:

function main x: integer, y: integer returns character;

One would execute the program as follows:

$ ./compile < test.txt 10 -10

In this case, the parameter x would be initialized to 10 and the parameter y to -10. An example

of a program execution is shown below:

$ ./compile < test.txt 10 -10

1 // Determines the quadrant of a point on the x-y plane

2

3 function main x: integer, y: integer returns character;

4 begin

5 if x > 0 then

6 if y > 0 then

7 ‘1’;

8 elsif y < 0 then

9 ‘4’;

10 else

11 ‘Y’;

12 endif;

13 elsif x < 0 then

14 if y > 0 then

15 ‘3’;

16 elsif y < 0 then

17 ‘2’;

18 else

19 ‘Y’;

20 endif;

21 else

22 if y <> 0 then

23 ‘X’;

24 else

25 ‘O’;

26 endif;

27 endif;

28 end;

Compiled Successfully

Result = 52

After the compilation listing is output, the value of the expression which comprises the body of

the function should be displayed as shown above.

The existing code evaluates some of the arithmetic, relational and logical operators together with

the case statement and decimal integer and real literals only. You are to add the necessary code

to include all of the following:

 Hexadecimal integer and character literals that include escape characters

 All additional arithmetic operators

 All additional relational and logical operators

 Both if and fold statements

 Functions with multiple variables

 Functions with parameters

The fold statement repeatedly applies the specified operation to the list of values, producing one

final value. A left fold associates the operator left to right and a right fold right to left. For

example, the following left fold:

fold left – (3, 2, 1) endfold;

would be evaluated as ((3 – 2) – 1) = 0, but using a right fold:

fold right – (3, 2, 1) endfold;

It would be evaluated as (3 – (2 – 1)) = 2. For operations that are associative, the result would be

the same whether it is as folded to the left or right.

This project requires modification to the bison input file, so that it defines the additional the

necessary computations for the above added features. You will need to add functions to the

library of evaluation functions already provided in values.cc. You must also make some

modifications to the functions already provided.

You are to submit two files.

1. The first is a .zip file that contains all the source code for the project. The .zip file

should contain the flex input file, which should be a .l file, the bison file, which should

be a .y file, all .cc and .h files and a makefile that builds the project.

2. The second is a Word document (PDF or RTF is also acceptable) that contains the

documentation for the project, which should include the following:

a. A discussion of how you approached the project

b. A test plan that includes test cases that you have created indicating what aspects

of the program each one is testing and a screen shot of your compiler run on that

test case

c. A discussion of lessons learned from the project and any improvements that could

be made