Parsing in Compiler Design

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.

parser

Parsing in Compiler Design

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.

What is Parsing?

Parsing is the process of taking the sequence of tokens (produced by the Lexical Analyzer) and organizing them into a structured representation called a parse tree or syntax tree. This tree represents the syntactic structure of the code.

Types of Parsers

The parser is mainly classified into two categories.

1. Top-down Parser
2. Bottom-up Parser

1. Top-Down Parsing

Starts from the root of the parse tree and works downward, trying to match the input tokens to the production rules of the grammar. Examples:

Recursive Descent Parsing: Uses recursive functions for each grammar rule.

Predictive Parsing: A non-recursive form that uses a lookahead symbol (usually one token).

2. Bottom-Up Parsing

Starts from the input tokens and works upward, reducing tokens to grammar rules until it reaches the start symbol.

Examples:

Shift-Reduce Parsing: Alternates between shifting tokens and reducing them.

LR Parsers: Includes SLR, CLR, and LALR parsers for more complex grammars.

Working of parser

1.Definition of Grammars

A context-free grammar has four components(V,T,P,S):

V — It is the collection of variables or non-terminal symbols. T — It is a set of terminals. P — It is the production rules that consist of both terminals and non-terminals. S — It is the starting symbol.

2. Derivations

A grammar derives strings by beginning with the start symbol and repeatedly replacing a nonterminal by the body of a production for that nonterminal. The terminal strings that can be derived from the start symbol form the language defined by the grammar.

3.Generating of Parse Trees

A parse tree pictorially shows how the start symbol of a grammar derives a string in the language. If nonterminal A has a production A -> XY Z, then a parse tree may have an interior node labelled.

Formally, given a context-free grammar, a parse tree according to the grammar is a tree with the following properties:

1. The root is labelled by the start symbol.

2. Each leaf is labelled by a terminal or by E.

3. Each interior node is labelled by a nonterminal.

4.If A is the nonterminal labelling some interior node and Xl , X2, ••• , Xn are the labels of the children.

“The process of finding a parse tree for a given string of terminals is called parsing that string.”