01-lp_tae.docx

G. H. RAISONI COLLEGE OF ENGINEERING SUB- LANGUEAGE PROCESSOR TAE- Technical Comparative Report on LL AND LR Parsing Techniques

Submitted by:Akanksha Borkar Roll no. -01

Technical Comparative Report on LL and LR Parsing Techniques

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 lookaheads. Generally k = 1, so LL(k) may also be written as LL(1).

At a high level, the difference between LL parsing and LR parsing is that LL parsers begin at the start symbol and try to apply productions to arrive at the target string, whereas LR parsers begin at the target string and try to arrive back at the start symbol. An LL parse is a left-to-right, leftmost derivation. That is, we consider the input symbols from the left to the right and attempt to construct a leftmost derivation. This is done by beginning at the start symbol and repeatedly expanding out the leftmost nonterminal until we arrive at the target string. An LR parse is a left-to-right, rightmost derivation, meaning that we scan from the left to right and attempt to construct a rightmost derivation. The parser continuously picks a substring of the input and attempts to reverse it back to a nonterminal. During an LL parse, the parser continuously chooses between two actions: 1. Predict: Based on the leftmost nonterminal and some number of lookahead tokens, choose which production ought to be applied to get closer to the input string. 2. Match: Match the leftmost guessed terminal symbol with the leftmost unconsumed symbol of input.

Diagram

Example 1)As an example, given this grammar:    

S→E E→T+E E→T T → int Then given the string int + int + int, an LL(2) parser (which uses two tokens of lookahead) would parse the string as follows:

Production Input Action --------------------------------------------------------S int + int + int Predict S -> E E int + int + int Predict E -> T + E T + E int + int + int Predict T -> int int + E int + int + int Match int + E + int + int Match + E int + int Predict E -> T + E T + E int + int Predict T -> int int + E int + int Match int + E + int Match + E int Predict E -> T T int Predict T -> int int int Match int Accept Notice that in each step we look at the leftmost symbol in our production. If it's a terminal, we match it, and if it's a nonterminal, we predict what it's going to be by choosing one of the rules.

2)Given the grammar:

E → TE’

1

E’ → +TE’

2

E’ → λ

3

T → FT’

4

T’ → *FT’

5

T’ → λ

6

F → (E)

7

F → id

8

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

In an LR parser, there are two actions: 1. Shift: Add the next token of input to a buffer for consideration. 2. Reduce: Reduce a collection of terminals and nonterminals in this buffer back to some nonterminal by reversing a production.

Diagram

Example 1)As an example, an LR(1) parser (with one token of lookahead) might parse that same string as follows: Workspace Input Action --------------------------------------------------------int + int + int Shift int + int + int Reduce T -> int T + int + int Shift T + int + int Shift T + int + int Reduce T -> int T + T + int Shift T + T + int Shift T + T + int Reduce T -> int T + T + T Reduce E -> T T + T + E Reduce E -> T + E T + E Reduce E -> T + E E Reduce S -> E S Accept 2)

for grammar G2 : 1. SE$ 2.EE+T 3.ET 4.T id 5.T (E)

 closure0( { T ( E ) }  = { T ( E ) , E  E + T , E  T , T  id , T  ( E ) }

LL vs. LR LL

LR

1.Does a leftmost derivation.

1.Does a rightmost derivation in reverse.

2.Starts with the root nonterminal on the stack. 3.Ends when the stack is empty. 4.Uses the stack for designating what is still to be expected. 5.Builds the parse tree top-down. 6.Continuously pops a nonterminal off the stack, and pushes the corresponding right hand side. 7.Expands the non-terminals. 8.Reads the terminals when it pops one off the stack. 9.Pre-order traversal of the parse tree. 10.LL parser begin at the start symbol and try to apply productions to arrive at the target string

2.Ends with the root nonterminal on the stack. 3.Starts with an empty stack. 4.Uses the stack for designating what is already seen. 5.Builds the parse tree bottom-up. 6.Tries to recognize a right hand side on the stack, pops it, and pushes the corresponding nonterminal. 7.Reduces the non-terminals. 8Reads the terminals while it pushes them on the stack. 9.Post-order traversal of the parse tree. 10.LR parser begin at the target string and try to arrive back at the start symbol.

11.LL parsing, also known as top-down

11.LR parsing, also known as bottom-up

parsing

parsing .

12.LL starts with only the root non

12.LR ends with only the root non terminal on

terminal on the stack

the stack .

13.LL uses grammar rules in an order

13. LR does a post-order traversal.

which corresponds to pre-order traversal of the parse tree 14.LL continuously pops a non terminal off 14.LR tries to recognize a right hand side on the stack, and pushes a corresponding right the stack, pops it, and pushes the hand side corresponding non terminal .

15.LL reads terminal when it pops one off

15. LR reads terminals while it pushes them

the stack

on the stack .