Activity: LL(1) parsing with and without a table

Table of Contents

1. Activity structure

This is an activity not an assignment.That means it is not graded: you won't get formal feedback on it, but it is a great chance to practice with the ideas we've been talking about and it may also guide you through some new ideas. You'll work on it during class, usually with another students, or if you have to miss class, you'll complete it outside of class.

If you're working with someone, you should work in a paired programming style. At any point in time, one of you is "driving," i.e. actually using the keyboard and mouse. The other is actively engaged following along, preventing bugs, and providing ideas. You'll tradeoff who is driving about every 10 minutes, and it's important that regardless of whose computer you're using, you take turns typing and controlling it - the owner of the computer should not be the only one who drives. Before you start coding for a new part of the activity, I strongly encourage you to sketch out your strategy with your partner. You might discuss possible approaches together, and write down some ideas on paper that will then help you when you begin coding.

At the end of class, you should make sure you turn your code in (even if you're not done), as that gives you access to my solutions, and to email the code to your partner (so they can turn it in to access my solutions).

2. Setup

If both you and your partner have computers with you with the tools for our class setup on it, decide whose computer you'll be using.

Them you'll do the activity in VS Code: download the starter code (below), unzip it, move it into the ProgrammingLanguages folder for our Docker container, and then open that folder within the Docker container in VSCode.

3. Setup

Download the starter code, move it to your ProgrammingLanguages folder, and open the ProgrammingLanguages folder in VSCode.

Click here to access the starter code for this activity

Note: This activity relies on Python. You can run python in your Docker container using python3

4. Tasks

In this activity, you'll be automatically creating a grammar table given a grammar, as well as using a grammar table to do LL(1) parsing. You'll write some of your own code and also read some of my code.

6. Creating a grammar table

We've spent a few days in class talking about rules for creating a grammar table. These can be complex to work through, but our goal was to describe them systematically so that they could be implemented on a computer. I've written part of the grammar table generator for you in tableGenerator.py and you'll write the rest.

6.1. Getting familiar with the code

First, take a look at the constructor (__init__) in the =Grammar class as well as the file grammar.txt. How are the instance variables set based on the grammar file? Try running the code and add lines to main to print out the instance variables from Grammar so you can see what they'll look like.

6.2. First sets

The method makeFirstSets has the start of making first sets: it initializes the first sets and then has a loop to continue to update the rules until no changes occur. However, the method it calls, updateFirstSets, is not yet implemented. You'll fill in the code. Note that the prototype is already there, along with a comment describing the expected behavior. Fill in the code so that they update the first set for the lefthand side of the given rule.

Test your implementation using main.

Some code tips:

  • If you want to initialize a set with a single string in it, you can do set([myString]) where myString is the string you'd like in the set.
  • I've provided a helper function unionIntoSetWithoutEpsilon. Read the comment to find out what it does. It returns two things: the new set, and a boolean for whether the elements of the set changed as a result of the union. Here's an example of how to call it:
newSet, changed = unionIntoSetWithoutEpsilon(setToStartWith, setToUnionIn)

6.3. Follow sets

Now that you have first sets implemented, we'll also want follow sets. Again, I've written a method makeFollowSets that has the start of the implementation, but you should fill in the missing code in updateFollowSets.

Test your implementation using main.

Some code tips:

  • I've provided the method getFirstSetForSequence which you may use as a helper.
  • You may also want to use unionIntoSetWithoutEpsilon as a helper.

6.4. Creating the table

Now, we want to use the first and follow sets to create the grammar table. Most of this code is present in makeGrammarTable, but I've deleted the lines that add rules to the table. Modify the code to correctly create the grammar table. Use addToTable as a helper function: it takes in a table, a row, a column, and a rule, and adds that rule in that spot in the table.

(Your code here is likely short: I only deleted three lines from my solution.)

6.5. Try it!

Uncomment the final part of main to write a grammar table! If you want to format your results more nicely, you can do something like 

  for t in table:
    for g in table[t]:
      print("(", t, ",", g, "):", table[t][g])

You can compare your results to grammarTableSolution.txt, although note that your rules may or may not appear in the same order.

7. Working with code for a table parser

Now that you have a grammar table, you might want to actually parse strings with it. In the starter code, you'll see a file name tableParser.py. Read through the code, and answer the questions about it in Questions.txt.

8. Extra time?

If you have extra time, here are a couple of things you might try:

  • On Moodle, there is a worksheet available for extra practice. Try doing the worksheet, and compare your results to what your table generator produces.
  • I have some repeated code in makeFollowSets and makeFirstSets. It turns out Python can be used in an imperative way, in an object-oriented way, and even in a functional way. You can pass functions to other functions as input! Refactor my code to avoid the duplication, taking advantage of the ability to pass one function to another.

Activity originally designed by Anna Rafferty - thanks for sharing!