In this course, we plan to discuss the design of programming languages and the implementation tools of programming languages. We start from the parsing of programming languages. In particular, we will discuss general parsing (for arbitrary context-free languages) and incremental parsing.
In the second part we will study attribute grammars, the definition, evaluation, evaluator generation, parallel and incremental evaluation. Attribute grammars are an important tool for compilers and practical tools for software development environments.
In the third part, we will study Post system. Post systems are a foundation of many formal systems, including type systems in programming languages.
In the fourth part of the course, we study functional programming. The topics include introduction, higher-order functions, polymorphic type checking, lazy evaluation, lambda calculus, and continuation.
In the last part, we will discuss denotational semantics of programming languages. If we have time at the end of the semester, the students will be asked to present papers.
The course material will be papers from journals and conference proceedings. We will offer you a reading list and a copy of original papers.
You are asked to implement an attribute-grammar system, including both the generator and the evaluator. Our attribute grammar is called the simple-minded AG (SMAG).
A sample SMAG is as follows:
This attribute grammar is called myFirstAG.
Put comments before %SYMBOL%
Blank lines may be inserted as you wish.
%SYMBOLS%
S(synthesized r);
X(inherited a, b; synthesized c);
Y(inherited d; synthesized e);
%RULES%
S ::= X
{ r = c +3;
a = 3;
b = 5; }
X ::= X Y Y
{ X@1.c = X@2.c + Y@1.e + Y@2.e;
X@2.a = X@1.b + 1;
X@2.b = X@2.a + 3;
Y@1.d = X@1.a - X@1.b;
Y@2.d = Y@1.e - X@2.c; }
X ::= Y
{ X.c = Y.e;
Y.d = X.a - X.b; }
Y ::= "hello"
{ Y.e = Y.d + 6; }
Y ::= "good"
{ Y.e = 9 - Y.d; }
%END%
More comments may follow %END%
An SMAG contains two sections, denoted by the keywords
%SYMBOLS%, %RULES%, and %END%.
SMAG ::== %SYMBOLS% SymbolSection %RULES% RuleSection %END%
All the nonterminal symbols and their attributes must be declared in the symbol section. The SMAG generator must check this requirement. The names of symbols and attributes consist of English letters and the digits and must begin with a letter. Upper and lower case letters are considered identical. The symbol section contains one or more symbol declaration.
SymbolSection ::== Declaration | Declaration SymbolSection
A declaration has a symbol followed by the declarations of its inherited attributes followed by its synthesized attributes.
Declaration ::== name ( [ inherited NameList ; ] [ synthesized NameList ] ) ; NameList ::== name | name , Namelist
Note that inherited and synthesized are reserved
keywords and the use of the three punctuation symbols ( ; ).
The rule section contains one or more rules.
RuleSection ::== Rule | Rule RuleSection
Each rule consists of a symbol, the derivation symbol ::=,
zero or more symbols or constants, and a set of zero or more
attribution rules.
A constant is anything enclosed within a pair of double quotes.
Rule ::== name ::= NameConstList '{' AttRules '}'
NameConstList ::= | NameConst | NameConst NameConstList
NameConst ::== name | constant
AttRules ::== | AttRule | AttRule AttRules
An attribution rule consists of an attribute occurrence,
an equal sign =, and an expression.
AttRule ::== Att = Exp ;
An attribute occurrence has the form name.name or
name@integer.name.
The first name denotes a symbol in the rule.
The second name denotes an attribute of the symbol.
When there are more than one occurrence of a symbol, they are numbered
from left to right with integers, and these symbols are appended with
an integer.
Att ::== name . name | name @ integer . name
An expression has the form of usual arithmetic notations and consists of
attributes occurrences, positive integer constants, addition sign
+, and subtraction sign -.
There are no parentheses nor other operators.
Evaluation of an expression proceeds from left to right.
Though we use much simplied expressions, you should design your programs
so that it is very easy to modify in order to manipulate complex expressions.
Exp ::== AttInt | AttInt + Exp | AttInt - Exp AttInt ::== Att | integer
In this project, you are asked to implement a plan generator, a lexical analyzer of the target language, a context-free-grammar parser of the target language, and an evaluator. The plan generator generates plans for an SMAG and it must also check that an input SMAG is in the correct form and it is an ordered attribute grammar. The evaluation system parses an input sentence with the help of the lexical analyzer and the parser of the target language, evaluates the attributes and, finally, prints the values of all the attributes of the start symbol in a readable format.