.lr

用于教育目的的 LR(1) 解析器生成器和可视化工具。

---

目录

• 什么是 LR(1) 解析器？
• 为什么你要制作这个？
• 我如何在 gif 中使用 CLI？
• 我可以将其作为独立的库使用吗？
• 它是如何工作的？
  • 1) 解析语法
  • 2) 计算FIRST集合
  • 3) 计算FOLLOW集合
  • 4) 构建LR(1)自动机
  • 5) 构建ACTION和GOTO表
  • 6) 分词输入
  • 7) 解析分词
• 有任何基准测试吗？
• 我可以修改它吗？
• 你在创建此项目时使用了哪些资源？
• 它的许可方式是什么？

什么是 LR(1) 解析器？

LR(1) 解析器 是一种 自底向上解析器，用于解析 上下文无关语言 的子集。

1 表示解析器在做出解析决策时将使用单个前瞻标记。

LR(1) 解析器功能强大，因为它们可以解析广泛的上下文无关语言，包括大多数编程语言！

为什么你要制作这个？

为了学习和帮助他人学习！该项目允许你可视化 LR(1) 解析器，从构建到解析，这使理解它们的工作方式变得更容易。

我如何在 gif 中使用 CLI？

如果你想用 dotlr 来可视化解析器构建和不同语法的逐步解析，你可以使用 crate 的主可执行文件。

安装

你可以从 crates.io 安装 dotlr CLI。

cargo install dotlr

用法

将以下内容粘贴到名为 grammar.lr 的文件中

P -> E

E -> E '+' T
E -> T

T -> %id '(' E ')'
T -> %id

%id -> /[A-Za-z][A-Za-z0-9]+/

使用语法文件和输入运行 dotlr CLI

dotlr grammar.lr "foo(bar + baz)"

它将打印

+--------------------------------+
|            Grammar             |
+--------------------------------+
| P -> E                         |
| E -> E '+' T                   |
| E -> T                         |
| T -> %id '(' E ')'             |
| T -> %id                       |
|                                |
| %id -> /^[A-Za-z][A-Za-z0-9]+/ |
+--------------------------------+
+--------+-----------+-----------------+
| Symbol | First Set |   Follow Set    |
+--------+-----------+-----------------+
| T      | { %id }   | { $, '+', ')' } |
+--------+-----------+-----------------+
| E      | { %id }   | { $, '+', ')' } |
+--------+-----------+-----------------+
| P      | { %id }   | { $ }           |
+--------+-----------+-----------------+
+-------+------------------------+--------------+---------------+
| State |         Items          |  Lookaheads  |  Transitions  |
+-------+------------------------+--------------+---------------+
| 0     |  P -> . E              | { $ }        |   E   ->  1   |
|       |  E -> . E '+' T        | { $, '+' }   |   T   ->  2   |
|       |  E -> . T              | { $, '+' }   |  %id  ->  3   |
|       |  T -> . %id '(' E ')'  | { $, '+' }   |               |
|       |  T -> . %id            | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 1     |  P -> E .              | { $ }        |  '+'  ->  14  |
|       |  E -> E . '+' T        | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 2     |  E -> T .              | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 3     |  T -> %id . '(' E ')'  | { $, '+' }   |  '('  ->  4   |
|       |  T -> %id .            | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 4     |  T -> %id '(' . E ')'  | { $, '+' }   |   E   ->  5   |
|       |  E -> . E '+' T        | { ')', '+' } |  %id  ->  6   |
|       |  E -> . T              | { ')', '+' } |   T   ->  9   |
|       |  T -> . %id '(' E ')'  | { ')', '+' } |               |
|       |  T -> . %id            | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 5     |  T -> %id '(' E . ')'  | { $, '+' }   |  '+'  ->  11  |
|       |  E -> E . '+' T        | { ')', '+' } |  ')'  ->  13  |
+-------+------------------------+--------------+---------------+
| 6     |  T -> %id . '(' E ')'  | { ')', '+' } |  '('  ->  7   |
|       |  T -> %id .            | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 7     |  T -> %id '(' . E ')'  | { ')', '+' } |  %id  ->  6   |
|       |  E -> . E '+' T        | { ')', '+' } |   E   ->  8   |
|       |  E -> . T              | { ')', '+' } |   T   ->  9   |
|       |  T -> . %id '(' E ')'  | { ')', '+' } |               |
|       |  T -> . %id            | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 8     |  T -> %id '(' E . ')'  | { ')', '+' } |  ')'  ->  10  |
|       |  E -> E . '+' T        | { ')', '+' } |  '+'  ->  11  |
+-------+------------------------+--------------+---------------+
| 9     |  E -> T .              | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 10    |  T -> %id '(' E ')' .  | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 11    |  E -> E '+' . T        | { ')', '+' } |  %id  ->  6   |
|       |  T -> . %id '(' E ')'  | { ')', '+' } |   T   ->  12  |
|       |  T -> . %id            | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 12    |  E -> E '+' T .        | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 13    |  T -> %id '(' E ')' .  | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 14    |  E -> E '+' . T        | { $, '+' }   |  %id  ->  3   |
|       |  T -> . %id '(' E ')'  | { $, '+' }   |   T   ->  15  |
|       |  T -> . %id            | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 15    |  E -> E '+' T .        | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
+-------+---------------------------------------+----------------------+
|       |                Action                 |         Goto         |
| State | ------------------------------------- | -------------------- |
|       |    '+'    '('    ')'    %id     $     |    P     E     T     |
+-------+---------------------------------------+----------------------+
| 0     |     -      -      -     s3      -     |    -     1     2     |
+-------+---------------------------------------+----------------------+
| 1     |    s14     -      -      -     a1     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 2     |    r3      -      -      -     r3     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 3     |    r5     s4      -      -     r5     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 4     |     -      -      -     s6      -     |    -     5     9     |
+-------+---------------------------------------+----------------------+
| 5     |    s11     -     s13     -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 6     |    r5     s7     r5      -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 7     |     -      -      -     s6      -     |    -     8     9     |
+-------+---------------------------------------+----------------------+
| 8     |    s11     -     s10     -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 9     |    r3      -     r3      -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 10    |    r4      -     r4      -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 11    |     -      -      -     s6      -     |    -     -     12    |
+-------+---------------------------------------+----------------------+
| 12    |    r2      -     r2      -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 13    |    r4      -      -      -     r4     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 14    |     -      -      -     s3      -     |    -     -     15    |
+-------+---------------------------------------+----------------------+
| 15    |    r2      -      -      -     r2     |    -     -     -     |
+-------+---------------------------------------+----------------------+

> foo(bar + baz)

P
└─ E
   └─ T
      ├─ foo
      ├─ (
      ├─ E
      │  ├─ E
      │  │  └─ T
      │  │     └─ bar
      │  ├─ +
      │  └─ T
      │     └─ baz
      └─ )

+------+---------------+-------------------+---------------------------+----------------------------+
| Step |  State Stack  |   Symbol Stack    |      Remaining Input      |        Action Taken        |
+------+---------------+-------------------+---------------------------+----------------------------+
| 0    | 0             |                   | %id '(' %id '+' %id ')' $ | Shift 3                    |
+------+---------------+-------------------+---------------------------+----------------------------+
| 1    | 0 3           | %id               |     '(' %id '+' %id ')' $ | Shift 4                    |
+------+---------------+-------------------+---------------------------+----------------------------+
| 2    | 0 3 4         | %id '('           |         %id '+' %id ')' $ | Shift 6                    |
+------+---------------+-------------------+---------------------------+----------------------------+
| 3    | 0 3 4 6       | %id '(' %id       |             '+' %id ')' $ | Reduce4 T -> %id           |
+------+---------------+-------------------+---------------------------+----------------------------+
| 4    | 0 3 4 9       | %id '(' T         |             '+' %id ')' $ | Reduce2 E -> T             |
+------+---------------+-------------------+---------------------------+----------------------------+
| 5    | 0 3 4 5       | %id '(' E         |             '+' %id ')' $ | Shift 11                   |
+------+---------------+-------------------+---------------------------+----------------------------+
| 6    | 0 3 4 5 11    | %id '(' E '+'     |                 %id ')' $ | Shift 6                    |
+------+---------------+-------------------+---------------------------+----------------------------+
| 7    | 0 3 4 5 11 6  | %id '(' E '+' %id |                     ')' $ | Reduce4 T -> %id           |
+------+---------------+-------------------+---------------------------+----------------------------+
| 8    | 0 3 4 5 11 12 | %id '(' E '+' T   |                     ')' $ | Reduce1 E -> E '+' T       |
+------+---------------+-------------------+---------------------------+----------------------------+
| 9    | 0 3 4 5       | %id '(' E         |                     ')' $ | Shift 13                   |
+------+---------------+-------------------+---------------------------+----------------------------+
| 10   | 0 3 4 5 13    | %id '(' E ')'     |                         $ | Reduce3 T -> %id '(' E ')' |
+------+---------------+-------------------+---------------------------+----------------------------+
| 11   | 0 2           | T                 |                         $ | Reduce2 E -> T             |
+------+---------------+-------------------+---------------------------+----------------------------+
| 12   | 0 1           | E                 |                         $ | Accept0 P -> E             |
+------+---------------+-------------------+---------------------------+----------------------------+

如果你省略了输入，你还可以进入 REPL 模式

dotlr grammar.lr

我可以将其作为独立的库使用吗？

是的，你可以从 crates.io 依赖 dotlr crate。

设置

将以下内容粘贴到你的 dependencies 部分的 Cargo.toml

dotlr = { version = "0.1", default-features = false }

示例

以下是一个基本示例，展示了 dotlr crate 的主要操作

use dotlr::{
  Grammar,
  Parser,
  ParserError,
};

const GRAMMAR: &str = r#"

P -> E

E -> E '+' T
E -> T

T -> %id '(' E ')'
T -> %id

%id -> /[A-Za-z][A-Za-z0-9]+/

"#;

const INPUT: &str = r#"

foo(bar + baz)

"#;

fn main() {
  let grammar = match Grammar::parse(GRAMMAR.trim()) {
    Ok(grammar) => grammar,
    Err(error) => {
      eprintln!("grammar error: {}", error);
      return;
    }
  };
  let parser = match Parser::new(grammar) {
    Ok(parser) => parser,
    Err(error) => {
      eprintln!("parser error: {}", error);
      if let ParserError::Conflict { parser, .. } = error {
        parser.dump();
      }
      return;
    }
  };
  let tokens = match parser.tokenize(INPUT.trim()) {
    Ok(tokens) => tokens,
    Err(error) => {
      eprintln!("tokenization error: {}", error);
      return;
    }
  };
  let (parse_trace, parse_tree) = match parser.trace(tokens) {
    Ok(result) => result,
    Err(error) => {
      eprintln!("tokenization error: {}", error);
      return;
    }
  };

  parser.dump();
  println!();
  parse_tree.dump();
  println!();
  parse_trace.dump(parser.grammar());
}

它是如何工作的？

让我们逐步构建以下语法的解析器

E -> E '+' F
E -> F

F -> F '*' T
F -> T

T -> %b

%b -> /[0-1]/

然后逐步解释以下输入的解析步骤

1 + 0 * 1

开始之前的一些注意事项

• $代表输入标记的结束
• 在dotlr中，不支持可以扩展为空字符串的符号，这简化了下面的解释（即没有像S ->这样的规则）

1) 解析语法

首先，我们需要将语法字符串解析为一个可以处理的语法对象。

语法对象将包含

• 符号（HashSet）

  • 语法中的符号集合
    （例如，{ E, F, T }）

• 起始符号（Symbol）

  • 要解析的符号
    （例如，E）

• 常量标记（HashSet）

  • 语法中的常量标记集合
    （例如，{ '+', '*' }）

• 正则表达式（HashMap）

  • 正则表达式标记到相应编译后正则表达式的映射
    （例如，{ b -> /[0-1]/ }）

• 规则（Vec）

  • 语法中的规则列表
    （例如，[ E -> E '+' F, E -> F, ... ]）

这通过一个简单的手写解析器在src/grammar.rs中完成。

2) 计算FIRST集合

现在，我们需要根据以下约束为语法中的每个符号计算一个标记集合

• 对于每个token ∈ FIRST(Symbol)，以下条件至少有一个必须成立
  • 符号->标记...∈ 语法.规则
  • Symbol -> 另一个符号 ... ∈ 语法.rules 并且
    标记 ∈FIRST(另一个符号)

至于实现，这里是一个类似Python的伪代码，用于计算FIRST集合的算法

# Start with FIRST(all_symbols) = {}
first_sets = {}

# Iterate until no more changes
while first_sets.has_changed():
    # Iterate over the rules of the grammar
    for rule in grammar:
        # If pattern of the rule starts with a token
        if rule.pattern[0].is_token:
            # S -> '+' ... <==> S can start with '+'
            # --------------------------------------
            # Add the matching token to the FIRST set of the symbol of the rule
            first_sets[rule.symbol].add(rule.pattern[0])

        # If pattern of the rule starts with a symbol
        elif rule.pattern[0].is_symbol:
            # S -> E ... <==> S can start with anything E can start with
            # ----------------------------------------------------------
            # Add every token in the FIRST set of the matching symbol
            # to the FIRST set of the symbol of the rule
            first_sets[rule.symbol].extend(first_sets[rule.pattern[0]])

这通过src/tables.rs来完成。

示例语法的FIRST集合

+--------+-----------+
| Symbol | First Set |
+--------+-----------+
| T      | { %b }    |
+--------+-----------+
| F      | { %b }    |
+--------+-----------+
| E      | { %b }    |
+--------+-----------+

3) 计算FOLLOW集合

接下来，我们需要根据以下约束为语法中的每个符号计算另一个标记集合

• 对于每个token ∈ FOLLOW(Symbol)，以下条件至少有一个必须成立

  • Symbol == 语法.start_symbol 并且
    标记== $

  • 任何内容-> ...符号标记...∈ 语法.规则

  • Anything -> ... 符号 另一个符号 ... ∈ 语法.rules 和
    标记 ∈FIRST(另一个符号)

  • 符号 -> ... 另一个符号 ∈ 语法.rules 和
    标记 ∈FOLLOW(另一个符号)

关于实现，下面是计算FOLLOW集的算法的类似Python的伪代码

# Start with just FOLLOW(grammar.start_symbol) = { $ }
follow_sets = { grammar.start_symbol: { $ } }

# Iterate until no more changes
while follow_sets.has_changed():
    # Iterate over the rules of the grammar
    for rule in grammar:
        # Iterate over the 2-windows of the pattern of the rule
        for i in range(len(rule.pattern) - 1):
            # If the first atomic pattern is a symbol
            if rule.pattern[i].is_symbol:
                # And if the second atomic pattern is a token
                if rule.pattern[i + 1].is_token:
                    # S -> ... E '+' ... <==> E can follow '+'
                    # ----------------------------------------
                    # Add the matching token to the FOLLOW set of the matching symbol
                    follow_sets[rule.pattern[i]].add(rule.pattern[i + 1])

                # Or if the second atomic pattern is a symbol
                elif rule.pattern[i + 1].is_symbol:
                    # S -> ... E F ... <==> E can follow anything F can start with
                    # ------------------------------------------------------------
                    # Add every token in the FIRST set of the second symbol
                    # to the FOLLOW set of the first symbol
                    follow_sets[rule.pattern[i]].extend(first_sets[rule.pattern[i + 1]])

        # If pattern of ends with a symbol
        if rule.pattern[-1].is_symbol:
            # S -> ... E <==> S can follow anything E can follow
            # --------------------------------------------------
            # Add every token in the FOLLOW set of the matching symbol
            # to the FOLLOW set of the symbol of the rule
            follow_sets[rule.symbol].extend(follow_sets[rule.patten[-1]])

这通过src/tables.rs来完成。

示例语法的FOLLOW集

+--------+-----------------+
| Symbol |   Follow Set    |
+--------+-----------------+
| T      | { $, '+', '*' } |
+--------+-----------------+
| F      | { $, '+', '*' } |
+--------+-----------------+
| E      | { $, '+' }      |
+--------+-----------------+

4) 构建LR(1)自动机

现在是时候为语法构建LR(1)自动机了。

这里是不同语法的LR(1)自动机的示意图，以便了解LR(1)自动机是什么

自动机对象只是一个状态列表。

每个状态有

• id (usize)

  • 状态的标识符
    (例如，0，1)

• items (Vec)

  • 状态LR(1)项的列表
    (例如，E -> E . '+' F | { $, '+' })

• transitions (HashMap<AtomicPattern, usize>)

  • 将导致转到新状态的原子模式的映射
    (例如，{ '+' -> 7 }，{ %b -> 4, T -> 6 })

# Setup the kernel of the first state
first_state = next_empty_state()
for rule in grammar.rules:
    if rule.symbol == grammar.start_symbol:
        first_state.add_item(Item(rule, dot=0, lookahead={$}))

# Initialize construction state
states_to_process = [first_state]
processed_states = []

# Iterate until there aren't any more states to process.
while len(states_to_process) > 0:
    # Get the state to process
    state_to_process = states_to_process.pop()

    # Computing closure of the state to process
    # Loop until no more items are added
    while True:
        new_items = []
        # Iterate current items to obtain new items
        for item in state_to_process.items:
            # If dot is not at the end of the pattern
            if item.dot != len(item.rule.pattern):
                # And if there is a symbol after dot
                if item.rule.pattern[item.dot].is_symbol:
                    # Compute the lookahead for the new item
                    if item.dot == len(item.rule.pattern) - 1:
                        # S -> ... . E <==> Tokens in the current lookahead can follow E
                        # --------------------------------------------------------------
                        lookahead = item.lookahead
                    elif item.rule.pattern[item.dot + 1].is_token:
                        # S -> ... . E '+' <==> '+' can follow E
                        # --------------------------------------
                        lookahead = {item.rule.pattern[item.dot + 1]}
                    elif item.rule.pattern[item.dot + 1].is_symbol:
                        # S -> ... . E F <==> Tokens in FIRST(F) can follow E
                        # ---------------------------------------------------
                        lookahead = first_sets[item.rule.pattern[item.dot + 1]]

                    # Iterate over the rules of the grammar
                    for rule in grammar.rules:
                        # If the rule is for the symbol after dot
                        if rule.symbol == item.rule.pattern[item.dot]:
                            # Create a new item from the rule, with dot at the beginning
                            new_item = Item(rule, dot=0, lookahead=lookahead)
                            # If the item is not already in items of the state
                            if new_item not in state_to_process.items:
                                # Add it the set of new items
                                new_items.push(new_item)

        # Process new items
        for new_item in new_items:
            # If a similar item with the same rule and the same dot but a different lookahead exists
            if state_to_process.has_same_base_item(new_item):
                # Merge lookaheads
                state_to_process.merge_base_items(new_item)

            # Otherwise
            else:
                # Add the new item directly
                state_to_process.items.add(new_item)

        # If state hasn't changed, break the loop
        if not state_to_process.items.has_changed():
            break

    # Merge the states to process with an already existing state with the same closure.
    replaced = False
    for existing_state_with_same_items in processed_states:
        if existing_state_with_same_items.items == state_to_process.items:
            replaced = True
            for state in processed_states:
                # Replace transitions from existing states to point to the correct state.
                state.transitions.replace_value(state_to_process, existing_state_with_same_items)
            break
    if replaced:
        # If it's merged with an existing state, there is nothing else to do
        continue

    # Compute transitions of from the state to process.
    for item in state_to_process.items:
        # If dot is not at the end
        if item.dot != len(item.rule.pattern):
            # S -> ... . E ... <==> Seeing E would cause a transition to another state
            # S -> ... . '+' ... <==> Seeing '+' would cause a transition to another state
            # ----------------------------------------------------------------------------
            atomic_pattern_after_dot = item.rule.pattern[item.dot]

            # If state to transition is not created yet, create an empty state for it.
            if atomic_pattern_after_dot is not in transitions:
                # Create an empty state to transition to
                state_to_process.transitions[atomic_pattern_after_dot] = next_empty_state()

            # Setup the kernel of the state to transition
            state_to_transition = state_to_process.transitions[atomic_pattern_after_dot]
            state_to_transition.items.push(item.shift_dot_to_right())

    # Add state to process to processed states, as we're done with it
    processed_states.push(state_to_process)

+-------+------------------+-----------------+--------------+
| State |      Items       |   Lookaheads    | Transitions  |
+-------+------------------+-----------------+--------------+
| 0     |  E -> . E '+' F  | { $, '+' }      |  E   ->  1   |
|       |  E -> . F        | { $, '+' }      |  F   ->  2   |
|       |  F -> . F '*' T  | { $, '+', '*' } |  T   ->  3   |
|       |  F -> . T        | { $, '+', '*' } |  %b  ->  4   |
|       |  T -> . %b       | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 1     |  E -> E . '+' F  | { $, '+' }      |  '+'  ->  7  |
+-------+------------------+-----------------+--------------+
| 2     |  E -> F .        | { $, '+' }      |  '*'  ->  5  |
|       |  F -> F . '*' T  | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 3     |  F -> T .        | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 4     |  T -> %b .       | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 5     |  F -> F '*' . T  | { $, '+', '*' } |  %b  ->  4   |
|       |  T -> . %b       | { $, '+', '*' } |  T   ->  6   |
+-------+------------------+-----------------+--------------+
| 6     |  F -> F '*' T .  | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 7     |  E -> E '+' . F  | { $, '+' }      |  T   ->  3   |
|       |  F -> . F '*' T  | { $, '+', '*' } |  %b  ->  4   |
|       |  F -> . T        | { $, '+', '*' } |  F   ->  8   |
|       |  T -> . %b       | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 8     |  E -> E '+' F .  | { $, '+' }      |  '*'  ->  5  |
|       |  F -> F . '*' T  | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+