吉基

吉基是一个为 Rust 设计的极简解析生成器。

目录

• 如何使用吉基
• 为什么使用吉基
• 吉基的限制
• 示例
• 指南
• 贡献

如何使用吉基？

阅读 快速入门指南。

为什么使用吉基？

• 易于学习。 如果你之前使用过其他解析生成器（例如，Bison/yacc），你可以在 10分钟内学会吉基。
• 易于编写。 如 Bison 或 lalrpop 之类的工具强制你编写语法、语义动作和语法树类型定义。吉基让你只需编写类型定义。吉基从类型定义中推断语法和语义动作。
• 易于阅读。 吉基具有极简的语法。这使得它易于学习，也易于阅读。

吉基的限制

• 吉基仅支持 LALR(1) 语法。
• 吉基解析标记序列，而不是字符串。
  • 换句话说，你必须提供自己的词法分析器。你可以手动实现词法分析器，或者使用词法分析器生成器（例如，logos）。

示例

在本节中，我们将构建一个玩具解析器，它可以识别算术表达式。例如

• 42
• 42 + 53
• 29 + (893 * 7)

为了简单起见，这种语言没有运算符优先级。相反，你必须使用括号（例如，29 + (893 * 7)）。

让我们比较一下我们如何使用 Bison 和吉基构建解析器。

使用 Bison

假设 Bison 假设支持 Rust（而不是仅支持 C/C++）。那么你可能写成

%{
    enum Expr {
        Num(i32),
        Op {
            left: Box<Expr>,
            kind: OpKind,
            right: Box<Expr>,
        },
    }

    enum OpKind {
        Add,
        Sub,
        Cons,
        Div,
    }
}

%token <i32> NUM

// Other than NUM, the rest of the tokens
// only have one possible value each.
// So, we set their type to the unit type (`()`).
%token <()> PLUS
%token <()> MINUS
%token <()> STAR
%token <()> SLASH
%token <()> LPAREN
%token <()> RPAREN

%start expr

%%

expr
    : term
        {
            $$ = $1;
        }
    | term PLUS term
        {
            $$ = Expr::Op {
                left: Box::new($1),
                kind: OpKind::Add,
                right: Box::new($3),
            };
        }
    | term MINUS term
        {
            $$ = Expr::Op {
                left: Box::new($1),
                kind: OpKind::Sub,
                right: Box::new($3),
            };
        }
    | term STAR term
        {
            $$ = Expr::Op {
                left: Box::new($1),
                kind: OpKind::Cons,
                right: Box::new($3),
            };
        }
    | term SLASH term
        {
            $$ = Expr::Op {
                left: Box::new($1),
                kind: OpKind::Div,
                right: Box::new($3),
            };
        }
;

term
    : NUM
        {
            $$ = Expr::Num($1);
        }
    | LPAREN expr RPAREN
        {
            $$ = $2;
        }
;

请注意，你必须编写 三 件事情

1. 语法（即 expr : term ...; 和 term : NUM ...;）。
2. 语义动作（例如，$$ = Expr::Op {...};）。
3. 语法树类型定义（即，enum Expr {...}和enum OpKind {...}）。

terminal Token {
    $Num: i32
    $Plus: ()
    $Minus: ()
    $Star: ()
    $Slash: ()
    $LParen: ()
    $RParen: ()
}

start Expr

enum Expr {
    Term(Term)
    Op {
        left: Expr
        kind: OpKind
        right: Expr
    }
}

enum OpKind {
    Add(_: $Plus)
    Sub(_: $Minus)
    Cons(_: $Star)
    Div(_: $Div)
}

enum Term {
    Num($Num)
    Parenthesized(
        _: $LParen
        Expr
        _: $RParen
    )
}