This is a rather informal introduction to development of a hobby compiler . The more formal chapters on compiler development will be given in later tutorials. By the end of this tutorial you will be able to create a simple interpreter . This can be easily converted into a compiler. The requirements for following this tutorial are<\/p>\n
1. A reasonable grasp of C \/ C++ \/ Python \/ C# \/ Java<\/p>\n
2. An elementary knowledge of basic data structures and recursion<\/p>\n
<\/strong><\/p>\n Compiler defined<\/strong><\/p>\n <\/strong><\/p>\n A compiler is defined as a program that converts a source file in a specified form to an output file that can be fed to an assembler or simulated by a machine (virtual \/ real). Most of the compiler convert the given source file into assembly language that can be assembled by an assembler of the target machine.<\/p>\n For example to see the code generated by your source program in Turbo C++ , type the following<\/p>\n tcc -S source.c<\/p>\n <\/strong><\/p>\n Phases of a compiler<\/strong><\/p>\n <\/strong><\/p>\n Lexical analysis : The lexical analysis phase of the compiler essentially does the tokenizing . This phase takes a stream of text as input and converts it into tokens required for the parser . For example the lexical analyzer splits the C source into if , else , while , int etc . The lexical analyzer can be constructed using a hard coded dfa or by using a generator like lex . In the next part of this tutorial I will describe how to write your own lex like generator . In this tutorial we will use an ad hoc lexical analyzer which will be sufficient for the purpose of demonstration. In fact you will be surprised to see that this sort of approach is taken in small hobby compilers like small- C .<\/p>\n Syntax Analysis : The lexemes must be arranged in such form that reflects the syntactic structure of the language . This is called syntax analysis or parsing . In this tutorial we will discuss only a form of top down parsing known as recursive descent parsing with one look ahead . Every programming language has a grammar which is usually represented in BNF form . A CFG grammar of a programming language is defined by the following<\/p>\n 1. A set of terminal symbols that cannot be substituted<\/p>\n 2. A set of non terminals which can be substituted by terminal or other non terminals<\/p>\n 3. A set of Productions that define the grammar (of the form NT -> A | B , ie LHS should have<\/p>\n only one nonterminal)<\/p>\n 4. A start symbol from which everything begins<\/p>\n Eg A grammar for the string aaaa ..any number of times is<\/p>\n S -> \u201ca \u201c S { terminals are enclosed in \u201c \u201c and non terminals in capital letters }<\/p>\n { | used to denote OR }<\/p>\n S -> nothing<\/p>\n ie this means that S can be an \u201ca\u201d followed by S itself or S can be nothing .<\/p>\n Lets see how aaa is derived<\/p>\n S->aS => S->aaS ( using S -> aS) => S->aaaS(using S->aS) => S->aaa (using S-> nothing_left) .<\/p>\n Now lets see how a recursive descent parser is constructed for this grammar. This is easily done by replacing each non terminal by function call and performing a match for the terminal<\/p>\n Void parseS()<\/p>\n {<\/p>\n match_current_input_token_for(\u201ca\u201d);<\/p>\n if( not_matched) error();<\/p>\n if(end_of_input) return ;<\/p>\n parseS();<\/p>\n }<\/p>\n In order to construct a recursive descent parser like the above the grammar should follow these<\/p>\n conditions .<\/p>\n For each production of the form S \u2013 > A | C | E .<\/p>\n The first sets of each non-terminal in each of this production must be disjoint<\/p>\n ie FIRST (A) intersection FIRST (C) intersection FIRST(E) = NULL<\/p>\n The first sets and the follow sets of a nonterminal must be disjoint ie \u2026<\/p>\n FIRST(A) intersection FOLLOW (A) = NULL<\/p>\n FIRST(C) intersection FOLLOW ( C ) = NULL<\/p>\n \u2026so on \u2026<\/p>\n This implies that the first set should not be equal to the follow set of the non- terminal.<\/p>\n The the first set of a terminal is the symbol itself. The first set of the non \u2013 terminal is the set of terminals with which the nonterminal can begin with . The follow set of a non terminal is the set of terminals which can come after the non terminal. Lets find out the First n Follow for the following<\/p>\n grammar .<\/p>\n S -> \u201ca\u201dA | C D<\/p>\n A->\u201db\u201dA |\u201dc\u201d<\/p>\n C -> \u201ce\u201d|nothing<\/p>\n D->\u201dd\u201d | \u201cg\u201d D<\/p>\n FIRST(S) = FIRST ( \u201ca\u201dA) union FIRST(CD)<\/p>\n = \u201ca\u201d union FIRST( C )<\/p>\n = \u201ca\u201d union FIRST ( C ) union FIRST (D) { since C can be nothing , first of D must be<\/p>\n included}<\/p>\n = \u201ca\u201d union FIRST ( \u201ce\u201d ) union FIRST (\u201cd\u201d) union FIRST (\u201cg\u201d)<\/p>\n = \u201ca\u201d union \u201ce\u201d union \u201cd\u201d union \u201cg\u201d<\/p>\n = { a , e , d , g }<\/p>\n Similarly FOLLOW(C) = FIRST(D) = { d , g } etc \u2026 Computing the first and follow of the rest of the symbols in the grammar is left as an exercise to you . These rules have to followed in order to avoid conflicts in the predictive parsing table. More about advanced parsing methods in later chapters .<\/p>\n Now i present a more formal algorithms for finding first and follow .is given below . You might find it easier to follow the informal definitions that the algorithms given below.<\/p>\n Finding all nothingable non terminals<\/p>\n 1) if given A -> nothing the set NOTINGABLE(A) = true<\/p>\n 2) while no changes made in NOTINGABLE table<\/p>\n 3) if production such that A -> A1 A2 A3 \u2026 Ak and all of NOTHINGABLE(A1)<\/p>\n NOTHINGABLE(A2) \u2026 NOTHINGABLE(Ak) = true<\/p>\n 4) then NOTINGABLE(A) = true<\/p>\n Finding first<\/p>\n 1) if terminal then set FIRST (Symbol) = symbol<\/p>\n 2) while no changes made in FIRST table<\/p>\n 3) if production such that A -> A1 A2 A3 \u2026 Ak<\/p>\n 4) FIRST(A) = FIRST(A) union FIRST (A1)<\/p>\n 5) while (NOTHINGABLE(A1 ) , NOTHINGABLE(A2) .. NOTHINGABLE(Aj). = TRUE)<\/p>\n 6) FIRST(A) = FIRST(A) U FIRST(A1) U FIRST (A2) U FIRST (A3) \u2026<\/p>\n FIRST(Aj+1)<\/p>\n Finding follow<\/p>\n 1) follow is not defined for terminals<\/p>\n 2) follow of the Start symbol is the end of input marker<\/p>\n 3) if there exits a nonterminal A such that B -> E A D then<\/p>\n 4) add FIRST(D) to FOLLOW(A)<\/p>\n 5) if there exists a production such that A -> G H such that NOTHINGABLE(H) = true then<\/p>\n 6) everything in FOLLOW (A) is also in FOLLOW (H)<\/p>\n As a final example, grammar for if statement.<\/p>\n S -> IFCONDTION<\/p>\n IFCONDITON -> \u201cif\u201d EXPRESSION \u201cthen\u201d STATEMENT<\/p>\n EXPRESSION -> TERM \u201c+\u201d TERM<\/p>\n TERM -> FACTOR *FACTOR<\/p>\n FACTOR -> id<\/p>\n EXPRESSION -> \u201c(\u201c EXPRESSION \u201c)\u201d<\/p>\n STATEMENT -> id \u201c;\u201d STATEMENT | nothing<\/p>\n It can be seen that right recursion in many cases is unneeded and can be removed using a simple loop .<\/p>\n As right recursion leads to tail recursion. Eg<\/p>\n The grammar S ->aS | nothing can be more compactly written as S-> (a)*<\/p>\n The parser reduces to<\/p>\n parseS()<\/p>\n {<\/p>\n while(current_token == \u201ca\u201d ) advance_input_pointer();<\/p>\n }<\/p>\n Left recursion will lead to an infinite loop and should be removed .For eg the grammar<\/p>\n S -> S B | D<\/p>\n can be re written as<\/p>\n S -> D S_DASH<\/p>\n S_DASH -> B S_DASH<\/p>\n Common factor in grammars should also be removed eg for the grammar<\/p>\n S ->\u201d if\u201d condition \u201cthen\u201d statement<\/p>\n S -> \u201cif\u201d condition \u201cthen\u201d statement \u201celse\u201d statement<\/p>\n can be modified into<\/p>\n S->AB<\/p>\n A -> \u201d if\u201d condition \u201cthen\u201d statement<\/p>\n B -> \u201celse\u201d statement | nothing<\/p>\n Semantic Analysis : Syntax analysis does not tell anything about the meaning of the statement under<\/p>\n consideration . It simply check whether the syntax is correct . For eg<\/p>\n const int i = 20;<\/p>\n i++;<\/p>\n The above lines are syntactically correct but semantically wrong . The semantics are sometimes given<\/p>\n using attribute grammars . .More about this later.<\/p>\n Code Generation : This is the final phase where the assembly code to the target machine is generated . I have skipped many other phases which are part of a more mature compiler. The purpose of this tutorial is to give quick introduction . The most of the hobby compilers the major component is the parser and code generation and semantic analysis is done when each non terminal is encountered in the parser.<\/p>\n As an example of developing a simple interpreter , I have provided the source code of a simple basic like interpreter. I have used the mingw port of gcc for compiling the source . I used dev-cpp as the ide .<\/p>\n