CSE340
Project 2: Parsing
The goal of this project is to give you experience in writing a top-down recursive descent parser and to get
introduced to the basics of symbol tables for nested scopes.
We begin by introducing the grammar of our language. Then we will discuss the semantics of our
language that involves lexical scoping rules and name resolution. Finally, we will go over a few examples
and formalize the expected output.
NOTE: This project is significantly more involved than the first project. You should start on it immediately.
1. Lexical Specification
Here is the list of tokens that your lexical analyzer needs to support:
PUBLIC="public"
PRIVATE = "private"
EQUAL = "="
COLON = ""
COMMA = ","
SEMICOLON = "; "
LBRACE = "{"
RBRACE = "}"
ID = letter (letter + digit)*
Comments and Space
In addition to these tokens, our input programs might have comments that should be ignored by the
lexical analyzer. A comment starts with // and continues until a newline character is encountered. The
regular expressions for comments is: // (any)* \n in which any is defined to be any character except
\n. Also, like in the first project, your lexical analyzer should skip space between tokens. 2. Grammar
Here is the grammar for our input language:
program
→ global_vars scope
global_vars → ε
global_vars → var_list SEMICOLON
var_list
→ ID
var_list
→ ID COMMA var_list
scope
→ ID LBRACE public_vars private_vars stmt_list RBRACE
public_vars → ε
public_vars → PUBLIC COLON var_list SEMICOLON
private_vars → ε
private_vars → PRIVATE COLON var_list SEMICOLON
stmt_list
stmt_list
stmt
stmt
→ stmt
→ stmt stmt_list
→ ID EQUAL ID SEMICOLON
→ scope
Here is an example input program with comments:
// These are global variables
a, b, c;
test {
public:
a, b, hello;
private:
x, y;
a = b%;B
hello
=
y = r;
nested {
c;
public:
a =
b;
// These are public variables of scope test
// These are private variables of scope test
// the body of test starts with this line
// this is a nested scope
b;
// which does not have private variables
x = hello;
C = y;
// we can also have lines that only contain comments like this
}
}
Note that our grammar does not recognize comments, so our parser would not know anything about
comments, but our lexical analyzer would deal with comments. This is similar to handling of spaces by
the lexer, the lexer skips the spaces. In a similar fashion, your lexer should skip comments.
We highlight some of the syntactical elements of the language:
• Global variables are optional
• The scopes have optional public and private variables
• Every scope has a body which is a list of statements
• A statement can be either a simple assignment or another scope (a nested scope)
3. Scoping and Resolving References
Here are the scoping rules for our language:
● The public variables of a scope are accessible to its nested scopes
● The private variables of a scope are not accessible to its nested scopes
• Lexical scoping rules are used to resolve name references
• Global variables are accessible to all scopes
Every reference to a variable is resolved to a specific declaration by specifying the variable's
defining scope. We will use the following notation to specify declarations:
•
If variable a is declared in the global variables list, we use::a to refer to it
•
If variable a is declared in scope b, we use b. a to refer to it
And if reference to name a cannot be resolved, we denote that by ? . a Here is the example program from the previous section, with all name references resolved (look at the
comments):
a, b, c;
test {
public:
a, b, hello;
}
private:
x, y;
a = b;
// test.a
=
test.b
hello =
c;
y = r;
// test.hello = ::C
// test.y = ?.r
nested {
public:
b;
a = b;
X
// test.a = nested.b
=
hello;
// ?.x
= test.hello
= y;
C =
// ::c = ?.y
4. Examples
The simplest possible program would be:
main {
a = a;
}
Let's add a global variable:
a;
main {
// ?.a = ?.a
a = a;
// ::a = ::a
} Now, let's add a public variable a:
a;
main {
public:
a;
a = a;
// main.a
= main.a
}
Or a private a:
a;
main {
private:
a;
a = a;
// main.a = main.a
}
Now, let's see a simple example with nested scopes:
a, b;
main {
nested {
a = b; // ::a = ::b
}
}
If we add a private variable in main:
a, b;
main {
private:
a;
nested {
a = b%;B
// ::α =
::b
}
}/n
