Lexer에 대한 신비

The Pipeline Behind compiling software can be challenging to grasp… I’ll try to break it down as much as i can

First of all the full pipeline looks something like this:

source code → [Lexer] → tokens → [Parser] → AST → [Semantic Analysis] → annotated AST → [LLVM IR] → optimized IR → machine code

Enter fullscreen mode Exit fullscreen mode

The Lexer

The lexer’s job is more mechanical. It’s also known as the tokenizer.
It reads code character by character dividing it into small items known as tokens which are small chunks of a program, Take this as an example:

let x = 3 + 4;

As raw text, that’s just a sequence of characters

l, e, t, a space, x, and so on.

The lexer’s job is to turn that into a clean stream of tokens:

After analysis from the lexer:

KEYWORD(let) IDENT(x) EQUALS NUMBER(5) PLUS NUMBER(3) SEMICOLON

Notice that the white space disappeared this is because after analysis they are not needed

Another thing is each chunk or Token got tagged with what kind of a token or type it is

One more thing i found interesting about the lexer is that is uses Regular Expressions (regex)

But how?
you might ask

Simple, The lexer uses it to convert raw character sequences into tokens which are then passed to a passer to verify against the BNF/EBNF which are formal notations systems used to define the syntax of grammar of programming languages

RAW TEXT INPUT: "if ( x > 10 )"
              │
              ▼
 ┌─────────────────────────┐
 │         LEXER           │ ◄── Powered by REGEX (Matches individual character patterns)
 └─────────────────────────┘
              │
              ▼ TOKENS: [KEYWORD("if"), LPAREN, IDENTIFIER("x"), GT, NUMBER(10), RPAREN]

Enter fullscreen mode Exit fullscreen mode

plaintext

The Parser

The parser also knows as a tree builder it builds a tree structure that captures how they relate to each other the (AST), the abstract syntax tree

How does the parser build a tree lets see

A token stream on it’s own has no structure

[KEYWORD("if"), LPAREN, IDENTIFIER("x"), GT, NUMBER(10), RPAREN]

The parser builds the tree by consuming the tokens outputted by the lexer

But it does this step by step,

1. Lexical analysis, Code text is split into small
   pieces called tokens

2. Grammar, it reads these tokens to make sure they follow the strict rules of the language used

3. Node creation, The parser builds memory objects for operations, variables and statements linking them together into a TREE shape

If we had this as an example
3 + 2 * 5

In the end we will have this as the tree

       / \
      3   *
         / \
        2   5

Enter fullscreen mode Exit fullscreen mode

plaintext

Semantic Analysis

Maybe you’ve heard of it before in Natural Language Processing (NLP) it refers to resolving meaning and ambiguity in natural language like figuring out if rock means a stone or music genre.

In compilers, it means something narrower and less fuzzy

The AST from the parser only tells you the code is grammatically valid it doesn’t know whether x was declared before it’s used or whether you’re trying to add a string to an integer.

Sematic analysis does this:

• Type checking is x + y valid if x is an int and y is a string it might Parse but its still a semantic error

• Scope resolution was x actually declared before this line uses it? if there are nested scopes which x does this one refer to?

• Declaration calling a function with the wrong number of arguments referencing undeclared variable

LLVM and LLVM IR

LLVM was probably the most complex bit of this expedition one thing i noticed is

LLVM doesn’t know or care about your language.

It’s a reusable, language agnostic backend for code generation and optimizing Frontends for C, C++, Rust, Swift and many more funnel into it your job as a language author is to translate your AST into LLVM IR

Front-end (Clang, Rust, your language) → LLVM IR → Back-end (x86, ARM, RISC-V, WASM)

Enter fullscreen mode Exit fullscreen mode

plaintext

Back then before LLVM adding a new language or creating your own language with good performance meant writing your own optimizer and codegen for every architecture as unbelievable as that sounds its true.

LLVM turns that N * M problem (language * architecture) into N + M write the optimizations once and they benefit every language

I also wondered what the IR looked like something like this

; Declare the global string constant containing "Hello, World!\n"
@.str = internal constant [15 x i8] c"Hello, World!\0A\00"

; Declare the external printf function signature
declare i32 @printf(ptr, ...)

; Define the main function entry point
define i32 @main() {
entry:
    ; Call printf by passing a pointer to the string
    %call = call i32 (ptr, ...) @printf(ptr @.str)

    ; Return 0 to indicate successful execution
    ret i32 0
}

Enter fullscreen mode Exit fullscreen mode