Grammar Analysis

Niels Reyngoud

---

List of updates

• 09-10-2003: Initial page was created.
• 09-17-2003: Added the literature we're going to use to the page.
• 09-30-2003: Richard quit with the AFP course so I'm now going to do this presentation on my own.
• 10-20-2003: Attached the document that has been used in the creation of the presentation.
• 10-27-2003: Added the exercise and the final version of the slides.
• 10-28-2003: Updated the slides and the exercise.

Literature

• Jeuring, Johan and Swierstra, Doaitse, Bottom-Up Grammar Analysis - A Functional Formulation.
  (this file wasn't available at the ACM, therefore it has been attached to this page).
• Jeuring, Johan and Swierstra, Doaitse, Constructing functional programs for grammar analysis problems.
  (this paper was dropped since I'm now doing this presentation on my own).

Slides

The slides of the presentation have been attached to this WIKI-page and can be downloaded at the bottom of the page.

Exercise

Exercise 1: At the lecture I discussed the "first(s)" grammar analysis problem. The exercise is to do the same for the "last(s)" problem. "last" deals with finding the set of terminals that can appear as the last element of a string of terminals derivable from a particular non-terminal nt. "lasts" deals with doing this for all the non-terminals in the grammar.

• Give the definition of the function "last".
• Show how the algorithm that was derived in the paper and during the lecture can be used to solve the "lasts" problem (the proof of the monotonity of the function H can be omitted).

Hint: In the paper you can find the definition for "first" and the way the "firsts" problem was solved with the algorithm.

Exercise 2: At the lecture I showed that the "first(s)" problem uses the "empties" problem. Show how these two problems can be combined in the algorithm that was derived at the lecture. Describe why you think your solution is correct.

The solution to this exercise has to be sent to nreijngo@cs.uu.nl before (or at ) the 4th of november.

Marks

studentnumber	mark
0019720	+
0054445	+
Arjan Oosting	+
0019356	+
0041130	+
9952330	+
0019755	+

-- NielsReyngoud - 27 Oct 2003