In this chapter, you will get to know about how to write a frontend for a language. By making use of a custom-defined TOY language, you will have recipes on how to write a lexer and a parser, and how to generate IR code from the Abstract Syntax Tree (AST) generated by the frontend.

Before implementing a lexer and parser, the syntax and grammar of the language need to be determined first. In this chapter, a TOY language is used to demonstrate how a lexer and a parser can be implemented. The purpose of this recipe is to show how a language is skimmed through. For this purpose, the TOY language to be used is simple but meaningful.

A language typically has some variables, some function calls, some constants, and so on. To keep things simple, our TOY language in consideration has only numeric constants of 32-bit Integer type A, a variable that need not declare its type (like Python, in contrast to C/C++/Java, which require a type declaration) in the TOY language.

Lexer is a part of the first phase in compiling a program. Lexer tokenizes a stream of input in a program. Then parser consumes these tokens to construct an AST. The language to tokenize is generally a context-free language. A token is a string of one or more characters that are significant as a group. The process of forming tokens from an input stream of characters is called tokenization. Certain delimiters are used to identify groups of words as tokens. There are lexer tools to automate lexical analysis, such as LEX. In the TOY lexer demonstrated in the following procedure is a handwritten lexer using C++.

$ vim toy.cpp

AST is a tree representation of the abstract syntactic structure of the source code of a programming language. The ASTs of programming constructs, such as expressions, flow control statements, and so on, are grouped into operators and operands. ASTs represent relationships between programming constructs, and not the ways they are generated by grammar. ASTs ignore unimportant programming elements such as punctuations and delimiters. ASTs generally contain additional properties of every element in it, which are useful in further compilation phases. Location of source code is one such property, which can be used to throw an error line number if an error is encountered in determining the correctness of the source code in accordance with the grammar (location, line number, column number, and so on, and other related properties are stored in an object of the SourceManager class in Clang frontend for C++).

The AST is used intensively during semantic analysis, where...

Parser analyzes a code syntactically according to the rules of the language's grammar. The parsing phase determines if the input code can be used to form a string of tokens according to the defined grammar. A parse tree is constructed in this phase. Parser defines functions to organize language into a data structure called AST. The parser defined in this recipe uses a recursive decent parser technique which is a top-down parser, and uses mutually recursive functions to build the AST.

In this recipe, you will learn how to parse a simple expression. A simple expression may consist of numeric values, identifiers, function calls, a function declaration, and function definitions. For each type of expression, individual parser logic needs to be defined.

In this recipe, you will learn how to parse a binary expression.