Skip to content

README.md

Latest commit

 

History

History
131 lines (102 loc) · 2.51 KB

README.md

File metadata and controls

131 lines (102 loc) · 2.51 KB

A handwritten parser

This package contains a handwritten parser for a simple expression language. The language supports:

  • Variables declarations with the types number and string
  • Variable Assignments
  • Arithmetic expressions
  • Print statements
  • Expressions, like basic arithmetic operations, string concatenation, variable references, literals and parentheses

How does it work?

Parsing is a linear process that takes a string of text and produces a tree-like structure that represents the structure of the text.

flowchart LR
    A[Lexer] --> B[Parser]
    CC@{shape: brace-r, label: "Typir is applied here"} --> C
    B --> C[Type System]
    C --> D[Validator]

    style C fill:#f9f,stroke:#333,stroke-width:4px
Loading

The following sections describe each step in the process.

Lexer

Input: A string of text

Output: A list of tokens

Task: Splits the text to tokens and classifies each token.

flowchart LR
    subgraph Text
      A["variable = 123"]
    end
    A --> B[Lexer]
    B --> Tokens
    subgraph Tokens
      T1[variable:ID]
      T2[=:ASSIGN]
      T3[123:NUMBER]
    end
Loading

Parser

Input: A list of tokens

Output: An Abstract Syntax Tree (AST)

Task: Takes token and arranges them as a tree.

flowchart LR
    subgraph Tokens
      T1[variable:ID]
      T2[=:ASSIGN]
      T3[123:NUMBER]
    end

    Tokens --> D[Parser]
    subgraph AST
        EE1[variable]
        EE2[=]
        EE3[123]
        EE2 --> EE1
        EE2 --> EE3
    end
    D --> AST
Loading

Type system

Input: An AST

Output: A typed AST

Task: Assigns types to the nodes of the AST.

flowchart LR
    subgraph AST
        EE1[variable]
        EE2[=]
        EE3[123]
        EE2 --> EE1
        EE2 --> EE3
    end
    FF@{shape: brace-r, label: "described by Typir"} --> F
    AST --> F[Type System]
    F --> AST2
    subgraph AST2["Typed AST"]
        FF1[variable:STRING]
        FF2[=]
        FF3[123:NUMBER]
        FF2 --> FF1
        FF2 --> FF3
    end

    style F fill:#f9f,stroke:#333,stroke-width:4px
Loading

Validator

Input: A typed AST

Output: a list of errors

Task: Checks if the AST is valid.

flowchart LR
    subgraph AST["Typed AST"]
        FF1[variable:STRING]
        FF2[=]
        FF3[123:NUMBER]
        FF2 --> FF1
        FF2 --> FF3
    end
    AST --> H[Validator]
    H --> Errors
    subgraph Errors
        I1["Variable got wrong type assigned"]
    end
    style I1 fill:#fdd,stroke:#333,stroke-width:4px
Loading