SLR(1) parse table building.

SLR (1) Parsing. It is a simple LR parsing. Most of the function of this parsing is the same as LR (0) parsing. The parsing table for both the parser vary. The SLR (1) parsing use canonical LR (0) item. The reduce move is placed only in the FOLLOW of those variables whose production is reduced. Building SLR Parse Tables The easiest technique for generating LR-based parse table is known as SLR (Simple LR). Understanding this technique should provide you with what you need to know to understand how LR parsers work in general; it is also the foundation for the more complex techniques (LR and LALR).

The user may build a SLR(1) parse table for a grammar with this operator. As with LL(1) table building, a full discussion of the method of building an SLR(1) parse table is beyond the scope of this discussion. The procedure followed is more or less the same as the SLR parse table building in the Dragon compiler book.

This shares some similarities with the LL(1) parse table builder view. The similarities include the building of the first and follow sets, the operations of controls at the top of the help window and so forth. That may be helpful as a reference.

NB: In this view, you may resize the views to see things better. For example, dragging the bar between the sets of items diagram and the parse table will adjust the sizes of both.

Steps

The following steps are completed in order to build an SLR(1) parse table:

1. The user first enters the first and follow sets for each variable. The interaction that takes place here is identical to that of the LL(1) parse table's first and follow sets construction.
2. 
   A set of items construction.

   The next step is the construction of the sets of items in a transitional diagram. What a transitional diagram is and how it is put together is not covered here, as a full description would be prohibitively long. JFLAP represents a transitional diagram by a FSA as shown in the figure at the top of the page, with each state corresponding to a set of items. The initial set of items corresponds to the initial state, and final states represent terminating sets of items. The items in a set are shown in the label below a state.

   An item is essentially a production with some placeholder character; JFLAP uses an underscore, _, as this special character. A production A BCD can produce the four items A _BCD, A B_CD, A BC_D, and A BCD_. The marker _ in an item represents which symbols have been processed (to the left of the marker) and which have not been processed (to the right of the marker).

   During the first part of the sets of items construction, the initial set of items is put together (i.e., S' S and its closure). To expand that set, use the transition tool (), and drag from a set to an empty space in the diagram. The user is queried as to the symbol to expand the set of items on. Once the user enters a grammar symbol and JFLAP confirms that the set of items does goto on that set, a dialog then pops up allowing the user to define the set of items.

   The view used for defining a set of items is shown above. The left hand column lists those productions in the grammar. The right hand column lists items already part of the set. To add an item to the set, click a production in the left hand list. A pop-up menu will appear with all possible placements of the sets of items. To save time, the 'Closure' item will take whatever items are selected in the right column, and add all items which comprise the closure of the selected item. The 'Finish' button will add all items that should be in the set of items. When 'OK' is pressed, the answer will be checked for mistakes. If everything is fine, a new set of items will appear at the point in the empty space that the user initially dragged to.

   If the user wishes to define a transition from an existing set of items to another existing set of items, in creating the transition she may drag to the second set rather than to empty space. This will avoid the bother of defining the second set of items, as JFLAP will assume the set dragged to is that second set.

   One uses the attribute tool () to drag states around, and set final and initial states as per the usual practice when editing. The attribute tool here does not have the ability to change transitions or set labels.

3. Once all sets of items are constructed, the parse table is built. In the parse table, a blank entry indicates an error in parsing, s means shift, r means reduce, a single number means goto that item, and acc is accept. To change the content of a cell, click the cell and start typing. For reduction, the number following the r is a production number. The productions are indexed from 0 onward in the order shown in the list on the left. For example, in the grammar given above r1 means 'reduce by S aSb.' To determine the number of a production without counting, hold the mouse over the production, and a tool tip will appear with the production number. When the table is completed the user may press 'Next.' If there are no errors, one may proceed to parse strings with that table.

Help

The style of help that is available for SLR(1) table construction is nearly identical to that available for LL(1) table construction: 'Do Selected,' 'Do Step,' and 'Do All' are all there and work in the same fashion.

In the case of the sets of items construction, the help options available are 'Do Step' and 'Do All,' which will randomly place any set of items. After the items are placed, one may rearrange them to make the view more aesthetically pleasing, but it will otherwise be immutable.

Parsing Details

The top figure shows a completed SLR(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.

There may be at least one cell in the table with more than one rule, and the user may choose which of the rules to use before parsing. Cells with more than one expansion are highlighted in a sort of sherbet orange color. One may click on these cells, and a pop-up menu will appear allowing the user to select which expansion to use for this cell. Note that if clarifying ambiguity becomes necessary, the parse table may not accept the same language as the original grammar since, obviously, the parser will not be aware that alternate shifts/reductions/whatever exist.

• Compiler Design Tutorial

• Compiler Design Useful Resources

• Selected Reading

C Parsing String

In the previous chapter, we understood the basic concepts involved in parsing. In this chapter, we will learn the various types of parser construction methods available.

Parsing can be defined as top-down or bottom-up based on how the parse-tree is constructed.

Top-Down Parsing

We have learnt in the last chapter that the top-down parsing technique parses the input, and starts constructing a parse tree from the root node gradually moving down to the leaf nodes. The types of top-down parsing are depicted below:

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.

This parsing technique is regarded recursive as it uses context-free grammar which is recursive in nature.

Back-tracking

Top- down parsers start from the root node (start symbol) and match the input string against the production rules to replace them (if matched). To understand this, take the following example of CFG:

For an input string: read, a top-down parser, will behave like this:

It will start with S from the production rules and will match its yield to the left-most letter of the input, i.e. ‘r’. The very production of S (S → rXd) matches with it. So the top-down parser advances to the next input letter (i.e. ‘e’). The parser tries to expand non-terminal ‘X’ and checks its production from the left (X → oa). It does not match with the next input symbol. So the top-down parser backtracks to obtain the next production rule of X, (X → ea).

Now the parser matches all the input letters in an ordered manner. The string is accepted.

Predictive Parser

Predictive parser is a recursive descent parser, which has the capability to predict which production is to be used to replace the input string. The predictive parser does not suffer from backtracking.

To accomplish its tasks, the predictive parser uses a look-ahead pointer, which points to the next input symbols. To make the parser back-tracking free, the predictive parser puts some constraints on the grammar and accepts only a class of grammar known as LL(k) grammar.

Sample Program In C++ Programming

Predictive parsing uses a stack and a parsing table to parse the input and generate a parse tree. Both the stack and the input contains an end symbol $ to denote that the stack is empty and the input is consumed. The parser refers to the parsing table to take any decision on the input and stack element combination.

In recursive descent parsing, the parser may have more than one production to choose from for a single instance of input, whereas in predictive parser, each step has at most one production to choose. There might be instances where there is no production matching the input string, making the parsing procedure to fail.

LL Parser

An LL Parser accepts LL grammar. LL grammar is a subset of context-free grammar but with some restrictions to get the simplified version, in order to achieve easy implementation. LL grammar can be implemented by means of both algorithms namely, recursive-descent or table-driven.

LL parser is denoted as LL(k). The first L in LL(k) is parsing the input from left to right, the second L in LL(k) stands for left-most derivation and k itself represents the number of look aheads. Generally k = 1, so LL(k) may also be written as LL(1).

LL Parsing Algorithm

We may stick to deterministic LL(1) for parser explanation, as the size of table grows exponentially with the value of k. Secondly, if a given grammar is not LL(1), then usually, it is not LL(k), for any given k.

Given below is an algorithm for LL(1) Parsing:

Slr Parsing Table Program In Ct

A grammar G is LL(1) if A → α | β are two distinct productions of G:

• for no terminal, both α and β derive strings beginning with a.

• at most one of α and β can derive empty string.

• if β → t, then α does not derive any string beginning with a terminal in FOLLOW(A).

Bottom-up Parsing

Bottom-up parsing starts from the leaf nodes of a tree and works in upward direction till it reaches the root node. Here, we start from a sentence and then apply production rules in reverse manner in order to reach the start symbol. The image given below depicts the bottom-up parsers available.

Shift-Reduce Parsing

C Programming String Parsing

Shift-reduce parsing uses two unique steps for bottom-up parsing. These steps are known as shift-step and reduce-step.

• Shift step: The shift step refers to the advancement of the input pointer to the next input symbol, which is called the shifted symbol. This symbol is pushed onto the stack. The shifted symbol is treated as a single node of the parse tree.

• Reduce step : When the parser finds a complete grammar rule (RHS) and replaces it to (LHS), it is known as reduce-step. This occurs when the top of the stack contains a handle. To reduce, a POP function is performed on the stack which pops off the handle and replaces it with LHS non-terminal symbol.

LR Parser

The LR parser is a non-recursive, shift-reduce, bottom-up parser. It uses a wide class of context-free grammar which makes it the most efficient syntax analysis technique. LR parsers are also known as LR(k) parsers, where L stands for left-to-right scanning of the input stream; R stands for the construction of right-most derivation in reverse, and k denotes the number of lookahead symbols to make decisions.

There are three widely used algorithms available for constructing an LR parser:

• SLR(1) – Simple LR Parser:
  • Works on smallest class of grammar
  • Few number of states, hence very small table
  • Simple and fast construction
• LR(1) – LR Parser:
  • Works on complete set of LR(1) Grammar
  • Generates large table and large number of states
  • Slow construction
• LALR(1) – Look-Ahead LR Parser:
  • Works on intermediate size of grammar
  • Number of states are same as in SLR(1)

Input Parsing C

LR Parsing Algorithm

Here we describe a skeleton algorithm of an LR parser:

LL vs. LR

Slr Parsing Table Program In C Programming

LL	LR
Does a leftmost derivation.	Does a rightmost derivation in reverse.
Starts with the root nonterminal on the stack.	Ends with the root nonterminal on the stack.
Ends when the stack is empty.	Starts with an empty stack.
Uses the stack for designating what is still to be expected.	Uses the stack for designating what is already seen.
Builds the parse tree top-down.	Builds the parse tree bottom-up.
Continuously pops a nonterminal off the stack, and pushes the corresponding right hand side.	Tries to recognize a right hand side on the stack, pops it, and pushes the corresponding nonterminal.
Expands the non-terminals.	Reduces the non-terminals.
Reads the terminals when it pops one off the stack.	Reads the terminals while it pushes them on the stack.
Pre-order traversal of the parse tree.	Post-order traversal of the parse tree.