home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The World of Computer Software
/
World_Of_Computer_Software-02-385-Vol-1of3.iso
/
p
/
pccts.zip
/
tutorial
/
advtut.txt
< prev
next >
Wrap
Text File
|
1992-12-08
|
93KB
|
3,907 lines
PCCTS Version 1.0x Advanced Tutorial
Terence Parr, Hank Dietz, Will Cohen
School of Electrical Engineering
Purdue University
West Lafayette, IN 47907
Spring 1992
parrt@ecn.purdue.edu
hankd@ecn.purdue.edu
cohenw@ecn.purdue.edu
Constructing a translator can be viewed as an iterative refine-
ment process moving from language recognition to intermediate-form
transformation. This document presents one possible sequence of
refinements. We shall use as many features of PCCTS as is reasonable
without regards to optimality.
We will develop a compiler for a simple string manipulation
language called sc. The compiler will generate code for a simple
stack machine.
This document assumes familiarity with the concept of a parser
generator and other language recognition tools - in particular, a
passing familiarity with YACC is useful.
The development will proceed as follows:
(i) Define a grammar to recognize functions, statements, variable
definitions and expressions in sc.
(ii) Add symbol table management to the grammar developed in (i)
(iii)Add actions to translate sc into stack code for a simple stack
machine.
(iv) Construct trees as an intermediate-form.
(v) Build a code-generator to translate the trees into executable C
code.
Page 1
PCCTS Advanced Tutorial 1.0x
1. sc Language definition
sc is a simple, C-like language with only one data object type-
string. It has global variables, functions, arguments and local vari-
ables. There are no arrays or structures.
1.1. sc Expressions
Expression atoms are limited to variables, string constants
("character(s)") and function calls (function(expr)). The string con-
stants "false" or "0" represent false and true or "1" represent true.
A limited set of operators are available (from highest to lowest pre-
cedence)
- Unary operator negate. Numeric operator.
*, / Binary operators multiply and divide. Groups left-to-right.
Numeric operator.
+, - Binary operators add and subtract. Groups left-to-right.
Numeric operator except for + which is "concatenate" if one of
operands is non-numeric.
==, != Binary operators equal, not equal. Groups left-to-right.
Numeric or non-numeric.
= Binary assignment operator. Groups right-to-left. For exam-
ple, a = b = c means to assign c to b and then to a.
1.2. sc Functions and statements
Functions may have multiple local variables, but at most one
parameter. All functions implicitly return a string to the calling
function, although the value need not be used. If a return-statement
is not executed within a function, the return value for that function
is undefined. Functions are defined exactly as in C:
function(arg)
{
statement(s)
}
A function called main() must exist so that our interpreter and
compiled code knows where to begin execution. Also, main() always has
a implicitly passed parameter which contains any command-line argu-
ment.
sc has six statements.
if Conditionals have the form:
Page 2
PCCTS Advanced Tutorial 1.0x
if ( expr ) statement
whileLoops have the form:
while ( expr ) statement
{ statement(s) }
Block statements treat more than one statement as a single state-
ment as in C. However, one cannot define variables local to a
block statement.
expr;An expr can include any valid sc expression, but only expressions
involving assignments and function calls are useful.
return expr ;
This statement behaves exactly like the C return statement except
that only strings can be returned.
print expr;
Print the string described by expr to stdout.
1.3. Example
The following code is a simple sc program that computes n fac-
torial.
main(n)
{
print fact(n);
print "\n";
}
fact(n)
{
if ( n == "0" ) return "1";
return n * fact(n - "1");
}
2. Language recognition
We begin our project by constructing a parser-a program that will
recognize phrases in sc. The first two subsections describe the sc
lexicon while the later subsections present the sc grammar with and
without symbol table management.
Page 3
PCCTS Advanced Tutorial 1.0x
2.1. Lexical analysis
Our language has only strings of upper- and lower-case letters,
called WORD's, operators, string constants and a few grammatical
grouping symbols; all of which except WORD will be defined implicitly
by mentioning them in the grammar. WORD will be placed last in the
grammar-i.e. after all keywords have been defined. Since keywords are
really just strings of characters as well, they must be treated spe-
cially. When two (or more) regular expressions can be matched for the
current input text, DLG scanners resolve the ambiguity by matching the
input to the expression mentioned first in the description. Hence, we
place
#token WORD "[a-zA-Z]+"
at the bottom of the file.
Tabs, blanks and carriage-returns are all considered white space
and are to be ignored (although we wish to track line numbers). The
following ANTLR code will instruct the parser to skip over white
space.
#token "[\t\ ]+" << zzskip(); >> /* Ignore White */
#token "\n" << zzline++; zzskip(); >>
Strings are strings of characters enclosed in double-quotes. For
simplicity we will allow any character not in the ASCII range 0..0x1F
(hex) plus any "escaped" version of the same character set.
#token STRING "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
2.2. Attributes
The DLG scanner matches keywords, WORD's, etc... on the input
stream. The way ANTLR parsers access that text is though the attri-
bute mechanism. Attributes are run-time objects associated will all
grammar elements (items to the right of the : in a rule definition).
Although attributes are associated with subrules and rule references,
only those attributes linked to grammar tokens are of interest to us.
Attributes are denoted $i where i is the grammar element i positions
from the start of the alternative. The user must define an attribute
type called Attrib. This type is most often some sort of string
whether constant or dynamically allocated. For simplicity, we employ
a standard attribute type available with the PCCTS system. Attributes
are structures that contain a constant width (30 character) string.
Page 4
PCCTS Advanced Tutorial 1.0x
By placing the character array inside of a structure, the entire
string can be copied like any simple C variable. The ANTLR pseudo-op
#header is used to describe attributes and other information that must
be present in all generated C files. In our case, we simply need to
include the standard text attribute definition. This pseudo-op must
occur first in the grammar file if it exists at all.
#header <<#include "charbuf.h">>
2.3. Grammatical analysis
This subsection describes the grammatical or syntactic aspects of
sc. No symbol table management is used and therefore functions and
variables are considered simple WORD's. Later versions of the grammar
can use the tokens VAR and FUNC.
2.3.1. Definitions, variables
An sc program is a sequence of definitions-variables or func-
tions:
p : ( func | "var" def ";" )* ;
The ( )* subrule means that there are zero or more definitions. The |
operator starts a new alternative.
The grammar for a variable definitions is broken up between the
rule p and def so that def can be reused for parameter definitions (it
also makes more sense when code generation has been added).
def : WORD ;
2.3.2. Functions
sc functions follow C's format except that the default return
type is a string instead of int.
func : WORD "\(" { WORD } "\)"
"\{"
( def )*
( statement )*
"\}"
;
Page 5
PCCTS Advanced Tutorial 1.0x
Note that the parentheses and the curly-braces must be escaped with \
because they are special regular expression symbols.
2.3.3. Statements
The statements outlined in the sc language definition can be
described with
statement
: expr ";"
| "\{" ( statement )* "\}"
| "if" "\(" expr "\)" statement {"else" statement}
| "while" "\(" expr "\)" statement
| "return" expr ";"
| "print" expr ";"
;
where { } means optional.
2.3.4. Expressions
The operators and expression atoms described in the language
definition can be recognized by the following grammar fragment.
expr : WORD "=" expr
| expr0
;
expr0 : expr1 ( ("=="|"!=") expr1 )*
;
expr1 : expr2 ( ("\+"|"\-") expr2 )*
;
expr2 : expr3 ( ("\*"|"/") expr3 )*
;
expr3 : {"\-"} expr4
;
expr4 : STRING
| WORD { "\(" { expr } "\)" }
| "\(" expr "\)"
;
Rule expr is ambiguous if we only look one token into the future since
WORD can also be an expr0. However, if we were to tell ANTLR to use
two tokens, it could see that the "=" assignment operator uniquely
Page 6
PCCTS Advanced Tutorial 1.0x
identifies which alternative to match when WORD is the first token of
lookahead. Rule expr makes this grammar LL(2); but, we only use the
extra token of lookahead in expr (leaving all others LL(1)). Please
note the use of ANTLR's command-line option "-k 2" in the makefiles
presented below.
ANTLR does not have a method of explicitly outlining operator
precedence. Instead precedence is implicitly defined by the rule
invocation sequence or abstractly by the parse-tree. Rule expr calls
expr0 which calls expr1 etc... nesting more and more deeply. The pre-
cedence rule-of-thumb in ANTLR (and any LL-type parser) is: the deeper
the nesting level, the higher the precedence (the more tightly the
operator binds). Operators in the expression starting rule have the
lowest precedence whereas operators in the last rule in the expression
recursion have the highest precedence. This becomes obvious when a
parse-tree for some input text is examined.
Once again, note that the operators for sc must be escaped as
they are reserved regular expression operators as well.
Page 7
PCCTS Advanced Tutorial 1.0x
2.4. Complete ANTLR description (w/o symbol table management)
The following code is the complete ANTLR description to recognize
sc programs. Nothing is added to the symbol table and undefined
variables/functions are not flagged.
Page 8
PCCTS Advanced Tutorial 1.0x
#header <<#include "charbuf.h">>
#token "[\t\ ]+" << zzskip(); >> /* Ignore White */
#token "\n" << zzline++; zzskip(); >>
#token STRING "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
<< main() { ANTLR(p(), stdin); } >>
p : ( func | "var" def ";" )*
"@"
;
def : WORD
;
func : WORD "\(" { def } "\)"
"\{"
( "var" def ";" )*
( statement )*
"\}"
;
statement
: expr ";"
| "\{" ( statement )* "\}"
| "if" "\(" expr "\)" statement {"else" statement}
| "while" "\(" expr "\)" statement
| "return" expr ";"
| "print" expr ";"
;
expr : WORD "=" expr
| expr0
;
expr0 : expr1 ( ("==" | "!=") expr1 )*
;
expr1 : expr2 ( ("\+" | "\-") expr2 )*
;
expr2 : expr3 ( ( "\*" | "/" ) expr3 )*
;
expr3 : {"\-" } expr4
;
expr4 : STRING
| WORD { "\(" { expr } "\)" }
| "\(" expr "\)"
;
#token WORD "[a-zA-Z]+"
Page 9
PCCTS Advanced Tutorial 1.0x
2.5. Makefile
The following makefile can be used to make the above language
description into an executable file. We assume that the ANTLR
includes and standard attribute packages are located in a directory
accessible to us as tut1.g.
#
# Makefile for 1.00 tutorial (no symbol table stuff)
# ANTLR creates parser.dlg, err.c, tut1.c, tokens.h
# DLG creates scan.c, mode.h
#
CFLAGS= -I../h
GRM=tut1
SRC=scan.c $(GRM).c err.c
OBJ=scan.o $(GRM).o err.o
tutorial: $(OBJ) $(SRC)
cc -o $(GRM) $(OBJ)
# build a parser and lexical description from a language description
$(GRM).c parser.dlg : $(GRM).g
antlr -k 2 $(GRM).g
# build the scanner from a lexical description
scan.c : parser.dlg
dlg -C2 parser.dlg scan.c
Remember that make wants a tab, not spaces, in front of the action
statements (e.g. cc, antlr, ...).
2.6. Testing
After successful completion of make, the executable tut will
exist in the current directory. tut takes input from stdin. There-
fore, one parses a file via
tut < file.sc
The prompt will return without a message if no syntax errors were
discovered. However, if file contains lexical or syntactic errors,
error messages will appear. We have given no instructions related to
translation, so nothing happens if all is well.
2.7. Symbol table management
The grammar presented thus far can only recognize sc programs.
No translation is possible because it does not deal with the semantics
Page 10
PCCTS Advanced Tutorial 1.0x
of the input program only its structure. To begin semantic interpre-
tation, one must add new symbols to a symbol table. The symbols
required to "understand" an sc program are
VAR Symbol is a local (denoted with the #define constant LOCAL),
a parameter (PARAMETER) or global (GLOBAL) variable.
FUNC Symbol is a function whose level is always GLOBAL.
A symbol table record requires two fields: token which indicates
either VAR or FUNC and level which is either LOCAL, PARAMETER or GLO-
BAL.
The PCCTS system comes with a simple symbol table manager. The
source is documented well and its functions will be referenced without
explanation here. To use the functions, our grammar must include a
file called sym.h and define a symbol table structure. We shall put
the #include in the #header directive.
#header <<#include "sym.h"
#include "charbuf.h">>
The file sym.c contains the actual functions and must be linked into
your executable. Our makefile will handle this automatically. The
sym.c can be found in the support/sym subdirectory of the standard
PCCTS installation; this should be copied into the tutorial directory.
The symbol table manager requires a number of fields within the
symbol table entry. A template has been provided that the user can
copy into their work directory and modify. The template in sym.h will
be modified in our case to include the two fields mentioned above-
token and level.
typedef struct symrec {
char *symbol;
struct symrec *next, *prev, **head, *scope;
int token; /* either FUNC or VAR */
int level; /* either LOCAL, GLOBAL, PARAMETER */
int offset; /* offset from sp on the stack */
/* locals are - offset, param is 0 */
/* used only in tut4; reserved */
} Sym, *SymPtr;
We add the following definitions to the front of our grammar.
Page 11
PCCTS Advanced Tutorial 1.0x
<<
#define HashTableSize 999
#define StringTableSize 5000
#define GLOBAL 0
#define PARAMETER 1
#define LOCAL 2
static Sym *globals = NULL; /* global scope for symbols */
>>
where globals is used to track all global symbols (functions and vari-
ables). Also, to print out symbol scopes, we define a function called
pScope(Sym *p) that dumps a scope to stdout. It's implementation is
unimportant and given with the full grammar description listed below.
To initialize the symbol table, we add a function call to the symbol
table manager library yielding a new main().
main()
{
zzs_init(HashTableSize, StringTableSize);
ANTLR(p(), stdin);
}
When a variable, parameter or function is defined, we want to add
that symbol to the symbol table. We shall treat parameters like vari-
ables grammatically and use field level to differentiate between them.
When a WORD is found in rule def, we will add it to the symbol table
using the scope and level passed into def. The situation is compli-
cated slightly by the fact that a local variable may have the same
name as a global variable. Scopes are linked lists that weave through
the symbol table grouping all entries within the same scope. Our
grammar for rule def becomes:
def[Sym **scope, int level] : <<Sym *var;>> (WORD | VAR) ;
where the init-action defines a local variable called var.
To handle the definition of previously unknown symbols, we add an
action after the WORD reference.
Page 12
PCCTS Advanced Tutorial 1.0x
( WORD
<<zzs_scope($scope); /* set current scope to scope passed in */
var = zzs_newadd($1.text); /* create entry, add text of WORD to table */
var->level = $level; /* set the level to level passed in */
var->token = VAR; /* symbol is a variable */
>>
| VAR
)
To deal with a symbol defined in another scope we add the following
action to the VAR reference.
( WORD
<<...>>
| VAR
<<var = zzs_get($1.text); /* get previous definition */
if ( level != var->level ) /* make sure we have a diff scope */
{
zzs_scope($scope); /* same here as above for unknown */
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
}
else printf("redefined variable ignored: %s\n", $1.text);
>>
)
Note that this implies that the lexical analyzer will modify the token
number according to its definition in the symbol table (if any). This
is generally not a good idea, but can be quite helpful when trying to
remove nasty ambiguities in your grammar. Typically more than one
token of lookahead makes it unnecessary to use "derived" tokens. We
do so here to illustrate the interaction of lexical analyzer and
parser.
Rule p must be modified to pass a scope and level to rule def.
In addition, we will remove the global scope at the end of parsing and
print out the symbols.
p : <<Sym *p;>>
( func | "var" def[&globals, GLOBAL] ";" )*
<<p = zzs_rmscope(&globals);
printf("Globals:\n");
if ( p != NULL ) pScope(p);
>>
"@"
;
Page 13
PCCTS Advanced Tutorial 1.0x
Rule func now must create a FUNC symbol table entry and define a
VAR entry for its parameter if one exists. Rule func checks for
duplicate FUNC entries by only matching unknown WORD's. If a function
had been previously defined, its token would be FUNC.
func : <<Sym *locals=NULL, *var, *p;>>
WORD
<<zzs_scope(&globals);
var = zzs_newadd($1.text);
var->level = GLOBAL;
var->token = FUNC;
>>
"\(" { def[&locals, PARAMETER] } "\)"
"\{"
( "var" def[&locals, LOCAL] ";" )*
( statement )*
"\}"
<<p = zzs_rmscope(&locals);
printf("Locals for %s:\n", $1.text);
if ( p != NULL ) pScope(p);
>>
;
At the end of the function, we remove the local scope of variables
(and parameter if it exists) and print the symbols out to stdout.
When a WORD is encountered on the input stream, we need to look
it up in the symbol table to find out whether it is a variable (param-
eter) or a function. The token number needs to be changed accordingly
before the parser sees it so that it will not try to match a WORD.
Any WORD references in an expression that are not defined in the sym-
bol table are undefined variables. We accomplish this token "deriva-
tion" strategy by attaching an action to the regular expression for
WORD.
#token WORD "[a-zA-Z]+"
<<{
Sym *p = zzs_get(LATEXT(1));
if ( p != NULL ) NLA = p->token;
}>>
The macro LATEXT(1) is always set to the text matched on the input
stream for the current token. NLA is the next token of look-ahead.
We need to change this from WORD to whatever is found in the symbol
table.
Rules for statements and expressions do not change when adding
symbol table management because they simply apply a structure to
Page 14
PCCTS Advanced Tutorial 1.0x
grammar symbols and do not introduce new ones.
2.8. Complete ANTLR description (with symbol table management)
The following code is the complete ANTLR description to recognize
sc programs. Functions, variables and parameters are added to the
symbol table and are printed to stdout after function definitions and
at the end of the sc program.
#header <<
#include "sym.h"
#include "charbuf.h"
>>
#token "[\t\ ]+" << zzskip(); >> /* Ignore White */
#token "\n" << zzline++; zzskip(); >>
#token STRING "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
<<
#define HashTableSize 999
#define StringTableSize 5000
#define GLOBAL 0
#define PARAMETER 1
#define LOCAL 2
static Sym *globals = NULL; /* global scope for symbols */
main()
{
zzs_init(HashTableSize, StringTableSize);
ANTLR(p(), stdin);
}
pScope(p)
Sym *p;
{
for (; p!=NULL; p=p->scope)
{
printf("\tlevel %d | %-12s | %-15s\n",
p->level,
zztokens[p->token],
p->symbol);
}
}
>>
Page 15
PCCTS Advanced Tutorial 1.0x
p : <<Sym *p;>>
( func | "var" def[&globals, GLOBAL] ";" )*
<<p = zzs_rmscope(&globals);
printf("Globals:\n");
pScope(p);
>>
"@"
;
def[Sym **scope, int level]
: <<Sym *var;>>
( WORD
<<zzs_scope($scope);
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
>>
| VAR
<<var = zzs_get($1.text);
if ( $level != var->level )
{
zzs_scope($scope);
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
}
else printf("redefined variable ignored: %s\n", $1.text);
>>
)
;
Page 16
PCCTS Advanced Tutorial 1.0x
func : <<Sym *locals=NULL, *var, *p;>>
WORD
<<zzs_scope(&globals);
var = zzs_newadd($1.text);
var->level = GLOBAL;
var->token = FUNC;
>>
"\(" { def[&locals, PARAMETER] } "\)"
"\{"
( "var" def[&locals, LOCAL] ";" )*
( statement )*
"\}"
<<p = zzs_rmscope(&locals);
printf("Locals for %s:\n", $1.text);
pScope(p);
>>
;
statement
: expr ";"
| "\{" ( statement )* "\}"
| "if" "\(" expr "\)" statement
{"else" statement}
| "while" "\(" expr "\)" statement
| "return" expr ";"
| "print" expr ";"
;
Page 17
PCCTS Advanced Tutorial 1.0x
expr : VAR "=" expr
| expr0
;
expr0 : expr1 ( ( "=="
| "!="
)
expr1
)*
;
expr1 : expr2 ( ( "\+"
| "\-"
)
expr2
)*
;
expr2 : expr3 ( ( "\*"
| "/"
)
expr3
)*
;
expr3 : {"\-" } expr4
;
expr4 : STRING
| VAR
| ( FUNC
| WORD
)
"\(" { expr } "\)"
| "\(" expr "\)"
;
#token WORD "[a-zA-Z]+"
<<{
Sym *p = zzs_get(LATEXT(1));
if ( p != NULL ) NLA = p->token;
}>>
2.9. File sym.h
The following is a modification of the sym.h template provided
with PCCTS. The fields of the symbol table entry structure have aug-
mented for our purposes as outlined above.
Page 18
PCCTS Advanced Tutorial 1.0x
/* define some hash function */
#ifndef HASH
#define HASH(p, h) while ( *p != '\0' ) h = (h<<1) + *p++;
#endif
typedef struct symrec {
char * symbol;
struct symrec *next, *prev, **head, *scope;
unsigned hash;
int token; /* either FUNC or VAR */
int level; /* either LOCAL, GLOBAL, PARAMETER */
int offset; /* offset from sp on the stack */
/* locals are - offset, param is 0 */
/* used only tut4; reserved */
} Sym, *SymPtr;
void zzs_init();
void zzs_done();
void zzs_add();
Sym *zzs_get();
void zzs_del();
void zzs_keydel();
Sym **zzs_scope();
Sym *zzs_rmscope();
void zzs_stat();
Sym *zzs_new();
Sym *zzs_newadd();
char *zzs_strdup();
2.10. Makefile (for use with symbol table management)
The following makefile can be used to make the above language
description into an executable file. We assume that the ANTLR
includes and standard attribute packages are located in a directory
accessible to us as current working directory. The grammar listed
above must be in file tut2.g.
Page 19
PCCTS Advanced Tutorial 1.0x
#
# Makefile for 1.00 tutorial
# ANTLR creates parser.dlg, err.c, tut1.c
# DLG creates scan.c
#
CFLAGS= -I../h
GRM=tut2
SRC=scan.c $(GRM).c err.c sym.c
OBJ=scan.o $(GRM).o err.o sym.o
tutorial: $(OBJ) $(SRC)
cc -o $(GRM) $(OBJ)
$(GRM).c parser.dlg : $(GRM).g
antlr -k 2 $(GRM).g
scan.c : parser.dlg
dlg -C2 parser.dlg scan.c
2.11. Sample input/output
The current state of the program accepts input like the following
sample.
var i;
var j;
f(k)
{
var local;
var j;
if ( "true" ) local = "zippo";
}
g()
{
var note;
note = "1";
while ( note )
{
i = "456";
}
}
The output of our executable, tut, would be
Page 20
PCCTS Advanced Tutorial 1.0x
Locals for f:
level 2 | VAR | j
level 2 | VAR | local
level 1 | VAR | k
Locals for g:
level 2 | VAR | note
Globals:
level 0 | FUNC | g
level 0 | FUNC | f
level 0 | VAR | j
level 0 | VAR | i
Note that the parameter k is level 1 for PARAMETER and the local vari-
able local is level 2 for LOCAL.
3. Translate sc to stack code
Generating code for a stack machine is simple and can be done by
simply adding printf() actions to the grammar in the appropriate
places.
We begin with a discussion of the stack machine and how to gen-
erate code for it. Next we augment our grammar with actions to dump
stack code to stdout.
3.1. A simple stack machine for sc
Our stack machine consists of a single CPU, a finite stack of
strings, a finite memory, a stack pointer (sp) and a frame pointer
(fp). All data items used by stack programs are strings (currently
set to a maximum length of 100). Our string stack grows downwards
towards 0 from the maximum stack height.
To make implementation simple, our stack code will actually be a
sequence of macro invocations in a C program. This way C will take
care of control-flow and allocating space etc... The minimum stack
code program defines a _main and includes sc.h which contains all of
the stack code macros:
#include "sc.h"
_main()
{
BEGIN;
END;
}
The BEGIN and END macros are explained below.
Page 21
PCCTS Advanced Tutorial 1.0x
3.1.1. Functions
Every sc program requires a main which will we translate to _main
(a C function main will call _main). Other functions are translated
verbatim. The parameter to your main program will be the first com-
mand line argument when you execute your sc program (after translation
to C). If no command line argument is specified, a "" is pushed.
Parameters are pushed on the string stack before a function is
called, so no argument is needed to the resulting C function. Return
values are implicitly strings but are also returned on the string
stack - avoiding the need to define a return type of the C function.
An "instruction" (macro) called BEGIN is executed before any other in
a function. This saves the current frame pointer and then makes it
point to the argument passed into the function. END is used to
restore the frame pointer to its previous value and make the stack
pointer point to the return value. After a function call, the top of
stack is always the return value.
Arguments and local variables are at offsets to the frame
pointer. The optional argument is at offset 0. The first local vari-
able is at offset 1, the second at offset 2 and so on. Graphically,
| . |
| . |
| arg | fp + 0
| 1st local | fp - 1
| 2nd local | fp - 2
| ... |
| . |
| . |
A dummy argument is pushed by the calling function if no argument is
specified.
To translate a function,
f(arg)
{
}
we simply dump the following
Page 22
PCCTS Advanced Tutorial 1.0x
f()
{
BEGIN;
END;
}
Note that the argument disappears because we pass arguments on the
string stack not the C hardware stack.
3.1.2. Variables
Global variables of the form
var name;
are translated to
SCVAR name;
where SCVAR is a C type defined in sc.h that makes space for a sc
variable.
Local variables are allocated on the string stack and are created
at run time via the instruction LOCAL. Each execution of LOCAL allo-
cates space for one more local variable on the stack. LOCAL's must be
executed after the BEGIN but before any other stack code instruction.
The END macro resets the stack pointer so that these locals disappear
after each function invocation. For example,
main()
{
var i;
var j;
}
is translated to:
Page 23
PCCTS Advanced Tutorial 1.0x
#include "sc.h"
_main()
{
BEGIN;
LOCAL;
LOCAL;
END;
}
3.1.3. Expressions
Operator precedence is defined implicitly in top-down (LL) gram-
mars. The deeper the level of recursion, the higher the precedence.
To generate code for operators, one prints out the correct macro for
that operator after the two operators have been seen (because we are
generating code for a stack machine). If the operator is a unary
operator like negate, we wait until the operand is seen and then print
the operator. For instance, expr1,
expr1 : expr2 ( ("\+"|"\-") expr2)*
;
would be translated as:
expr1 : <<char *op;>>
expr2 ( ( "\+" <<op="ADD";>>
| "\-" <<op="SUB";>>
)
expr2
<<printf("\t%s;\n", op);>>
)*
;
where ADD and SUB are sc stack machine macros defined below.
The assignment operator groups right to left and must generate
code that duplicates itself after each assignment so that the value of
the expression is on the stack for any chained assignement. For exam-
ple,
Page 24
PCCTS Advanced Tutorial 1.0x
main()
{
var a;
var b;
a = b = "test";
}
would be translated to:
#include "sc.h"
_main() /* main() */
{
BEGIN;
LOCAL; /* var a; */
LOCAL; /* var b; */
SPUSH("test"); /* a = b = "test"; */
DUP;
LSTORE(2); /* store into b */
DUP;
LSTORE(1); /* store into a */
POP;
END;
}
Since an expression is a statement, it is possible that a value
could be left on the stack. For example,
main()
{
"expression";
}
We must pop this extraneous value off the stack:
#include "sc.h"
_main()
{
BEGIN;
SPUSH("expression");
POP;
END;
}
Page 25
PCCTS Advanced Tutorial 1.0x
3.1.4. Instructions
All instructions take operands from the stack and return results
on the stack. Some have no side effects on the stack but alter the C
program counter.
PUSH(v) Push the value of variable v onto the stack.
SPUSH(s) Push the value of the string constant s onto the stack.
LPUSH(n) Push the value of the local variable or function argument
at offset n onto the stack.
STORE(v) Pop the top of stack and store it into variable v.
LSTORE(n) Pop the top of stack and store it into local variable or
function argument at offset n.
POP Pop the top of stack; stack is one string smaller. No
side effects with data memory.
LOCAL Create space on the stack for a local variable. Must
appear after BEGIN but before any other instruction in a
function.
BRF(a) Branch, if top of stack is "false" or "0", to "address" a
(C label); top of stack is popped off.
BRT(a) Branch, if top of stack is "true" or "1", to "address" a
(C label); top of stack is popped off.
BR(a) Branch to "address" a (C label). Stack is not touched.
CALL(f) Call the function f. Returns with result on stack top.
PRINT Pop the top of stack and print the string to stdout.
RETURN Set the return value to the top of stack. Return from the
function.
EQ Perform stack[sp] = (stack[sp+1] == stack[sp]).
NEQ Perform stack[sp] = (stack[sp+1] != stack[sp]).
ADD Perform stack[sp] = (stack[sp+1] + stack[sp]).
SUB Perform stack[sp] = (stack[sp+1] - stack[sp]).
MUL Perform stack[sp] = (stack[sp+1] * stack[sp]).
DIV Perform stack[sp] = (stack[sp+1] / stack[sp]).
NEG Perform stack[sp] = -stack[sp].
Page 26
PCCTS Advanced Tutorial 1.0x
DUP Perform PUSH(stack[sp]).
BEGIN Function preamble.
END Function cleanup.
Boolean operations yield string constants "false" for false and
true for true. All other operations yield string constants represent-
ing numerical values ("3"+"4" is "7").
3.2. Examples
The sample factorial program from above,
main(n)
{
print fact(n);
print "\n";
}
fact(n)
{
if ( n == "0" ) return "1";
return n * fact(n - "1");
}
would be translated to:
#include "sc.h"
_main() /* main(n) */
{ /* { */
BEGIN;
LPUSH(0); /* print fact(n); */
CALL(fact);
PRINT;
SPUSH("\n"); /* print "\n"; */
PRINT;
END; /* } */
}
Page 27
PCCTS Advanced Tutorial 1.0x
fact() /* fact(n) */
{
BEGIN;
LPUSH(0); /* if ( n == "0" ) */
SPUSH("0");
EQ;
BRF(iflabel0);
SPUSH("1"); /* return "1"; */
RETURN;
iflabel0: ;
LPUSH(0); /* return n * fact(n - "1"); */
LPUSH(0);
SPUSH("1");
SUB;
CALL(fact);
MUL;
RETURN;
END; /* } */
}
3.3. Augmenting grammar to dump stack code
In order to generate code, we must track the offset of local
variables. To do so, we add a field, offset, to our symbol table
record:
typedef struct symrec {
char * symbol;
struct symrec *next, *prev, **head, *scope;
unsigned hash;
int token; /* either FUNC or VAR */
int level; /* either LOCAL, GLOBAL, PARAMETER */
int offset; /* offset from sp on the stack */
/* locals are negative offsets, param is 0 */
} Sym, *SymPtr;
We begin modifying our grammar by making a global variable that
tracks the offset of local variables and defining a variable to track
label numbers:
static int current_local_var_offset, LabelNum=0;
Because the translation of all programs must include the sc stack
machine definitions, we add a printf to rule p:
Page 28
PCCTS Advanced Tutorial 1.0x
p : <<Sym *p; printf("#include \"sc.h\"\n"); >>
( func | "var" def[&globals, GLOBAL] ";" )*
<< p = zzs_rmscope(&globals); >>
"@"
;
In order to generate the variable definition macros and update
the symbol table, we modify rule def as follows:
def[Sym **scope, int level]
: <<Sym *var;>>
( WORD
<<zzs_scope($scope);
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
var->offset = current_local_var_offset++;
switch(var->level) {
case GLOBAL: printf("SCVAR %s;\n", $1.text); break;
case LOCAL : printf("\tLOCAL;\n"); break;
}
>>
| VAR
<<var = zzs_get($1.text);
if ( $level != var->level )
{
zzs_scope($scope);
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
var->offset = current_local_var_offset++;
switch(var-> level) {
case GLOBAL: printf("\tSCVAR %s;\n",$1.text);break;
case LOCAL : printf("\tLOCAL;\n"); break;
}
}
else printf("redefined variable ignored: %s\n",$1.text);
>>
)
;
The function definition rule must now dump a function template to
stdout and generate the BEGIN and END macros. func must also update
current_local_var_offset. Note that the code to dump symbols is gone.
Page 29
PCCTS Advanced Tutorial 1.0x
func : <<Sym *locals=NULL, *var, *p; current_local_var_offset =0;>>
WORD
<<zzs_scope(&globals);
var = zzs_newadd($1.text);
var->level = GLOBAL;
var->token = FUNC;
if (strcmp("main",$1.text)) { printf("%s()\n",$1.text); }
else printf("_main()\n");
>>
"\(" ( def[&locals, PARAMETER]
| <<current_local_var_offset = 1;>>
)
"\)"
"\{" << printf("{\n\tBEGIN;\n"); >>
( "var" def[&locals, LOCAL] ";" )*
( statement )*
"\}" << printf("\tEND;\n}\n"); >>
<< p = zzs_rmscope(&locals); >>
;
Statements are easy to handle since expr generates most of the
code.
statement : <<int n;>>
expr ";" <<printf("\tPOP;\n");>>
| "\{" ( statement )* "\}"
| "if" "\(" expr "\)" << n = LabelNum++;
printf("\tBRF(iflabel%d);\n",n); >>
statement << printf("iflabel%d: ;\n",n); >>
{"else" statement}
|
"while" << n = LabelNum++;
printf("wbegin%d: ;\n", n); >>
"\(" expr "\)" << printf("\tBRF(wend%d);\n",n); >>
statement << printf("\tBR(wbegin%d);\n", n); >>
<< printf("wend%d: ;\n",n); >>
<< n++; >>
| "return" expr ";" << printf("\tRETURN;\n"); >>
| "print" expr ";" << printf("\tPRINT;\n"); >>
;
3.4. Full translator
The following grammar accepts programs in sc and translates them
into stack code.
Page 30
PCCTS Advanced Tutorial 1.0x
#header <<#include "sym.h"
#include "charbuf.h"
>>
#token "[\t\ ]+" << zzskip(); >> /* Ignore White */
#token "\n" << zzline++; zzskip(); >>
#token STRING "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
<<
#define HashTableSize 999
#define StringTableSize 5000
#define GLOBAL 0
#define PARAMETER 1
#define LOCAL 2
static Sym *globals = NULL; /* global scope for symbols */
static int current_local_var_offset, LabelNum=0;
main()
{
zzs_init(HashTableSize, StringTableSize);
ANTLR(p(), stdin);
}
pScope(p)
Sym *p;
{
for (; p!=NULL; p=p->scope)
{
printf("\tlevel %d | %-12s | %-15s\n",
p->level,
zztokens[p->token],
p->symbol);
}
}
>>
Page 31
PCCTS Advanced Tutorial 1.0x
p : <<Sym *p; printf("#include \"sc.h\"\n"); >>
( func | "var" def[&globals, GLOBAL] ";" )*
<< p = zzs_rmscope(&globals); >>
"@"
;
def[Sym **scope, int level]
: <<Sym *var;>>
( WORD
<<zzs_scope($scope);
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
var->offset = current_local_var_offset++;
switch(var->level) {
case GLOBAL: printf("SCVAR %s;\n", $1.text); break;
case LOCAL : printf("\tLOCAL;\n"); break;
}
>>
| VAR
<<var = zzs_get($1.text);
if ( $level != var->level )
{
zzs_scope($scope);
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
var->offset = current_local_var_offset++;
switch(var-> level) {
case GLOBAL: printf("\tSCVAR %s;\n", $1.text); break;
case LOCAL : printf("\tLOCAL;\n"); break;
}
}
else printf("redefined variable ignored: %s\n", $1.text);
>>
)
;
Page 32
PCCTS Advanced Tutorial 1.0x
func : <<Sym *locals=NULL, *var, *p; current_local_var_offset = 0;>>
WORD
<<zzs_scope(&globals);
var = zzs_newadd($1.text);
var->level = GLOBAL;
var->token = FUNC;
if (strcmp("main",$1.text)) { printf("%s()\n",$1.text); }
else printf("_main()\n");
>>
"\(" ( def[&locals, PARAMETER]
| <<current_local_var_offset = 1;>>
)
"\)"
"\{" << printf("{\n\tBEGIN;\n"); >>
( "var" def[&locals, LOCAL] ";" )*
( statement )*
"\}" << printf("\tEND;\n}\n"); >>
<< p = zzs_rmscope(&locals); >>
;
statement : <<int n;>>
expr ";" <<printf("\tPOP;\n");>>
| "\{" ( statement )* "\}"
| "if" "\(" expr "\)" << n = LabelNum++;
printf("\tBRF(iflabel%d);\n",n); >>
statement << printf("iflabel%d: ;\n",n); >>
{"else" statement}
|
"while" << n = LabelNum++;
printf("wbegin%d: ;\n", n); >>
"\(" expr "\)" << printf("\tBRF(wend%d);\n",n); >>
statement << printf("\tBR(wbegin%d);\n", n); >>
<< printf("wend%d: ;\n",n); >>
<< n++; >>
| "return" expr ";" << printf("\tRETURN;\n"); >>
| "print" expr ";" << printf("\tPRINT;\n"); >>
;
Page 33
PCCTS Advanced Tutorial 1.0x
expr : <<Sym *s;>>
VAR "=" expr << printf("\tDUP;\n"); >>
<<s = zzs_get($1.text);
if ( s->level != GLOBAL )
printf("\tLSTORE(%d);\n", s->offset);
else printf("\tSTORE(%s);\n", s->symbol);
>>
| expr0
;
expr0 : <<char *op;>>
expr1 ( ( "==" <<op="EQ";>>
| "!=" <<op="NEQ";>>
)
expr1
<<printf("\t%s;\n", op);>>
)*
;
expr1 : <<char *op;>>
expr2 ( ( "\+" <<op="ADD";>>
| "\-" <<op="SUB";>>
)
expr2
<<printf("\t%s;\n", op);>>
)*
;
expr2 : <<char *op;>>
expr3 ( ( "\*" <<op="MUL";>>
| "/" <<op="DIV";>>
)
expr3
<<printf("\t%s;\n", op);>>
)*
;
Page 34
PCCTS Advanced Tutorial 1.0x
expr3 : <<char *op=NULL;>>
{"\-" <<op="NEG";>>} expr4
<<if ( op!=NULL ) printf("\t%s;\n", op);>>
;
expr4 : <<Sym *s; int arg;>>
STRING << printf("\tSPUSH(%s);\n", $1.text); >>
| VAR << s = zzs_get($1.text);
if ( s->level != GLOBAL )
printf("\tLPUSH(%d);\n", s->offset);
else printf("\tPUSH(%s);\n", s->symbol);
>>
| ( FUNC <<$0=$1;>>
| WORD <<$0=$1;>>
)
"\(" { <<arg=0;>> expr <<arg=1;>> } "\)"
<<if ( !arg ) printf("\tSPUSH(\"\");\n");
printf("\tCALL(%s);\n", $1.text);>>
| "\(" expr "\)"
;
#token WORD "[a-zA-Z]+"
<<{
Sym *p = zzs_get(zzlextext);
if ( p != NULL ) NLA = p->token;
}>>
3.5. Makefile for Full Translator
The makefile is no different from the one used for the symbol
table management version of the tutorial except that we need to change
the GRM make variable as follows:
GRM=tut3
which implies that tut3.g is the file containing the third revision of
our sc translator.
3.6. Use of translator
Once the translator has been made using the makefile, it is ready
to translate sc programs. To translate and execute the factorial
example from above, we execute the following:
tut3 < fact.c > temp.c
Page 35
PCCTS Advanced Tutorial 1.0x
where fact.c is the file containing the factorial code. temp.c will
contain the translated program. It is valid C code because it is
nothing more than a bunch of macro invocations (the macros are defined
in sc.h). We can compile temp.c like any other C program:
cc temp.c
To execute the program, we type:
a.out n
where n is the number you want the factorial of. Typing:
a.out 8
yields:
40320.000000
3.7. Stack code macros - sc.h
The following file is included by any C program using the stack
code instructions outlined above.
Page 36
PCCTS Advanced Tutorial 1.0x
/* sc.h -- string C stack machine macros
*
* For use with PCCTS advanced tutorial version 1.0x
*/
#include <stdio.h>
#include <ctype.h>
#include <math.h>
/*
* The function invocation stack looks like:
*
* | . |
* | . |
* | arg | fp + 0 arg is "" if none specified
* | 1st local | fp - 1
* | 2nd local | fp - 2
* | ... |
* | . |
* | . |
*/
#define STR_SIZE 100
#define STK_SIZE 200
/* define stack */
typedef struct { char text[STR_SIZE]; } SCVAR;
static SCVAR stack[STK_SIZE];
static int sp = STK_SIZE, fp;
/* number begins with number or '.' followed by number. All numbers
* are converted to floats before comparison.
*/
#define SCnumber(a) (isdigit(a[0]) || (a[0]=='.' && isdigit(a[1])))
Page 37
PCCTS Advanced Tutorial 1.0x
#define TOS stack[sp].text
#define NTOS stack[sp+1].text
#define TOSTRUE ((strcmp(TOS, "true")==0)||(strcmp(TOS, "1")==0) \
||(SCnumber(TOS)&&atof(TOS)==1.0) )
#define TOSFALSE ((strcmp(TOS, "false")==0)||(strcmp(TOS, "0")==0) \
||(SCnumber(TOS)&&atof(TOS)==0.0) )
#define PUSH(a) {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
strcpy(stack[--sp].text, (a).text);}
#define SPUSH(a) {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
strcpy(stack[--sp].text, a);}
#define LPUSH(a) {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
stack[--sp] = stack[fp-a];}
#define CALL(f) {f();}
#define POP stack[sp++]
#define LOCAL {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
stack[--sp].text[0] = '\0';}
#define BRF(lab) if ( TOSFALSE ) {POP; goto lab;} else POP;
#define BRT(lab) if ( TOSTRUE ) {POP; goto lab;} else POP;
#define BR(lab) goto lab
#define PRINT printf("%s", POP.text)
#define RETURN {strcpy(stack[fp].text, TOS); END; return;}
#define STORE(v) {v = POP;}
#define LSTORE(off) {stack[fp-off] = POP;}
Page 38
PCCTS Advanced Tutorial 1.0x
/* operators */
#define EQ {char *a,*b; float c,d; \
a = POP.text; b = POP.text; \
if ( SCnumber(a) && SCnumber(b) ) { \
c=atof(a); d=atof(b); \
if ( c == d ) {SPUSH("true");} \
else SPUSH("false"); \
} \
else if ( strcmp(a, b)==0 ) {SPUSH("true");}\
else SPUSH("false");}
#define NEQ {SCVAR a,b; float c,d; \
a = POP.text; b = POP.text; \
if ( SCnumber(a) && SCnumber(b) ) { \
c=atof(a); d=atof(b); \
if ( c != d ) {SPUSH("true");} \
else SPUSH("false"); \
} \
else if ( strcmp(a, b)!=0 ) {SPUSH("true");}\
else SPUSH("false");}
#define ADD {SCVAR c; float a,b; \
if ( !SCnumber(NTOS) || !SCnumber(TOS) ) { \
strncat(NTOS, TOS, STR_SIZE - strlen(NTOS));\
sp++; \
} else { \
a=atof(POP.text); b=atof(POP.text);\
sprintf(c.text, "%f", a+b); PUSH(c);\
}}
#define SUB {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \
sprintf(c.text, "%f", b-a); PUSH(c);}
#define MUL {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \
sprintf(c.text, "%f", a*b); PUSH(c);}
#define DIV {SCVAR c; float a,b; a=atof(POP.text); b=atof(POP.text); \
sprintf(c.text, "%f", b/a); PUSH(c);}
#define NEG {SCVAR c; float a; a=atof(POP.text); \
sprintf(c.text, "%f", -a); PUSH(c);}
#define DUP {if ( sp==0 ) {fprintf(stderr, "stk ovf!\n"); exit(-1);} \
stack[sp-1] = stack[sp]; --sp;}
Page 39
PCCTS Advanced Tutorial 1.0x
#define BEGIN int save_fp = fp; fp = sp
#define END sp = fp; fp = save_fp;
main(argc, argv)
int argc;
char *argv[];
{
if ( argc == 2 ) {SPUSH(argv[1]);}
else SPUSH("");
CALL(_main);
POP;
}
4. Intermediate form construction
This section describes how trees can be used as an intermediate
form of the sc source program and how our tut2.g symbol table manage-
ment example can be modified to construct these trees. Example tree
constructions are given as well as the complete source.
Note that this section and the code generation section essen-
tially duplicate the translation achieved in the previous section on
stack code. We arrive at the solution from a different angle, how-
ever. This method is much more general and would be used for "real"
grammars.
4.1. Tree Construction
To construct an intermediate form (IF) representation of an sc
program, we will construct trees using the abstract syntax tree (AST)
mechanism provided with PCCTS. PCCTS supports an automatic and an
explicit tree construction mechanism; we will use both. We will aug-
ment the grammar that has the symbol table management actions -
tut2.g.
In order to use the AST mechanism within PCCTS, we must do the
following:
o Define the AST fields, AST_FIELDS, needed by the user.
o Define the default AST node constructor, zzcr_ast(), that con-
verts from a lexeme to an AST node.
o Define an explicit AST node constructor - zzmk_ast() (because we
use the explicit tree constructor mechanism also).
Our tree nodes will contain a token number to identify the node.
This token number can also be a value for which there is no
corresponding lexical item (e.g. a function call may have a node
called DefineVar). If the token indicates that the node represents a
variable or function, we must have information as to its level, offset
Page 40
PCCTS Advanced Tutorial 1.0x
from the frame pointer (if a local or parameter) and the string
representing the name of the item. This information can all be held
via:
#define AST_FIELDS int token, level, offset; char str[D_TextSize];
which will be added to the #header PCCTS pseudo-op action. Note that
D_TextSize is defined in charbuf.h.
To tell PCCTS how it should build AST nodes for use with the
automatic tree construction mechanism, we define the following macro
in the #header action:
#define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
which merely calls a function we define as follows:
create_ast(ast,attr,tok,text)
AST *ast;
Attrib *attr;
int tok;
char *text;
{
Sym *s;
ast->token = tok;
if ( tok == VAR )
{
s = zzs_get(text);
ast->level = s->level;
ast->offset = s->offset;
}
if ( tok == STRING || tok == VAR || tok == FUNC ) strcpy(ast->str, text);
}
Because of the symbol table lookup etc... we make the node constructor
a function rather than have the code replicated at each invocation of
the zzcr_ast macro.
When we explicitly construct trees, the automatic node construc-
tor is generally disabled and we must explicitly call a function to
create an AST node:
Page 41
PCCTS Advanced Tutorial 1.0x
AST *
zzmk_ast(node, token, str)
AST *node;
int token;
char *str;
{
Sym *s;
node->token = token;
if ( token == VAR )
{
s = zzs_get(str);
node->level = s->level;
node->offset = s->offset;
}
if ( tok == STRING || tok == VAR || tok == FUNC )
strcpy(node->str, str);
return node;
}
This function will be invoked when we have a grammar action with a
reference of the form #[token, string].
In order to print out the trees that we have defined, let us
define a simple function to do a preorder, lisp-like walk of our
trees:
lisp(tree)
AST *tree;
{
while ( tree!= NULL )
{
if ( tree->down != NULL ) printf(" (");
if ( tree->token == STRING ||
tree->token == VAR ||
tree->token == FUNC ) printf(" %s", tree->str);
else printf(" %s", zztokens[tree->token]);
lisp(tree->down);
if ( tree->down != NULL ) printf(" )");
tree = tree->right;
}
}
PCCTS automatically assumes that all rules will produce trees and
that all terminals within rules will result in nodes added to the
current tree. In the case of rules p, expr4, statement and func, this
is not true. We will explicitly handle the trees within these rules.
Therefore, we append a ! after the definition of these rules. We need
to decide how each sc construct will be translated to a subtree and
Page 42
PCCTS Advanced Tutorial 1.0x
when we will pass these trees off to the code generator. We will col-
lect all subtrees within a function and then, just before we remove
the symbols for that function, we will pass this tree off to lisp to
be printed; we will pass it off to the code generator when we define
it in the next section. After it has been printed, the function trees
will be destroyed. For global variable definitions, we will pass each
one individually off to lisp and then destroy the tree.
Before modifying the rules of the grammar, we must define labels
for a number of regular expressions so that the token value of that
expression can be referenced from within an action. We also define
labels for tokens which do not exist physically in a program, but are
needed for code generation.
/* Not actual terminals, just node identifiers */
#token DefineFunc
#token SLIST
/* Define tokens for code generation */
#token DefineVar "var"
#token Mul "
#token Div "/"
#token Add "+"
#token Sub "-"
#token Equal "=="
#token NotEqual "!="
#token If "if"
#token While "while"
#token Return "return"
#token Print "print"
#token Assign "="
All PCCTS grammars that use the AST mechanism need to pass the
address of a NULL pointer to the starting rule.
main()
{
AST *root=NULL;
zzs_init(HashTableSize, StringTableSize);
ANTLR(p(&root), stdin);
}
Rule p is modified as follows:
Page 43
PCCTS Advanced Tutorial 1.0x
p! : <<Sym *p; AST *v;>>
( func
| "var" def[&globals, GLOBAL] ";"
<<v = #(#[DefineVar], #2);
lisp(v); printf("\n"); zzfree_ast(v);
>>
)*
<<p = zzs_rmscope(&globals);>>
"@"
;
The #[DefineVar] reference calls our zzmk_ast macro to create an AST
node whose token is set to DefineVar. The reference to
#(#[DefineVar], #2) is a tree constructor which makes the DefineVar
node the parent of the tree returned by rule def - #2. In general,
the tree constructor has the form:
#( root, sibling1, sibling2, ..., siblingN )
where any NULL pointer terminates the list except for the root
pointer. #2 refers to the second AST node or tree within an
alternative - def in our case. Rule def itself does not change
because PCCTS automatically creates a node for the WORD or VAR and
passes it back to the invoking rule.
Trees for functions are constructed in the following form:
DefineFunc
|
v
FUNC -> DefineVar -> DefineVar -> SLIST
| | |
v | v
optional_arg | stat1 -> ... > statn
v
local1 -> ... -> localn
where DefineFunc and DefineVar are dummy tokens used only in trees (as
opposed to the grammar). Rule func is modified to build these trees:
Page 44
PCCTS Advanced Tutorial 1.0x
func! : <<Sym *locals=NULL, *var, *p; AST *f,*parm=NULL,*v=NULL,*s=NULL;
current_local_var_offset = 0;>>
WORD
<<zzs_scope(&globals);
var = zzs_newadd($1.text);
var->level = GLOBAL;
var->token = FUNC;
>>
"\(" ( def[&locals, PARAMETER] <<parm=#1;>>
| <<current_local_var_offset = 1;>>
)
"\)"
"\{"
( "var" def[&locals, LOCAL]
<<if ( v==NULL ) v = #2; else v = #(NULL,v,#2);>>
";"
)*
( statement
<<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
)*
"\}"
<<s = #(#[SLIST], s);
v = #(#[DefineVar], v);
parm = #(#[DefineVar], parm);
f = #(#[DefineFunc], #[FUNC,$1.text], parm, v, s);
lisp(f); printf("\en"); zzfree_ast(f);
p = zzs_rmscope(&locals);>>
;
Variable parm is set to the AST node created by def if a parameter is
found else it is NULL. Variable v is used to maintain a list of local
variables. The tree constructor
v = #(NULL,v,#2);
says to make a new tree with no root and with siblings v and #2 -
which effectively links #2 to the end of the current list of vari-
ables. Variable s behaves in a similar fashion. After the list of
variables and statements have been accumulated, we add a dummy node
(DefineVar, SLIST) as a root to each list so that we get the structure
given above. To examine the trees we have constructed, we make a call
to lisp and then destroy the tree.
Even though it is not necessary to do so, we will build trees for
statement explicitly (in general, the automatic mechanism is best for
expressions with simple operator/operand relationships).
Page 45
PCCTS Advanced Tutorial 1.0x
statement!: <<AST *s=NULL, *el=NULL;>>
expr ";" <<#0 = #1;>>
| "\{"
( statement
<<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
)*
"\}" <<#0 = #(#[SLIST], s);>>
| "if" "\(" expr "\)" statement
{"else" statement <<el=#2;>>} <<#0 = #(#[If], #3, #5,el);>>
| "while" "\(" expr "\)" statement <<#0 = #(#[While], #3,#5);>>
| "return" expr ";" <<#0 = #(#[Return], #2);>>
| "print" expr ";" <<#0 = #(#[Print], #2);>>
;
Many of the tokens in statement are not included in the tree because
they are a notational convenience for humans or are used for grouping
purposes. As before, we track lists of statements using the tree con-
structor: #(NULL,s,#1).
The last unusual rule is expr:
expr4! : <<AST *f=NULL, *arg=NULL;>>
STRING <<#0 = #[STRING, $1.text];>>
| VAR <<#0 = #[STRING, $1.text];>>
| ( FUNC <<f = #[FUNC, $1.text];>>
| WORD <<f = #[FUNC, $1.text];>>
)
"\(" { expr <<arg=#1;>> } "\)"
<<#0 = #(f, arg);>>
| "\(" expr "\)" <<#0 = #2;>>
;
Assigning a tree to #0 makes that tree the return tree. However, it
should really only be used in rules that do not use the automatic tree
construction mechanism; i.e. there is a ! after the rule definition.
For a function call, we make a tree with a FUNC node at the root and
the optional argument as the child. The third alternative merely
returns what is computed by expr; the parenthesis are mechanism for
syntactic precedence and add nothing to the tree. The tree structure
itself embodies the precedence.
The only other required modifications to the grammar are to indi-
cate which tokens are operators (subtree roots) and which are operands
in the expression rules. To indicate that a token is to be made a
subtree root, we append a ^. All other tokens are considered operands
(children). Appending a token with ! indicates that it is not to be
included in the tree. For example, to make trees like:
Page 46
PCCTS Advanced Tutorial 1.0x
operator
|
v
opnd1 -> opnd2
we modify the operators in expr through expr3 in a fashion similar to:
expr1 : expr2 ( ( "\+"^
| "\-"^
)
expr2
)*
;
and
expr3 : { "\-"^ } expr4
;
4.2. Full Grammar to Construct Trees
The following grammar constructs AST's as an intermediate form
(IF) of an sc program and prints out the IF in lisp-like preorder.
#header <<#include "sym.h"
#include "charbuf.h"
#define AST_FIELDS int token, level, offset; char str[D_TextSize];
#define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
#define DONT_CARE 0
#define SIDE_EFFECTS 1
#define VALUE 2
>>
#token "[\t\ ]+" << zzskip(); >> /* Ignore White */
#token "\n" << zzline++; zzskip(); >>
#token STRING "\"(~[\0-\0x1f\"\\]|(\\~[\0-\0x1f]))*\"" <<;>>
/* Not actual terminals, just node identifiers */
#token DefineFunc
#token SLIST
Page 47
PCCTS Advanced Tutorial 1.0x
/* Define tokens for code generation */
#token DefineVar "var"
#token Mul "\*"
#token Div "/"
#token Add "\+"
#token Sub "\-"
#token Equal "=="
#token NotEqual "!="
#token If "if"
#token While "while"
#token Return "return"
#token Print "print"
#token Assign "="
<<;>>
<<
#define HashTableSize 999
#define StringTableSize 5000
#define GLOBAL 0
#define PARAMETER 1
#define LOCAL 2
static Sym *globals = NULL; /* global scope for symbols */
static int current_local_var_offset=0;
create_ast(ast,attr,tok,text)
AST *ast;
Attrib *attr;
int tok;
char *text;
{
Sym *s;
ast->token = tok;
if ( tok == VAR )
{
s = zzs_get(text);
ast->level = s->level;
ast->offset = s->offset;
}
if ( tok == STRING || tok == VAR || tok == FUNC ) strcpy(ast->str, text);
}
Page 48
PCCTS Advanced Tutorial 1.0x
AST *
zzmk_ast(node, token, str)
AST *node;
int token;
char *str;
{
Sym *s;
node->token = token;
if ( token == VAR )
{
s = zzs_get(str);
node->level = s->level;
node->offset = s->offset;
}
if ( token == STRING || token == VAR || token == FUNC )
strcpy(node->str, str);
return node;
}
lisp(tree)
AST *tree;
{
while ( tree!= NULL )
{
if ( tree->down != NULL ) printf(" (");
if ( tree->token == STRING ||
tree->token == VAR ||
tree->token == FUNC ) printf(" %s", tree->str);
else printf(" %s", zztokens[tree->token]);
lisp(tree->down);
if ( tree->down != NULL ) printf(" )");
tree = tree->right;
}
}
main()
{
AST *root=NULL;
zzs_init(HashTableSize, StringTableSize);
ANTLR(p(&root), stdin);
}
Page 49
PCCTS Advanced Tutorial 1.0x
pScope(p)
Sym *p;
{
for (; p!=NULL; p=p->scope)
{
printf("\tlevel %d | %-12s | %-15s\n",
p->level,
zztokens[p->token],
p->symbol);
}
}
>>
p! : <<Sym *p; AST *v;>>
( func
| "var" def[&globals, GLOBAL] ";"
<<v = #(#[DefineVar], #2);
gen(v,DONT_CARE); printf("\n"); zzfree_ast(v);
>>
)*
<<p = zzs_rmscope(&globals);>>
"@"
;
Page 50
PCCTS Advanced Tutorial 1.0x
def[Sym **scope, int level]
: <<Sym *var;>>
( WORD
<<zzs_scope($scope);
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
var->offset = current_local_var_offset++;
>>
| VAR
<<var = zzs_get($1.text);
if ( $level != var->level )
{
zzs_scope($scope);
var = zzs_newadd($1.text);
var->level = $level;
var->token = VAR;
var->offset = current_local_var_offset++;
}
else printf("redefined variable ignored: %s\n", $1.text);
>>
)
;
func! : <<Sym *locals=NULL, *var, *p; AST *f,*parm=NULL,*v=NULL,*s=NULL;
current_local_var_offset = 0;>>
WORD
<<zzs_scope(&globals);
var = zzs_newadd($1.text);
var->level = GLOBAL;
var->token = FUNC;
>>
"\(" ( def[&locals, PARAMETER] <<parm=#1;>>
| <<current_local_var_offset = 1;>>
)
"\)"
"\{"
( "var" def[&locals, LOCAL]
<<if ( v==NULL ) v = #2; else v = #(NULL,v,#2);>>
";"
)*
( statement
<<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
)*
"\}"
<<s = #(#[SLIST], s);
v = #(#[DefineVar], v);
parm = #(#[DefineVar], parm);
f = #(#[DefineFunc], #[FUNC,$1.text], parm, v, s);
gen(f,DONT_CARE); printf("\n"); zzfree_ast(f);
p = zzs_rmscope(&locals);>>
;
Page 51
PCCTS Advanced Tutorial 1.0x
statement!: <<AST *s=NULL, *el=NULL;>>
expr ";" <<#0 = #1;>>
| "\{"
( statement
<<if ( s==NULL ) s = #1; else s = #(NULL,s,#1);>>
)*
"\}" <<#0 = #(#[SLIST], s);>>
| "if" "\(" expr "\)" statement
{"else" statement <<el=#2;>>} <<#0 = #(#[If], #3, #5, el);>>
| "while" "\(" expr "\)" statement <<#0 = #(#[While], #3, #5);>>
| "return" expr ";" <<#0 = #(#[Return], #2);>>
| "print" expr ";" <<#0 = #(#[Print], #2);>>
;
expr : VAR "="^ expr
| expr0
;
expr0 : expr1 ( ( "=="^
| "!="^
)
expr1
)*
;
expr1 : expr2 ( ( "\+"^
| "\-"^
)
expr2
)*
;
expr2 : expr3 ( ( "\*"^
| "/"^
)
expr3
)*
;
Page 52
PCCTS Advanced Tutorial 1.0x
expr3 : { "\-"^ } expr4
;
expr4! : <<AST *f=NULL, *arg=NULL;>>
STRING <<#0 = #[STRING, $1.text];>>
| VAR <<#0 = #[VAR, $1.text];>>
| ( FUNC <<f = #[FUNC, $1.text];>>
| WORD <<f = #[FUNC, $1.text];>>
)
"\(" { expr <<arg=#1;>> } "\)"
<<#0 = #(f, arg);>>
| "\(" expr "\)" <<#0 = #2;>>
;
#token WORD "[a-zA-Z]+"
<<{
Sym *p = zzs_get(LATEXT(1));
if ( p != NULL ) NLA = p->token;
}>>
4.3. Example translations
To illustrate how functions get translated, consider the follow-
ing sc program:
var a;
main(n)
{
var b;
}
Our translator would create trees represented by:
( DefineVar WORD )
( DefineFunc FUNC ( DefineVar WORD ) ( DefineVar WORD ) SLIST )
where WORD represents the variables found on the input stream. SLIST
has no child because there were no statements in the function.
Some example statement transformations follow.
if:
Page 53
PCCTS Advanced Tutorial 1.0x
if ( b == "hello" ) print n;
translates to
( If ( Equal b "hello" ) ( Print n ) )
while:
while ( i != "10" ) { print i; i = i+"1"; }
translates to
( While ( NotEqual i "10" ) ( SLIST ( Print i ) ( = i ( Add i "1" ) ) ) )
Expressions have the operator at the root and the operands as
children. For example,
i = a + "3" * "9" + f("jim");
would be translated to:
( = i ( Add ( Add a ( Mul "3" "9" ) ) ( f "jim" ) ) )
which looks like:
Page 54
PCCTS Advanced Tutorial 1.0x
=
|
v
i -> Add
|
v
Add --------------> f
| |
v v
a -> Mul "jim"
|
v
"3" -> "9"
5. Code generation from intermediate form
To translate the intermediate form (IF) to the stack code
described above, we present the following simple little code genera-
tor. We use no devious C programming to make this fast or nifty
because this document concentrates on how PCCTS grammars are developed
not on how to write spectacular C code.
5.1. Modification of tree construction grammar
To convert from the translator above that printed out trees in
lisp format, we add the following definitions needed as arguments to
gen() in the #header action.
#define DONT_CARE 0
#define SIDE_EFFECTS 1
#define VALUE 2
Also, we replace all calls to lisp(tree) with gen(tree,
DONT_CARE).
5.2. Code generator
Function gen() presented below accepts an AST as an argument and
walks the tree generating output when necessary. You will notice all
the header information needed by this file, code.c. This illustrates
one of the minor inconveniences of PCCTS. Any C file that needs to
access PCCTS variables, rules, etc... must include all of the things
that PCCTS generates at the head of all PCCTS generated files.
The code generator accepts an evaluation mode argument so that it
can remove some unnecessary code. For example,
Page 55
PCCTS Advanced Tutorial 1.0x
main()
{
"3" + f();
}
f()
{}
would result in
#include "sc.h"
_main()
{
BEGIN;
CALL(f);
POP;
END;
}
f()
{
BEGIN;
END;
}
Code to push and add "3" was eliminated because it had no side
effects. Only function calls have side effects in sc.
Page 56
PCCTS Advanced Tutorial 1.0x
/*
* Simple code generator for PCCTS 1.0x tutorial
*
* Terence Parr
* Purdue University
* Electrical Engineering
* March 19, 1992
*/
#include <stdio.h>
#include "sym.h"
#include "charbuf.h"
#define AST_FIELDS int token, level, offset; char str[D_TextSize];
#define zzcr_ast(ast,attr,tok,text) create_ast(ast,attr,tok,text)
#include "antlr.h"
#include "ast.h"
#include "tokens.h"
#include "dlgdef.h"
#include "mode.h"
#define GLOBAL 0
#define PARAMETER 1
#define LOCAL 2
static int LabelNum=0, GenHeader=0;
#define DONT_CARE 0
#define SIDE_EFFECTS 1
#define VALUE 2
gen(t,emode)
AST *t;
int emode; /* evaluation mode member { SIDE_EFFECTS, VALUE, DONT_CARE } */
{
AST *func, *arg, *locals, *slist, *a, *opnd1, *opnd2, *lhs, *rhs;
int n;
if ( t == NULL ) return;
if ( !GenHeader ) { printf("#include \"sc.h\"\n"); GenHeader=1; }
switch ( t->token )
{
Page 57
PCCTS Advanced Tutorial 1.0x
case DefineFunc :
func = zzchild(t);
arg = zzchild( zzsibling(func) );
locals = zzchild( zzsibling( zzsibling(func) ) );
slist = zzsibling( zzsibling( zzsibling(func) ) );
if ( strcmp(func->str, "main") == 0 )
printf("_%s()\n{\n\tBEGIN;\n", func->str);
else
printf("%s()\n{\n\tBEGIN;\n", func->str);
for (a=locals; a!=NULL; a = zzsibling(a)) printf("\tLOCAL;\n");
gen( slist, DONT_CARE );
printf("\tEND;\n}\n");
break;
case SLIST :
for (a=zzchild(t); a!=NULL; a = zzsibling(a))
{
gen( a, EvalMode(a->token) );
if ( a->token == Assign ) printf("\tPOP;\n");
}
break;
case DefineVar :
printf("SCVAR %s;\n", zzchild(t)->str);
break;
Page 58
PCCTS Advanced Tutorial 1.0x
case Mul :
case Div :
case Add :
case Sub :
case Equal :
case NotEqual :
opnd1 = zzchild(t);
opnd2 = zzsibling( opnd1 );
gen( opnd1, emode );
gen( opnd2, emode );
if ( emode == SIDE_EFFECTS ) break;
switch ( t->token )
{
case Mul : printf("\tMUL;\n"); break;
case Div : printf("\tDIV;\n"); break;
case Add : printf("\tADD;\n"); break;
case Sub : if ( opnd2==NULL ) printf("\tNEG;\n");
else printf("\tSUB;\n");
break;
case Equal : printf("\tEQ;\n"); break;
case NotEqual : printf("\tNEQ;\n"); break;
}
break;
case If :
a = zzchild(t);
gen( a, VALUE ); /* gen code for expr */
n = LabelNum++;
printf("\tBRF(iflabel%d);\n", n);
a = zzsibling(a);
gen( a, EvalMode(a->token) ); /* gen code for statement */
printf("iflabel%d: ;\n", n);
break;
case While :
a = zzchild(t);
n = LabelNum++;
printf("wbegin%d: ;\n", n);
gen( a, VALUE ); /* gen code for expr */
printf("\tBRF(wend%d);\n", n);
a = zzsibling(a);
gen( a, EvalMode(a->token) ); /* gen code for statement */
printf("\tBR(wbegin%d);\n", n);
printf("wend%d: ;\n", n);
break;
Page 59
PCCTS Advanced Tutorial 1.0x
case Return :
gen( zzchild(t), VALUE );
printf("\tRETURN;\n");
break;
case Print :
gen( zzchild(t), VALUE );
printf("\tPRINT;\n");
break;
case Assign :
lhs = zzchild(t);
rhs = zzsibling( lhs );
gen( rhs, emode );
printf("\tDUP;\n");
if ( lhs->level == GLOBAL ) printf("\tSTORE(%s);\n", lhs->str);
else printf("\tLSTORE(%d);\n", lhs->offset);
break;
case VAR :
if ( emode == SIDE_EFFECTS ) break;
if ( t->level == GLOBAL ) printf("\tPUSH(%s);\n", t->str);
else printf("\tLPUSH(%d);\n", t->offset);
break;
case FUNC :
gen( zzchild(t), VALUE );
printf("\tCALL(%s);\n", t->str);
break;
case STRING :
if ( emode == SIDE_EFFECTS ) break;
printf("\tSPUSH(%s);\n", t->str);
break;
Page 60
PCCTS Advanced Tutorial 1.0x
default :
printf("Don't know how to handle: %s\n", zztokens[t->token]);
break;
}
}
EvalMode( tok )
int tok;
{
if ( tok == Assign || tok == If || tok == While ||
tok == Print || tok == Return ) return VALUE;
else return SIDE_EFFECTS;
}
5.3. Makefile for code generator
This makefile is roughly the same as before except that we need
to tell PCCTS to generate tree information and we need to link in the
code generator.
CFLAGS= -I../h
GRM=tut4
SRC=scan.c $(GRM).c err.c sym.c code.c
OBJ=scan.o $(GRM).o err.o sym.o code.o
tutorial: $(OBJ) $(SRC)
cc -o $(GRM) $(OBJ)
$(GRM).c parser.dlg : $(GRM).g
antlr -k 2 -gt $(GRM).g
scan.c : parser.dlg
dlg -C2 parser.dlg scan.c
Page 61
Table of Contents
1. sc Language definition ....................................... 2
1.1. sc Expressions .................................... 2
1.2. sc Functions and statements ....................... 2
1.3. Example ........................................... 3
2. Language recognition ......................................... 3
2.1. Lexical analysis .................................. 4
2.2. Attributes ........................................ 4
2.3. Grammatical analysis .............................. 5
2.3.1. Definitions, variables ................. 5
2.3.2. Functions .............................. 5
2.3.3. Statements ............................. 6
2.3.4. Expressions ............................ 6
2.4. Complete ANTLR description (w/o symbol table
management) ..................................................... 8
2.5. Makefile .......................................... 10
2.6. Testing ........................................... 10
2.7. Symbol table management ........................... 10
2.8. Complete ANTLR description (with symbol table
management) ..................................................... 15
2.9. File sym.h ........................................ 18
2.10. Makefile (for use with symbol table management)
2.11. Sample input/output .............................. 20
3. Translate sc to stack code ................................... 21
3.1. A simple stack machine for sc ..................... 21
3.1.1. Functions .............................. 22
3.1.2. Variables .............................. 23
3.1.3. Expressions ............................ 24
3.1.4. Instructions ........................... 26
3.2. Examples .......................................... 27
3.3. Augmenting grammar to dump stack code ............. 28
3.4. Full translator ................................... 30
3.5. Makefile for Full Translator ...................... 35
3.6. Use of translator ................................. 35
3.7. Stack code macros - sc.h .......................... 36
4. Intermediate form construction ............................... 40
4.1. Tree Construction ................................. 40
4.2. Full Grammar to Construct Trees ................... 47
4.3. Example translations .............................. 53
5. Code generation from intermediate form ....................... 55
5.1. Modification of tree construction grammar ......... 55
5.2. Code generator .................................... 55
5.3. Makefile for code generator ....................... 61
Page 1