Scribd
Upload
10 views

CC lec 15

The document provides an overview of LR parsing, a bottom-up parsing technique for context-free languages that utilizes rightmost derivation in reverse. It discusses the advantages of LR parsers, including their ability to recognize a wide range of programming constructs and detect syntactic errors early, while also noting the challenges in manual construction. Additionally, it outlines the types of LR parsers, the concept of canonical items, and the functions of closure and goto in constructing the LR(0) automaton.

Uploaded by

waseem khosa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
10 views

CC lec 15

The document provides an overview of LR parsing, a bottom-up parsing technique for context-free languages that utilizes rightmost derivation in reverse. It discusses the advantages of LR parsers, including their ability to recognize a wide range of programming constructs and detect syntactic errors early, while also noting the challenges in manual construction. Additionally, it outlines the types of LR parsers, the concept of canonical items, and the functions of closure and goto in constructing the LR(0) automaton.

Uploaded by

waseem khosa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 14

COMPILER

CONSTRUCTIO
N
Lecture 15
LR PARSING
Introduction:
 The LR(k) parser will parse the input string by applying rightmost
derivation in reverse. The LR(k) parsers are bottom-up parsers that are
capable of handling context-free languages very efficiently.
 where
 The L is for left to right scanning of the input.
 The R for constructing a rightmost derivation in reverse.
 The k for the number of input symbols of lookahead that are used in making
parsing decisions.
 The cases k=0 or k=1 are of practical interest, and we shall only consider
LR parsers with here. When (k) is omitted, k is assumed to be 1.
WHY LR PARSERS
 LR parsing Advantages:
 LR parsing is attractive for a variety of reasons:
 LR parsers can be constructed to recognize virtually all programming
languages constructs for which context-free grammars can be written.
 The LR parsing method is the most general non-backtracking shift-reduce
parsing methos known, yet it can be implemented as other, more primitive
shift-reduce methods.
WHY LR PARSERS
 LR parsers are table-driven, much like the non-recursive LL parsers.
 A grammar for which we can construct a parsing table using on of the LR
parsing method (SLR – Simple LR/CLR – Canonical LR/LALR – Lookahead LR)
is said to be an LR grammar.
 For a grammar to be LR if is sufficient that a left-to-right shift-reduce parser
be able to recognize handles of right-sentential forms when they appear on
top of the stack.
WHY LR PARSERS
 LR parsing Advantages:
 An LR parser can detect a syntactic error as soon as it is possible to do so
on a left- to – right scan of the input.
 LR parsers can describe more languages than LL grammars.
WHY LR PARSERS
 LR Parsing Disadvantages:
 The main drawback of LR parsers is that they consume too much time to
construct by hand for a typical programming language grammar.
 But this advantage can be eliminated using LR parser generators such as
YACC (Yet- Another Compiler – Compiler)
TYPES OF LR PARSERS
 There are three types of LR parsers are shown below:

LR(0)
 SLR(1)
 CLR(1)
 LALR(1)
LR GRAMMAR
 For a Grammar to be LR it is sufficient that a left-to-right shift-reduce
parser be able to recognize handles of right sentential form.
CANONICAL ITEMS FOR
LR(0) - ITEMS
 Definition: Item or LR(0) item
 An LR(0) item or item of a grammar G is a production of G with a dot(.) on
the right – hand side (RHS) of a production.
 Example:
 Consider the production A->XYZ. The various items that can be obtained
using this production are:
 A-> .XYZ
 A-> X.YZ
 A-> XY.Z
 A-> XYZ.
CANONICAL ITEMS FOR
LR(0) - ITEMS
 Purpose:
 LR parser makes shift-reduce decisions by maintaining states to keep track
of where we are in a parsing.
 Using these items called canonical LR(0) collection, we can construct a DFA
(Deterministic finite Automata) which is used to make parsing decision
such as shifting and reducing.
 Note:
 For the production of the form A-> The item is: A-> .
AUGMENT GRAMMAR
 Augmented grammar:
 If G is a grammar with start symbol S the G’ the augment grammar for G, is
G with the new start symbol S’ and production S’ -> S.
 Purpose:
 The main purpose of the new staring production is to indicate to the parser
when it should stop parsing and announce acceptance of the input. That is,
acceptance occurs whenever the parser is about to reduce using the
production S’ -> S.
LR(0) AUTOMATON
 DFA that is used to make parsing decisions.
 Each state of LR(0) automaton represents a set of items in canonical LR(0)
collection.
 Functions includes:
 Closure of Item Sets
 The Goto Functiom
CLOSURE FUNCTION
 If I is a set of items for a grammar G, then CLOSURE(I) is the set of items
constructed from I by two rules:
1. Add every item in I to CLOSURE(I).
2. If in CLOSURE(I) and is a production, then add to CLOSURE(I). Apply this
rule until no newer item can be added to CLOSURE(I).
THE GOTO FUNCTION
 The GOTO Function is used to define transitions.
 For GOTO(I,X):
1. Move (.)dot after X.
2. Find the CLOSURE for all results in step 1.

You might also like