Logo

Syntax Analysis Compiler Design

Syntax Analysis

This article will describe the parsing method used in the compiler. The grammatical rule of programming language can be constructed with the help of context-free grammars or BNF (Backus–Naur form) notations. The grammar offers some great benefits for language designers and compiler designers.

  • Grammar provides an exact, not much hard, linguistic description of a programming language.
  • With the help of classes of grammars, a well-organized parser can be constructed that determines the syntactic structure of the source program. A parser-construction can detect ambiguities and spots the trouble that has been missed at the beginning phase of a language.
  • The grammar is helpful for converting a source code into the correct target code and for detecting errors.
  • A grammar provides a language developed by adding new features to perform new operations. The new constructs can easily be implemented by obeying the grammatical rule of the language.

Introduction

In this section, we examine the position of the parser in a typical compiler. And then, we will look at the typical grammars for arithmetic expressions. 

The Role of the Parser

In the figure given below, the parser collects a collection of token forms from the lexical analyzer. It verifies that the grammar of the source code generates the group of tokens. We believe that the parser should report any syntax error as soon as possible and remove that error to continue advancing the rest of the program. The parser's main role is to constructs the parse tree and forwards it to the compiler for further operation. Due to checking and translation action interspersed with parsing, the parse tree should not be constructed explicitly. So the parser and the front end could be implemented by a single model.

There are two kinds of parsers for grammars: top-down and bottom-up.

The commonly used parsing method is either top-down or bottom-up. As the name suggests, the top-down method built a parse tree from the top (root) to the bottom (leaves), while the bottom-up starts from leaves and works till the top (root). In both cases, an input to the parser is scanned from left to right and one input at a time.

Context-Free Grammar

Grammar was brought to systematically narrate the syntax of programming languages like expressions and statements. A lexical analyzer can check tokens with the help of regular and patterns rule. But due to some limitation of the regular expression, the lexical analyzer cannot detect the syntax of a particular sentence. Therefore the context-free grammar is used by this phase, which is accepted by pushdown automata.

The production is:

                    stmt            if (expr) stmt else stmt                               (1.1)

CFG is a subset of regular grammar, as shown in the figure:

After seeing the figure above, we can say that every Regular Grammar is also context-free grammar. There is some problem that is far away from the regular grammar that's why CFG helps to describe the syntax of programming language.

Context-free grammar consist of four components:

  • The terminals are a basic symbol in which string is formed. Terminal symbol (?) is a group of tokens. In (1.1), If, else and the symbol "(" and ")" are terminal.
  • Non-terminals are the linguistic variable that denotes sets of strings. It is represented by (V). In (1.1), stmt and expr are non-terminals. The non-terminals help to define the language generated by the grammar. 
  • In grammar, non-terminals are the start symbol (S), which is the starting point of production. 
  • The productions portray the pattern in which the terminals and non-terminals merge to form a string. Each production consist of:

 a) The production's left side is known as non-terminals. The left side of production is also known as the head of the productions.

 b) An arrow.

 c) The production’s right side should have zero or more terminals and non – terminals. The right side of production is also known as the body of the production.

Related Topics

Run-Time Storage Management

Run-Time Storage Management Every executing program has its own logical address space. Logical address space is partitioned into: Code: It is responsible for storing the executable target code. Static: It is used to...

3 minutes read.

CLR Parsing Compiler Design

CLR Parsing CLR parsing refers to the canonical lookahead. We will use the canonical collection of LR(1) items for the construction of the CLR(1) parsing table. Generally, CLR(1) parsing has more...

6 minutes read.

LALR 1 Parsing | Compiler Design

LALR (1) Parsing The LALR parsing refers to the "lookahead LR" that has many lesser steps than typical parsers based on LR(1) items. For constructing the LALR(1) parsing table, the canonical...

6 minutes read.

Syntax-Directed Translation

Syntax-Directed Translation A context-free-grammar with some additional rules is known as a syntax-directed definition. In SDT, attributes are associated with grammar symbols and rules are associated with productions. The attributes can...

3 minutes read.

Translation of Array References in Compiler Design

Translation of Array References We can access the elements of an array stored in consecutive blocks very easily and quickly. In a programming language like C and Java, the size of...

2 minutes read.

Optimization of Basic Blocks in Compiler Design

Optimization of Basic Blocks We can apply the optimization process on a basic block. While optimization, there is no need to change the set of expressions computed by the block. The basic...

3 minutes read.

Evolution of Programming Languages in Compiler Design

The Evolution of Programming Languages The first computer came in the 1940s and was programmed in a binary language that told the computer what operations are to be performed and in...

4 minutes read.

Basic Blocks and Flow Graphs in Compiler Design

Basic Blocks and Flow Graphs In this section, we are going to learn how to work with basic block and flow graphs in compiler design. Basic Block The basic block is a set...

3 minutes read.

Stack Allocation of Space

Stack Allocation of Space Almost all compilers for languages that use procedure, functions, or methods manage their run-time memory as a stack. Whenever a procedure is called, the local variable's space...

2 minutes read.

Shift Reduce Parsing in Compiler Design

Like the bottom-up parsing, the shift reduce parser also builds the parse tree from the leaves (bottom) to the root (up). The LR parser is a more versatile variation of...

4 minutes read.

Errors in Compiler Design

Introduction Errors in compiler design refer to mistakes or issues that arise during the process of execution of the program. A compiler is a program that translates source code written in...

4 minutes read.

Data Flow Analysis in Compiler Design

Data Flow Analysis All the optimization techniques we have learned earlier depend on data flow analysis. DFA is a technique used to know about how the data is flowing in any...

3 minutes read.

Finite State Machine

Finite State Machine A finite state machine is a simple machine to recognize patterns. It takes a string of symbols as the input and changes its state to another state, but...

3 minutes read.

Bottom-Up Parsing in Compiler Design

Bottom-Up Parsing A bottom-up parsing constructs the parse tree for an input string beginning from the bottom (the leaves) and moves to work towards the top (the root). Bottom-up parsing is...

6 minutes read.

Code Generation

Code Generation The last phase of the compiler is code generation. It is the compiler's back-end that makes multiple passes over the IR before generating the target program. The code generator's...

4 minutes read.

Symbol Table Compiler Design

Symbol Table It is an important data structure used by the compiler. It stores information about various entities such as object, class, variable names, functions name, interfaces, procedure, literals, string etc.  The...

3 minutes read.

S-attributed and L-attributed SDTs

S-attributed and L-attributed SDTs STD stands for Syntax Directed Translation. When we associate some informal notations called semantic rules and the grammar, they are known as STD. So we can say...

2 minutes read.

SLR 1 Parsing Compiler Design

SLR(1) Parsing It is a simple LR parsing. Most of the function of this parsing is the same as LR(0) parsing. The parsing table for both the parser vary. The SLR(1)...

5 minutes read.

Ambiguity Elimination Compiler Design

Ambiguity Elimination Ambiguity elimination makes the sentence clear and readable. A sentence is grammatically ambiguous if it can produce more than one parse tree for a particular grammar. In this article,...

3 minutes read.

Syntax Analysis Compiler Design

Syntax Analysis This article will describe the parsing method used in the compiler. The grammatical rule of programming language can be constructed with the help of context-free grammars or BNF (Backus–Naur...

3 minutes read.