此外，骨架定义了一个具有代表标记号的常量的 Lexer 结构，如下所示

// AUTO-GENERATED
impl Lexer {
    /* Token kinds.  */
    // Token "end of file", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const YYEOF: i32 = 0;
    // Token error, to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const YYerror: i32 = 256;
    // Token "invalid token", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const YYUNDEF: i32 = 257;
    // Token "+", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const tPLUS: i32 = 258;
    // Token "-", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const tMINUS: i32 = 259;
    // Token "*", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const tMUL: i32 = 260;
    // Token "/", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const tDIV: i32 = 261;
    // Token "(", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const tLPAREN: i32 = 262;
    // Token ")", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const tRPAREN: i32 = 263;
    // Token "number", to be returned by the scanner.
    #[allow(non_upper_case_globals, dead_code)]
    pub const tNUM: i32 = 264;
}

因此，我们可以定义我们的词法分析逻辑

use crate::{Loc, Value};

/// A token that is emitted by a lexer and consumed by a parser
#[derive(Clone)]
pub struct Token {
    // Required field, used by a skeleton
    pub token_type: i32,

    // Optional field, used by our custom parser
    pub token_value: i32,

    // Required field, used by a skeleton
    pub loc: Loc,
}

/// `Debug` implementation
impl std::fmt::Debug for Token {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_> /*' fix quotes */) -> std::fmt::Result {
        f.write_str(&format!(
            "[{}, {:?}, {}...{}]",
            token_name(self.token_type()),
            self.token_value,
            self.loc.begin,
            self.loc.end
        ))
    }
}

impl Token {
    /// Used by a parser to "unwrap" `Value::Token` variant into a plain Token value
    pub(crate) fn from(value: Value) -> Token {
        match value {
            Value::Token(v) => v,
            other => panic!("expected Token, got {:?}", other),
        }
    }
}


#[allow(non_upper_case_globals)]
impl Lexer {
    pub fn new(src: &str) -> Self {
        let mut tokens = vec![];

        for (idx, c) in src.chars().enumerate() {
            let (token_type, token_value) = match c {
                '0' => (Self::tNUM, 0),
                '1' => (Self::tNUM, 1),
                '2' => (Self::tNUM, 2),
                '3' => (Self::tNUM, 3),
                '4' => (Self::tNUM, 4),
                '5' => (Self::tNUM, 5),
                '6' => (Self::tNUM, 6),
                '7' => (Self::tNUM, 7),
                '8' => (Self::tNUM, 8),
                '9' => (Self::tNUM, 9),
                '+' => (Self::tPLUS, -1),
                '-' => (Self::tMINUS, -1),
                '*' => (Self::tMUL, -1),
                '/' => (Self::tDIV, -1),
                '(' => (Self::tLPAREN, -1),
                ')' => (Self::tRPAREN, -1),
                ' ' => continue,
                _ => panic!("unknown char {}", c),
            };
            let token = Token {
                token_type,
                token_value,
                loc: Loc {
                    begin: idx,
                    end: idx + 1,
                },
            };
            tokens.push(token)
        }
        tokens.push(Token {
            token_type: Self::YYEOF,
            token_value: 0,
            loc: Loc {
                begin: src.len(),
                end: src.len() + 1,
            },
        });

        Self { tokens }
    }

    pub(crate) fn yylex(&mut self) -> Token {
        self.tokens.remove(0)
    }
}

这个词法分析器不是缓冲的，并且在出现语法错误时执行了不必要的操作，但让我们使用它，因为它更容易理解。

现在我们来定义 Parser <-> Lexer 组合

impl Parser {
    pub fn new(lexer: Lexer) -> Self {
        Self {
            yy_error_verbose: true,
            yynerrs: 0,
            yyerrstatus_: 0,
            yylexer: lexer,
        }
    }

    fn next_token(&mut self) -> Token {
        self.yylexer.yylex()
    }

    fn report_syntax_error(&self, ctx: &Context) {
        eprintln!("syntax error: {:#?}", ctx)
    }
}

Parser 封装了 Lexer 并在骨架调用的 next_token 方法中调用它。

是时候定义规则了

%type <Number> expr number program

%%

 program: expr
            {
                self.result = Some($<Number>1);
                $$ = Value::None;
            }
        | error
            {
                self.result = None;
                $$ = Value::None;
            }

    expr: number
            {
                $$ = $1;
            }
        | tLPAREN expr tRPAREN
            {
                $$ = $2;
            }
        | expr tPLUS expr
            {
                $$ = Value::Number($<Number>1 + $<Number>3);
            }
        | expr tMINUS expr
            {
                $$ = Value::Number($<Number>1 - $<Number>3);
            }
        | expr tMUL expr
            {
                $$ = Value::Number($<Number>1 * $<Number>3);
            }
        | expr tDIV expr
            {
                $$ = Value::Number($<Number>1 / $<Number>3);
            }

  number: tNUM
            {
                $$ = Value::Number($<Token>1.token_value());
            }

%%

正如你所见，我们的语法有以下规则

program: expr
       | error

   expr: number
       | '(' number ')'
       | number '+' number
       | number '-' number
       | number '*' number
       | number '/' number

 number: [0-9]

$$ 是一个返回值，其类型为 Value。你可以使用 $1、$2 等，以获取未展开的项 1、2 等，即它们也有类型 Value。要展开它，你可以使用 $<Variant>1，但这时你必须有以下方法

impl Variant {
    fn from(value: Value) -> Self {
        match value {
            Value::Variant(out) => out,
            other => panic!("wrong type, expected Variant, got {:?}", other),
        }
    }
}

在我们的情况下，我们只想有一个这样的变体 - Number

use crate::Value;

#[allow(non_snake_case)]
pub(crate) mod Number {
    use super::Value;

    pub(crate) fn from(value: Value) -> i32 {
        match value {
            Value::Number(out) => out,
            other => panic!("wrong type, expected Number, got {:?}", other),
        }
    }
}

是的，这是一个模块，但这绝对没问题。这并不重要 Variant 是什么，关键是调用 Variant::from(Value)。

此外，你可能注意到，顶层规则 program 中有一个 self.result = ... 赋值。需要它的原因是无法获取堆栈上留下的值，因为堆栈不是解析器状态的一部分。

这就是为什么我们还需要声明它的原因

%code parser_fields {
    result: Option<i32>,
}

// And Parser's constructor must return
fn new(lexer: Lexer) -> Self {
    Self {
        result: None,
        // ...
    }
}

现在我们需要一个 build.rs 脚本

extern crate rust_bison_skeleton;
use rust_bison_skeleton::{process_bison_file, BisonErr};
use std::path::Path;

fn main() {
    match process_bison_file(&Path::new("src/parser.y")) {
        Ok(_) => {}
        Err(BisonErr { message, .. }) => {
            eprintln!("Bison error:\n{}\nexiting with 1", message);
            std::process::exit(1);
        }
    }
}

因此，在运行 cargo build 之后，我们应该得到包含所有自动生成和手动编写的代码合并到一个文件中的 src/parser.rs。

你可以在 tests/src/calc.y 中找到一个完整的示例。

错误恢复

这个骨架完全匹配其他内置 Bison 骨架的行为

• 如果你想在推导过程中返回错误，你可以
  • 执行以下操作 return Ok(Self::YYERROR);
  • 或者直接 Err(())?
• 如果您想完全终止执行，您可以
  • return Ok(Self::YYACCEPT); 以类似成功的状态码终止
  • return Ok(Self::YYABORT); 以类似错误的状态码终止

一旦返回了错误，特殊的 error 规则可以捕获并“吞噬”它

 numbers: number
          {
              $$ = Value::NumbersList(vec![ $Number<1> ]);
          }
        | numbers number
          {
              $$ = Value::NumbersList( $<NumbersList>1.append($<Number>2) );
          }
        | error number
          {
              // ignore $1 and process only $<Number>2
              $$ = Value::NumbersList(vec![ $Number<2> ]);
          }


  number: tNUM         { $$ = $1 }
        | tINVALID_NUM { return Ok(Self::YYERROR); }

有关错误的详细信息将自动传递到 Parser::report_syntax_error。它接受的 Context 有 token() 和 location() 方法，因此该方法的实现可能如下所示

fn report_syntax_error(&mut self, ctx: &Context) {
    let token_id: usize = ctx.token().code().try_into().unwrap();
    let token_name: &'static str = Lexer::TOKEN_NAMES[id];
    let error_loc: &Loc = ctx.location();

    eprintln!("Unexpected token {} at {:?}", token_name, loc);
}

通用解析器

为了使 Parser 成为泛型，您需要配置以下指令

%define api.parser.generic {<T1, T2>}

此代码添加到 struct Parser 和 impl Parser

struct Parser<T1, T2> {
    // ...
}

impl<T1, T2> Parser<T1, T2> {
    // ...
}

如果您想指定生存期，请确保使用注释修正引号

%define api.parser.generic {<'a /* 'fix quotes */, T>}

性能

您可以在 perf 示例中找到它，该示例运行 Parser 千次并创建火焰图。

$ TIMES=20000 cargo run --bin perf --release