Build LL(1) Parse Table

LL(1) parse table building.

The user may build a LL(1) parse table for a grammar with this operator. A full discussion of the method of building an LL(1) parse table is far too elaborate for this documentation. Rather, this assumes that one has some understanding of building LL(1) parse tables, and merely explains JFLAPs interface convention for helping the user complete this procedure.

The LL(1) parse table construction and parse tree construction algorithm is as described in the ``Dragon'' compiler book. Put very loosely, the idea behind LL(1) parsing is that the grammar starts with the start symbol, and repeatedly attempts to replace variables with their right hand side expansion based on what the next symbol of the input is, until the input string is derived.

Steps

When the user first chooses the menu item to build the parse table, JFLAP first checks to make sure that the grammar is LL(1). If it is not, then the user is warned and is given the option to abort. Assuming the grammar is LL(1), or if the user wishes to continue in spite of the grammar not being LL(1), these following steps are completed in order:

1. The user first enters the first sets for each variable, i.e., the set of terminals that a variable can start with. ! serves as the special symbol for lambda. This set is entered by the user as a simple string of symbols, without any delimiters: e.g., if the user wishes to indicate that a, b, and are in the first set, then the user enters ab! as a single non-spaced string. When the user is finished defining the first sets, he or she may press "Next," and JFLAP will either move to defining the follow sets, or will notify the user about errors.
2. The user then enters the follow sets for each variable, i.e., the set of terminals that can immediately follow a variable in a derivation. The input convention is the same as for the first sets, except that the $ symbol indicates the end-of-string character. When the user has finished, again "Next" may be pressed to move on or be notified of errors.
3. With the first and follow sets as a reference, it is possible to fill out the entries in the parse table. Given a production A and every symbol b in FIRST(), the (b, A) entry in the table gets . Multiple entries in a table cell (possible only if the grammar is not LL(1)) are separated by spaces. The ! string represents a lambda production.

Help

Users may elect to let JFLAP do some or all of the work rather than entering data themselves.

Do Selected

In any of the above steps, the user enters input into cells in a table. If the user selects any of these cells and elects to "Do Selected", the answer appropriate to the cells will be entered into those cells which are currently selected. Non-selected cells shall be left alone.

Do Step

This will either complete all first sets, or all follow sets, or complete the parse table according to which step we are on.

Do All

This will do everything. After pressing this, JFLAP should display a working parse table.

Parsing Details

The top figure shows a completed LL(1) parse table. Once the table is completed, the user has the option to proceed to parsing strings using the table by pressing the "Parse" button. The interface for that parsing is explained here. If the original grammar was not LL(1) the user will not be able to use the parse table to parse strings.