Introduction

The project was created based on the book COMPILERS: PRINCIPLES, TECHNIQUES AND TOOLS by Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman.

The structure of a compiler is usually divided into two main parts: frontend and backend. The frontend of the compiler is responsible for analyzing the source code and is responsible for understanding its structure and meaning. It consists of phases such as:

• Lexical analysis - transforms the stream of source code characters into lexemes, which are grouped into tokens.
• Syntactic analysis - uses tokens to build a syntax tree that maps the grammatical structure of the code.
• Semantic analysis - checks whether the source code is semantically consistent and complies with the rules of the language.

In my project, I implement a frontend for a simple C-inspired language. The last two phases are integrated within the parser module. The compiler backend, which deals with generating the output code and optimization, is not part of the project.

Example Input	Example Output

Project structure

The source code is analyzed by a lexer, which generates tokens based on it. The parser transforms the stream of tokens of the source program into a syntax tree, the nodes of which are implemented as objects. These objects are responsible for constructing tree nodes, type checking, and generating intermediate code in three-address form.

The Word class supports lexemes for keywords, identifiers, and compound tokens, and operators in intermediate code. The Lexer class, whose main method is scan, recognizes numbers, identifiers, and keywords, mapping them to Word objects. The Env class assigns tokens Id objects, representing identifiers. The Type class, as a subclass of Word, transforms type names into objects.

The syntax tree nodes are implemented by the Node class, which stores the source line number in the lexline field, which makes it easier to report errors. This class supports code generation, providing methods such as gen for creating terms in three-address instructions, and reduce, which simplifies expressions to single addresses. Jumping code for logical expressions is generated by the jumping method, which redirects control to the appropriate true or false labels.

The instructions are implemented as subclasses of Stmt, which makes them easier to implement and extend. This parser structure scheme allows for efficient transformation of source code into intermediate code with support for various types and language constructs.

Language description

A source program consists of a block containing optional declarations (decl) and statements (stmt). The basic token represents basic types. Productions for expressions support associativity and operator precedence. They use a hierarchy of nonterminals corresponding to individual precedence levels, ending with the nonterminal factor for parenthesized expressions, identifiers, array references, and constants.

program  → block

block    → "{" decls stmts "}"

decls    → decls decl
         | ε

decl     → type id ";"

type     → type "[" num "]"
         | basic

stmts    → stmts stmt
         | ε

stmt     → loc "=" bool ";"
         | "if" "(" bool ")" stmt
         | "if" "(" bool ")" stmt "else" stmt
         | "while" "(" bool ")" stmt
         | "do" stmt "while" "(" bool ")" ";"
         | "break" ";"
         | block

loc      → loc "[" bool "]"
         | id

bool     → bool "||" join
         | join

join     → join "&&" equality
         | equality

equality → equality "==" rel
         | equality "!=" rel
         | rel

rel      → expr "<" expr
         | expr "<=" expr
         | expr ">=" expr
         | expr ">" expr
         | expr

expr     → expr "+" term
         | expr "-" term
         | term

term     → term "*" unary
         | term "/" unary
         | unary

unary    → "!" unary
         | "-" unary
         | factor

factor   → "(" bool ")"
         | loc
         | num
         | real
         | "true"
         | "false"