A tool & library to help you with the compiler course.

Overview

Compiler Course Helper

Support:

  • eliminate left recursion (require grammar with no cycles or ϵ-production)
  • calculate nullable, first sets, follow, sets
  • generate LL(1) parsing table
  • generate LR(0) automata, parsing table
  • generate LR(1) automata, parsing table
  • generate LALR automata, parsing table
  • output format: plaintext JSON LaTeX
  • WebAssembly

Build

$ cargo run
$ cargo build --release
$ wasm-pack build --help

CLI

Usage

$ ./compiler-course-helper
Usage: compiler-course-helper [action]... output... [option] [grammar file]
action:
  elf: Eliminate left recursion
output:
  prod: Productions
  nff: Nullable first and follow
  ll1: LL(1) parsing table
  lr0fsm: LR(0) Automata
  lr1fsm: LR(1) Automata
  lalrfsm: LALR Automata
  lr0table: LR(0) parsing table
  lr1table: LR(1) parsing table
  lalrtable: LALR parsing table
option:
  -h: Print this help
  -l: Print in LaTeX format
  -j: Print in JSON format

Example

$ ./compiler-course-helper elf prod ll1 -l
E -> E a | a (this is input)
\[\begin{array}{cll}\\
E & \rightarrow & \text{a} \  E'\\
E' & \rightarrow & \text{a} \  E' \mid \epsilon\\
\end{array}\]
\[\begin{array}{c|l|l}
 & \text{\$} & \text{a}\\\hline
E &  & E \rightarrow \text{a} \  E'\\
E' & E' \rightarrow \epsilon & E' \rightarrow \text{a} \  E'
\end{array}\]
$ ./compiler-course-helper lr0table ../../testcase/expr.txt (read grammar from file)
   |             $ |             + |             * |  ( |             ) | id | E |  T |  F
 0 |               |               |               | s1 |               | s5 | 2 |  4 |  3
 1 |               |               |               | s1 |               | s5 | 6 |  4 |  3
 2 |           acc |            s7 |               |    |               |    |   |    |
 3 |     r(T -> F) |     r(T -> F) |     r(T -> F) |    |     r(T -> F) |    |   |    |
 4 |     r(E -> T) |     r(E -> T) |            s8 |    |     r(E -> T) |    |   |    |
 5 |    r(F -> id) |    r(F -> id) |    r(F -> id) |    |    r(F -> id) |    |   |    |
 6 |               |            s7 |               |    |            s9 |    |   |    |
 7 |               |               |               | s1 |               | s5 |   | 10 |  3
 8 |               |               |               | s1 |               | s5 |   |    | 11
 9 | r(F -> ( E )) | r(F -> ( E )) | r(F -> ( E )) |    | r(F -> ( E )) |    |   |    |
10 | r(E -> E + T) | r(E -> E + T) |            s8 |    | r(E -> E + T) |    |   |    |
11 | r(T -> T * F) | r(T -> T * F) | r(T -> T * F) |    | r(T -> T * F) |    |   |    |

WebAssembly Library

#[wasm_bindgen]
pub fn wasm_grammar_to_output(json: &str) -> String {
    let args: WasmArgs = serde_json::from_str(json).unwrap();
    let result = grammar_to_output(&args.grammar, &args.actions, &args.outputs);
    serde_json::to_string(&result).unwrap()
}

Example argument:

{
    "grammar": "E -> E + a | a",
    "actions": ["EliminateLeftRecursion"],
    "outputs": [
        {"Production": "Plain"},
        {"LL1ParsingTable": "LaTeX"},
        {"LRParsingTable": ["LR0", "JSON"]}
    ]
}

Example outputs:

{
    "Ok": [
        {
            "Ok": " E -> a E'\nE' -> + a E'\n    | ϵ"
        },
        {
            "Ok": "\\[\\begin{array}{c|l|l|l}\n & \\text{\\$} & \\text{+} & \\text{a}\\\\\\hline\nE &  &  & E \\rightarrow \\text{a} \\  E'\\\\\nE' & E' \\rightarrow \\epsilon & E' \\rightarrow \\text{+} \\  \\text{a} \\  E' & \n\\end{array}\\]"
        },
        {
            "Ok": "{\"t\":\"LR0\",\"terminals\":[\"$\",\"+\",\"a\"],\"non_terminals\":[\"E\",\"E'\"],\"action\":[[[],[],[{\"Shift\":2}]],[[\"Accept\"],[],[]],[[{\"Reduce\":[\"E'\",[\"ϵ\"]]}],[{\"Shift\":3}],[]],[[],[],[{\"Shift\":5}]],[[{\"Reduce\":[\"E\",[\"a\",\"E'\"]]}],[],[]],[[{\"Reduce\":[\"E'\",[\"ϵ\"]]}],[{\"Shift\":3}],[]],[[{\"Reduce\":[\"E'\",[\"+\",\"a\",\"E'\"]]}],[],[]]],\"goto\":[[1,null],[null,null],[null,4],[null,null],[null,null],[null,6],[null,null]]}"
        }
    ]
}

Rust Library

use compiler_course_helper::{Grammar, LRFSMType};

fn main() {
    let mut g = Grammar::parse(
        "
    E -> E + T | T
    T -> T * F | F
    F -> ( E ) | id",
    )
    .unwrap();
    
    g.eliminate_left_recursion();

    println!("{}", g.to_production_output_vec().to_plaintext());
    println!("{}", g.to_production_output_vec().to_latex());

    println!("{}", g.to_non_terminal_output_vec().to_plaintext());
    println!("{}", g.to_non_terminal_output_vec().to_latex());

    println!("{}", g.generate_ll1_parsing_table().to_latex());
    println!("{}", g.generate_ll1_parsing_table().to_plaintext());

    let fsm = g.to_lr_fsm(LRFSMType::LR0).unwrap();
    println!("{}", fsm.to_plaintext());
    println!("{}", fsm.to_latex());

    let table = fsm.to_parsing_table();
    println!("{}", table.to_plaintext());
    println!("{}", table.to_latex());
}
You might also like...
A console viewer for trees – pet project to help me learn Rust.

treeviewer This is a pet project to help me learn Rust. But maybe it’ll end up being of actual use for someone? The idea is to write a program that, g

proc-macro to help with using surrealdb's custom functions

SurrealDB Functions This is a proc-macro crate that given a path to a .surql file or a folder of .surql files, will parse DEFINE FUNCTION fn::s inside

Take your first step in writing a compiler. Implemented in Rust.

first-step-rust Take your first step in writing a compiler, using Rust. Building from Source Make sure the Rust toolchain is installed on your compute

Bril: A Compiler Intermediate Representation for Learning

Bril: A Compiler Intermediate Representation for Learning Bril (the Big Red Intermediate Language) is a compiler IR made for teaching CS 6120, a grad

The first cesil transpiler/compiler in 50 years!
The first cesil transpiler/compiler in 50 years!

CesilC CESIL, or Computer Education in Schools Instruction Language, is a programming language designed to introduce pupils in British secondary schoo

ArbOS operating system, to run at Layer 2 on Arbitrum chains. Also a compiler for Mini, the language in which ArbOS is written.

ArbOS and Mini compiler ArbOS is the "operating system" that runs at Layer 2 on an Arbitrum chain, to manage the chain's operation, maintain security,

The Rust Compiler Collection is a collection of compilers for various languages, written with The Rust Programming Language.

rcc The Rust Compiler Collection is a collection of compilers for various languages, written with The Rust Programming Language. Compilers Language Co

A rust version of "the super tiny compiler"

The (Rust) super tiny compiler This project is a rust version of the super tiny compiler (the original one (JS) was created by Jamie Kyle). The output

Rust lib for fetching official protoc (Protocol Buffer compiler) releases

protoc-fetcher Rust library for fetching official Protocol Buffer compiler (protoc) releases, pegged to a specific version. protoc-fetcher downloads a

Owner
水夕
水夕
P523 is a classic compiler course taught by R. Kent Dybvig.

P523 is a classic compiler course taught by R. Kent Dybvig. This repo implements the course using Rust, provides a framework to help you master P523.

Sirius Demon 44 Dec 26, 2022
This is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust to everyone.

Comprehensive Rust ?? This repository has the source code for Comprehensive Rust ?? , a four day Rust course developed by the Android team. The course

Google 5.2k Jan 3, 2023
rust database for you to use and help me make!

Welcome To Rust Database! What is this? this is a database for you to git clone and use in your project! Why should i use it? It is fast and it takes

Carghai74 2 Dec 4, 2022
The best Intermediate Rust course out there!

Ultimate Rust 2: Intermediate Concepts This is the companion repository for the Ultimate Rust 2: Intermediate Concepts (the followup to the popular Ul

Nathan Stocks 155 Jan 4, 2023
Free Rust 🦀 course in English 🇬🇧

Learn Rust ?? Free Rust ?? course in English ???? This course was inspired by Dcode Before starting to learn a programming language, you need to under

Skwal 10 Jul 5, 2022
Rust Crash Course, by BPB Publications

Rust Crash Course Grasp the fundamentals of programming in Rust and put your knowledge to use. This is the repository for Rust Crash Course ,published

BPB Online 9 Nov 26, 2022
Course Material for Ardan Labs - Ultimate Rust: Foundations

Ultimate Rust 1: Foundations Presented by Ardan Labs, Ultima Rust: Foundations gives you a "zero to hero" class to get you started with Rust. You'll l

Herbert 9 Mar 8, 2023
A tool that helps you to turn in one command a Rust crate into a Haskell Cabal library!

cabal-pack A tool that helps you to turn in one command a Rust crate into a Haskell Cabal library! To generate bindings, you need to annotate the Rust

Yvan Sraka 18 Dec 31, 2022
A webapp that reads your articles to you while you're on the subway

ReadToMyShoe Video Demo A website that reads articles to you, even when you're offline. Still in early development. This is a full-stack Rust webapp,

Michael Rosenberg 20 Dec 10, 2022
A tray application for Windows that gives you push notifications and instant downloads of new posts, messages and stories posted by models you subscribe to on Onlyfans.

OF-notifier A tray application for Windows that gives you push notifications and instant downloads of new posts, messages and stories posted by models

Gentlemen Mercenary 10 Dec 20, 2022