Compiler and Interpreter Assignments Overview
T
D
D
D
5
5
-
C
o
m
p
i
l
e
r
s
a
n
d
I
n
t
e
r
p
r
e
t
e
r
s
L
e
s
s
o
n
3
Zeinab Ganjei (zeinab.ganjei@liu.se)
Department of Computer and Information Science
Linköping University
1
.
G
r
a
m
m
a
r
s
a
n
d
T
o
p
-
D
o
w
n
P
a
r
s
i
n
g
•
Some grammar rules are given
•
Your task:
₋
Rewrite the grammar (eliminate left recursion, etc.)
₋
Add attributes and attribute rules to the grammar
₋
Implement your grammar in a C++ class named
Parser
.
The
Parser
class should contain a method named
Parse
that returns the value of a single statement in the
language.
2
.
S
c
a
n
n
e
r
S
p
e
c
i
f
i
c
a
t
i
o
n
•
Finish a scanner specification given in a
scanner.l
flex file, by adding rules for C and C++ style
comments, identifiers, integers, and floating point
numbers.
3
.
P
a
r
s
e
r
G
e
n
e
r
a
t
o
r
s
•
Finish a parser specification given in a
parser.y
bison
file, by adding rules for expressions, conditions and
function definitions, .... You also need to augment
the grammar with error productions.
4
.
I
n
t
e
r
m
e
d
i
a
t
e
C
o
d
e
G
e
n
e
r
a
t
i
o
n
•
The purpose of this assignment to learn about how
abstract syntax trees can be translated into
intermediate code.
•
You are to finish a generator for intermediate code
by adding rules for some language statements.
Laboratory Skeleton
~
TDDD55
/lab
/doc
Documentation for the assignments.
Contains all the necessary files to complete assignment
three and four
Bison – Parser Generator
P
u
r
p
o
s
e
o
f
a
P
a
r
s
e
r
•
The parser accepts tokens from the scanner and verifies the
syntactic correctness of the program.
₋
Syntactic correctness is judged by verification against a formal
grammar which specifies the language to be recognized.
•
Along the way, it also derives information about the program
and builds a fundamental data structure known as parse tree
or abstract syntax tree (ast).
•
The abstract syntax tree is an internal representation of the
program and augments the symbol table.
B
o
t
t
o
m
-
U
p
P
a
r
s
i
n
g
•
Recognize the components of a program and then combine
them to form more complex constructs until a whole
program is recognized.
•
The parse tree is then built from the bottom and up, hence
the name.
B
o
t
t
o
m
-
U
p
P
a
r
s
i
n
g
(
2
)
:=
x
*
+
a
b
c
X
:= (
a
+
b
) *
c
;
L
R
P
a
r
s
i
n
g
•
A Specific bottom-up parsing technique
₋
LR stands for Left to right scan, Rightmost derivation.
₋
Probably the most common & popular parsing technique.
₋
yacc, bison, and many other parser generation tools utilize LR
parsing.
₋
Great for machines, not so great for humans
P
r
o
s
a
n
d
C
o
n
s
o
f
L
R
p
a
r
s
i
n
g
•
Advantages of LR:
₋
Accepts a wide range of grammars/languages
₋
Well suited for automatic parser generation
₋
Very fast
₋
Generally easy to maintain
•
Disadvantages of LR:
₋
Error handling can be tricky
₋
Difficult to use manually
B
i
s
o
n
•
Bison
is a general-purpose parser generator that converts a
grammar description of a context-free grammar into a
C
program to parse that grammar
•
Similar idea to flex
B
i
s
o
n
(
2
)
•
Input: a specification file containing mainly the grammar
definition
•
Output: a C source file containing the parser
•
The entry point is the function int yyparse();
₋
yyparse reads tokens by calling yylex and parses until
•
end of file to be parsed, or
•
unrecoverable syntax error occurs
₋
returns 0 for success and 1 for failure
B
i
s
o
n
U
s
a
g
e
B
i
s
o
n
S
p
e
c
i
f
i
c
a
t
i
o
n
F
i
l
e
•
A Bison specification is composed of 4 parts.
%{/* C declarations */
%}
/* Bison declarations */
%%
/* Grammar rules */
%%
/* Additional C code */
1
.
1
.
C
D
e
c
l
a
r
a
t
i
o
n
s
•
Contains macro definitions and declarations of functions and
variables that are used in the actions in the grammar rules
•
Copied to the beginning of the parser file so that they
precede the definition of yyparse
•
Use #include to get the declarations from a header file. If C
declarations isn’t needed, then the %{ and %} delimiters canbe omitted
1
.
2
.
B
i
s
o
n
D
e
c
l
a
r
a
t
i
o
n
s
•
Contains:
₋
declarations that define terminal and non-terminal
symbols
₋
Data types of semantic values of various symbols
₋
specify precedence
B
i
s
o
n
S
p
e
c
i
f
i
c
a
t
i
o
n
F
i
l
e
•
A Bison specification is composed of 4 parts.
%{/* C declarations */
%}
/* Bison declarations */
%%
/* Grammar rules */
%%
/* Additional C code */
2
.
G
r
a
m
m
a
r
R
u
l
e
s
•
Contains one or more Bison grammar rules
•
Example:
₋
expression : expression ‘+’ term { $$ = $1 + $3; } ;•
There must always be at least one grammar rule, and the
first %% (which precedes the grammar rules) may never be
omitted even if it is the first thing in the file.
B
i
s
o
n
S
p
e
c
i
f
i
c
a
t
i
o
n
F
i
l
e
•
A Bison specification is composed of 4 parts.
%{/* C declarations */
%}
/* Bison declarations */
%%
/* Grammar rules */
%%
/* Additional C code */
3
.
A
d
d
i
t
i
o
n
a
l
C
C
o
d
e
•
Copied verbatim to the end of the parser file, just as the C
declarations section is copied to the beginning.
•
This is the most convenient place to put anything that should
be in the parser file but isn’t needed before the definition of
yyparse().
•
The definitions of yylex() and yyerror() often go here.
B
i
s
o
n
E
x
a
m
p
l
e
1
–
P
a
r
s
i
n
g
s
i
m
p
l
e
m
a
t
h
e
m
a
t
i
c
a
l
e
x
p
r
e
s
s
i
o
n
s
%{#include <ctype.h> /* standard C declarations here */
double int yylex();
}%
%token DIGIT /* bison declarations */
%%
/* Grammar rules */
line : expr ‘\n’
{ printf { “%d\n”, $1 }; };expr : expr ‘+’ term
{ $$ = $1 + $3; }| term
{ $$ = $1; } ;term : term ‘*’ factor
{ $$ = $1 * $3; }| factor
{ $$ = $1; } ;factor : ‘(‘ expr ’)’
{ $$ = $2; }| DIGIT ;
B
i
s
o
n
E
x
a
m
p
l
e
1
(
c
o
n
t
)
%%
/* Additional C code */
int yylex () {/* A really simple lexical analyzer */
int c = getchar ();
if ( isdigit (c) ) {yylval = c - ’0’ ;
return DIGIT;
}
return c;
}
B
i
s
o
n
E
x
a
m
p
l
e
2
–
M
i
d
-
R
u
l
e
s
thing
: A { printf(“seen an A”); } B ;The same as:
thing
: A fakename B ;
fakename: /* empty */ { printf(“seen an A”); } ;B
i
s
o
n
E
x
a
m
p
l
e
3
–
S
i
m
p
l
e
C
a
l
c
u
l
a
t
o
r
%{#define YYSTYPE double
#include <math.h>
%}
/* BISON Declarations */
%token NUM
/*introduce precedence and associativity */
%left '-' '+'
%left '*' '/‘
%right '^' /* exponentiation */
%%
B
i
s
o
n
E
x
a
m
p
l
e
3
(
c
o
n
t
)
input: /* empty string */
| input line ;
line: '\n'
| expr '\n' { printf ("\t%.10g\n", $1); };expr : NUM
{ $$ = $1; }| expr '+' expr
{ $$ = $1 + $3; }| expr '-' expr
{ $$ = $1 - $3; }| expr '*' expr
{ $$ = $1 * $3; }| expr '/' expr
{ $$ = $1 / $3; }| expr '^' expr
{ $$ = pow ($1, $3); } | '(' expr ')‘{ $$ = $2; };
%%
S
y
n
t
a
x
E
r
r
o
r
s
•
Error productions can be added to the specification
•
They help the compiler to recover from syntax errors and to
continue to parse
•
In order for the error productions to work we need at least
one valid token after the error symbol
•
Example:
₋
functionCall : ID ‘(‘ paramList ‘)’
| ID ‘(‘ error ‘)’
•
Recover from syntax errors by discarding tokens until it reaches
the valid token.
U
s
i
n
g
B
i
s
o
n
W
i
t
h
F
l
e
x
•
Bison and flex are designed to work together
•
Bison produces a driver program called yylex()
₋
#include “lex.yy.c” in the last part of bison specification
₋
this gives the program yylex access to bisons’ token
names
U
s
i
n
g
B
i
s
o
n
w
i
t
h
F
l
e
x
(
2
)
•
Thus, do the following:
₋
flex scanner.l
₋
bison parser.y
₋
cc y.tab.c -ly -ll
•
This will produce an a.out which is a parser with an
integrated scanner included
L
a
b
o
r
a
t
o
r
y
A
s
s
i
g
n
m
e
n
t
3
P
a
r
s
e
r
G
e
n
e
r
a
t
i
o
n
•
Finnish a parser specification given in a
parser.y
bison file, by
adding rules for expressions, conditions and function
definitions, ....
F
u
n
c
t
i
o
n
s
•
Outline:
function : funcnamedecl parameters ‘:’ type variables functions
block ‘;’
{// Set the return type of the function
// Set the function body
// Set current function to point to the parent again
} ;
funcnamedecl : FUNCTION id
{// Check if the function is already defined, report error if so
// Create a new function information and set its parent to
current function
// Link the newly created function information to the current
function
// Set the new function information to be the current function
} ;
E
x
p
r
e
s
s
i
o
n
s
•
For precedence and associativity you can
factorize the rules for expressions …
•
Or specify precedence and associativy at the
top of the Bison specification file, in the
Bison Declarations section. Read more about
this in the Bison reference.
E
x
p
r
e
s
s
i
o
n
s
(
2
)
•
Example with factoring:
expression
: expression ‘+’ term
{// If any of the sub-expressions is NULL, set $$ to
NULL
// Create a new Plus node and return in $$
//IntegerToReal casting might be needed
}
|
...
L
a
b
o
r
a
t
o
r
y
A
s
s
i
g
n
m
e
n
t
4
I
n
t
e
r
m
e
d
i
a
t
e
c
o
d
e
I
n
t
e
r
m
e
d
i
a
t
e
C
o
d
e
•
Closer to machine code, but not machine
specific
•
Can handle temporary variables.
•
Means higher portability, intermediate code
can easier be expanded to assembly code.
•
Offers the possibility of performing code
optimizations such as register allocation.
I
n
t
e
r
m
e
d
i
a
t
e
C
o
d
e
•
Why do we use intermediate languages?
•
Retargeting - build a compiler for a new
machine by attaching a new code generator
to an existing front-end and middle-part
•
Optimization - reuse intermediate code
optimizers in compilers for different
languages and different machines
•
Code generation - for different source
languages can be combined
I
n
t
e
r
m
e
d
i
a
t
e
L
a
n
g
u
a
g
e
s
•
Infix notation
•
Postfix notation
•
Three address code
₋
Triples
₋
Quadruples
Q
u
a
d
r
u
p
l
e
s
•
You will use quadruples as intermediate
language where an instruction has four
fields:
operator
operand1
operand2
result
G
e
n
e
r
a
t
i
o
n
o
f
I
n
t
e
r
m
e
d
i
a
t
e
C
o
d
e
program
example;
const
PI =
3.14159;
var
a :
real
;
b :
real
;
begin
b
:
= a
+
PI;
end
.
Q
u
a
d
r
u
p
l
e
s
(A + B) * (C + D) - E
I
n
t
e
r
m
e
d
i
a
t
e
C
o
d
e
G
e
n
e
r
a
t
i
o
n
•
The purpose of this assignment is to learn
how abstract syntax trees can be translated
into intermediate code.
•
You are to finish a generator for intermediate
code (quadruples) by adding rules for some
language constructs.
•
You will work in the file
codegen.cc
.
B
i
n
a
r
y
O
p
e
r
a
t
i
o
n
s
•
In function
BinaryGenerateCode
:
₋
Generate code for left expression and right
expression.
₋
Generate either a
realop
or
intop
quadruple
•
Type of the result is the same as the type of the operands
•
You can use
currentFunction->TemporaryVariable
A
r
r
a
y
R
e
f
e
r
e
n
c
e
s
•
The absolute address is computed as follows:
₋
absAdr = baseAdr + arrayTypeSize * index
•
Generate code for the index expression
•
You must then compute the absolute address
₋
You will have to create several temporary variables
(of integer type) for intermediate storage
₋
Generate a quadruple
iaddr
with
id
variable as input
for getting the base address
₋
Create a quadruple for loading the size of the type in
question to a temporary variable
₋
Then generate
imul
and
iadd
quadruples
₋
Finally generate either a
istore
or
rstore
quadruple
I
f
S
t
a
t
e
m
e
n
t
•
S
if E then S
1
•
S
if E then S
1
else S
2
W
H
I
L
E
S
t
a
t
e
m
e
n
t
•
S
while E do S
1
In this overview, you will find information about various assignments related to compilers and interpreters. From rewriting grammar rules to implementing parsers, scanner specifications, parser generators, and intermediate code generation tasks are covered. The assignments involve tasks like eliminating left recursion, adding attributes, implementing in C++, and adding rules for expressions and function definitions. The laboratory skeleton provides documentation and necessary files for completing the assignments.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
TDDD55 TDDD55- - Compilers Compilers and Interpreters Lesson 3 and Interpreters Zeinab Ganjei (zeinab.ganjei@liu.se) Department of Computer and Information Science Link ping University
1. Grammars and Top 1. Grammars and Top- -Down Parsing Down Parsing Some grammar rules are given Your task: Rewrite the grammar (eliminate left recursion, etc.) Add attributes and attribute rules to the grammar Implement your grammar in a C++ class named Parser. The Parser class should contain a method named Parse that returns the value of a single statement in the language.
2. Scanner Specification 2. Scanner Specification Finish a scanner specification given in a scanner.l flex file, by adding rules for C and C++ style comments, identifiers, integers, and floating point numbers.
3. Parser Generators 3. Parser Generators Finish a parser specification given in a parser.y bison file, by adding rules for expressions, conditions and function definitions, .... You also need to augment the grammar with error productions.
4. Intermediate Code Generation 4. Intermediate Code Generation The purpose of this assignment to learn about how abstract syntax trees can be translated into intermediate code. You are to finish a generator for intermediate code by adding rules for some language statements.
Laboratory Skeleton ~TDDD55 /lab /doc Documentation for the assignments. /lab1 Contains all the necessary files to complete the first assignment /lab2 Contains all the necessary files to complete the second assignment /lab3-4 Contains all the necessary files to complete assignment three and four
Purpose Purpose of of a Parser a Parser The parser accepts tokens from the scanner and verifies the syntactic correctness of the program. Syntactic correctness is judged by verification against a formal grammar which specifies the language to be recognized. Along the way, it also derives information about the program and builds a fundamental data structure known as parse tree or abstract syntax tree (ast). The abstract syntax tree is an internal representation of the program and augments the symbol table.
Bottom Bottom- -Up Up Parsing Parsing Recognize the components of a program and then combine them to form more complex constructs until a whole program is recognized. The parse tree is then built from the bottom and up, hence the name.
Bottom Bottom- -Up Up Parsing Parsing(2) (2) X := ( a + b ) * c; := x * + c a b
LR Parsing LR Parsing A Specific bottom-up parsing technique LR stands for Left to right scan, Rightmost derivation. Probably the most common & popular parsing technique. yacc, bison, and many other parser generation tools utilize LR parsing. Great for machines, not so great for humans
Pros Pros and and Cons Cons of of LR parsing LR parsing Advantages of LR: Accepts a wide range of grammars/languages Well suited for automatic parser generation Very fast Generally easy to maintain Disadvantages of LR: Error handling can be tricky Difficult to use manually
Bison Bison Bison is a general-purpose parser generator that converts a grammar description of a context-free grammar into a C program to parse that grammar Similar idea to flex
Bison (2) Bison (2) Input: a specification file containing mainly the grammar definition Output: a C source file containing the parser The entry point is the function int yyparse(); yyparse reads tokens by calling yylex and parses until end of file to be parsed, or unrecoverable syntax error occurs returns 0 for success and 1 for failure
Bison Bison Usage Usage Bison source program Bison Compiler y.tab.c parser.y C Compiler y.tab.c a.out Parse tree a.out Token stream
Bison Bison Specification Specification File File A Bison specification is composed of 4 parts. %{ %} /* C declarations */ /* Bison declarations */ %% /* Grammar rules */ %% /* Additional C code */
1.1. C 1.1. C Declarations Declarations Contains macro definitions and declarations of functions and variables that are used in the actions in the grammar rules Copied to the beginning of the parser file so that they precede the definition of yyparse Use #include to get the declarations from a header file. If C declarations isn t needed, then the %{ and %} delimiters can be omitted
1.2. Bison 1.2. Bison Declarations Declarations Contains: declarations that define terminal and non-terminal symbols Data types of semantic values of various symbols specify precedence
Bison Bison Specification Specification File File A Bison specification is composed of 4 parts. %{ %} /* C declarations */ /* Bison declarations */ %% /* Grammar rules */ %% /* Additional C code */
2. 2. Grammar Grammar Rules Rules Contains one or more Bison grammar rules Example: expression : expression + term { $$ = $1 + $3; } ; There must always be at least one grammar rule, and the first %% (which precedes the grammar rules) may never be omitted even if it is the first thing in the file.
Bison Bison Specification Specification File File A Bison specification is composed of 4 parts. %{ %} /* C declarations */ /* Bison declarations */ %% /* Grammar rules */ %% /* Additional C code */
3. 3. Additional Additional C C Code Code Copied verbatim to the end of the parser file, just as the C declarations section is copied to the beginning. This is the most convenient place to put anything that should be in the parser file but isn t needed before the definition of yyparse(). The definitions of yylex() and yyerror() often go here.
Bison Bison Example Example 1 1 Parsing simple mathematical mathematical expressions expressions Parsing simple %{ #include <ctype.h> /* standard C declarations here */ double int yylex(); }% %token DIGIT /* bison declarations */ %% /* Grammar rules */ line : expr \n { printf { %d\n , $1 }; }; expr : expr + term { $$ = $1 + $3; } | term { $$ = $1; } ; term : term * factor { $$ = $1 * $3; } | factor factor : ( expr ) { $$ = $2; } | DIGIT ; { $$ = $1; } ;
Bison Bison Example Example 1 ( 1 (cont cont) ) %% /* Additional C code */ int yylex () { /* A really simple lexical analyzer */ int c = getchar (); if ( isdigit (c) ) { yylval = c - 0 ; return DIGIT; } return c; }
Bison Bison Example Example 2 2 Mid Mid- -Rules Rules thing: A { printf( seen an A ); } B ; The same as: thing: A fakename B ; fakename: /* empty */ { printf( seen an A ); } ;
Bison Bison Example Example 3 3 Simple Simple Calculator Calculator %{ #define YYSTYPE double #include <math.h> %} /* BISON Declarations */ %token NUM /*introduce precedence and associativity */ %left '-' '+' %left '*' '/ %right '^' /* exponentiation */ %%
Bison Bison Example Example 3 ( 3 (cont cont) ) input: /* empty string */ | input line ; line: '\n' | expr '\n' { printf ("\t%.10g\n", $1); }; expr : NUM | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | expr '^' expr | '(' expr ') ; %% { $$ = $1; } { $$ = $1 + $3; } { $$ = $1 - $3; } { $$ = $1 * $3; } { $$ = $1 / $3; } { $$ = pow ($1, $3); } { $$ = $2; }
Syntax Syntax Errors Errors Error productions can be added to the specification They help the compiler to recover from syntax errors and to continue to parse In order for the error productions to work we need at least one valid token after the error symbol Example: functionCall : ID ( paramList ) | ID ( error ) Recover from syntax errors by discarding tokens until it reaches the valid token.
Using Using Bison Bison With With Flex Flex Bison and flex are designed to work together Bison produces a driver program called yylex() #include lex.yy.c in the last part of bison specification this gives the program yylex access to bisons token names
Using Using Bison Bison with with Flex Flex (2) (2) Thus, do the following: flex scanner.l bison parser.y cc y.tab.c -ly -ll This will produce an a.out which is a parser with an integrated scanner included
Laboratory Assignment 3 Laboratory Assignment 3
Parser Generation Parser Generation Finnish a parser specification given in a parser.y bison file, by adding rules for expressions, conditions and function definitions, ....
Functions Functions function : funcnamedecl parameters : type variables functions block ; { Outline: // Set the return type of the function // Set the function body // Set current function to point to the parent again } ; funcnamedecl : FUNCTION id { // Check if the function is already defined, report error if so // Create a new function information and set its parent to current function // Link the newly created function information to the current function // Set the new function information to be the current function } ;
Expressions Expressions For precedence and associativity you can factorize the rules for expressions Or specify precedence and associativy at the top of the Bison specification file, in the Bison Declarations section. Read more about this in the Bison reference.
Expressions (2) Expressions (2) Example with factoring: expression : expression + term { // If any of the sub-expressions is NULL, set $$ to NULL // Create a new Plus node and return in $$ //IntegerToReal casting might be needed } | ...
Laboratory Assignment 4 Laboratory Assignment 4 Intermediate code Intermediate code
Intermediate Intermediate Code Code Closer to machine code, but not machine specific Can handle temporary variables. Means higher portability, intermediate code can easier be expanded to assembly code. Offers the possibility of performing code optimizations such as register allocation.
Intermediate Intermediate Code Code Why do we use intermediate languages? Retargeting - build a compiler for a new machine by attaching a new code generator to an existing front-end and middle-part Optimization - reuse intermediate code optimizers in compilers for different languages and different machines Code generation - for different source languages can be combined
Intermediate Intermediate Languages Languages Infix notation Postfix notation Three address code Triples Quadruples
Quadruples Quadruples You will use quadruples as intermediate language where an instruction has four fields: operator result operand1 operand2
Generation Generation of of Intermediate Intermediate Code Code program example; const PI = 3.14159; var a : real; b : real; begin b := a + PI; end. instr_list := NULL q_rplus A PI $1 q_rassign $1 - B b + q_labl 4 - - a PI
Quadruples Quadruples (A + B) * (C + D) - E operator operand1 operand2 result A B T1 + + C D T2 * T1 T2 T3 - T3 E T4
Intermediate Intermediate Code Code Generation Generation The purpose of this assignment is to learn how abstract syntax trees can be translated into intermediate code. You are to finish a generator for intermediate code (quadruples) by adding rules for some language constructs. You will work in the file codegen.cc.
Binary Binary Operations Operations In function BinaryGenerateCode: Generate code for left expression and right expression. Generate either a realop or intop quadruple Type of the result is the same as the type of the operands You can use currentFunction->TemporaryVariable
Array Array References References The absolute address is computed as follows: absAdr = baseAdr + arrayTypeSize * index Generate code for the index expression You must then compute the absolute address You will have to create several temporary variables (of integer type) for intermediate storage Generate a quadruple iaddr with id variable as input for getting the base address Create a quadruple for loading the size of the type in question to a temporary variable Then generate imul and iadd quadruples Finally generate either a istore or rstore quadruple
If Statement If Statement S if E then S1 S if E then S1 else S2
WHILE Statement WHILE Statement S while E do S1
