Translator from arithmetic expressions to LLVM IR

This repository implements a small expression language compiler that emits LLVM IR. It uses Jison for parsing/lexing.

The language is not very different than the Dragon language described in https://github.com/ULL-ESIT-PL/dragon2js (the one we have used for the labs "Competenciales") but it is smaller. It still supports:

• basic types: int (mapped to i32), real (mapped to double), and bool (mapped to i1)
• explicit declarations (int a, real x, bool b, int[3] v, etc.)
• assignments (a[0] = e) and arithmetic (+, -, *, /)
• comparison operators (<, <=, >, >=, ==, !=) returning booleans
• logical operators (&&, ||) on booleans
• unary minus
• comma operator
• explicit printing with PRINT(e) / print(e)
• arrays with indexing
• block scopes with lexical shadowing

Install dependencies

npm install

Install llvm and make sure lli is in your PATH for executing generated IR.

Build parser

npm run build

Equivalent command:

npx jison src/calc.jison src/calc.l -o src/calc.js

Run tests

npm test

Use the translator

Input modes:

• From file: bin/use_calc.js path/to/input.calc
• Inline: bin/use_calc.js --expression 'int a; a = 3, a + 1'

By default the generated LLVM IR is printed to stdout.

Useful options:

• --output path/to/output.ll writes IR to file
• --verbose prints IR even when --output is used

Language overview

Declarations are explicit

Scalars and arrays must be declared before use. Supported types are int, real, and bool.

int a
real x
bool b
int[3] v
int[2][3] m

Top-level programs are either:

• decls ; expression
• expression

Inside blocks, declarations must appear at the beginning:

{ int b; b = 4, print(b) }

Expression operators

Arithmetic

• binary: + - * / (on int and real with automatic type promotion)
• unary: -e (on int, real, or bool)

Comparison (return bool)

• < <= > >= == != (on int and real)

Logical (require bool operands, return bool)

• && ||

Other

• assignment: loc = e
• comma: e1, e2 (returns value/type of e2)

print

print(e) is an expression that prints e and returns it. If the whole program has no explicit print, the compiler emits an implicit print of the final expression.

Current storage strategy in generated IR

Declared variables are emitted as local stack slots (alloca) in @main.

• scalar example: %.a.addr = alloca i32
• array example: %.v.addr = alloca [3 x i32]
• identifier main is safely emitted as %.main.addr (no collision with function @main)

Example: mixed integers and floats

bin/use_calc.js --expression '3-2-1.0' | lli
0.000000

Representative IR:

declare i32 @printf(i8*, ...)
@.str.i32 = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
@.str.double = private unnamed_addr constant [4 x i8] c"%f\0A\00", align 1

define i32 @main() {
  %1 = sub i32 3, 2
  %2 = sitofp i32 %1 to double
  %3 = fsub double %2, 1.0
  %4 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.double, i32 0, i32 0), double %3)
  ret i32 0
}

Example: explicit scalar declarations

bin/use_calc.js --expression 'int a; int b; a = 5, b = 3 + a' | lli
8

Representative IR:

define i32 @main() {
  %.a.addr = alloca i32
  %.b.addr = alloca i32
  store i32 5, i32* %.a.addr
  %1 = load i32, i32* %.a.addr
  %2 = add i32 3, %1
  store i32 %2, i32* %.b.addr
  %3 = call i32 (i8*, ...) @printf(..., i32 %2)
  ret i32 %2
}

Example: block scope and shadowing

bin/use_calc.js --expression 'int a; a = 1, { int a; a = 2, print(a) }, print(a)' | lli
2
1

Example: arrays

bin/use_calc.js --expression 'int[3] a; a[1] = 42, a[1]' | lli
42

Representative IR pattern:

%.a.addr = alloca [3 x i32]
%1 = getelementptr inbounds [3 x i32], [3 x i32]* %.a.addr, i32 0, i32 1
store i32 42, i32* %1
%2 = getelementptr inbounds [3 x i32], [3 x i32]* %.a.addr, i32 0, i32 1
%3 = load i32, i32* %2

Example: boolean comparisons

bin/use_calc.js --expression '5 > 3' | lli
1

bin/use_calc.js --expression 'bool a; a = (10 <= 20), a && true' | lli
1

Representative IR for comparison:

%1 = icmp sgt i32 5, 3
%2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.i32, i32 0, i32 0), i32 %1)
ret i32 %1

Example: boolean type

bin/use_calc.js --expression 'true, false' | lli
0

Boolean literals true and false are mapped to i1 in LLVM.

Error examples

Undeclared variable:

bin/use_calc.js --expression 'a = 1'

Type mismatch:

bin/use_calc.js --expression 'int a; a = 1, a = 2.5'

Indexing scalar:

bin/use_calc.js --expression 'int a; a = 1, a[0]'

Execute LLVM IR

With lli

bin/use_calc.js --expression 'int a; a = -2' | lli
-2

Save IR and execute:

bin/use_calc.js examples/input.calc --output tmp/salida.ll
lli tmp/salida.ll

With clang

Compile (links printf from libc):

clang tmp/salida.ll -o tmp/salida
./tmp/salida

If needed:

clang tmp/salida.ll -o tmp/salida -Wno-override-module

Compiler Explorer

1. Go to https://godbolt.org/
2. Select LLVM IR as language.
3. Paste generated IR.
4. Select clang and compile.
5. (Optional) enable execution and inspect output.

Tutorial

Go to our tutorial: Hello LLVM