Building a Mini-Compiler: A Journey Through Lexical, Syntax, and Semantic Analysis

Introduction

Compilation is a fundamental process in computer science, transforming high-level code into machine-readable instructions. In our project, we set out to build a mini-compiler for a programming language inspired by Khwarizm: HumanScript. Our goal was to create a user-friendly language with an intuitive syntax that simplifies programming for beginners while maintaining robust computational principles.

This article will guide you through the different phases of our compiler’s development, focusing on the semantic analysis phase, a crucial step in ensuring that the written code adheres to the rules of the language. We will explore how we designed the symbol table, generated intermediate code using quadruples, and implemented semantic routines for control structures like loops.

Let’s begin by introducing HumanScript, its inspirations, and its core design principles.

HumanScript: A Language Designed for Readability

HumanScript is a programming language inspired by Khwarizm, an educational language. The primary goal of HumanScript is to combine the efficiency of formal programming languages with a natural, human-like syntax. This makes the language more accessible and easier to learn, especially for beginners. The syntax of HumanScript is designed to be intuitive, resembling everyday language while maintaining robust computational concepts.

Here’s an example of code written in HumanScript:

Let int x be 6
Let Dict nom be {"Family name": "REZZOUG", "first name": "Aicha"}
int r
r == 3
const float m be 3.14
const bool n be true
Let int y be 3
Let int z be y * x
Let float k be m + 1.3

As you can see, the syntax is straightforward and easy to understand, making it an excellent choice for educational purposes.

Lexical Analysis: The First Step in Compilation

The first phase of any compiler is lexical analysis. This step involves breaking down the source code into a series of tokens (or lexemes), which are the basic building blocks of the language. These tokens are then passed on to the next stages of the compilation process, such as syntax and semantic analysis.

In the case of HumanScript, the lexical analyzer was modified to include type assignments, which allow for type compatibility checks during the semantic analysis phase. This ensures that the compiler can detect type mismatches early in the process, reducing the likelihood of runtime errors.

Key Components of Lexical Analysis

1. Tokenization: The process of converting a sequence of characters into a sequence of tokens.
2. Type Checking: Ensuring that variables and operations are compatible in terms of data types.
3. Error Detection: Identifying and reporting lexical errors, such as invalid characters or incorrect syntax.

Syntax Analysis: Building the Parse Tree

Once the lexical analysis is complete, the next step is syntax analysis. This phase involves parsing the tokens to ensure they conform to the grammatical rules of the language. In HumanScript, the syntax analysis was implemented using a top-down parsing approach, which is a common technique in compiler design.

Steps in Syntax Analysis

1. Grammar Selection: Choosing a subset of the HumanScript grammar to focus on.
2. Grammar Refinement: Ensuring the grammar is clean and free of ambiguities.
3. Construction of FIRST and FOLLOW Sets: These sets are used to build the parsing table, which guides the parser in making decisions during the parsing process.
4. Parsing Table Construction: Creating a table that maps non-terminal symbols to production rules based on the current input token.

Example of Syntax Analysis in HumanScript

Here’s an example of how the syntax analyzer works in HumanScript:

hind23@DESKTOP-05BNM2D:~$ gcc -o prog prog.c tableSymboles.c
hind23@DESKTOP-05BNM2D:~$ ./prog
Donner déclaration : intt x
Erreur! intt
hind23@DESKTOP-05BNM2D:~$ gcc -o prog prog.c tableSymboles.c
hind23@DESKTOP-05BNM2D:~$ ./prog
Donner déclaration : int c
La chaine est syntaxiquement correcte !

In this example, the syntax analyzer detects an error when an invalid type (`intt`) is used, but it accepts a valid declaration (`int c`).

Syntax Analysis with Bison

The team used Bison, a popular parser generator, to implement the syntax analysis. Bison allows developers to define the grammar rules and automatically generates the parsing code. Here’s an example of how the grammar rules were defined in Bison:

%left LOGICAL_OR
%left LOGICAL_AND
%left EQUAL NOT_EQUAL
%left LESS_THAN GREATER_THAN LESS_EQUAL GREATER_EQUAL
%left ADD SUB
%left MUL DIV MOD INT_DIV
%right LOGICAL_NOT
%nonassoc UMINUS /* For unary negation */

These rules define the precedence and associativity of operators in HumanScript, ensuring that expressions are parsed correctly.

Semantic Analysis: Understanding the Meaning

After the syntax analysis, the compiler moves on to semantic analysis. This phase is concerned with the meaning of the code, ensuring that the program makes sense in terms of the language’s semantics. The semantic analyzer checks for type compatibility, variable declarations, and other semantic rules.

Key Steps in Semantic Analysis

1. Transformation of Syntax Grammar into Semantic Grammar: This step involves adding semantic actions to the grammar rules.
2. Intermediate Code Generation: The compiler generates an intermediate representation of the code,in the form of quadruples.
3. Adding Semantic Routines: These routines perform checks and transformations during the semantic analysis phase.

Symbol Table: The Heart of Semantic Analysis

The symbol table is a critical data structure in semantic analysis. It stores information about variables, functions, and other symbols in the program. In HumanScript, the symbol table is implemented as a hash table, where each entry contains the following information:

Get Dinari Yasmine’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

- ID: A unique identifier for the symbol.
- Name: The name of the variable or constant.
- Type: The data type (e.g., integer, float, boolean, etc.).
- Value: The current value of the variable.
- isConst: A boolean indicating whether the symbol is a constant.
- isInitialized: A boolean indicating whether the variable has been initialized.
- scopeLevel: The scope level of the symbol, used to manage nested blocks.
- next: A pointer to the next entry in the same bucket (for handling collisions).

Semantic Routines and Quadruples

The semantic analyzer generates quadruples, which are a form of intermediate code. Each quadruple consists of an operator and up to three operands. Here’s an example of how quadruples are generated for a simple program in HumanScript:

Quad[1]=[ := , 0 , , x ]
Quad[2]=[ := , 10 , , num ]
Quad[3]=[ := , 3.14 , , y ]
Quad[4]=[ := , 5 , , o ]
Quad[5]=[ + , 10 , 5 , t5 ]
Quad[6]=[ := , 15 , , h ]
Quad[7]=[ := , true , , isActive ]
Quad[8]=[ CONCAT , Aicha , Rezzoug , t8 ]
Quad[9]=[ := , AichaRezzoug , , name ]
Quad[10]=[ ARRAY_DECL , numbers , [1,2,3,4,5] , t10 ]

These quadruples represent the intermediate steps that the compiler takes to execute the program.

Handling Control Structures: The Repeat-Until Loop

One of the key challenges in semantic analysis is handling control structures, such as loops and conditionals. In HumanScript, the Repeat-Until loop is a control structure that executes a block of code at least once and then checks a condition to determine whether to repeat the execution.

Here’s how the Repeat-Until loop is translated into quadruples:

RepeatLoop: RepeatStart StatementList RepeatEnd;
RepeatStart: REPEAT COLON {
 int repeatId = qc;
 char repeatStartLabel[20];
 sprintf(repeatStartLabel, "REPEAT_START_%d", repeatId);
 inserepQuadreplet(&q, repeatStartLabel, "", "", "", qc++);
 empiler(stack, repeatId);
}
RepeatEnd : UNITL Expression ENDREPEAT
{
int repeatId = depiler(stack);
 char repeatStartLabel[20];
 char repeatEndLabel[20];
 sprintf(repeatStartLabel, "REPEAT_START_%d", repeatId);
 sprintf(repeatEndLabel, "REPEAT_END_%d", repeatId);
 char typestr[MAX_TYPE_LENGTH];
 getTypestring($2.type, typestr);
if (!strcmp(typeStr,"boolean")) {
 yverror("Repeat-until condition must be a boolean expression");
 YVERROR;
 }
 inserepQuadreplet(&q, "BZ", repeatStartLabel, "", $2.value, qc++);
 inserepQuadreplet(&q, repeatEndLabel, "", "", "", qc++);
}

This code snippet shows how the compiler generates quadruples for the Repeat-Until loop, ensuring that the loop executes correctly and that the condition is properly evaluated.

Conclusion: A Successful Mini-Compiler

Building a mini-compiler for HumanScript was both a challenging and rewarding experience. We successfully implemented a lexical analyzer, syntax parser, and semantic analyzer, allowing us to generate intermediate code in the form of quadruples. By focusing on readability and structured programming, HumanScript serves as a stepping stone for beginners exploring the world of programming languages and compilation.

Through this project, we deepened our understanding of symbol tables, semantic rules, and control structures like loops. The journey of compiler construction has reinforced key computer science principles and given us a hands-on experience in developing language processing tools.

While our current implementation is a great starting point, there is always room for improvement. Future enhancements could include optimizations, additional language features, and a full-fledged backend for final code generation.

We hope this article provided you with valuable insights into the fascinating world of compilation and language design.

HumanScript Github repo