LL(1) Tables (First Look)

Laboratory Exercise for February 19

Objectives

The objectives of this laboratory exercise are:

to have you evaluate someone else's scanner.
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.

Preparing for Lab

One of your project assignments for this week was to have a binder of your program due today ready for evaluation. You were also to have your executable code ready for testing. With these items, do the following:

The team leader must place an executable version of your scanner (complete with driver, of course) in your root directory (or as specified by the TA). This executable version is to be called mp. Permissions must be set to make this file (mp) readable by the world. Also, it may be necessary for the team leader to set permissions on his or her home directory to make it readable and executable by the world so that others can actually get into the file to obtain a copy of your mp. Once this has been done, a different member of the team can see if he or she can execute the scanner by copying mp from the directory of the team leader to his or her local directory and then executing it. Be sure to not make only your executable mp accessible to others, not your scanner source, or worse, your entire directory structure!
Turn your binders in to the TA. He will redistribute them so that you are evaluating some other team's code and executable.
Follow the TA's directions on submitting your scanner source code.
Turn your journal and time sheet in to the TA individually. Do not include them in the binder!

To Do

Program Evaluation

Complete the evaluation worksheet.

LL(1) Table Construction

Get out a clean sheet of paper. Construct an LL(1) table for the grammar below. You don't know the algorithms 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. Use an editor or word processor to complete this task, and print the results when you are done. 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 in that situation.
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, print your table and turn it in to the TA. Access the LL(1) 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> -> l
6.  <term>            -> <factor> <term_tail>
7.  <term_tail>       -> * <factor> <term_tail>
8.  <term_tail>       -> / <factor> <term_tail>
9.  <term_tail>       -> l
10. <factor>          -> <primary> <factor_tail>
11. <factor_tail>     -> ^ <primary> <factor_tail>
12. <factor_tail>     -> l
13. <primary>         -> identifier
14. <primary>         -> integer_literal
15. <primary>         -> ( <expression> )

Parser Stubs

Your project assignment 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 program evaluation, your LL(1) table, and your parse trees printed from the grammar animator.

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