LL Parser in Compiler Design

LL Parser in Compiler Design
LL parser in compiler design is a predictive parser implementation that uses an implicit stack and parsing
table to determine the production that should be used for a non-terminal.
It searches a parsing table created from a specific grammar for the production that should be applied.
It will try to forecast the correct production to extend the non-terminal at the present derivation step if more than one
production relates to the same non-terminal. As a result, to build a predictive parser, we need to know which
production options to use, given the current input symbol and the non-terminal that has to be extended.
For example
Concerning the productions, the syntax is as follows:
stmt -> if expr then stmt else stmt | while stmt then stmt | begin stmt_list end
The keywords "if," "while," and "begin" then indicate which alternative may be successful if we are looking for a
statement.
Model of LL Parser in Compiler Design
The three models of LL parser in compiler design are the following:

 Input: This contains a string that will be parsed with the end-marker $.
 Stack: A predictive parser sustains a stack. It is a collection of grammar symbols with the dollar sign ($) at the
bottom.
 Parsing table: M[A, S] is a two-dimensional array, where A is a non-terminal, and S is a terminal. With the
entries in this table, it becomes effortless for the top-down parser to choose the production to be applied.
LL(1) PARSER
If an LL parser uses k look-ahead tokens to parse a sentence, it is called an LL(k) parser. Because LL grammars,
especially LL(1) grammars, are simple to build as parsers, many computer languages are created to be LL(1). The 1
denotes using a single input symbol for forward-looking decisions during each phase of the parsing process.
When LL(k) parsers encounter a non-terminal, they must anticipate which production it will be replaced with. The
fundamental LL algorithm begins with a stack comprising [S, $] (top to bottom) and performs the relevant action till
finished:
1. If a non-terminal is at the top of the stack, choose one of its productions as the top by utilizing the following k
input symbols (without changing the input cursor), and proceed.
2. Read the following input token if a terminal is at the top of the stack. Pop the stack and carry on if it's the same
terminal. Otherwise, the procedure ends because the parse was unsuccessful.
3. The procedure is complete if the stack is empty because the parse was successful. (We presume the input's final
$ EOF-marker is unique.)
Prime Requirement of LL(1)
The following are the prime requirements for the LL(1) parser:
 The grammar must have no left factoring and no left recursion.
 FIRST() & FOLLOW()
 Parsing Table
 Stack Implementation
 Parse Tree
Algorithm to Construct LL(1) Parsing Table
Step 1: Verify the prime requirement of LL Parser before moving on to step 2.
Step 2: Perform First() and Follow() calculations on each non-terminal. Let us see these two calculations.
 First(): The first terminal symbol is referred to as the First if there is a variable, and we attempt to derive all the
strings from that variable.
 Follow(): The terminal symbol that follows a variable throughout the derivation process.
Step 3. For each production, like A –> α.
 Locate First(α) and enter A -> α for each terminal in First() in the table.
 Locate Follow(A) and put an item in the table for each terminal in Follow(A) if First(α) contains epsilon as a
terminal.
 Make entry A-> ε in the table for the $ if First(ε) includes and Follow(A) contains $ as terminal.
The Non-Terminals will be in the table's rows, and the Terminal Symbols will be in the table's column. The Follow
elements will cover all the Grammars' Null Productions, while the First set of elements will cover the rest of the
productions.
Let us see an example of an LL(1) parser.

Example
The grammar is given below:
G --> SG'
G' --> +SG' | ε
S --> FS'
S' --> *FS' | ε
F --> id | (G)

LL Parser in Compiler Design

Uploaded by

Copyright:

Available Formats

LL Parser in Compiler Design

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

LL Parser in Compiler Design

Uploaded by

Copyright:

Available Formats

LL Parser in Compiler Design

The three models of LL parser in compiler design are the following:

 FIRST() & FOLLOW()

Step 3. For each production, like A –> α.

Let us see an example of an LL(1) parser.

You might also like