An efficient bottom-up syntax analysis technique that can be used CFG is called LR(k) parsing. The ‘L’ is for left-to-right scanning of the input, the ‘R’ for constructing a rightmost derivation in reverse, and the ‘k’ for the number of input symbols. When ‘k’ is omitted, it is

assumed to be 1.

**Advantages of LR parsing:**

1. It recognizes virtually all programming language constructs for which CFG can be written.

2. It is an efficient non-backtracking shift-reduce parsing method.

3. A grammar that can be parsed using LR method is a proper superset of a grammar that can be parsed with predictive parser

4. 4. It detects a syntactic error as soon as possible.

**Drawbacks of LR method:**

It is too much of work to construct a LR parser by hand for a programming language grammar. A specialized tool, called a LR parser generator, is needed. Example: YACC.

**Types of LR parsing method:**

1. SLR- Simple LR

Easiest to implement, least powerful.

2. CLR- Canonical LR

Most powerful, most expensive.

3. LALR- Look-Ahead LR

Intermediate in size and cost between the other two methods.

**The LR parsing algorithm:**

The schematic form of an LR parser is as follows:

**Fig. 2.5 Model of an LR parser**

It consists of an input, an output, a stack, a driver program, and a pa parts (action and goto).

Ø The driver program is the same for all LR parser.

Ø The parsing program reads characters from an input buffer one at a time.

Ø The program uses a stack to store a string of the form s0X1s1X2s2…Xmsm, where sm is on top. Each Xi is a grammar symbol and each si is a state.

Ø The parsing table consists of two parts : action and goto functions.

**Action : **The parsing program determines sm, the state currently on top of stack, and ai, the** **current input symbol. It then consults action[sm,ai] in the action table which can have one of four values:

1. shift s, where s is a state,

2. reduce by a grammar production A → β,

3. accept,

4. 4. error.

**Goto : **The function goto takes a state and grammar symbol as arguments and produces a state.

**LR Parsing algorithm:**

Input: An input string w and an LR parsing table with functions action and goto for grammar G. Output: If w is in L(G), a bottom-up-parse for w; otherwise, an error indication.

Method: Initially, the parser has s0 on its stack, where s0 is the initial state, and w$ in the input buffer. The parser then executes the following program:

set ip to point to the first input symbol of w$; repeat forever begin

let s be the state on top of the stack and

a the symbol pointed to by ip;

if action[s, a] = shift s’ then begin

push a then s’ on top of the stack; advance ip to the next input symbol end

else if action[s, a] = reduce A→β then begin pop 2* | β | symbols off the stack;

let s’ be the state now on top of the stack; push A then goto[s’, A] on top of the stack; output the production A→ β

end

else if action[s, a] = accept then

return

else error( )

end