sakria9/compiler-course-helper

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

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());
}