Lab 4 - Constructing the LL(1) Table

Objectives

The objectives of this laboratory exercise are:

to give you your first hands-on exposure to the construction of LL(1) tables.
to allow you to begin work on expanding your parser stubs.

To Do

LL(1) Table Construction

NOTE: Chrome may not be able to run the animations in the page. Use Firefox.

Open a spreadheet. Construct an LL(1) table for the grammar below. You don't know the algorithms well for doing this yet, but you are to explore how such algorithms might be designed by simply trying to build the LL(1) table from scratch. Be sure that the following points are covered.

The rows are to be labeled with the nonterminals of the grammar.
The columns are to be labeled with the tokens of the grammar.
The entries of the table are to be the numbers of the correct grammar rules to apply. That is, if one is about to expand nonterminal A and the lookahead token is t then the entry in row A column t should be the rule number i to apply to A. Note that most entries in row A for all nonterminals A will be blank. This just means that if one is about to expand A and the lookahead token is t', but the entry in row A, column t' is empty, no rule applies, indicating a parse error.
The table must be constructed (as all LL(1) tables are) to find errors at the earliest possible point. This just means that you should not apply a rule except in cases where you know exactly which tokens predict that this rule should be applied.

Once your table has been constructed, turn it in to the Lab 4 dropbox. Then access the LL(1) animator (be sure to use Firefox when accessign the animator) written by Master's student Nick Degenhart, to test your LL(1) table. You will need to be patient as you load the animator...might take a while.

To input a grammar, click the "grammar" button and read the rules.
Input the rules one line at a time.
When finished inputting the rules of the grammar, click the "grammar" button again and then click "submit"
The top pane will tell you whether your grammar is in the proper form or not. If it isn't, fix it
Once the grammar is fixed you can click the proper button to construct the LL(1) table and compare it with yours (or just click the "show" button to see the LL(1) table for your grammar).
To construct an LL(1) table click the "construct" button, and then the "start" button. Enter the values into the table. When you want to check your work, click "construct" again, and the "finish". If there is an error in any entry, a "^" will be printed in that entry.

In order to use the LL(1) animator, you will need to enter the grammar below. Do this by shortening all of the names in the standard way. For example, change <expression> to <e> and <expression_tail> to <e_t>. When you enter a rule, do it in the following form:

 3 <e_t> ⟶ + <t> <e_t>

Notice that there is a leading number, which is the number of the rule. This number has no period behind it. Between each piece there is a blank. The rule arrow is the - followed by the >. The best way to install the grammar is to do a "submit" after each rule you enter to see if the grammar is progressing ok.

Try to understand any mistakes you made. Modify your LL(1) table appropriately and use it to parse the following strings. You can use the grammar_animator to do these parses. Bring up the grammar called Arithmetic Exp #3. To do this, click the Access Grammar Tools Menu button in the animation window. This brings up another list; click select a different grammar from menu. Finally click on the desired grammar. You can now begin working.

Use <expression> as the start symbol. You should be able to do each of these parses without thinking. If you have to think ahead more than one lookahead token, you aren't trusting your LL(1) table.

a + b * c ^ 3 eof

a * b + c ^ 3 eof

a ^ ( 3 + b ) * c eof

The Grammar

1.  <start>           ⟶ <expression> eof
2.  <expression>      ⟶ <term> <expression_tail>
3.  <expression_tail> ⟶ + <term> <expression_tail>
4.  <expression_tail> ⟶ - <term> <expression_tail>
5.  <expression_tail> ⟶ ε
6.  <term>            ⟶ <factor> <term_tail>
7.  <term_tail>       ⟶ * <factor> <term_tail>
8.  <term_tail>       ⟶ / <factor> <term_tail>
9.  <term_tail>       ⟶ ε
10. <factor>          ⟶ <primary> <factor_tail>
11. <factor_tail>     ⟶ ^ <primary> <factor_tail>
12. <factor_tail>     ⟶ ε
13. <primary>         ⟶ identifier
14. <primary>         ⟶ integer_literal
15. <primary>         ⟶ ( <expression> )

Parser Stubs

Your project milestone for next week will be to flesh out the nonterminal stubs in your parser. For this lab, practice as a group by writing a pseudocode procedure for <term> from the above grammar and a pseudocode procedure for <term_tail> using your LL(1) table. Agree on how it is to be done.

To Turn In

Turn in your updated LL(1) table, and your parse trees printed or captured from the grammar animator in PDF form.

Be sure your team information is in the upper left corner:

Your group number
The lab number
Today's date
Your team names and e-mail addresses