This should take no longer than about 40 minutes and is simply intended to probe whether you have understood the material in the prac questions. You may use your textbook if you think it will help, but not a computer. Answer on the question sheet (4 sides).
1. Sorry, I am getting past it and have forgotten. What are your: (first name) surname student number (in that format)? [2]
2. Define concisely the meaning of "ambiguous grammar". [2]
3. Define concisely the conditions that must be satisfied for a grammar to earn the title "LL(1) grammar". [4]
4. Can an "LL(1) grammar" be ambiguous? [1]
5. Give an example of a simple grammar that is unambiguous, but is also non-LL(1)? [3]
Time to stop watching videos, playing computer games, and checking FB - listen to steam radio
Consider how we might describe the daily activities of SAFM - "your news and information leader" (more realistically described as a non-stop party political broadcast). Hour by hour Bongi, Tsepiso, Nancy, Ashraf, Elvis, Sakina and their comrades present what are generously called shows. These include music and advertisements when there is nothing more interesting. What passes as "information" is provided by news bulletins, weather reports and talk shows. News bulletins consist of a homogeneous stream of stories, while talk shows consist of interchanges between a host and any listeners who are keen enough to phone in - with the announcer hosting the talk show getting the first and last word on the subject, of course.
The staff at Auckland Park have made an attempt to describe a typical day's activities as shown below. Items like "advert", "rain" and "music" are really in the category of the lexical terminals which a scanner (in the person of someone listening to the radio) would recognize as key symbols while parsing a broadcast.
Radio = { TalkShow | NewsBulletin | "music" | "advert" } .
NewsBulletin = "advert" NewsItem { NewsItem } [ Weather ] Filler .
NewsItem = "ANC" [ "Zuma" ] | "strike" | [ "Zuma" ] "ANC" | "Wayde"
| "corruption" | "LGE" { "LGE" } | "Oscar" | Accident .
TalkShow = {"host" "listener" } "host" [ Filler ] .
Accident = "another" ( number "lives" | "life" ) "lost" .
Filler = "advert" | "music" .
Weather = { ( "snow" | "rain" | "cloudy" | "windy" ) "in" province } .
6. Read the productions very carefully and then add a few lines of code so as to produce a complete Cocol grammar which also incorporates the directives or pragmas that request Coco/R to test the grammar and to evaluate the FIRST and FOLLOW sets for the non-terminals. [8]
Radio = { TalkShow | NewsBulletin | "music" | "advert" } .
NewsBulletin = "advert" NewsItem { NewsItem } [ Weather ] Filler .
NewsItem = "ANC" [ "Zuma" ] | "strike" | [ "Zuma" ] "ANC" | "Wayde"
| "corruption" | "LGE" { "LGE" } | "Oscar" | Accident .
TalkShow = {"host" "listener" } "host" [ Filler ] .
Accident = "another" ( number "lives" | "life" ) "lost" .
Filler = "advert" | "music" .
Weather = { ( "snow" | "rain" | "cloudy" | "windy" ) "in" province } .
7. What are the sets FIRST(Weather) and FOLLOW(Weather)? [4]
8. As it is expressed here, which (if any) of the seven non-terminals would be regarded as "nullable"? [4]
9. HM, the COO of the SABC, asked a graduate of CSC 301 to use Coco to analyse this grammar. To his horror he was told that this turned up 8 (eight) distinct "LL(1) warnings". He demanded an explanation for each one, presumably so that #HeadsMustRoll. Can you predict at least seven of these and explain them (without using Coco for yourself). [24]
Radio = { TalkShow | NewsBulletin | "music" | "advert" } .
NewsBulletin = "advert" NewsItem { NewsItem } [ Weather ] Filler .
NewsItem = "ANC" [ "Zuma" ] | "strike" | [ "Zuma" ] "ANC" | "Wayde"
| "corruption" | "LGE" { "LGE" } | "Oscar" | Accident .
TalkShow = {"host" "listener" } "host" [ Filler ] .
Accident = "another" ( number "lives" | "life" ) "lost" .
Filler = "advert" | "music" .
Weather = { ( "snow" | "rain" | "cloudy" | "windy" ) "in" province } .
10. Being a good politician, HM hoped that all these warnings must mean that this description was in fact ambiguous. His logic might or might not be correct, but can you put him at ease and confirm his suspicion? (He will need convincing, merely saying yes or no won't satisfy him.) [3]
11, Clearly the SABC should be restructured to avoid all these potential problems. Can you write a grammar similar to the one suggested here that would pass a Coco test and would adequately describe a day's activities? REMINDER - in Terry-speak, "Can you write" doesn't just mean "answer yes or no". It means - "if yes, actually write the new set of productions" else "if no, explain exactly why not".
You need only write out the new versions of those productions that must be changed. [10]