/parse-tree-java

A simple parse tree generator for any user-defined LR(1) programming language

Primary LanguageJavaMIT LicenseMIT

LR(1) Parse Tree Generator

JDK-15 version-1.0.3 license-MIT

This project is heavily inspired by LYRON, a universal compiler framework.

Usage

Modify config.yml if necessary, place your test file, e.g., test.txt, and then execute

cat test.txt | java -jar parse-tree.jar

You can also execute the jar file directly and input your test code in the console.

Examples

Lexical Analysis

NFA to DFA

Take the regular expression (a|b)*abb for example.

  1. Create an NFA.

    1-NFA

  2. Convert the NFA to a DFA.

    1-DFA

Merge multiple NFAs

Take the regular expressions a*b+, a, abb for example.

  1. Create three NFAs and combine them into one large NFA.

    2-NFA

  2. Convert the DFA to DFA.

    2-DFA

Creating Parse Tree

  1. Get the predefined grammar.

    1. S'->S
2. S->CβBA
3. A->Aαβ
4. A->αβ
5. B->C
6. B->Dβ
7. C->α
8. D->α

  2. Write a config file (in YAML format).

    nonterminalSymbols:
  # ? name
  ? A
  ? B
  ? C
  ? D
  ? S
terminalSymbols:
  # name: regex
  α: a
  β: b
ignoredSymbols:
startSymbol: S
productions:
  # - left part -> right part
  - S -> C β B A
  - A -> A α β
  - A -> α β
  - B -> C
  - B -> D β
  - C -> α
  - D -> α

  3. Generate the parse table.

    ACTION GOTO
    α β $ S A B C D
    0 s1 3 2
    1 r7
    2 s4
    3 acc
    4 s5 6 7 8
    5 r7 r8
    6 s10 9
    7 r5
    8 s11
    9 s12 r2
    10 s13
    11 r6
    12 s14
    13 r4 r4
    14 r3 r3

  4. Generate the parse tree.

    The input string is abababab.

    Parse Tree