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
=
( "+" Term
| "-" Term
| Term
) { AddOp
Term
} .
Term
= Factor
{ MulOp
Factor
} .
Factor
=
Designator
| number
| "(" Expression
")" .
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 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?
COMPILER EBNF $CN
CHARACTERS
letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" .
digit = "0123456789" .
noquote1 = ANY - "'" .
noquote2 = ANY - '"' .
TOKENS
nonterminal = letter {letter | lowline } .
terminal = "'" noquote1 {noquote1} "'" | '"' noquote2 {noquote2} '"' .
IGNORE CHR(9) .. CHR(13)
PRODUCTIONS
EBNF
=
{ Production
}
EOF
.
Production
= SYNC nonterminal
WEAK "="
Expression
SYNC "." .
Expression
= Term
{ WEAK "|" Term
} .
Term
= [ Factor
{ Factor
}
] .
Factor
=
nonterminal
| terminal
| "[" Expression "]"
| "(" Expression ")"
| "{" Expression "}" .
END EBNF.
3. You will remember meeting the staff in a previous practical (you can find this in Staff1.txt):
R. J. Foss, BSc, MSc, PhD.
Professor Philip Machanick, PhD.
Professor P. D. Terry, MSc, PhD.
George Clifford Wells, BSc(Hons), MSc, PhD.
Greg G. Foster, PhD.
James Connan, MSc.
Ms Michelle Coupe.
Phumezo Dukashe.
Professor Karen Lee Bradshaw, MSc, PhD.
Mx Mic Halse, MSc.
Vivian Kila .
Dr Mos Tsietsi .
C. Hubert H. Parry, BMus.
Prof Barry V. W. Irwin, PhD.
Miss Busi Mzangwa.
Mrs Caroline A. Watkins, BSc.
and, perhaps, coming up with something like the following grammar for parsing such a list (Staff.atg):
COMPILER Staff $CN
/* Describe a list of academic staff in a department
P.D. Terry, Rhodes University, 2016 */
CHARACTERS
uLetter = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" .
lLetter = "abcdefghijklmnopqrstuvwxyz" .
letter = uLetter + lLetter .
TOKENS
name = uLetter { letter | "'" uLetter | "-" uLetter } .
initial = uLetter "." .
IGNORE CHR(0) .. CHR(31)
PRODUCTIONS
Staff = { Person } EOF .
Person = [ Title ] FullName { "," Degree } SYNC "." .
FullName = NameLast { NameLast } .
NameLast = { initial } name .
Title = "Professor" | "Prof" | "Dr" | "Mr" | "Mrs" | "Ms" | "Mx" | "Miss" .
Degree = "BA" | "BSc" | "BCom" | "BMus" | "BEd" | "BSocSci"
| "BSc(Hons)" | "BCom(Hons)" | "MA" | "MSc" | "PhD" .
END Staff.
The HR Division (who should already know all these things, but like to pretend they do not, just to make work for people like Mrs Caroline A. Watkins) have asked us to prepare them a list extracted from the above list (or another one like it - each department has been asked to do this, and you could Get Rich by putting your compiler course to good use). The extract list must simply list all the initials and surnames for each of the staff who has a PhD, namely be something like
Dr R.J. Foss
Dr P. Machanick
Dr P.D. Terry
Dr G.C. Wells
Dr G.G. Foster
Dr K.L. Bradshaw
Dr M. Tsietsi
Dr B.V.W. Irwin
(What a clever bunch. Work hard and you might join them some day.)
Add to the Cocol grammar the appropriate actions needed to perform this task, and let's get HR off our backs until tomorrow, when doubtless they will throw more administrivia in our direction.
Oh, while you are about it, sometimes the degree qualifications mention where that degree was obtained.
R. J. Foss, BSc (Natal), MSc(UNISA), PhD(Rhodes).
Professor Philip Machanick, PhD.
Professor P. D. Terry, MSc(Rhodes), PhD (Cantab).
George Clifford Wells, BSc(Hons) (Rhodes), MSc(Rhodes), PhD (Bristol).
Greg G. Foster, PhD(Rhodes ).
James Connan, MSc(Stell).
Ms Michelle Coupe.
Phumezo Dukashe.
Dr Karen Lee Bradshaw, MSc(Rhodes), PhD(Cantab).
Mx Mic Halse, MSc(Rhodes).
Vivian Kila .
Dr Mos Tsietsi .
C. Hubert H. Parry, BMus(Cantab).
Professor Hannah Thinyane, BA, BSc (Adelaide), PhD(South Australia).
Dr Barry V. W. Irwin, PhD(Rhodes).
Professor Alfredo Terzoli.
Ms Busi Mzangwa.
Mrs Caroline A. Watkins, BSc (UCT).
How could you handle this sort of list without adding to the already long list of possible qualifications?
And by now you should know that "How would you" is PDT-speak for "write the code to do it"!
Hints:
For a problem as simple as this one does not really need to parameterise the parsing routines - it will suffice to store the "semantic state" in a few static fields in the Parser class, which can be introduced at the start of the ATG file. Take particular care with the way in which you add the actions - it is easy to put them in slightly wrong places, and then to wonder why the system does not give the results you expect.