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

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.

YACC in Compiler Design

YACC  YACC is known as Yet Another Compiler Compiler. It is used to produce the source code of the syntactic analyzer of the language produced by LALR (1) grammar. The input...

5 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.

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.

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.

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.

Target Machine

Target Machine A target machine is a byte-addressable machine. This machine has n general-purpose registers, R0, R1,.....Rn-1. A Simple Target Machine Model has three-address instruction. A full-edged assembly language would have...

3 minutes read.

Lexical Analysis in Compiler Design

Lexical Analysis It is the first phase of the compiler. As we know, it is also known as a scanner. The input for lexical analysis is source code. After taking source...

2 minutes read.

Run-Time Environments

Run-Time Environments Storage Organization Every target program has its own logical address, and an executable program runs in it. The logical address space has the location for each program value. The...

2 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.

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.

LEX

LEX Lex is a tool/computer program that generates a Lexical analyzer. Lex is developed by Vern Paxson in C around 1987. Lex works together with the YACC parser generator. It allows...

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.

Intermediate-Code Generator Compiler Design

Intermediate-Code Generator The process of translating a source language into machine code for a given target machine is done by intermediate-code. It lies between the high-level language and the machine language....

2 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.

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.

Switch Case Statement Compiler Design

Case Statement The “case” or “switch” statement is available in various languages. The following is the syntax for the case statement: switch (E)  {             case V1: S1             case V2: S2 ...

1 minute 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.

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.

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.