3.2.

Parser

Types of Parsers in Compiler Design

Compiler design has many functional modules one of them is the parser which takes the
output of the lexical analyzer (often a set of tokens list) and builds a parse tree. The main
responsibility of the parser is to confirm whether the generated language can produce the
input string and helps in the analysis of syntax.

What is a Parser?
The parser is one of the phases of the compiler which takes a token of string as input and
converts it into the corresponding Intermediate Representation (IR) with the help of an
existing grammar. The parser is also known as Syntax Analyzer.

Classification of Parser
Types of Parsers
The parser is mainly classified into two categories.
1.​ Top-down Parser
2.​ Bottom-up Parser
Top-Down Parser
Top-down parser is the parser that generates parse tree for the given input string with the
help of grammar productions by expanding the non-terminals. It starts from the start
symbol and ends down on the terminals. It uses left most derivation.
Further Top-down parser is classified into 2 types: 1) Recursive descent parser and 2)
non-recursive descent parser.
1.​ Recursive descent parser is also known as the Brute force parser or the
backtracking parser. It basically generates the parse tree by using brute force
and backtracking techniques.
2.​ Non-recursive descent parser is also known as LL(1) parser or predictive parser
or without backtracking parser or dynamic parser. It uses a parsing table to
generate the parse tree instead of backtracking.

Bottom-Up Parser
Bottom-up Parser is the parser that generates the parse tree for the given input string with
the help of grammar productions by compressing the terminals. It starts from terminals
and ends upon the start symbol. It uses the rightmost derivation in reverse order.
Bottom-up parser is classified into two types:
LR parser: This is a bottom-up parser that generates the parse tree for the given string by
using unambiguous grammar. It follows the reverse of the rightmost derivation. LR parser
is classified into four types:
●​ LR(0)
●​ SLR(1)
●​ LALR(1)
●​ CLR(1)
Operator precedence parser: Operator Precedence Parser generates the parse tree from
given grammar and string but it has the condition that two consecutive non-terminals and
epsilon will never appears on the right-hand side of any production. The operator
precedence parsing technique is applied to Operator grammars.
What is Operator Grammar?
An operator precedence grammar is a context-free grammar that has the property that no
production has either:
●​ An empty on the right-hand side
●​ Two adjacent non-terminals in its right-hand side.

Conclusion
Parser is one of the important phases in compiler design that takes a token of string as
input and converts into the intermediate representation. If the programming code does not
follow the rules, then the compiler will generate an error message and the compilation
process will be stopped. Parser is classified into two types namely Top-down Parser and
Bottom-up Parser. Based on the requirements and the goals of the programming language
the appropriate parsing technique is used.

Working of Top Down Parser

A top-down parser is a type of parser used in compiler design and language processing.
It works by starting at the highest level of grammar (usually called the "start symbol")
and breaking it down step by step into its components, trying to match the structure of the
input. In this article, we are going to cover the working of a top-down parser and will see
how we can take input and parse it and also cover some basics of top-down.

What is a Top Down Parser?

In the top-down technique, parse tree constructs from the top, and input will read from
left to right. In a top-down parser, It will start the symbol to proceed to the string or
input. It follows left most derivation. In a top-down parser, difficulty with top-down
parser is if the variable contains more than one possibility selecting 1 is difficult.
Working of Top Down Parser
Let's consider an example where grammar is given and you need to construct a parse tree
by using a top-down parser technique. ​
Example:
S -> aABe
A -> Abc | b
B -> d
Now, let's consider the input to read and construct a parse tree with top-down approach. ​
​
Input -
abbcde
Now, you will see how top-down approach works. Here, you will see how you can
generate a input string from the grammar for top top-down approach.
●​ First, you can start with S -> a A B e and then you will see input string 'a' in
the beginning and 'e' in the end.
●​ Now, you need to generate abbcde.
●​ Expand A-> Abc and Expand B-> d.
●​ Now, You have a string like aAbcde and your input string is abbcde.
●​ Expand A->b.
●​ Final string, you will get abbcde.
Given below is the Diagram explanation for constructing a top-down parse tree. You can
see clearly in the diagram how you can generate the input string using grammar with
top-down approach.
 Top Down Parser

Conclusion
A top-down parser works by starting at the main structure of a language (like a sentence
or a piece of code) and breaking it down step by step, following grammar rules. It checks
if the input matches the expected pattern from the top to the bottom. If the input fits the
rules, the parser moves forward; if not, it tries different options. This makes top-down
parsing useful for analyzing and understanding structured inputs like programming
languages or sentences.

Working of Bottom up parser

Parsing, also known as syntactic analysis, is the process of analyzing a sequence of
tokens to determine the grammatical structure of a program. It takes the stream of tokens,
which are generated by a lexical analyzer or tokenizer, and organizes them into a parse
tree or syntax tree.

Bottom Up Parsing
As the name suggests, bottom-up parsing works in the opposite way of top-down parsing.
While a top-down parser starts from the start symbol and moves down to the input string,
a bottom-up parser starts from the input string (terminals) and works its way up to the
start symbol.
It does this by looking for parts of the input that match the right-hand side of grammar
rules, then replaces them with the left-hand side (the non-terminal), building the parse
tree from the bottom to the top.

Note : ​
In bottom-up parser, no variable that's why not have any derivation from the bottom but
in reverse order it is looking like top-down, when you have rightmost derivation.

Working of Bottom-up parser

1. Start with tokens: The parser begins with the terminal symbols (the input tokens),
which are the leaves of the parse tree.
2. Shift and reduce: The parser repeatedly applies two actions:
●​ Shift: The next token is pushed onto a stack.
●​ Reduce: A sequence of symbols on the stack is replaced by a non-terminal
according to the production rules of the grammar. This step is called
“reduction,” where the parser replaces the right-hand side of a production with
the left-hand side non-terminal.
3. Repeat until root: The process of shifting and reducing continues until the entire input
is reduced to the start symbol, indicating the sentence has been successfully parsed.
Let's consider an example where grammar is given and you need to construct a parse tree
by using bottom-up parser technique.

Example 1:
●​ E → T
●​ T → T * F
●​ T → id
●​ F → T
 ●​ F → id
input string: “id * id”

STEPS INVOLVE IN PARSING

Example 2:
●​ S→A+B
●​ A→3
●​ B→5
Now, let’s parse the string “3 + 5”:
●​ First, we start with the input string: “3 + 5”.
●​ We look for parts of the string that match a production rule.
●​ We see that “3” matches A, so we replace it with A (so now we have A+5).
●​ Next, “5” matches B, so we replace it with B (now we have A+B).
●​ Finally, A+B matches the production S→A+B, so we replace A+B with S.
Now, we’ve reduced the entire input to the start symbol S, meaning the input has been
successfully parsed.
Classification of Bottom-up Parsers
Classification Of Bottom up Parsers
●​ LR(0) Parser :
○​ Simplest form and no lookahead.
○​ LR(0) parser parses the input by examining the current symbol and
using predefined rules based on the grammar.
○​ Rarely used due to limitations in grammar coverage.
●​ SLR(1) Parser (Simple LR)
○​ SLR(1) Parser uses First and Follow sets to resolve parsing
conflicts, which helps in determining whether to reduce or shift.
○​ Easier to implement compared to the canonical LR parsers.
○​ Less powerful, meaning it may fail on certain complex grammars
that would be solvable by more powerful parsers.
●​ LALR(1) Parser (Look-Ahead LR)
○​ LALR(1) Parser are most commonly used in practical compilers.
○​ It combines similar LR(1) states to reduce the size of the parsing
table, making it more efficient.
○​ Strikes a balance between parsing power and table size, and is used
in many production compilers like Yacc and Bison.
●​ Canonical LR(1) Parser
○​ Canonical LR(1) Parser are most powerful LR parser, as it uses full
lookahead (1 token) to make parsing decisions.
○​ Can handle the widest range of grammars, including those that
would challenge other LR parsers.
○​ However, it results in very large parsing tables, making it less
practical for real-world usage, as the table size grows exponentially.