1. Consider the by now rather hackneyed grammar for expressions which has been written out again below. How would you add attributes so that a parser, after recognising an Expression, would be able to determine whether that Expression was a "constant expression" (meaning that in principle it could be evaluated at compile time) or was a "variable expression" (meaning that it could not be evaluated until run time)? Assume that the Designator production can be attributed so that it returns the result of searching the symbol table to determine whether the associated identifier denotes a variable or a constant.
Expression<out boolean isConst> (. boolean alsoConst; .)
= ( "+" Term<out isConst>
| "-" Term<out isConst>
| Term<out isConst>
)
{ AddOp Term<out alsoConst> (. isConst = isConst && alsoConst; .)
} .
Term<out boolean isConst> (. boolean alsoConst; .)
= Factor<out isConst>
{ MulOp Factor<out alsoConst> (. isConst = isConst && alsoConst; .)
} .
Factor<out boolean isConst>
= Designator<out isConst>
| number (. isConst = true; .)
| "(" Expression<out isConst> ")"
.
2. Consider the familiar grammar below for describing a set of EBNF productions. How could you add attributes to this grammar so that it could determine which non-terminal had the longest right hand side (in terms of the number of terminals and non terminals in any one of its alternatives)?
Two solutions follow. In the first one we simply use some static fields in the Parser class to record the quantities of interest:
import library.*;
COMPILER EBNF $CN
/* Describe simple EBNF productions and find which has the longest right side
P.D. Terry, Rhodes University, 2012 */
static String thisName, maxName;
static int maxLength = 0;
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" .
noquote2 = ANY - '"' .
TOKENS
nonterminal = letter {letter | digit } .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
EBNF (. int maxRHS; .)
= { Production<out maxRHS> (. if (maxRHS > maxLength) maxName = thisName; .)
} (. IO.writeLine("Longest production was for "
+ maxName); .)
EOF .
Production<out int maxRHS>
= SYNC nonterminal (. thisName = token.val; .)
WEAK "="
Expression<out maxRHS>
SYNC "." .
Expression<out int expLength> (. int altLength; .)
= Term<out expLength>
{ WEAK "|" Term<out altLength> (. if (altLength > expLength)
expLength = altLength; .)
} .
Term<out int termLength> (. int N; termLength = 0; .)
= [ Factor<out termLength>
{ Factor<out N> (. termLength += N; .)
}
] .
Factor<out int factorLength> (. factorLength = 0; .)
= nonterminal (. factorLength = 1; .)
| terminal (. factorLength = 1; .)
| "[" Expression<out factorLength> "]"
| "(" Expression<out factorLength> ")"
| "{" Expression<out factorLength> "}"
.
END EBNF.
In the second solution we show how one can arrange for parsing methods to return objects that encapsulate the quantities of interest:
import library.*;
COMPILER EBNF $CN
/* Describe simple EBNF productions and find which has the longest right side
P.D. Terry, Rhodes University, 2012 */
static class Prod {
public String name = "";
public int maxRHS = 0;
}
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" .
noquote2 = ANY - '"' .
IGNORE CHR(9) .. CHR(13)
TOKENS
nonterminal = letter {letter | digit } .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
EBNF (. Prod bigProd = new Prod(), nextProd; .)
= { Production<out nextProd> (. if (nextProd.maxRHS > bigProd.maxRHS)
bigProd = nextProd; .)
} (. IO.writeLine("Longest production was for "
+ bigProd.name); .)
EOF .
Production<out Prod p> (. p = new Prod(); .)
= SYNC nonterminal (. p.name = token.val; .)
WEAK "="
Expression<out p.maxRHS>
SYNC "." .
Expression<out int expLength> (. int altLength; .)
= Term<out expLength>
{ WEAK "|" Term<out altLength> (. if (altLength > expLength)
expLength = altLength; .)
} .
Term<out int termLength> (. int N; termLength = 0; .)
= [ Factor<out termLength>
{ Factor<out N> (. termLength += N; .)
}
] .
Factor<out int factorLength> (. factorLength = 0; .)
= nonterminal (. factorLength = 1; .)
| terminal (. factorLength = 1; .)
| "[" Expression<out factorLength> "]"
| "(" Expression<out factorLength> ")"
| "{" Expression<out factorLength> "}"
.
END EBNF.
3. Consider the familiar grammar below for describing a set of EBNF productions. How could you add attributes to this grammar so that it could check a set of productions to determine whether any non-terminals had not been defined, and whether any non-terminals could not possibly be reachable?
For a change, here is a C# version, including the code for a simple table handler
COMPILER EBNFCheck $CN
/* Check a set of EBNF productions to make sure all apparent non-terminals are both defined
(appear on the left of a production rule) and referenced (appear on the right of a rule)
P.D. Terry, Rhodes University, 2012 */
const bool defined = true; // Name them, name them!
const bool referenced = false;
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" .
noquote2 = ANY - '"' .
TOKENS
nonterminal = letter {letter | digit | "_" } .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
EBNFCheck
= (. Table.Clear(); .)
{ Production }
EOF (. Table.CheckNonTerminals(); .)
.
Production
=
SYNC nonterminal (. Table.Add(token.val, defined); .)
WEAK "="
Expression
SYNC "." .
Expression
=
Term
{ WEAK "|" Term
} .
Term
=
[ Factor
{ Factor
}
] .
Factor
= nonterminal (. Table.Add(token.val, referenced); .)
| terminal
| "[" Expression "]"
| "(" Expression ")"
| "{" Expression "}" .
END EBNFCheck.
======================= Table Handler stored in .\EBNFCheck\Table.cs
// Table handler for EBNF checker
// P.D. Terry, Rhodes University, 2012 (C# version)
using Library;
using System;
using System.Collections.Generic;
using System.Text;
namespace EBNFCheck {
class Entry {
public bool defined, referenced;
public string name;
public Entry(string name) {
this.defined = false;
this.referenced = false;
this.name = name;
}
} // Entry
class Table {
static List<Entry> list = new List<Entry>();
public static void Clear() {
// Clear all entries in table
list = new List<Entry>();
} // Clear
public static int Add(string name, bool defining) {
// Search for, and possibly add a nonterminal "name" to the table, according as
// to "where" in a production it was found, and return the position as the
// index where the name was either added previously or added by this call
// debug: IO.WriteLine("add " + name + " " + where);
int position = 0;
while (position < list.Count && !name.Equals(list[position].name)) position++;
if (position >= list.Count) list.Add(new Entry(name));
if (defining)
list[position].defined = true;
else
list[position].referenced = true;
return position;
} // Add
public static void CheckNonTerminals() {
// Check to see whether any non-terminals are not defined or are not referenced
// This could be made rather more sophisticated!
IO.WriteLine("The following non-terminals were never defined");
for (int i = 0; i < list.Count; i++)
if (! list[i].defined) IO.WriteLine(list[i].name);
IO.WriteLine("The following non-terminals were never referenced");
for (int i = 1; i < list.Count; i++) // no need to check goal symbol
if (! list[i].referenced) IO.WriteLine(list[i].name);
} // CheckNonTerminals
} // Table
} //namespace
Home © P.D. Terry