Faul-Lang compiler

• Faul-Lang compiler
  • Usage
  • Build
    • Building the executable
    • Linux/Mac
    • Windows
  • Running Examples
  • Structure
    • Vision
  • Language
    • Rules (Grammar)
    • Operator Precedence
    • Tokens
      • Basic
      • Keywords
      • Operators
  • Compiler Phases
    • Frontend
      • Input
      • Lexer
      • Parser
      • Semantic Analysis
    • Backend
      • Program Optimization
      • Code Generation
        • MIPS32
        • Variable-Register Strategy
        • Generated Code
  • Finite State Machines
    • Integer
    • Word
  • Todo

A small compiler that translates faul-lang into MIPS assembly.

Usage

faul-compiler -h
usage: faul-compiler <file> [options]
 -d,--debug       Create parse tree and abstract sytntax tree
 -h,--help        print this message
 -o,--out <arg>   Output file

Build

Building the executable

chmod +x ./src/test/resources/Mars4_5.jar
mvn clean package

Linux/Mac

./target/faul-compiler

Windows

java -jar ./target/faul-compiler

Running Examples

./target/faul-compiler examples/fibonacci.faul
java -jar ./src/test/resources/Mars4_5.jar examples/fibonacci.asm

Structure

Vision

Initially, there should be two data types: integer (int) and boolean (bool).

This should make it possible to formulate simple statements:

int n = readI();
if(n <= 1) {
  print(false);
  exit();
}
int i = 2;
while(i<n){
  if(n % i == 0){
    print(false);
    exit();
  }
  i = i +1;
}
print(true);

Statements are terminated by a semicolon.

Language

Rules (Grammar)

Backus-Naur Form (BNF) is used to denote the rules.

More specifically, the syntax defined here is used: BNF Playground.

<program>           ::= <ows> <statement>*
<statement>         ::= "int" <ws> <ident> <ows> "=" <ows> <expression> <ows> <semi> <ows>
                      | "bool" <ws> <ident> <ows> "=" <ows> <expression> <ows> <semi> <ows>
                      | "if" <ows> "(" <ows> <expression> <ows> ")" <ows> "{" <ows> <statement>* <ows> "}" <ows> ("else" <ows> "{" <ows> <statement>* <ows> "}" <ows>)?
                      | "while" <ows> "(" <ows> <expression> <ows> ")" <ows> "{" <ows> <statement>* <ows> "}" <ows>
                      | <ident> <ows> "=" <ows> <expression> <ows> <semi> <ows>
                      | <ident> <ows> <function_call> <ows> <semi> <ows>

<expression>        ::= <equality> ( <ows> ("&&" | "||" | "&" | "|") <ows> <expression> )?
<equality>          ::= <comparision> ( <ows> ("!=" | "==") <ows> <equality> )?
<comparision>       ::= <arithmeticExpr> ( <ows> (">" | ">=" | "<" | "<=") <ows> <comparision> )?
<arithmeticExpr>    ::= <term> ( <ows> ("+" | "-") <ows> <arithmeticExpr> )?
<term>              ::= <unary> ( <ows> ("*" | "/" | "%") <ows> <term> )?
<unary>             ::= ("!" | "-") <ows> <unary>
                      | <primary>

<primary>           ::= <vbool> 
                      | <vint> 
                      | <ident>
                      | "(" <ows> <expression> <ows> ")"

<vbool>             ::= "true" | "false"
<vint>              ::= [1-9] [0-9]*
                      | "0"
<ident>             ::= ("_" | [a-z]) ("_" | [a-z] | [0-9])* (<ows> <function_call>)?
<function_call>     ::= "(" <ows> (<expression> <ows> ("," <ows> <expression> <ows>)*)? ")"
<semi>              ::= ";" (<ows> ";")*
<ws>                ::= (" " | "\t" | "\n" | "\r")+
<ows>               ::= (" " | "\t" | "\n" | "\r")*

Operator Precedence

1. Function calls
2. Parentheses
3. - !
4. * /
5. + -
6. > >= < <=
7. && || | &

Tokens

Tokens of Faul-Lang.

Basic

Name	Description
EOF	End of input
SEMICOLON	Statement terminator
V_INT	Integer
V_BOOL	Boolean truth value
OPEN_PARENTHESES	{
CLOSE_PARENTHESES	}
IDENT	Variable name

Keywords

Name	Description
INT	To declare an integer
BOOL	To declare a boolean
IF	Starts an If-Statement
ELSE	Starts an ELSE-Statement
WHILE	Starts a While-Statement

Operators

Name	Description
EQ	=
PLUS	+
MINUS	-
ASTERISK	*
SLASH	/
OR
AND	& (Bitwise AND)
EQEQ	==
NOTEQ	!=
GT	>
GTEQ	>=
LT	<
LTEQ	<=
LOR
LAND	&& (Logical AND)
NOT	!
OPEN_BRACKET	(
CLOSE_BRACKET	)

Compiler Phases

Frontend

Input

int n = readI();
if(n <= 1) {
  print(false);
  exit();
}
int i = 2;
while(i<n){
  if(n % i == 0){
    print(false);
    exit();
  }
  i = i +1;
}
print(true);

Lexer

The lexer generates a stream of Tokens from the Input.

Parser

The parser processes the Token-Stream and outputs a parse tree. During this process, it also checks for syntax errors.

This can be printed out using the toString method, for example like this:

Parse Tree (Syntax Tree)

PROGRAM
├── STATEMENT
│   ├── IDENT: n
│   ├── EQ: =
│   ├── EXPRESSION
│   │   └── EQUALITY
│   │       └── COMPARISON
│   │           └── ARITHMETIC_EXPR
│   │               └── TERM
│   │                   └── UNARY
│   │                       └── PRIMARY
│   │                           ├── IDENT: readI
│   │                           └── FUNC_CALL
│   └── SEMICOLON: ;
... (omitted for brevity, assume full output follows identically)

(Note: I kept the code block structure identical here to match your original)

Semantic Analysis

Often, a parse tree is not created at all, but rather an Abstract Syntax Tree (AST) directly. This compiler does not do this for reasons of simplicity. The AbstractSyntaxTreeFactory processes the Parse Tree into an AST.

This can also be output with the toString() method as follows:

Abstract Syntax Tree

PROGRAM, Type: T: VOID; rT: null,  Position: 0:0
├── DECLARATION, Type: T: VOID; rT: VOID,  Position: 1:1
│   ├── IDENT: n, Type: T: VAR; rT: INTEGER,  Position: 1:5
... (omitted for brevity, assume full output follows identically)

Backend

Program Optimization

Currently, there are no major optimizations. Empty "else" statements are ignored.

However, possible optimizations could include:

• Ignoring plus and minus 0
• Setting terms to 0 if they are multiplied by zero
• Not branching or removing the branch entirely for expressions that evaluate statically to true or false
• Replacing static variables with their respective values

Code Generation

Code generation occurs naively by traversing the AST. For Expressions, a modified depth-first search (DFS) is used to evaluate them in the correct order. The DFS is adapted so that instead of always visiting the left or right branch of the binary tree first, it chooses the branch that is deeper. This ensures that no more than two intermediate result registers are ever needed.

MIPS32

The generated code is MIPS32 Assembly. MIPS32 Instruction Set Quick Reference

To run it, you can use the MARS MIPS simulator - Missouri State University. This also supports some pseudo-instructions, such as li.

Variable-Register Strategy

By convention, the registers $s0 - $s7 are used to store values across procedure calls over a longer period of time. Procedures (functions) must (or should) restore these before returning. Therefore, loaded variables are stored there.

Of course, a program can have more than eight variables, which is why there must be a strategy to decide when which variable is loaded into which register and when it is written to memory.

When a variable is needed, is not already in a register, and all registers are occupied, the variable that has not been used for the longest time is moved to memory. After that, a register is free for the new variable.

Generated Code

main:
# initializing s0 with address 16
        move $s0, $0
        jal readI
        nop
# Assgining reg s0 with address 4
        move $s0, $v0
# If start
# Loading value 1
        li $t0, 1
# Less than equals
        sle $t0, $s0, $t0
        beqz $t0, label_0
...

Finite State Machines

Integer

---
Title: Integer Parser
---
stateDiagram-v2
    [*] --> s0
    s0 --> s1:1,2,3,4,5,6,7,8,9
    s1 --> s1:0,1,2,3,4,5,6,7,8,9
    s1 --> s2: +,-.*,/,<,>,!,),#semi;
    s2 --> [*]

Loading

Word

---
Title: Word Parser
---
stateDiagram-v2
    [*] --> s0
    s0 --> s1:a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,\nA,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,Y,Z,_
    s1 --> s1:0,1,2,3,4,5,6,7,8,9,\na,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,\nA,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,Y,Z,_
    s1 --> s2: WHITESPACE, +,-.*,/,<,>,!,),,(,{,#semi;
    s2 --> [*]

Loading

Todo

• Lexer

• Parser

• Abstract Syntax Tree (AST)

• Semantic Analysis

• Typechecking

• Optimization

• Code generation