Introduction
This article deals with parsing and semantic analysis.
A full LL(1) parsing engine is introduced as an example to show a possible implementation.
The following samples do not describe the peculiarities of C# constructs; C# is used as an ordinary language except for its polymorphic behavior. Please check other articles for effective C# coding style.
The Basics
You may refer to a Compiler Design book for the theory: an excellent book is K. Louden [1997], see chapter 4.
If we consider Top Down Parsing, there are two equivalent methods to perform it.
We can use the familiar recursive descent parsing in which each Nonterminal is represented by a procedure and each Terminal is a match or an error. Formally, the inherited attributes are parameters to the procedures and the synthesized attributes are the function returned values.
Alternatively, we can use also LL(1) parsing in which recursion is simulated through a stack and the parser is table driven.
Here I present the two formally equivalent methods, given the same set of Productions. The first implementation
just prints an inverted string of an arbitrary complex C declaration, the second builds a complete inverted type from
a declaration with full semantic checking, using a stack to simulate recursion.
This method works for an LL(1) grammar, so you may need to review the constraints for this kind of grammars.
The grammar must not contain left recursion, must be left factorized, constraints on First and Follow Sets are
also enforced.
Recursive Descent Parsing
The first project is Recursive Descent. In a simple example of this first method, the output is just a string representation
of an arbitrary C declaration.
The simple grammar is as follows:
Decl --> Pointer DirDcl ;
Pointer --> Star Pointer
Pointer --> Lambda
DirDcl --> Id DirDclTail
DirDcl --> ( Dcl ) DirDclTail
DirDclTail --> [ Num ] DirDclTail
DirDclTail --> ( ) DirDclTail
DirDclTail --> Lambda
Let's begin with the Lexer: the tokens are contained in an enum and the returned lexeme is left in tokenValue.
public enum TokenKind {INT, CHAR, LONG, Num, Id, LParen ,
RParen, LQParen, RQParen, Star, Comma, SemiColon, EOI , UnKnown };
public class Lexer
{
public string tokenvalue = "";
public TokenKind getToken(ref int index, string stream)
{
tokenvalue = "";
while (index < stream.Length && ( stream[index] == ' '
|| stream[index] == '\t' || stream[index] == '\n' || stream[index] == '\r'))
index++;
if (index == stream.Length || stream[index] == '$')
return TokenKind.EOI;
if ((stream[index] >= 'A' && stream[index] <= 'Z') ||
(stream[index] >= 'a' && stream[index] <= 'z'))
{
tokenvalue += stream[index++];
while ((stream[index] >= 'A' && stream[index] <= 'Z') ||
(stream[index] >= 'a' && stream[index] <= 'z') ||
(stream[index] >= '0' && stream[index] <= '9') )
tokenvalue += stream[index++];
if (tokenvalue.ToUpper() == "INT")
return TokenKind.INT;
if (tokenvalue.ToUpper() == "CHAR")
return TokenKind.CHAR;
if (tokenvalue.ToUpper() == "LONG")
return TokenKind.LONG;
return TokenKind.Id;
}
if ((stream[index] >= '0' && stream[index] <= '9'))
{
tokenvalue += stream[index++];
while (stream[index] >= '0' && stream[index] <= '9')
tokenvalue += stream[index++];
return TokenKind.Num;
}
switch (stream[index])
{
case (';'):
index++;
return TokenKind.SemiColon;
case (','):
index++;
return TokenKind.Comma;
case ('*'):
index++;
return TokenKind.Star;
case ('('):
index++;
return TokenKind.LParen;
case ('['):
index++;
return TokenKind.LQParen;
case (')'):
index++;
return TokenKind.RParen;
case (']'):
index++;
return TokenKind.RQParen;
}
return TokenKind.UnKnown;
}
}
You may find useful to review the CodeProject article: How to interpret complex C/C++ declarations
By Vikram A Punathambekar, 3 Jul 2004 .
Look at the right to left rule.
The first parsing function is simple, just match the token and advance the input or signal an error and close the Form.
private void match(TokenKind token)
{
if (token == tokenKind)
tokenKind = lexx.getToken(ref index, stream);
else
{
MessageBox.Show(" unexpected token " + tokenKind);
this.Close();
}
}
To parse a declarator, parse Pointer then a DirDcl. This is accomplished by calling a procedure
for each nonterminal, from the right to left rule you can see that you must first go right then left
starting from the innermost Declarator.
private void _Decl()
{
int ns = 0;
_Pointer(ref ns);
_DirDcl();
while (ns-- > 0)
_out += " pointer to ";
}
To parse a Pointer, follows these rules:
a) if it is a star (*), simply count it
b) if it is a legal follow item, do nothing
c) return an error in all other cases
Please note the use of inherited attribute ns.
private void _Pointer(ref int ns)
{
switch (tokenKind)
{
case (TokenKind.Star):
match(TokenKind.Star);
ns++;
_Pointer(ref ns);
break;
case (TokenKind.Id):
case (TokenKind.LParen):
break;
default:
MessageBox.Show(" syntax error");
this.Close();
break;
}
}
Match the first item or raise an error in order to parse a DirDcl. To be noticed that ( Decl ) DirDclTail implies an additional parsing of a
subexpression of type Decl.
private void _DirDcl()
{
switch (tokenKind)
{
case (TokenKind.Id):
_out += " " + lexx.tokenvalue + " ";
match(TokenKind.Id);
_DirDclTail();
break;
case (TokenKind.LParen):
match(TokenKind.LParen);
_Decl();
match(TokenKind.RParen);
_DirDclTail();
break;
default:
MessageBox.Show(" syntax error");
this.Close();
return;
}
}
A DirDclTail may be an array or a function. At the end follow items must be a Left Parenthesis or a semicolon.
private void _DirDclTail()
{
string num = null;
int nn = 0;
switch (tokenKind)
{
case (TokenKind.LQParen):
match(TokenKind.LQParen);
num = lexx.tokenvalue;
match(TokenKind.Num);
nn = Convert.ToInt16(num);
_out += " array [" + nn + "] of ";
match(TokenKind.RQParen);
_DirDclTail();
break;
case (TokenKind.LParen):
match(TokenKind.LParen);
match(TokenKind.RParen);
_out += " function returning ";
_DirDclTail();
break;
case (TokenKind.RParen):
case (TokenKind.SemiColon):
break;
default:
MessageBox.Show(" syntax error");
this.Close();
break;
}
}
Let's trace an execution path with this declaration: int *(*pi[5])[10];
Decl
_Pointer(ref ns)
ns++ parse *
_Pointer(ref ns)
_DirDcl()
match('(') parse (
_Decl
_Pointer(ref ns)
ns++ parse *
Pointer(ref ns)
_DirDcl()
match(Id) output : pi
_DirDclTail
match('[') parse [
match(Num) parse 5
match(']') parse ] output : array[5] of
-> output : pointer to
match(')') parse )
_DirDclTail
match('[') parse [
match(Num) parse 10
match(']') parse ] output : array[10] of
--> output : pointer to
return to caller
output is : pi array[5] of pointer to array[10] of pointer to
The parsing is intuitive and the output is correct.
The process is not automated and the flow of attributes can be complex.
In section 5.1 of The C Programming Language, you can find a similar sample for complex declarations.
LL(1) Table Driven Parser
In a NonRecursive predictive parser, recursion is simulated through a semantic stack, parsing is guided by a predictive table.
In order to create this table, you should review the concepts of First and Follow Sets: First Set represents the lookaheads
that predict a particular production, the Follow Set is useful in Lambda production management.
Prediction here means not recurring to BackTracking; in Algol like languages this is quite natural.
The theory behind this method is presented in Aho, Lam, Sethi and Ullman [1986] second ed., section 5.5.3 L-Attributed SDD's and LL Parsing
with the use of a stack of objects. In addition, chapter 5 deals with inherited and synthesized attributes and how to manage them.
Here are the Productions used in the C complex declarations system.
Declaration
Declaration_Specifiers Declarator SemiColon
Declaration_Specifiers
Storage_Class_Specifier Sign_Specifier Type_Specifier
Storage_Class_Specifier
EXTERN STATIC AUTO REGISTER Lambda
Sign_Specifier
SIGNED UNSIGNED Lambda
Type_Specifier
VOID CHAR SHORT INT LONG
Declarator
Pointer Direct_Declarator
Direct_Declarator
Id Direct_Declarator_Tail
LParen Declarator RParen Direct_Declarator_Tail
Direct_Declarator_Tail
LSParen Integer_Constant RSParen Direct_Declarator_Tail
LParen Parameter_Type_List RParen Direct_Declarator_Tail
Lambda
Pointer
Star Type_Qualifier_List Pointer
Lambda
Parameter_Type_List
Parameter_List
Parameter_List
Parameter_Declaration Parameter_List_Tail
Parameter_List_Tail
Comma Parameter_Declaration Parameter_List_Tail
Lambda
Parameter_Declaration
Declaration_Specifiers Parameter_Declaration_Tail
Parameter_Declaration_Tail
Declarator
Here is the parser in LLParser.cs that represents the parsing state machine: it predicts productions, advance input or generate an error,
it schedules actions at appropriate times.
The functionality here is similar to that of the recursive version: when we predict a production, we push terminals and nonterminals in
reverse order.
Expanding a production is analogous to a function call: matching terminals advance input or signal an error until end of input.
Please note that synthesized attributes are pushed first in the stack and executed last. Tehy represent a final action on data computed so far.
Prediction in LL(1) parsing means to choose a production given a [NonTerminal,Terminal] pair. Execution begins with the start symbol
Declaration on top of SemanticStack, Declaration_Specifiers is the first NonTerminal of production number 1 that can be predicted by an
optional Storage_Class_Specifier, an optional Sign_Specifier and a mandatory Type_Specifier.
The Type_Specifier must be one of VOID, CHAR, SHORT, INT, LONG otherwise an syntax error is raised. This means, for instance, that entry
[Type_Specifier,CHAR] is a valid entry in the predictive table while blank entries represents error entries.
The Parse algorithm is not difficult to be understood: it checks the semantic stack looking for anything that is (derives from) a SynthesizedAttribute
and it executes the associated action popping the stack, if present. If it is another kind of object, it proceeds checking if it is a kind of
InheritedAttribute and if it is so, it continues predicting, with a [NonTermnal,Terminal] pair, the next production (this means expanding a production), executing any function found, popping the semantic stack and pushing the contents of the production in reverse order (this is like a
function call in the recursive version).
If the symbol on top of the semantic stack is not anything like an Inherited attribute, then it must be
a Terminal or EOI. If it's a terminal or EOI it compares it with the token from input: if they match, it executes a semantic action if present and get the next token; if they don't match, it signals an error and ends.
public bool Parse()
{
bool fret = false;
Production pp = null;
object sym = Stack.Top();
SynthesizedAttribute syn = sym as SynthesizedAttribute;
if (syn != null)
{
if (syn.FireAction != null)
{
fret = syn.FireAction(Stack, pp);
if (fret == false)
return fret;
}
Stack.Pop();
return true;
}
SemanticAction sma = sym as SemanticAction;
if (sma != null)
{
Stack.Pop();
sym = Stack.Top();
}
InheritedAttribute inh = sym as InheritedAttribute;
if (inh != null)
{
if (token != TokenLookup.TokenKind.UnKnown)
pp = (Production)M[(int)inh.nTerm.Category, (int)token];
if (pp == null)
{
MessageBox.Show("syntax error ");
return false;
}
if (sma != null)
{
fret = sma.FireAction(Stack, pp, lexx.TokenValue);
if (fret == false)
return fret;
}
Stack.Pop();
for (int j = pp.rhs.Count - 1; j >= 0; j--)
{
Terminal tt = pp.rhs[j] as Terminal;
if (tt != null && tt.Token == TokenLookup.TokenKind.Lambda)
continue;
if (pp.synth != null && pp.synth[j] != null)
{
if (pp.synth[j] is SDeclTypeAttribute)
{
SDeclTypeAttribute sa = (SDeclTypeAttribute)pp.synth[j] as SDeclTypeAttribute;
Stack.Push(new SDeclTypeAttribute(sa));
}
pp.synth[j].Clear();
}
if (tt != null)
Stack.Push(pp.rhs[j]);
if (pp.inh != null && pp.inh[j] != null)
{
if (pp.inh[j] is IDeclTypeAttribute)
{
IDeclTypeAttribute ie = pp.inh[j] as IDeclTypeAttribute;
Stack.Push(new IDeclTypeAttribute(ie));
}
else
Stack.Push(new InheritedAttribute(pp.inh[j]));
pp.inh[j].Clear();
}
if (pp.action != null && pp.action[j] != null)
Stack.Push(pp.action[j]);
}
}
else
{
Terminal tt = sym as Terminal;
if (token == TokenLookup.TokenKind.EOI)
{
MessageBox.Show("stream successfully parsed ");
return false;
}
else
if (token == tt.Token)
{
if (sma != null)
{
fret = sma.FireAction(Stack, null, lexx.TokenValue);
if (fret == false)
return fret;
}
Stack.Pop();
token = lexx.getToken();
return true;
}
else
{
MessageBox.Show("Unexpected token : " + token + ", expected : " + tt.Token + ") ;
return false;
}
}
return true;
}
Let's analyze the structure of the semantic Engine: we have synthesized and inherited attributes represented by two parent classes
and action routines. From these, you can declare classes that inherits from these basics classes and are the containers of data
to be transferred by the program logic. These classes are in Semantic.cs.
public class SemanticStack
{
public object[] ss = null;
public int sp;
public SemanticStack(int nn)
{
ss = new object[nn];
sp = 0;
}
public object Top()
{
object sym = ss[sp - 1];
return sym;
}
public void Push(object sym)
{
ss[sp++] = sym;
}
public object Pop()
{
return ss[--sp];
}
}
public class SemanticAction
{
public delegate bool Action(SemanticStack Stack, Production pp, string token);
public Action FireAction;
public SemanticAction()
{
}
public SemanticAction(Action action)
{
FireAction = action;
}
public override string ToString()
{
return "a(" + FireAction.Method.Name.ToString() + ")";
}
}
public abstract class SynthesizedAttribute
{
public NonTerminal nTerm;
public delegate bool Action(SemanticStack Stack, Production pp);
public Action FireAction;
public virtual void Clear()
{
}
}
public class SDeclTypeAttribute : SynthesizedAttribute
{
public ArrayList Tuples = new ArrayList();
public SignSpecifier signed = SignSpecifier.SIGNED;
public StorageClass sclass = StorageClass.UnKnown;
public Type basety = null;
public Type tmpty = null;
public Symbol sym = null;
public List<symbol> lsym = new List<symbol>();
public Stack<type> stype = new Stack<type>();
public int np = 0;
public string id = null;
public int size;
...
public class InheritedAttribute
{
public string ErrMsg = null;
public NonTerminal nTerm;
public InheritedAttribute() { }
public InheritedAttribute(InheritedAttribute inh)
{
nTerm = inh.nTerm;
ErrMsg = inh.ErrMsg;
}
public InheritedAttribute(NonTerminal nt)
{
nTerm = nt;
}
public InheritedAttribute(NonTerminal nt, string _errmsg)
{
nTerm = nt;
ErrMsg = _errmsg;
}
public virtual void Clear()
{
}
}
public class IDeclTypeAttribute : InheritedAttribute
{
public ArrayList Tuples = new ArrayList();
public SignSpecifier signed = SignSpecifier.SIGNED;
public StorageClass sclass = StorageClass.UnKnown;
public Type basety = null;
public Type tmpty = null;
public Symbol sym=null;
public List<symbol> lsym = new List<symbol>();
public Stack<type> stype = new Stack<type>();
public int np = 0;
public string id = null;
public int size;
...
As you can see, we've a simple stack of objects that is pushed to and popped from continuosly by the parser. The SemanticStack
contains action routines from the class SemanticAction, Inherited classes and derived, custom classes derived from SynthesizedAttribute.
These classes are the basic containers of data and the data flow in the application logic is through these classes.
The action routines act on the custom data structures defined by the user based on Inherited and Synthesized custom classes.
We have a parser, we have the objects that represents the layout of the stack, and we have semantic actions that act on these objects
at known and fixed positions inside the stack.
The layout on the stack of a given Production must be specified in advance all the time, that is the information that the parser must push and pop from the SemanticStack.
The layout is specified with parallel lists, it's up to the programmer to fill these lists correctly, error checking is left to him.
BuildBaseType is a SemanticAction executed on matching the terminal INT or CHAR (for instance). We know that the parser on a match
executes a SemanticAction if present: here BuildBaseType is called with the token representing the basic type, it accesses the stack object
referring to the SDeclTypeAttribute of Type_Specifier at fixed displacement on the SemanticStack and loads the basety field accordingly.
...
lhs = lg.FindNTermByName("Type_Specifier");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("CHAR"));
actions = new List<semanticaction>();
actions.Add(new SemanticAction(BuildBaseType));
lg.Prod.Add(new Production(lhs, rhs, actions, null, null));
lhs = lg.FindNTermByName("Type_Specifier");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("INT"));
actions = new List<semanticaction>();
actions.Add(new SemanticAction(BuildBaseType));
lg.Prod.Add(new Production(lhs, rhs, actions, null, null));
...
static bool BuildBaseType(SyntaxStack ss, Production pp, string token)
{
SDeclTypeAttribute sp = ss.ss[ss.sp - 2] as SDeclTypeAttribute;
string ty = token.ToUpper();
switch (ty)
{
case ("CHAR"):
sp.basety = BuildType(TypeOperator.CHAR, null, 1,null);
break;
case ("INT"):
sp.basety = BuildType(TypeOperator.INT, null, 2,null);
break;
case ("LONG"):
sp.basety = BuildType(TypeOperator.LONG, null, 4,null);
break;
case ("VOID"):
sp.basety = BuildType(TypeOperator.VOID, null, 0, null);
break;
}
return true;
}
Here is ActionLoadBaseType that gets scheduled when is on top of stack with a SDeclTypeAttribute object of Type_Specifier as we can see in Parse. It loads the IDeclTypeAttribute of Declarator loading the basety field.
The function is declared in advance in the layout of the Production as an Action associated with the SDeclTypeAttribute of Type_Specifier and gets scheduled at end of Production Type_Specifier --> INT | CHAR | LONG |VOID.
...
lhs = lg.FindNTermByName("Declaration_Specifiers");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindNTermByName("Storage_Class_Specifier"));
rhs.Add(lg.FindNTermByName("Sign_Specifier"));
rhs.Add(lg.FindNTermByName("Type_Specifier"));
inh = new List<inheritedattribute>();
inh.Add(new InheritedAttribute(lg.FindNTermByName("Storage_Class_Specifier"), null));
inh.Add(new InheritedAttribute(lg.FindNTermByName("Sign_Specifier"), null));
inh.Add(new InheritedAttribute(lg.FindNTermByName("Type_Specifier"), null));
synth = new List<synthesizedattribute>();
synth.Add(new SDeclTypeAttribute(lg.FindNTermByName("Storage_Class_Specifier"), ActionLoadStorageClassModifier));
synth.Add(new SDeclTypeAttribute(lg.FindNTermByName("Sign_Specifier"), ActionLoadSignSpecifier));
synth.Add(new SDeclTypeAttribute(lg.FindNTermByName("Type_Specifier"), ActionLoadBaseType));
lg.Prod.Add(new Production( lhs, rhs, null, synth, inh));
...
static bool ActionLoadBaseType(SyntaxStack ss, Production pp)
{
IDeclTypeAttribute ip = ss.ss[ss.sp - 3] as IDeclTypeAttribute;
SDeclTypeAttribute sp = ss.ss[ss.sp - 1] as SDeclTypeAttribute;
switch (sp.basety.op)
{
case (TypeOperator.VOID):
case (TypeOperator.CHAR):
case (TypeOperator.INT):
case (TypeOperator.LONG):
ip.basety = sp.basety;
ip.basety.signed = ip.signed;
break;
}
return true;
}
And here is ActionExpandDeclarator that executes when it is on Top of Stack: it proceeds to expand
the production Declarator-> Pointer Direct_Declarator. It loads the IDeclTypeAttribute of Pointer with the basic type created, accessing the
IDeclTypeAttribute of Declarator in the stack.
As you see, the production is accessed through the inh field [0], referring to the IDecltypeAttribute of Pointer, containing the right info.
This is done immediately after accessing the predictive table: the field contents are moved to the production, and next in the loop the
production contents are pushed in reverse order. Parse uses a copy constructor for each instance of the synthesized and inherited attributes.
We will have then a copy of this data on the semantic stack at known position.
...
lhs = lg.FindNTermByName("Declaration");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindNTermByName("Declaration_Specifiers"));
rhs.Add(lg.FindNTermByName("Declarator"));
rhs.Add(lg.FindTermByName("SemiColon"));
inh = new List<inheritedattribute>();
inh.Add(new InheritedAttribute(lg.FindNTermByName("Declaration_Specifiers"), null));
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Declarator"), null));
inh.Add(null);
actions = new List<semanticaction>();
actions.Add(null);
actions.Add(new SemanticAction(ActionOnExpandDeclarator));
actions.Add(null);
synth = new List<synthesizedattribute>();
synth.Add(null);
synth.Add(new SDeclTypeAttribute(lg.FindNTermByName("Declarator"), ActionProcessSymbolTableDeclarator));
synth.Add(null);
lg.Prod.Add(new Production( lhs, rhs, actions, synth, inh));
...
static bool ActionOnExpandDeclarator(SyntaxStack ss, Production pp, string token)
{
IDeclTypeAttribute sp = ss.ss[ss.sp - 1] as IDeclTypeAttribute;
IDeclTypeAttribute dp = null;
dp = pp.inh[0] as IDeclTypeAttribute;
dp.basety = sp.basety;
dp.sclass = sp.sclass;
return true;
}
In this semantic engine you must declare the NonTerminals, the Terminals and the Productions in your language.
LL01.cs responsabily is to fill correctly the predictive table, once the table is created. Parsing is quite natural, you can forget
about the predictive table, just add valid productions compatible with LL(1) grammar format.
To begin, we declare the grammar: actions synth and inh represents collections of data safely saved inside the Language class.
A single action is a SemanticAction, a synth is a class derived from SynthesizedAttribute and an inh is an InheritedAttribute
or a derived class.
Giving the parser, the objects and the actions, we have all we need.
Inside DeclsGrammar.cs, we begin by declaring the basic blocks: NonTerminals, Terminals and Productions to compute the First and Follow Sets
and the predictive table.
We specify then the layout of any given production. This allows the parser to work correctly.
TokenLookup.TokenKind[] tokens = (TokenLookup.TokenKind[])Enum.GetValues(typeof(TokenLookup.TokenKind));
string[] names = TokenLookup.TokenNames;
Terminal tt = null;
foreach (TokenLookup.TokenKind tok in tokens)
{
tt = new Terminal(names[idx], tok);
lg.Term.Add(tt);
if (lg.HashTerm[names[idx]] != null)
MessageBox.Show(" Terminal " + names[idx] + " already inserted");
else
lg.HashTerm.Add(names[idx], tt);
idx++;
}
Category[] categories = (Category[])Enum.GetValues(typeof(Category));
idx = 0;
NonTerminal nt = null;
foreach (Category cat in categories)
{
nt = new NonTerminal(Enum.Format(typeof(Category), cat, "G"), cat);
lg.NTerm.Add(nt);
if (lg.HashNTerm[cat] != null)
MessageBox.Show(" Nonterminal " + cat + " already inserted");
else
lg.HashNTerm.Add(cat.ToString(), nt);
}
List<semanticaction> actions = new List<semanticaction>();
List<inheritedattribute> inh = new List<inheritedattribute>();
List<synthesizedattribute> synth = new List<synthesizedattribute>();
NonTerminal lhs = null;
List<syntaxsymbol> rhs = null;
lhs = lg.FindNTermByName("Declaration");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindNTermByName("Declaration_Specifiers"));
rhs.Add(lg.FindNTermByName("Declarator"));
rhs.Add(lg.FindTermByName("SemiColon"));
inh = new List<inheritedattribute>();
inh.Add(new InheritedAttribute(lg.FindNTermByName("Declaration_Specifiers"), null));
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Declarator"), null));
inh.Add(null);
actions = new List<semanticaction>();
actions.Add(null);
actions.Add(new SemanticAction(ActionOnExpandDeclarator));
actions.Add(null);
synth = new List<synthesizedattribute>();
synth.Add(null);
synth.Add(new SDeclTypeAttribute(lg.FindNTermByName("Declarator"), ActionProcessSymbolTableDeclarator));
synth.Add(null);
lg.Prod.Add(new Production( lhs, rhs, actions, synth, inh));
...
lg.ComputeFirstSet();
lg.ComputeFollowSet();
lg.FillTable();
Here we've added:
*) the Terminals contained in enum TokenKind Tokens.c returned by the Lexer in a specialized collection Term
*) the NonTerminals contained in the Category enum (in the same file) in the collection Nterm
These collections are used to compute First and Follow Sets; in addition the first production is added to the Prod collection, used to fill the parsing table.
A production consists of action routines and the custom data structures associated.
We have basically three kinds of action routines:
a) those associated with
NonTerminals: they represent production expansion and are executed after a valid prediction
b) those associated with
Terminals: they means access to input tokens and are executed after a successful match with the input token if an action is required
c) those relative to a
SynthesizedAttribute and are specified in the right constructor.
Now we present the Language grammar with the introduction of the Declarator subsystem. As you can imagine, it is a function with
input parameters and a return value (DeclGrammar.cs).
The Declarator subsystem is exactly similar to the recursive version presented early.
The two functions given below executes on expansion of NonTerminals Pointer and Direct_Declarator. This means that in ActionOnExpandPointer,
a Pointer is predicted by [Pointer,*] and is also nullable: in other words, it can be canceled on the Follow Items. A Direct_Declarator can be predicted
by an Id and a (.
The two actions are linked in the parallel list actions, containing the SemanticActions, in the same position of IDeclTypeAttribute Pointer and
Direct_Declarator.
As we've seen, we copy the parameters in the production to be expanded, for example on Pointer -> Star Pointer, we know that the next production
has the IDeclTypeAttribute Pointer at index 1.
The field np is the Pointer count, on predicting [Pointer,*] it increments the counter, when there are no more stars it copies the total left
to right (Inherited attribute flow) to Direct_Declarator.
Note that while copying the data on predicting [Direct_Declarator,(] to Direct_Declarator_Tail it performs the right to left evaluation.
...
lhs = lg.FindNTermByName("Declarator");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindNTermByName("Pointer"));
rhs.Add(lg.FindNTermByName("Direct_Declarator"));
inh = new List<inheritedattribute>();
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Pointer"), null));
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Direct_Declarator"), null));
actions = new List<semanticaction>();
actions.Add(new SemanticAction(ActionOnExpandPointer));
actions.Add(new SemanticAction(ActionOnExpandDirectDecl));
synth = new List<synthesizedattribute>();
synth.Add(new SDeclTypeAttribute(lg.FindNTermByName("Pointer"), null));
synth.Add(null);
lg.Prod.Add(new Production( lhs, rhs, actions, synth, inh));
...
static bool ActionOnExpandPointer(SemanticStack ss, Production pp, string token)
{
IDeclTypeAttribute sp = ss.ss[ss.sp - 1] as IDeclTypeAttribute;
IDeclTypeAttribute ip = null;
switch (pp.prodno)
{
case (22):
ip = pp.inh[1] as IDeclTypeAttribute;
ip.basety = sp.basety;
ip.sclass = sp.sclass;
ip.np = sp.np;
ip.np++;
break;
case (23):
ip = ss.ss[ss.sp - 4] as IDeclTypeAttribute;
ip.basety = sp.basety;
ip.sclass = sp.sclass;
ip.np = sp.np;
break;
}
return true;
}
static bool ActionOnExpandDirectDecl(SemanticStack ss, Production pp, string token)
{
IDeclTypeAttribute sp = ss.ss[ss.sp - 1] as IDeclTypeAttribute;
IDeclTypeAttribute ip = null;
switch (pp.prodno)
{
case (17):
ip = pp.inh[1] as IDeclTypeAttribute;
ip.basety = sp.basety;
ip.sclass = sp.sclass;
ip.np = sp.np;
break;
case (18):
ip = pp.inh[3] as IDeclTypeAttribute;
ip.basety = sp.basety;
ip.sclass = sp.sclass;
ip.np = sp.np;
break;
}
return true;
}
...
The next two functions are ActionOnLoadIdToDirectDeclTail and ActionOnProcessTempDeclarator. ActionOnLoadIdToDirectDeclTail, associated with Terminal Id, eats an Id and passes it to the IDeclTypeAttribute of Direct_Declarator_Tail in the stack with a fixed displacement. ActionOnProcessTempDeclarator gets executed at the end of Declarator production on synthesized attribute SDeclTypeAttribute on top of stack: the function builds an inner type associated with Declarator and passes the temporary concatenated type inner to outer to Direct_Declarator_Tail.
The linkage is obtained inserting in the synth list the SDeclTypeAttribute on a Declarator with the function ActionOnProcessTempDeclarator.
llhs = lg.FindNTermByName("Direct_Declarator");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("Id"));
rhs.Add(lg.FindNTermByName("Direct_Declarator_Tail"));
inh = new List<inheritedattribute>();
inh.Add(null);
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Direct_Declarator_Tail"), null));
actions = new List<semanticaction>();
actions.Add(new SemanticAction(ActionOnLoadIdToDirectDeclTail));
actions.Add(new SemanticAction(ActionOnExpandDirectDeclTail));
lg.Prod.Add(new Production( lhs, rhs, actions, null, inh));
lhs = lg.FindNTermByName("Direct_Declarator");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("LParen"));
rhs.Add(lg.FindNTermByName("Declarator"));
rhs.Add(lg.FindTermByName("RParen"));
rhs.Add(lg.FindNTermByName("Direct_Declarator_Tail"));
inh = new List<inheritedattribute>();
inh.Add(null);
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Declarator"),null));
inh.Add(null);
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Direct_Declarator_Tail"), null));
synth = new List<synthesizedattribute>();
synth.Add(null);
synth.Add(new SDeclTypeAttribute(lg.FindNTermByName("Declarator"),ActionOnProcessTempDeclarator));
synth.Add(null);
synth.Add(null);
actions = new List<semanticaction>();
actions.Add(null);
actions.Add(null);
actions.Add(null);
actions.Add(new SemanticAction(ActionOnExpandDirectDeclTail));
lg.Prod.Add(new Production(lhs, rhs, actions, synth, inh));
...
static bool ActionOnLoadIdToDirectDeclTail(SemanticStack ss, Production pp, string token)
{
IDeclTypeAttribute sp = ss.ss[ss.sp - 3] as IDeclTypeAttribute;
sp.id = token.ToUpper();
return true;
}
static bool ActionOnProcessTempDeclarator(SemanticStack ss, Production pp)
{
SDeclTypeAttribute sp = ss.ss[ss.sp - 1] as SDeclTypeAttribute;
IDeclTypeAttribute ip = ss.ss[ss.sp - 4] as IDeclTypeAttribute;
Type ty = null, tty = null;
for (int _j = 0; _j < sp.np; _j++)
tty = BuildType(TypeOperator.POINTER, tty, 4,null);
for (int _j = 0; _j < sp.stype.Count; _j++)
{
ty = sp.stype.Pop();
tty = BuildType(ty.op, tty, ty.size,ty.lsym);
}
ty = sp.tmpty;
while (ty != null && ty.type != null)
ty = ty.type;
if (sp.tmpty == null)
sp.tmpty = tty;
else
ty.type = tty;
ip.tmpty = sp.tmpty;
ip.id = sp.id;
return true;
}
...
The next function gets executed on expansion of a Direct_Declarator_Tail. The prediction occurs on symbol [, ( and the item is nullable.
ActionOnLoadNumToDirectDeclTail eats the Integer_Constant returned by the Lexer inside parsing production
Direct_Declarator_Tail
->
[ Integer_Constant ] Direct_Declarator_Tail.
lhs = lg.FindNTermByName("Direct_Declarator_Tail");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("LSParen"));
rhs.Add(lg.FindTermByName("Integer_Constant"));
rhs.Add(lg.FindTermByName("RSParen"));
rhs.Add(lg.FindNTermByName("Direct_Declarator_Tail"));
inh = new List<inheritedattribute>();
inh.Add(null);
inh.Add(null);
inh.Add(null);
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Direct_Declarator_Tail"), null));
actions=new List<semanticaction>();
actions.Add(null);
actions.Add(new SemanticAction(ActionOnLoadNumToDirectDeclTail));
actions.Add(null);
actions.Add(new SemanticAction(ActionOnExpandDirectDeclTail));
lg.Prod.Add(new Production( lhs, rhs, actions, null, inh));
lhs = lg.FindNTermByName("Direct_Declarator_Tail");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("LParen"));
rhs.Add(lg.FindNTermByName("Parameter_Type_List"));
rhs.Add(lg.FindTermByName("RParen"));
rhs.Add(lg.FindNTermByName("Direct_Declarator_Tail"));
inh = new List<inheritedattribute>();
inh.Add(null);
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Parameter_Type_List"), null));
inh.Add(null);
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Direct_Declarator_Tail"), null));
actions = new List<semanticaction>();
actions.Add(null);
actions.Add(new SemanticAction(ActionOnExpandParameterTypeList));
actions.Add(null);
actions.Add(new SemanticAction(ActionOnExpandDirectDeclTail));
lg.Prod.Add(new Production( lhs, rhs, actions, null, inh));
lhs = lg.FindNTermByName("Direct_Declarator_Tail");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("Lambda"));
lg.Prod.Add(new Production( lhs, rhs, null, null, null));
...
static bool ActionOnExpandDirectDeclTail(SemanticStack ss, Production pp, string token)
{
IDeclTypeAttribute sp = ss.ss[ss.sp - 1] as IDeclTypeAttribute;
IDeclTypeAttribute ip = null;
switch (pp.prodno)
{
case (19):
ip = pp.inh[3] as IDeclTypeAttribute;
ip.basety = sp.basety;
ip.tmpty = sp.tmpty;
ip.sclass = sp.sclass;
ip.np = sp.np;
ip.id = sp.id;
__Copy_Stack(ip.stype, sp.stype);
break;
case (20):
ip = pp.inh[3] as IDeclTypeAttribute;
ip.basety = sp.basety;
ip.tmpty = sp.tmpty;
ip.sclass = sp.sclass;
ip.np = sp.np;
ip.id = sp.id;
__Copy_Stack(ip.stype, sp.stype);
break;
case (21):
SDeclTypeAttribute dp = ss.ss[ss.sp - 2] as SDeclTypeAttribute;
dp.basety = sp.basety;
dp.tmpty = sp.tmpty;
dp.sclass = sp.sclass;
dp.np = sp.np;
dp.id = sp.id;
__Copy_Stack(dp.stype, sp.stype);
break;
}
return true;
}
static bool ActionOnLoadNumToDirectDeclTail(SemanticStack ss, Production pp, string token)
{
IDeclTypeAttribute sp = ss.ss[ss.sp - 4] as IDeclTypeAttribute;
sp.stype.Push(BuildType(TypeOperator.ARRAY,null, Convert.ToInt16(token),null));
return true;
}
....
As you can see, there is a chain of static functions that will be executed by the parser at appropriate time, expansion of productions that
will be executed at production prediction while consulting the predictive table and synthesized actions present in synthesized attributes that represent final actions, usually at end of production, to compute values or to perform a particular action (e.g. insert a fully parsed symbol
into a symbol table).
lhs = lg.FindNTermByName("Pointer");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("Star"));
rhs.Add(lg.FindNTermByName("Pointer"));
inh = new List<inheritedattribute>();
inh.Add(null);
inh.Add(new IDeclTypeAttribute(lg.FindNTermByName("Pointer"), null));
actions = new List<semanticaction>();
actions.Add(null);
actions.Add(new SemanticAction(ActionOnExpandPointer));
lg.Prod.Add(new Production( lhs, rhs, actions, null, inh));
lhs = lg.FindNTermByName("Pointer");
rhs = new List<syntaxsymbol>();
rhs.Add(lg.FindTermByName("Lambda"));
lg.Prod.Add(new Production( lhs, rhs, null, null, null));
Here is the last function that gets executed at end of Declarator production processing. It computes a complete string representation obtained
from partial temporary types built inner to outer.
The action here could be more significative: indeed we have a full inverted type and all associated data,
even a parameter list, if present, could have been processed, the usual action being to add the symbol to the appropriate symbol table
static bool ActionProcessSymbolTableDeclarator(SemanticStack ss, Production pp)
{
SDeclTypeAttribute sp = ss.ss[ss.sp - 1] as SDeclTypeAttribute;
Type ty;
int nitems = 0;
for (int _j = 0; _j < sp.np; _j++)
sp.basety = BuildType(TypeOperator.POINTER, sp.basety, 4, null);
nitems = sp.stype.Count;
for (int _j = 0; _j < nitems; _j++)
{
ty = sp.stype.Pop();
sp.basety = BuildType(ty.op, sp.basety, ty.size, ty.lsym);
}
ty = sp.tmpty;
while (ty != null && ty.type != null)
ty = ty.type;
if (ty != null)
{
ty.type = sp.basety;
sp.basety = sp.tmpty;
}
Symbol sym = new Symbol();
sym.name = sp.id;
sym.sclass = sp.sclass;
sym.type = sp.basety;
if (CheckInvalidType(sp.basety))
return false;
EAGrammar._type = _FormatType(sym);
return true;
}
Let's look at the parse tree for input int *(*pi[5])[10]; and trace execution. I have termed here Declarator (Decl), DirDecl (Direct_Declarator) and
DirDclTail (Direct_Declarator_Tail).
To follow the logic, put breakpoints inside the functions in the Declarator region:
(1) Input to Decl (Declarator) is a basety of type int.
(2) ActionOnExpandDeclarator : expand Decl and pass (basety=int) to Pointer
(3) AncionOnExpandPointer : first expansion of Pointer count *, np=1
(4) ActionOnExpandPointer : second expansion of Pointer to Lamdba, pass (np=1,basety=int) to DirDecl (synth)
(5) ActionOnExpandDirectDecl : expand DirDecl with ( Decl ) DirDeclTail pass (np=1,basety=int) to DirDeclTail
(6) Expand Decl
(7) ActionOnExpandPointer : expand Pointer and count np=1
(8) ActionOnExpandPointer : expand Pointer to Lambda and copy (np=1,basety=null) to DirDecl (synth)
(9) ActionOnExpandDirectDecl : expand DirDecl to Id DirDeclTail pass (np=1,basety=null) to DirDeclTail
(10) ActionOnLoadIdToDirectDeclTail : load DirDeclTail (with id=pi)
(11) ActionOnExpandDirectDeclTail :expand DirDeclTail -> [ Num ] DirDeclTail and load DirDeclTail with (id=pi,basety=null,np=1)
(12) ActionOnLoadNumToDirectDeclTail: stack an stype of (ARRAY 5) to DirDeclTail
(13) ActionOnExpandDirectDeclTail : expand DirDeclTail to Lambda and pass (tmpty=null,basety=null,np=1,stype=(ARRAY 5)) to synth Decl
(14) ActionOnProcessTempDeclarator : load DirDeclTail (with tmpty = (ARRAY 5 POINTER))
(15) ActionOnExpandDirectDeclTail : expand DirDelcTail with [ Num ] DirDeclTail and load DirDeclTail with (with tmpty = (ARRAY 5 POINTER))
(16) ActionOnLoadNumToDirectDeclTail : stack an stype of (ARRAY 10) to DirDeclTail
(17) ActionOnExpandDirectDeclTail : expand DirDeclTail to Lamdba and load synthesized Decl with (basety=int,np=1,tmpty=(ARRAY 5 POINTER),stype=(ARRAY 10),id=pi)
(18) ActionProcessSymbolTableDeclarator : load EAGrammar._tyoe with (PI: ARRAY 5 POINTER TO ARRAY 10 POINTER TO INT)
As you can see, the output is correct and recursion is simulated with a stack.
Inherited attributes flow is left to right and top down, synthesized attributes flow is bottom up,
ActionOnProcessTempDeclarator
is associated with inner Declarators and is executed at end of production Declarator building a
temporary inverted type,
ActionProcessSymbolTableDeclarator is associated with the top level Declarator,
it is executed at end giving a full inverted type.
This flow of information conforms to the theory and results in a deterministic evaluation.
I haven't presented the Lexer because it's almost similar to the recursive version, it returns tokens and lexemes.
Consult Semantic.cs for stacked objects and DataStructure.cs for common ds like Type.
The advantage of using the tabular method is that programming is modular and can be well documented, it's easy to
write a Compiler Generator Engine and common subsystems can be easily re-utilized, like the Declarator one.
You can see from the code that the Declarator subsystem is used without modifications also in parameter list processing.
A Declarator builds an inverted type given some input parameters, the logic of complex C Declarations is performed at the
proper times inner expressions to outer resulting in a complete inverted type.
Bibliography
- Compiler Construction: Principles and Practice, K.C Louden [1997].
- Compilers Principles Techniques and Tools, 2nd Edition, Aho, Sethi, Lam and Ullman [1986].
- Algorithms for Compiler Design, O.G. Kakde [2002].
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
