<!DOCTYPE html><html><body><title>Compiler Design</title>

<h4 style="margin:0px 2px 3px -2px!important;">Quick Links</h4>

<h1>Audience</h1>

<h1>Instructor</h1>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Compiler Design Tutorial</title>

<h1>Compiler Design Tutorial</h1>

<p>A compiler translates the code written in one language to some other language without changing the meaning of the program. It is also expected that a compiler should make the target code efficient and optimized in terms of time and space.</p>

<p>Compiler design principles provide an in-depth view of translation and optimization process. Compiler design covers basic translation mechanism and error detection &amp; recovery. It includes lexical, syntax, and semantic analysis as front end, and code generation and optimization as back-end.</p>

<h1>Audience</h1>

<p>This tutorial is designed for students interested in learning the basic principles of compilers.Enthusiastic readers who would like to know more about compilers and those who wish to design a compiler themselves may start from here.</p>

<h1>Prerequisites</h1>

<p>This tutorial requires no prior knowledge of compiler design but requires basic understanding of at least one programming language such as C, Java etc.It would be an additional advantage if you have had prior exposure to Assembly Programming.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Compiler Design - Overview</title>

<h1>Compiler Design - Overview</h1>

<p>Computers are a balanced mix of software and hardware. Hardware is just a piece of mechanical device and its functions are being controlled by a compatible software. Hardware understands instructions in the form of electronic charge, which is the counterpart of binary language in software programming. Binary language has only two alphabets, 0 and 1. To instruct, the hardware codes must be written in binary format, which is simply a series of 1s and 0s. It would be a difficult and cumbersome task for computer programmers to write such codes, which is why we have compilers to write such codes.</p>

<h2>Language Processing System</h2>

<p>We have learnt that any computer system is made of hardware and software. The hardware understands a language, which humans cannot understand. So we write programs in high-level language, which is easier for us to understand and remember. These programs are then fed into a series of tools and OS components to get the desired code that can be used by the machine. This is known as Language Processing System.</p>

<p>The high-level language is converted into binary language in various phases. A <b>compiler</b> is a program that converts high-level language to assembly language. Similarly, an <b>assembler</b> is a program that converts the assembly language to machine-level language.</p>

<p>Let us first understand how a program, using C compiler, is executed on a host machine.</p>

<p>User writes a program in C language (high-level language).</p>

<p>The C compiler, compiles the program and translates it to assembly program (low-level language).</p>

<p>An assembler then translates the assembly program into machine code (object).</p>

<p>A linker tool is used to link all the parts of the program together for execution (executable machine code).</p>

<p>A loader loads all of them into memory and then the program is executed.</p>

<p>Before diving straight into the concepts of compilers, we should understand a few other tools that work closely with compilers.</p>

<h3>Preprocessor</h3>

<p>A preprocessor, generally considered as a part of compiler, is a tool that produces input for compilers. It deals with macro-processing, augmentation, file inclusion, language extension, etc.</p>

<h3>Interpreter</h3>

<p>An interpreter, like a compiler, translates high-level language into low-level machine language. The difference lies in the way they read the source code or input. A compiler reads the whole source code at once, creates tokens, checks semantics, generates intermediate code, executes the whole program and may involve many passes. In contrast, an interpreter reads a statement from the input, converts it to an intermediate code, executes it, then takes the next statement in sequence. If an error occurs, an interpreter stops execution and reports it. whereas a compiler reads the whole program even if it encounters several errors.</p>

<h3>Assembler</h3>

<p>An assembler translates assembly language programs into machine code.The output of an assembler is called an object file, which contains a combination of machine instructions as well as the data required to place these instructions in memory.</p>

<h3>Linker</h3>

<p>Linker is a computer program that links and merges various object files together in order to make an executable file. All these files might have been compiled by separate assemblers. The major task of a linker is to search and locate referenced module/routines in a program and to determine the memory location where these codes will be loaded, making the program instruction to have absolute references.</p>

<h3>Loader</h3>

<p>Loader is a part of operating system and is responsible for loading executable files into memory and execute them. It calculates the size of a program (instructions and data) and creates memory space for it. It initializes various registers to initiate execution.</p>

<h3>Cross-compiler</h3>

<p>A compiler that runs on platform (A) and is capable of generating executable code for platform (B) is called a cross-compiler.</p>

<h3>Source-to-source Compiler</h3>

<p>A compiler that takes the source code of one programming language and translates it into the source code of another programming language is called a source-to-source compiler.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Compiler Design - Architecture</title>

<h1>Compiler Design - Architecture</h1>

<p>A compiler can broadly be divided into two phases based on the way they compile.</p>

<h3>Analysis Phase</h3>

<p>Known as the front-end of the compiler, the <b>analysis</b> phase of the compiler reads the source program, divides it into core parts and then checks for lexical, grammar and syntax errors.The analysis phase generates an intermediate representation of the source program and symbol table, which should be fed to the Synthesis phase as input.</p>

<h3>Synthesis Phase</h3>

<p>Known as the back-end of the compiler, the <b>synthesis</b> phase generates the target program with the help of intermediate source code representation and symbol table.</p>

<p>A compiler can have many phases and passes.</p>

<p><b>Pass</b> : A pass refers to the traversal of a compiler through the entire program.</p>

<p><b>Phase</b> : A phase of a compiler is a distinguishable stage, which takes input from the previous stage, processes and yields output that can be used as input for the next stage. A pass can have more than one phase.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Compiler Design - Phases of Compiler</title>

<h1>Compiler Design - Phases of Compiler</h1>

<p>The compilation process is a sequence of various phases. Each phase takes input from its previous stage, has its own representation of source program, and feeds its output to the next phase of the compiler. Let us understand the phases of a compiler.</p>

<h3>Lexical Analysis</h3>

<p>The first phase of scanner works as a text scanner. This phase scans the source code as a stream of characters and converts it into meaningful lexemes. Lexical analyzer represents these lexemes in the form of tokens as:</p>

<h3>Syntax Analysis</h3>

<p>The next phase is called the syntax analysis or <b>parsing</b>. It takes the token produced by lexical analysis as input and generates a parse tree (or syntax tree). In this phase, token arrangements are checked against the source code grammar, i.e. the parser checks if the expression made by the tokens is syntactically correct.</p>

<h3>Semantic Analysis</h3>

<p>Semantic analysis checks whether the parse tree constructed follows the rules of language. For example, assignment of values is between compatible data types, and adding string to an integer. Also, the semantic analyzer keeps track of identifiers, their types and expressions; whether identifiers are declared before use or not etc. The semantic analyzer produces an annotated syntax tree as an output.</p>

<h3>Intermediate Code Generation</h3>

<p>After semantic analysis the compiler generates an intermediate code of the source code for the target machine. It represents a program for some abstract machine. It is in between the high-level language and the machine language. This intermediate code should be generated in such a way that it makes it easier to be translated into the target machine code.</p>

<h3>Code Optimization</h3>

<p>The next phase does code optimization of the intermediate code. Optimization can be assumed as something that removes unnecessary code lines, and arranges the sequence of statements in order to speed up the program execution without wasting resources (CPU, memory).</p>

<h3>Code Generation</h3>

<p>In this phase, the code generator takes the optimized representation of the intermediate code and maps it to the target machine language. The code generator translates the intermediate code into a sequence of (generally) re-locatable machine code. Sequence of instructions of machine code performs the task as the intermediate code would do.</p>

<h3>Symbol Table</h3>

<p>It is a data-structure maintained throughout all the phases of a compiler. All the identifier's names along with their types are stored here. The symbol table makes it easier for the compiler to quickly search the identifier record and retrieve it. The symbol table is also used for scope management.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<pre class="prettyprint notranslate">

&lt;token-name, attribute-value&gt;

<title>Compiler Design - Lexical Analysis</title>

<h1>Compiler Design - Lexical Analysis</h1>

<p>Lexical analysis is the first phase of a compiler. It takes the modified source code from language preprocessors that are written in the form of sentences. The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code.</p>

<p>If the lexical analyzer finds a token invalid, it generates an error. The lexical analyzer works closely with the syntax analyzer. It reads character streams from the source code, checks for legal tokens, and passes the data to the syntax analyzer when it demands.</p>

<h2>Tokens</h2>

<p>Lexemes are said to be a sequence of characters (alphanumeric) in a token. There are some predefined rules for every lexeme to be identified as a valid token. These rules are defined by grammar rules, by means of a pattern. A pattern explains what can be a token, and these patterns are defined by means of regular expressions.</p>

<p>In programming language, keywords, constants, identifiers, strings, numbers, operators and punctuations symbols can be considered as tokens.</p>

<p>For example, in C language, the variable declaration line</p>

<p>contains the tokens:</p>

<h2>Specifications of Tokens</h2>

<p>Let us understand how the language theory undertakes the following terms:</p>

<h3>Alphabets</h3>

<p>Any finite set of symbols {0,1} is a set of binary alphabets, {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F} is a set of Hexadecimal alphabets, {a-z, A-Z} is a set of English language alphabets.</p>

<h3>Strings</h3>

<p>Any finite sequence of alphabets is called a string. Length of the string is the total number of occurrence of alphabets, e.g., the length of the string tutorialspoint is 14 and is denoted by |tutorialspoint| = 14. A string having no alphabets, i.e. a string of zero length is known as an empty string and is denoted by ε (epsilon).</p>

<h3>Special Symbols</h3>

<p>A typical high-level language contains the following symbols:-</p>

<h3>Language</h3>

<h2>Longest Match Rule</h2>

<p>When the lexical analyzer read the source-code, it scans the code letter by letter; and when it encounters a whitespace, operator symbol, or special symbols, it decides that a word is completed.</p>

<p><b>For example:</b></p>

<p>While scanning both lexemes till ‘int’, the lexical analyzer cannot determine whether it is a keyword <i>int</i> or the initials of identifier int value.</p>

<p>The Longest Match Rule states that the lexeme scanned should be determined based on the longest match among all the tokens available.</p>

<p>The lexical analyzer also follows <b>rule priority</b> where a reserved word, e.g., a keyword, of a language is given priority over user input. That is, if the lexical analyzer finds a lexeme that matches with any existing reserved word, it should generate an error.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<pre class="prettyprint notranslate">

int value = 100;

<p>contains the tokens:</p>

<pre class="prettyprint notranslate">

int (keyword), value (identifier), = (operator), 100 (constant) and ; (symbol).

<h2>Specifications of Tokens</h2>

<p>Let us understand how the language theory undertakes the following terms:</p>

<h3>Alphabets</h3>

<p>Any finite set of symbols {0,1} is a set of binary alphabets, {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F} is a set of Hexadecimal alphabets, {a-z, A-Z} is a set of English language alphabets.</p>

<h3>Strings</h3>

<p>Any finite sequence of alphabets is called a string. Length of the string is the total number of occurrence of alphabets, e.g., the length of the string tutorialspoint is 14 and is denoted by |tutorialspoint| = 14. A string having no alphabets, i.e. a string of zero length is known as an empty string and is denoted by ε (epsilon).</p>

<h3>Special Symbols</h3>

<p>A typical high-level language contains the following symbols:-</p>

<table class="table table-bordered">

<td style="width:26%;">Arithmetic Symbols</td>

<td>Addition(+), Subtraction(-), Modulo(%), Multiplication(*), Division(/)</td>

<td>Punctuation</td>

<td>Comma(,), Semicolon(;), Dot(.), Arrow(->)</td>

<td>Assignment</td>

<td>=</td>

<td>Special Assignment</td>

<td>+=, /=, *=, -=</td>

<td>Comparison</td>

<td>==, !=, <, <=, >, >=</td>

<td>Preprocessor</td>

<td>#</td>

<td>Location Specifier</td>

<td>&amp; </td>

<td>Logical</td>

<td>&amp;, &amp;&amp;, |, ||, !</td>

<td>Shift Operator</td>

<td>>>, >>>, <<, <<<</td>

<h3>Language</h3>

<p>A language is considered as a finite set of strings over some finite set of alphabets.

Computer languages are considered as finite sets, and mathematically set operations can be performed on them. Finite languages can be described by means of regular expressions.</p>

<h2>Longest Match Rule</h2>

<p>When the lexical analyzer read the source-code, it scans the code letter by letter; and when it encounters a whitespace, operator symbol, or special symbols, it decides that a word is completed.</p>

<p><b>For example:</b></p>

<pre class="prettyprint notranslate">

int intvalue;

<title>Compiler Design - Regular Expressions</title>

<h1>Compiler Design - Regular Expressions</h1>

<p>The lexical analyzer needs to scan and identify only a finite set of valid string/token/lexeme that belong to the language in hand. It searches for the pattern defined by the language rules.</p>

<p>Regular expressions have the capability to express finite languages by defining a pattern for finite strings of symbols. The grammar defined by regular expressions is known as <b>regular grammar</b>. The language defined by regular grammar is known as <b>regular language</b>.</p>

<p>Regular expression is an important notation for specifying patterns. Each pattern matches a set of strings, so regular expressions serve as names for a set of strings. Programming language tokens can be described by regular languages. The specification of regular expressions is an example of a recursive definition. Regular languages are easy to understand and have efficient implementation.</p>

<p>There are a number of algebraic laws that are obeyed by regular expressions, which can be used to manipulate regular expressions into equivalent forms.</p>

<h2>Operations</h2>

<p>The various operations on languages are:</p>

<p>Union of two languages L and M is written as</p>

<p>L U M = {s | s is in L or s is in M}</p>

<p>Concatenation of two languages L and M is written as</p>

<p>LM = {st | s is in L and t is in M}</p>

<p>The Kleene Closure of a language L is written as</p>

<p>L* = Zero or more occurrence of language L.</p>

<h2>Notations</h2>

<p>If r and s are regular expressions denoting the languages L(r) and L(s), then</p>

<p><b>Union</b> : (r)|(s) is a regular expression denoting L(r) U L(s)</p>

<p><b>Concatenation</b> : (r)(s) is a regular expression denoting L(r)L(s)</p>

<p><b>Kleene closure</b> : (r)* is a regular expression denoting (L(r))*</p>

<p>(r) is a regular expression denoting L(r)</p>

<h2>Precedence and Associativity</h2>

<h3>Representing valid tokens of a language in regular expression</h3>

<p>If x is a regular expression, then:</p>

<p>x* means zero or more occurrence of x.</p>

<p>i.e., it can generate { e, x, xx, xxx, xxxx, … }</p>

<p>x+ means one or more occurrence of x.</p>

<p>i.e., it can generate { x, xx, xxx, xxxx … } or x.x*</p>

<p>x? means at most one occurrence of x</p>

<p>i.e., it can generate either {x} or {e}.</p>

<p>[a-z] is all lower-case alphabets of English language.</p>

<p>[A-Z] is all upper-case alphabets of English language.</p>

<p>[0-9] is all natural digits used in mathematics.</p>

<h3>Representing occurrence of symbols using regular expressions</h3>

<p>letter = [a – z] or [A – Z]</p>

<p>digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 or [0-9]</p>

<p>sign = [ + | - ]</p>

<h3>Representing language tokens using regular expressions</h3>

<p>Decimal = (sign)^?(digit)⁺</p>

<p>Identifier = (letter)(letter | digit)*</p>

<p>The only problem left with the lexical analyzer is how to verify the validity of a regular expression used in specifying the patterns of keywords of a language. A well-accepted solution is to use finite automata for verification.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Compiler Design - Finite Automata</title>

<h1>Compiler Design - Finite Automata</h1>

<p>Finite automata is a state machine that takes a string of symbols as input and changes its state accordingly. Finite automata is a recognizer for regular expressions. When a regular expression string is fed into finite automata, it changes its state for each literal. If the input string is successfully processed and the automata reaches its final state, it is accepted, i.e., the string just fed was said to be a valid token of the language in hand.</p>

<p>The mathematical model of finite automata consists of:</p>

<p>The transition function (δ) maps the finite set of state (Q) to a finite set of input symbols (Σ), Q × Σ ➔ Q</p>

<h3>Finite Automata Construction</h3>

<p>Let L(r) be a regular language recognized by some finite automata (FA).</p>

<p><b>States</b> : States of FA are represented by circles. State names are written inside circles.</p>

<p><b>Start state</b> : The state from where the automata starts, is known as the start state. Start state has an arrow pointed towards it.</p>

<p><b>Intermediate states</b> : All intermediate states have at least two arrows; one pointing to and another pointing out from them.</p>

<p><b>Final state</b> : If the input string is successfully parsed, the automata is expected to be in this state. Final state is represented by double circles. It may have any odd number of arrows pointing to it and even number of arrows pointing out from it. The number of odd arrows are one greater than even, i.e. <b>odd = even+1</b>.</p>

<p><b>Transition</b> : The transition from one state to another state happens when a desired symbol in the input is found. Upon transition, automata can either move to the next state or stay in the same state. Movement from one state to another is shown as a directed arrow, where the arrows points to the destination state. If automata stays on the same state, an arrow pointing from a state to itself is drawn.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<title>Compiler Design - Syntax Analysis</title>

<h1>Compiler Design - Syntax Analysis</h1>

<p>Syntax analysis or parsing is the second phase of a compiler. In this chapter, we shall learn the basic concepts used in the construction of a parser.</p>

<p>We have seen that a lexical analyzer can identify tokens with the help of regular expressions and pattern rules. But a lexical analyzer cannot check the syntax of a given sentence due to the limitations of the regular expressions. Regular expressions cannot check balancing tokens, such as parenthesis. Therefore, this phase uses context-free grammar (CFG), which is recognized by push-down automata.</p>

<p>CFG, on the other hand, is a superset of Regular Grammar, as depicted below:</p>

<p>It implies that every Regular Grammar is also context-free, but there exists some problems, which are beyond the scope of Regular Grammar. CFG is a helpful tool in describing the syntax of programming languages.</p>

<h2>Context-Free Grammar</h2>

<p>In this section, we will first see the definition of context-free grammar and introduce terminologies used in parsing technology.</p>

<p>A context-free grammar has four components:</p>

<p>A set of <b>non-terminals</b> (V). Non-terminals are syntactic variables that denote sets of strings. The non-terminals define sets of strings that help define the language generated by the grammar.</p>

<p>A set of tokens, known as <b>terminal symbols</b> (Σ). Terminals are the basic symbols from which strings are formed.</p>

<p>A set of <b>productions</b> (P). The productions of a grammar specify the manner in which the terminals and non-terminals can be combined to form strings. Each production consists of a <b>non-terminal</b> called the left side of the production, an arrow, and a sequence of tokens and/or <b>on- terminals</b>, called the right side of the production.</p>

<p>One of the non-terminals is designated as the start symbol (S); from where the production begins.</p>

<p>The strings are derived from the start symbol by repeatedly replacing a non-terminal (initially the start symbol) by the right side of a production, for that non-terminal.</p>

<h3>Example</h3>

<p>We take the problem of palindrome language, which cannot be described by means of Regular Expression. That is, L = { w | w = w^R } is not a regular language. But it can be described by means of CFG, as illustrated below:</p>

<p>Where:</p>

<p>This grammar describes palindrome language, such as: 1001, 11100111, 00100, 1010101, 11111, etc.</p>

<h2>Syntax Analyzers</h2>

<p>A syntax analyzer or parser takes the input from a lexical analyzer in the form of token streams. The parser analyzes the source code (token stream) against the production rules to detect any errors in the code. The output of this phase is a <b>parse tree</b>.</p>

<p>This way, the parser accomplishes two tasks, i.e., parsing the code, looking for errors and generating a parse tree as the output of the phase.</p>

<p>Parsers are expected to parse the whole code even if some errors exist in the program. Parsers use error recovering strategies, which we will learn later in this chapter.</p>

<h2>Derivation</h2>

<p>A derivation is basically a sequence of production rules, in order to get the input string. During parsing, we take two decisions for some sentential form of input:</p>

<p>To decide which non-terminal to be replaced with production rule, we can have two options.</p>

<h3>Left-most Derivation</h3>

<p>If the sentential form of an input is scanned and replaced from left to right, it is called left-most derivation. The sentential form derived by the left-most derivation is called the left-sentential form.</p>

<h3>Right-most Derivation</h3>

<p>If we scan and replace the input with production rules, from right to left, it is known as right-most derivation. The sentential form derived from the right-most derivation is called the right-sentential form.</p>

<p><b>Example</b></p>

<p>Production rules:</p>

<p>Input string: id + id * id</p>

<p>The left-most derivation is:</p>

<p>Notice that the left-most side non-terminal is always processed first.</p>

<p>The right-most derivation is:</p>

<h2>Parse Tree</h2>

<p>A parse tree is a graphical depiction of a derivation. It is convenient to see how strings are derived from the start symbol. The start symbol of the derivation becomes the root of the parse tree. Let us see this by an example from the last topic.</p>

<p>We take the left-most derivation of a + b * c</p>

<p>The left-most derivation is:</p>

<p>Step 1:</p>

<p>Step 2:</p>

<p>Step 3:</p>

<p>Step 4:</p>

<p>Step 5:</p>

<p>In a parse tree:</p>

<p>A parse tree depicts associativity and precedence of operators. The deepest sub-tree is traversed first, therefore the operator in that sub-tree gets precedence over the operator which is in the parent nodes.</p>

<h2>Ambiguity</h2>

<p>A grammar G is said to be ambiguous if it has more than one parse tree (left or right derivation) for at least one string.</p>

<p><b>Example</b></p>

<p>For the string id + id – id, the above grammar generates two parse trees:</p>

<p>The language generated by an ambiguous grammar is said to be <b>inherently ambiguous</b>. Ambiguity in grammar is not good for a compiler construction. No method can detect and remove ambiguity automatically, but it can be removed by either re-writing the whole grammar without ambiguity, or by setting and following associativity and precedence constraints.</p>

<h2>Associativity</h2>

<p>If an operand has operators on both sides, the side on which the operator takes this operand is decided by the associativity of those operators. If the operation is left-associative, then the operand will be taken by the left operator or if the operation is right-associative, the right operator will take the operand.</p>

<p><b>Example</b></p>

<p>Operations such as Addition, Multiplication, Subtraction, and Division are left associative. If the expression contains:</p>

<p>it will be evaluated as:</p>

<p>For example, (id + id) + id</p>

<p>Operations like Exponentiation are right associative, i.e., the order of evaluation in the same expression will be:</p>

<p>For example, id ^ (id ^ id)</p>

<h2>Precedence</h2>

<p>If two different operators share a common operand, the precedence of operators decides which will take the operand. That is, 2+3*4 can have two different parse trees, one corresponding to (2+3)*4 and another corresponding to 2+(3*4). By setting precedence among operators, this problem can be easily removed. As in the previous example, mathematically * (multiplication) has precedence over + (addition), so the expression 2+3*4 will always be interpreted as:</p>

<p>These methods decrease the chances of ambiguity in a language or its grammar.</p>

<h2>Left Recursion</h2>

<p>A grammar becomes left-recursive if it has any non-terminal ‘A’ whose derivation contains ‘A’ itself as the left-most symbol. Left-recursive grammar is considered to be a problematic situation for top-down parsers. Top-down parsers start parsing from the Start symbol, which in itself is non-terminal. So, when the parser encounters the same non-terminal in its derivation, it becomes hard for it to judge when to stop parsing the left non-terminal and it goes into an infinite loop.</p>

<p><b>Example:</b></p>

<p>(1) is an example of immediate left recursion, where A is any non-terminal symbol and α represents a string of non-terminals.</p>

<p>(2) is an example of indirect-left recursion.</p>

<p>A top-down parser will first parse the A, which in-turn will yield a string consisting of A itself and the parser may go into a loop forever.</p>

<h3>Removal of Left Recursion</h3>

<p>One way to remove left recursion is to use the following technique:</p>

<p>The production</p>

<p>is converted into following productions</p>

<p>This does not impact the strings derived from the grammar, but it removes immediate left recursion.</p>

<p>Second method is to use the following algorithm, which should eliminate all direct and indirect left recursions.</p>

<p><b>Example</b></p>

<p>The production set</p>

<p>after applying the above algorithm, should become</p>

<p>and then, remove immediate left recursion using the first technique.</p>

<p>Now none of the production has either direct or indirect left recursion.</p>

<h2>Left Factoring</h2>

<p>If more than one grammar production rules has a common prefix string, then the top-down parser cannot make a choice as to which of the production it should take to parse the string in hand.</p>

<p><b>Example</b></p>

<p>If a top-down parser encounters a production like</p>

<p>Then it cannot determine which production to follow to parse the string as both productions are starting from the same terminal (or non-terminal). To remove this confusion, we use a technique called left factoring.</p>

<p>Left factoring transforms the grammar to make it useful for top-down parsers. In this technique, we make one production for each common prefixes and the rest of the derivation is added by new productions.</p>

<p><b>Example</b></p>

<p>The above productions can be written as</p>

<p>Now the parser has only one production per prefix which makes it easier to take decisions.</p>

<h2>First and Follow Sets</h2>

<p>An important part of parser table construction is to create first and follow sets. These sets can provide the actual position of any terminal in the derivation. This is done to create the parsing table where the decision of replacing T[A, t] = α with some production rule.</p>

<h3>First Set</h3>

<p>This set is created to know what terminal symbol is derived in the first position by a non-terminal. For example,</p>

<p>That is α derives t (terminal) in the very first position. So, t ∈ FIRST(α).</p>

<h4>Algorithm for calculating First set</h4>

<p>Look at the definition of FIRST(α) set:</p>

<p>First set can be seen as:</p>

<h3>Follow Set</h3>

<p>Likewise, we calculate what terminal symbol immediately follows a non-terminal α in production rules. We do not consider what the non-terminal can generate but instead, we see what would be the next terminal symbol that follows the productions of a non-terminal.</p>

<h4>Algorithm for calculating Follow set:</h4>

<p>if α is a start symbol, then FOLLOW() = $</p>

<p>if α is a non-terminal and has a production α → AB, then FIRST(B) is in FOLLOW(A) except ℇ.</p>

<p>if α is a non-terminal and has a production α → AB, where B ℇ, then FOLLOW(A) is in FOLLOW(α).</p>

<p>Follow set can be seen as: FOLLOW(α) = { t | S *αt*}</p>

<h2>Limitations of Syntax Analyzers</h2>

<p>Syntax analyzers receive their inputs, in the form of tokens, from lexical analyzers. Lexical analyzers are responsible for the validity of a token supplied by the syntax analyzer. Syntax analyzers have the following drawbacks -</p>

<p>These tasks are accomplished by the semantic analyzer, which we shall study in Semantic Analysis.</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<pre class="result notranslate">

G = ( V, Σ, P, S )

<p>Where:</p>

<pre class="result notranslate">

V = { Q, Z, N }

Σ = { 0, 1 }

P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }

S = { Q }

<p>This grammar describes palindrome language, such as: 1001, 11100111, 00100, 1010101, 11111, etc.</p>

<h2>Syntax Analyzers</h2>

<p>A syntax analyzer or parser takes the input from a lexical analyzer in the form of token streams. The parser analyzes the source code (token stream) against the production rules to detect any errors in the code. The output of this phase is a <b>parse tree</b>.</p>

<img src="/compiler_design/images/syntax_analyzer.jpg" alt="Syntax Analyzer" />

<p>This way, the parser accomplishes two tasks, i.e., parsing the code, looking for errors and generating a parse tree as the output of the phase.</p>

<p>Parsers are expected to parse the whole code even if some errors exist in the program. Parsers use error recovering strategies, which we will learn later in this chapter.</p>

<h2>Derivation</h2>

<p>A derivation is basically a sequence of production rules, in order to get the input string. During parsing, we take two decisions for some sentential form of input:</p>

<ul class="list">

<li>Deciding the non-terminal which is to be replaced.</li>

<li>Deciding the production rule, by which, the non-terminal will be replaced.</li>

<p>To decide which non-terminal to be replaced with production rule, we can have two options.</p>

<h3>Left-most Derivation</h3>

<p>If the sentential form of an input is scanned and replaced from left to right, it is called left-most derivation. The sentential form derived by the left-most derivation is called the left-sentential form.</p>

<h3>Right-most Derivation</h3>

<p>If we scan and replace the input with production rules, from right to left, it is known as right-most derivation. The sentential form derived from the right-most derivation is called the right-sentential form.</p>

<p><b>Example</b></p>

<p>Production rules:</p>

<pre class="prettyprint notranslate">

E → E + E

E → E * E

E → id

<p>Input string: id + id * id</p>

<p>The left-most derivation is:</p>

<pre class="prettyprint notranslate">

E → E * E

E → E + E * E

E → id + E * E

E → id + id * E

E → id + id * id

<p>Notice that the left-most side non-terminal is always processed first.</p>

<p>The right-most derivation is:</p>

<pre class="prettyprint notranslate">

E → E + E

E → E + E * E

E → E + E * id

E → E + id * id

E → id + id * id

<h2>Parse Tree</h2>

<p>A parse tree is a graphical depiction of a derivation. It is convenient to see how strings are derived from the start symbol. The start symbol of the derivation becomes the root of the parse tree. Let us see this by an example from the last topic.</p>

<p>We take the left-most derivation of a + b * c</p>

<p>The left-most derivation is:</p>

<pre class="prettyprint notranslate">

E → E * E

E → E + E * E

E → id + E * E

E → id + id * E

E → id + id * id

<p>Step 1:</p>

<table class="table table-bordered">

<tr><td width="50%" style="vertical-align:middle">E → E * E</td><td><img src="/compiler_design/images/parse_tree_step_1.jpg" alt="Parse Tree Construction" /></td></tr>

<p>Step 2:</p>

<table class="table table-bordered">

<tr><td width="50%" style="vertical-align:middle">E → E + E * E</td><td><img src="/compiler_design/images/parse_tree_step_2.jpg" alt="Parse Tree Construction" /></td></tr>

<p>Step 3:</p>

<table class="table table-bordered">

<tr><td width="50%" style="vertical-align:middle">E → id + E * E</td><td><img src="/compiler_design/images/parse_tree_step_3.jpg" alt="Parse Tree Construction" /></td></tr>

<p>Step 4:</p>

<table class="table table-bordered">

<tr><td width="50%" style="vertical-align:middle">E → id + id * E</td><td><img src="/compiler_design/images/parse_tree_step_4.jpg" alt="Parse Tree Construction" /></td></tr>

<p>Step 5:</p>

<table class="table table-bordered">

<tr><td width="50%" style="vertical-align:middle">E → id + id * id</td><td><img src="/compiler_design/images/parse_tree_step_5.jpg" alt="Parse Tree Construction" /></td></tr>

<p>In a parse tree:</p>

<ul class="list">

<li>All leaf nodes are terminals.</li>

<li>All interior nodes are non-terminals.</li>

<li>In-order traversal gives original input string.</li>

<p>A parse tree depicts associativity and precedence of operators. The deepest sub-tree is traversed first, therefore the operator in that sub-tree gets precedence over the operator which is in the parent nodes.</p>

<h2>Ambiguity</h2>

<p>A grammar G is said to be ambiguous if it has more than one parse tree (left or right derivation) for at least one string.</p>

<p><b>Example</b></p>

<pre class="prettyprint notranslate">

E → E + E

E → E – E

E → id

<p>For the string id + id – id, the above grammar generates two parse trees:</p>

<img src="/compiler_design/images/parse_tree_ambiguity.jpg" alt="Parse Tree Construction" />

<p>The language generated by an ambiguous grammar is said to be <b>inherently ambiguous</b>. Ambiguity in grammar is not good for a compiler construction. No method can detect and remove ambiguity automatically, but it can be removed by either re-writing the whole grammar without ambiguity, or by setting and following associativity and precedence constraints.</p>

<h2>Associativity</h2>

<p>If an operand has operators on both sides, the side on which the operator takes this operand is decided by the associativity of those operators. If the operation is left-associative, then the operand will be taken by the left operator or if the operation is right-associative, the right operator will take the operand.</p>

<p><b>Example</b></p>

<p>Operations such as Addition, Multiplication, Subtraction, and Division are left associative. If the expression contains:</p>

<pre class="prettyprint notranslate">

id op id op id

<p>it will be evaluated as:</p>

<pre class="prettyprint notranslate">

(id op id) op id

<p>For example, (id + id) + id</p>

<p>Operations like Exponentiation are right associative, i.e., the order of evaluation in the same expression will be:</p>

<pre class="prettyprint notranslate">

id op (id op id)

<p>For example, id ^ (id ^ id)</p>

<h2>Precedence</h2>

<p>If two different operators share a common operand, the precedence of operators decides which will take the operand. That is, 2+3*4 can have two different parse trees, one corresponding to (2+3)*4 and another corresponding to 2+(3*4). By setting precedence among operators, this problem can be easily removed. As in the previous example, mathematically * (multiplication) has precedence over + (addition), so the expression 2+3*4 will always be interpreted as:</p>

<pre class="prettyprint notranslate">

2 + (3 * 4)

<p>These methods decrease the chances of ambiguity in a language or its grammar.</p>

<h2>Left Recursion</h2>

<p>A grammar becomes left-recursive if it has any non-terminal ‘A’ whose derivation contains ‘A’ itself as the left-most symbol. Left-recursive grammar is considered to be a problematic situation for top-down parsers. Top-down parsers start parsing from the Start symbol, which in itself is non-terminal. So, when the parser encounters the same non-terminal in its derivation, it becomes hard for it to judge when to stop parsing the left non-terminal and it goes into an infinite loop.</p>

<p><b>Example:</b></p>

<pre class="result notranslate">

(1) A => Aα | β

(2) S => Aα | β

A => Sd

<p>(1) is an example of immediate left recursion, where A is any non-terminal symbol and α represents a string of non-terminals.</p>

<p>(2) is an example of indirect-left recursion.</p>

<img src="/compiler_design/images/left_recursion.jpg" alt="Left Recursion" />

<p>A top-down parser will first parse the A, which in-turn will yield a string consisting of A itself and the parser may go into a loop forever.</p>

<h3>Removal of Left Recursion</h3>

<p>One way to remove left recursion is to use the following technique:</p>

<p>The production</p>

<pre class="result notranslate">

A => Aα | β

<p>is converted into following productions</p>

<pre class="result notranslate">

A => βA'

A'=> αA' | &epsilon;

<p>This does not impact the strings derived from the grammar, but it removes immediate left recursion.</p>

<p>Second method is to use the following algorithm, which should eliminate all direct and indirect left recursions.</p>

<pre class="result notranslate">

START

Arrange non-terminals in some order like A1, A2, A3,…, A_n

for each i from 1 to n

{

for each j from 1 to i-1

{

replace each production of form A_i ⟹Aj𝜸

with A_i ⟹ δ1𝜸 | δ2𝜸 | δ3𝜸 |…| 𝜸

where A_j ⟹ δ₁ | δ₂|…| δ_n are current A_j productions

}

}

eliminate immediate left-recursion

END

<p><b>Example</b></p>

<p>The production set</p>

<pre class="result notranslate">

S => Aα | β

A => Sd

<p>after applying the above algorithm, should become</p>

<pre class="result notranslate">

S => Aα | β

A => Aαd | βd

<p>and then, remove immediate left recursion using the first technique.</p>

<pre class="result notranslate">

A => βdA'

A' => αdA' | &epsilon;

<p>Now none of the production has either direct or indirect left recursion.</p>

<h2>Left Factoring</h2>

<p>If more than one grammar production rules has a common prefix string, then the top-down parser cannot make a choice as to which of the production it should take to parse the string in hand.</p>

<p><b>Example</b></p>

<p>If a top-down parser encounters a production like</p>

<pre class="result notranslate">

A ⟹ αβ | α𝜸 | …

<p>Then it cannot determine which production to follow to parse the string as both productions are starting from the same terminal (or non-terminal). To remove this confusion, we use a technique called left factoring.</p>

<p>Left factoring transforms the grammar to make it useful for top-down parsers. In this technique, we make one production for each common prefixes and the rest of the derivation is added by new productions.</p>

<p><b>Example</b></p>

<p>The above productions can be written as</p>

<pre class="result notranslate">

A => αA'

A'=> β | 𝜸 | …

<p>Now the parser has only one production per prefix which makes it easier to take decisions.</p>

<h2>First and Follow Sets</h2>

<p>An important part of parser table construction is to create first and follow sets. These sets can provide the actual position of any terminal in the derivation. This is done to create the parsing table where the decision of replacing T[A, t] = α with some production rule.</p>

<h3>First Set</h3>

<p>This set is created to know what terminal symbol is derived in the first position by a non-terminal. For example,</p>

<pre class="result notranslate">

α → t β

<title>Compiler Design - Types of Parsing</title>

<h1>Compiler Design - Types of Parsing</h1>

<p>Syntax analyzers follow production rules defined by means of context-free grammar. The way the production rules are implemented (derivation) divides parsing into two types : top-down parsing and bottom-up parsing.</p>

<h3>Top-down Parsing</h3>

<p>When the parser starts constructing the parse tree from the start symbol and then tries to transform the start symbol to the input, it is called top-down parsing.</p>

<p><b>Recursive descent parsing</b> : It is a common form of top-down parsing. It is called recursive as it uses recursive procedures to process the input. Recursive descent parsing suffers from backtracking.</p>

<h3>Bottom-up Parsing</h3>

<p>As the name suggests, bottom-up parsing starts with the input symbols and tries to construct the parse tree up to the start symbol.</p>

<p><b>Example:</b></p>

<p>Input string : a + b * c</p>

<p>Production rules:</p>

<p>Let us start bottom-up parsing</p>

<p>Read the input and check if any production matches with the input:</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<pre class="prettyprint notranslate">

S → E

E → E + T

E → E * T

E → T

T → id

<p>Let us start bottom-up parsing</p>

<pre class="prettyprint notranslate">

a + b * c

<p>Read the input and check if any production matches with the input:</p>

<pre class="prettyprint notranslate">

a + b * c

T + b * c

E + b * c

E + T * c

E * c

E * T

E

S

<title>Compiler Design - Top-Down Parser</title>

<h1>Compiler Design - Top-Down Parser</h1>

<p>We have learnt in the last chapter that the top-down parsing technique parses the input, and starts constructing a parse tree from the root node gradually moving down to the leaf nodes. The types of top-down parsing are depicted below:</p>

<h3>Recursive Descent Parsing</h3>

<p>Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as <b>predictive parsing</b>.</p>

<p>This parsing technique is regarded recursive as it uses context-free grammar which is recursive in nature.</p>

<h3>Back-tracking</h3>

<p>Top- down parsers start from the root node (start symbol) and match the input string against the production rules to replace them (if matched). To understand this, take the following example of CFG:</p>

<p>For an input string: read, a top-down parser, will behave like this:</p>

<p>It will start with S from the production rules and will match its yield to the left-most letter of the input, i.e. ‘r’. The very production of S (S → rXd) matches with it. So the top-down parser advances to the next input letter (i.e. ‘e’). The parser tries to expand non-terminal ‘X’ and checks its production from the left (X → oa). It does not match with the next input symbol. So the top-down parser backtracks to obtain the next production rule of X, (X → ea).</p>

<p>Now the parser matches all the input letters in an ordered manner. The string is accepted.</p>

<h3>Predictive Parser</h3>

<p>Predictive parser is a recursive descent parser, which has the capability to predict which production is to be used to replace the input string. The predictive parser does not suffer from backtracking.</p>

<p>To accomplish its tasks, the predictive parser uses a look-ahead pointer, which points to the next input symbols. To make the parser back-tracking free, the predictive parser puts some constraints on the grammar and accepts only a class of grammar known as LL(k) grammar.</p>

<p>Predictive parsing uses a stack and a parsing table to parse the input and generate a parse tree. Both the stack and the input contains an end symbol <b>$</b> to denote that the stack is empty and the input is consumed. The parser refers to the parsing table to take any decision on the input and stack element combination.</p>

<p>In recursive descent parsing, the parser may have more than one production to choose from for a single instance of input, whereas in predictive parser, each step has at most one production to choose. There might be instances where there is no production matching the input string, making the parsing procedure to fail.</p>

<h3>LL Parser</h3>

<p>An LL Parser accepts LL grammar. LL grammar is a subset of context-free grammar but with some restrictions to get the simplified version, in order to achieve easy implementation. LL grammar can be implemented by means of both algorithms namely, recursive-descent or table-driven.</p>

<p>LL parser is denoted as LL(k). The first L in LL(k) is parsing the input from left to right, the second L in LL(k) stands for left-most derivation and k itself represents the number of look aheads. Generally k = 1, so LL(k) may also be written as LL(1).</p>

<h3>LL Parsing Algorithm</h3>

<p>We may stick to deterministic LL(1) for parser explanation, as the size of table grows exponentially with the value of k. Secondly, if a given grammar is not LL(1), then usually, it is not LL(k), for any given k.</p>

<p>Given below is an algorithm for LL(1) Parsing:</p>

<p>A grammar G is LL(1) if A &rarr; α | β are two distinct productions of G:</p>

<p>for no terminal, both α and β derive strings beginning with a.</p>

<p>at most one of α and β can derive empty string.</p>

<p>if β &rarr; t, then α does not derive any string beginning with a terminal in FOLLOW(A).</p>

<p>&copy; Copyright 2017. All Rights Reserved.</p>

<pre class="prettyprint notranslate">

S → rXd | rZd

X → oa | ea

Z → ai

<p>For an input string: read, a top-down parser, will behave like this:</p>

<p>It will start with S from the production rules and will match its yield to the left-most letter of the input, i.e. ‘r’. The very production of S (S → rXd) matches with it. So the top-down parser advances to the next input letter (i.e. ‘e’). The parser tries to expand non-terminal ‘X’ and checks its production from the left (X → oa). It does not match with the next input symbol. So the top-down parser backtracks to obtain the next production rule of X, (X → ea).</p>

<p>Now the parser matches all the input letters in an ordered manner. The string is accepted.</p>

<table class="table table-bordered">

<img src="/compiler_design/images/back_tracking_1.jpg" alt="Back Tracking" />

<img src="/compiler_design/images/back_tracking_2.jpg" alt="Back Tracking" />

<img src="/compiler_design/images/back_tracking_3.jpg" alt="Back Tracking" />

<img src="/compiler_design/images/back_tracking_4.jpg" alt="Back Tracking" />

<h3>Predictive Parser</h3>

<p>Predictive parser is a recursive descent parser, which has the capability to predict which production is to be used to replace the input string. The predictive parser does not suffer from backtracking.</p>

<p>To accomplish its tasks, the predictive parser uses a look-ahead pointer, which points to the next input symbols. To make the parser back-tracking free, the predictive parser puts some constraints on the grammar and accepts only a class of grammar known as LL(k) grammar.</p>

<img src="/compiler_design/images/predictive_parser.jpg" alt="Predictive Parser" />

<p>Predictive parsing uses a stack and a parsing table to parse the input and generate a parse tree. Both the stack and the input contains an end symbol <b>$</b> to denote that the stack is empty and the input is consumed. The parser refers to the parsing table to take any decision on the input and stack element combination.</p>

<img src="/compiler_design/images/top_down_parser_construction.jpg" alt="Top-Down Parser Construction" />

<p>In recursive descent parsing, the parser may have more than one production to choose from for a single instance of input, whereas in predictive parser, each step has at most one production to choose. There might be instances where there is no production matching the input string, making the parsing procedure to fail.</p>

<h3>LL Parser</h3>

<p>An LL Parser accepts LL grammar. LL grammar is a subset of context-free grammar but with some restrictions to get the simplified version, in order to achieve easy implementation. LL grammar can be implemented by means of both algorithms namely, recursive-descent or table-driven.</p>

<p>LL parser is denoted as LL(k). The first L in LL(k) is parsing the input from left to right, the second L in LL(k) stands for left-most derivation and k itself represents the number of look aheads. Generally k = 1, so LL(k) may also be written as LL(1).</p>

<img src="/compiler_design/images/ll_parser.jpg" alt="LL Parser" />

<h3>LL Parsing Algorithm</h3>

<p>We may stick to deterministic LL(1) for parser explanation, as the size of table grows exponentially with the value of k. Secondly, if a given grammar is not LL(1), then usually, it is not LL(k), for any given k.</p>

<p>Given below is an algorithm for LL(1) Parsing:</p>

<pre class="prettyprint notranslate">

Input:

string ω

parsing table M for grammar G

Output:

If ω is in L(G) then left-most derivation of ω,

error otherwise.

Initial State : $S on stack (with S being start symbol)

ω$ in the input buffer

SET ip to point the first symbol of ω$.

repeat

let X be the top stack symbol and a the symbol pointed by ip.

if X&isin; V_t or $

if X = a

POP X and advance ip.

else

error()

endif

else /* X is non-terminal */

if M[X,a] = X → Y1, Y2,... Yk

POP X

PUSH Yk, Yk-1,... Y1 /* Y1 on top */

Output the production X → Y1, Y2,... Yk

else

error()

endif

endif

until X = $ /* empty stack */

<title>Compiler Design - Bottom-Up Parser</title>

<h1>Compiler Design - Bottom-Up Parser</h1>

<p>Bottom-up parsing starts from the leaf nodes of a tree and works in upward direction till it reaches the root node. Here, we start from a sentence and then apply production rules in reverse manner in order to reach the start symbol. The image given below depicts the bottom-up parsers available.</p>

<h3>Shift-Reduce Parsing</h3>

<p>Shift-reduce parsing uses two unique steps for bottom-up parsing. These steps are known as shift-step and reduce-step.</p>

<p><b>Shift step</b>: The shift step refers to the advancement of the input pointer to the next input symbol, which is called the shifted symbol. This symbol is pushed onto the stack. The shifted symbol is treated as a single node of the parse tree.</p>

<p><b>Reduce step</b> : When the parser finds a complete grammar rule (RHS) and replaces it to (LHS), it is known as reduce-step. This occurs when the top of the stack contains a handle. To reduce, a POP function is performed on the stack which pops off the handle and replaces it with LHS non-terminal symbol.</p>

<h3>LR Parser</h3>

<p>The LR parser is a non-recursive, shift-reduce, bottom-up parser. It uses a wide class of context-free grammar which makes it the most efficient syntax analysis technique. LR parsers are also known as LR(k) parsers, where L stands for left-to-right scanning of the input stream; R stands for the construction of right-most derivation in reverse, and k denotes the number of lookahead symbols to make decisions.</p>

<p>There are three widely used algorithms available for constructing an LR parser:</p>

<h3>LR Parsing Algorithm</h3>

<p>Here we describe a skeleton algorithm of an LR parser:</p>