Parser in Compiler Design

A parser is an important component of a compiler that receives a sequence of tokens from the lexical analysis phase and analyzes their syntactic structure according to the grammar of the language. It checks whether the token sequence follows the rules of the language and typically produces a parse tree or another structured representation.

Parsing techniques are mainly divided into top-down parsing and bottom-up parsing.

In this chapter, you will learn what a parser is, how it processes tokens, the main types of parsing, and the basic concept of top-down parsing.

What is a Parser?

A parser is a component of a compiler that takes a sequence of tokens generated by the lexical analyzer as input and determines whether the tokens follow the grammar of the language.

The parser generally produces a parse tree that represents the syntactic structure of the input.

The basic process can be represented as:

Source Code
     ↓
Lexical Analysis
     ↓
Tokens
     ↓
Parser
     ↓
Parse Tree

Types of Parsing

Parsing techniques are mainly classified into two types:

1. Top-Down Parsing
2. Bottom-Up Parsing

Top-down parsing starts with the start symbol of the grammar and attempts to derive the input string. Bottom-up parsing starts with the input symbols and works toward the start symbol.

Top-Down Parsing

Top-down parsing constructs the parse tree starting from the start symbol and proceeds toward the input symbols.

In this approach, the parser begins with the start symbol of the grammar and repeatedly expands non-terminal symbols until the generated symbols match the input tokens.

Top-down parsing is also commonly associated with recursive-descent parsing and predictive parsing techniques.

The basic process can be represented as:

Start Symbol
     ↓
Non-Terminals
     ↓
Input Symbols

Characteristics of Top-Down Parsing

The important characteristics of top-down parsing include:

• Parsing starts from the start symbol.
• The parser attempts to derive the input string from the grammar.
• The parse tree is constructed from the root toward the leaves.
• It can be implemented using recursive-descent or predictive parsing techniques.
• Grammars containing direct left recursion need to be modified before they can be handled by common top-down parsing techniques.

Limitations of Top-Down Parsing

Top-down parsing has some limitations:

• Left Recursion: Direct left-recursive grammars cannot be handled directly by common recursive-descent parsing techniques because they can cause infinite recursion.
• Backtracking: Some top-down parsing techniques may require backtracking, which can increase parsing effort.
• Grammar Restrictions: Predictive parsing generally requires a grammar suitable for making the required parsing decisions without backtracking.

Parse Tree Representation

For an input string such as:

acdb

the parser uses the grammar rules to construct its corresponding parse tree.

Top-down parsing with backtracking

• The top down parsing is known as recursive parsing or predictive parsing.
• Bottom up parsing is used to construct a parse tree for an input string.
• In the top down parsing, the parsing starts from the start symbol and transform it into the input symbol.

Demerits of Top down parsing

• In top down parsing error reporting is not possible.
• Left recursion is not handled.

Parse Tree representation of input string "acdb" is as follows:

Top down parsing with backtracking

In this, the parser examines different possibilities when faced with an option. If one possibility does not work then the parser goes back to the previous decision point and tries another possibility.

Merits of Top down parsing with backtracking

• This can hold grammars where there are multiple possible ways to extend a non terminal symbol.

Demerits of Top down parsing with backtracking

• This can be slow and inefficient.

Top down Parsing without Backtracking

In this parser, using the first choice to find a match to the input string, if it does not match it fails immediately instead of going back to try another option. Therefore, the parser does not backtrack.

Merits of Top down parsing without backtracking

Following is the list of merits of top down parsing.

• It is faster than without backtracking technique because it does not waste time going back to previous steps.

Demerits of Top down parsing without backtracking

Following is the list of demerits of top down parsing.

• It can hold simple grammars.

Bottom up parsing

• Bottom up parsing is also known as shift-reduce parsing.
• Bottom up parsing is used to construct a parse tree for an input string.
• In the bottom up parsing, the parsing starts with the input symbol and construct the parse tree up to the start symbol by tracing out the rightmost derivations of string in reverse.

Demerits of Bottom up parsing

• It does not support the flow of information.
• This leads to the production of ambiguous grammar.

Example

Production

Parse Tree representation of input string "id * id" is as follows:

Bottom up parsing is classified in to various parsing. These are as follows:

1. Shift-Reduce Parsing
2. Operator Precedence Parsing
3. Table Driven LR Parsing

1. LR( 1 )
2. SLR( 1 )
3. CLR ( 1 )
4. LALR( 1 )

Distinguish between Top down and Bottom up Parsers

The difference between the bottom up and top down parser is as follows.

What is the role of a parser?

Following is the list of various functions performed by parser:

• It performs syntactic and semantic analysis of the source code and converts it into an intermediate representation while detecting and handling errors.
• The parser checks whether the structure of the code follows the basic rules of the programming language.
• The parser creates a simplified version of your code that is easier for the computer to understand and work.
• If something is wrong with your code, the parser tries to clearly explain the problem so that you can fix it.
• The parser tries to fix small errors in your code so that it continues to work without breaking completely.