# 一个完整的例子

下面我们简单讲解一下[一个解析四则运算表达式的parser](https://github.com/chyyuu/compiler_lab/tree/master/rust/decaf-related/calc)，我们会使用除了`#[use_unsafe]`之外的所有选项。

```rust
struct Parser; // 用户希望成为parser的struct

#[lalr1(Expr)]
#[verbose("verbose.txt")]
#[log_token]
#[log_reduce]
#[expand]
#[show_fsm("fsm.dot")]
#[show_dfa("dfa.dot")]
#[lex(r#"
# 描述终结符的优先级和结合性，越靠后优先级越高；结合性分为left，right和no_assoc
priority = [
  { assoc = 'left', terms = ['Add', 'Sub'] },
  { assoc = 'left', terms = ['Mul', 'Div', 'Mod'] },
  { assoc = 'no_assoc', terms = ['UMinus'] },
  { assoc = 'no_assoc', terms = ['RPar'] },
]

# 描述识别出终结符的正则表达式
[lexical]
'\(' = 'LPar'
'\)' = 'RPar'
'\+' = 'Add'
'-' = 'Sub'
'\*' = 'Mul'
'/' = 'Div'
'%' = 'Mod'
'\d+' = 'IntLit'
'\s+' = '_Eps'
"#)]
impl Parser {
  // 为了简单起见，这里都没有实现错误处理
  // 任何一个非终结符的类型必须在整个parser中是统一的，例如这里的Expr是i32类型
  // 任何一个终结符必须具有Token类型
  // 函数的名字其实是可以随便取的，最终的代码中并不会被保留，不过为了可读性还是最好符合本条规则的含义
  #[rule(Expr -> Expr Add Expr)]
  fn expr_add(l: i32, _op: Token, r: i32) -> i32 { l + r }
  #[rule(Expr -> Expr Sub Expr)]
  fn expr_sub(l: i32, _op: Token, r: i32) -> i32 { l - r }
  #[rule(Expr -> Expr Mul Expr)]
  fn expr_mul(l: i32, _op: Token, r: i32) -> i32 { l * r }
  #[rule(Expr -> Expr Div Expr)]
  fn expr_div(l: i32, _op: Token, r: i32) -> i32 { l / r }
  #[rule(Expr -> Expr Mod Expr)]
  fn expr_mod(l: i32, _op: Token, r: i32) -> i32 { l % r }
  #[rule(Expr -> Sub Expr)]
  #[prec(UMinus)] // 本条产生式与UMinus相同，比二元运算符都高
  fn expr_neg(_op: Token, r: i32) -> i32 { -r }
  #[rule(Expr -> LPar Expr RPar)]
  fn expr_paren(_l: Token, i: i32, _r: Token) -> i32 { i }
  #[rule(Expr -> IntLit)]
  fn expr_int(i: Token) -> i32 { std::str::from_utf8(i.piece).unwrap().parse().unwrap() }
}
```

利用`#[expand]`，得到过程宏输出的代码如下(为了美观，代码经过了格式化)：

```rust
// 两个宏用来集中管理safe和unsafe模式下的下标访问和不可达
// 如果使用了use_unsafe的话，它们分别会调用get_unchecked和unreachable_unchecked
macro_rules! index { ($arr: expr, $idx: expr) => { $arr[$idx as usize] }; }
macro_rules! impossible { () => { unreachable!() }; }

// 非终结符的编号
// 终结符和非终结符都有编号，并且保证终结符的编号都小于非终结符的编号
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum TokenKind { _Eps = 2, _Eof, _Err, Add, Sub, Mul, Div, Mod, UMinus, RPar, LPar, IntLit }

// lr分析的value stack的元素，这个例子里只能是lexer解析出来的token或者表示Expr的i32
pub enum StackItem<'p> { _Token(Token<'p>), _0(i32) }

// lexer解析出来的token的类型，包含了终结符种类，对应的字符串片段，行列号信息
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Token<'l> {
  pub ty: TokenKind,
  pub piece: &'l [u8],
  pub line: u32,
  pub col: u32,
}

pub struct Lexer<'l> {
  pub string: &'l [u8],
  pub line: u32,
  pub col: u32,
}

impl<'l> Lexer<'l> {
  pub fn new(string: &[u8]) -> Lexer {
    Lexer { string, line: 1, col: 1 }
  }

  // 新解析一个Token
  // 如果解析结果是_Eps就不会返回给parser，如果是_Eof可能会导致parser完成最终的Acc或者出错
  // 如果是_Err会导致parser出错
  pub fn next(&mut self) -> Token<'l> {
    // ACC表示每个dfa节点对应于哪个终结符，如果一个都不对应就是_Err
    static ACC: [TokenKind; 10] = [一张巨大的表，这里不列了];
    // EC表示equivalent char，有些字符对dfa处理起来可能是一样的，用EC先减小字符集的大小，从而减小dfa转移表的大小
    static EC: [u8; 256] = [一张巨大的表，这里不列了];
    // DFA_EDGE表示dfa的状态转移表，逻辑上DFA_EDGE[state][char]表示在state处遇到char时的下一个state编号
    // 规定编号0必须代表出错状态
    // 下面的所有u8(不包括上面那个EC的u8)，都是可以变化的，是可以容纳状态数的最小无符号整数
    static DFA_EDGE: [[u8; 10]; 10] = [一张巨大的表，这里不列了];
    // 这个循环不断把字符喂给dfa，直到：
    // 识别出一个非_Eps的token后出错或文件结尾 => 返回这个token
    // 没有识别出非_Eps的token时出错 => 返回_Err
    // 没有识别出非_Eps的token时文件结尾 => 返回_Eof
    loop {
      let (mut line, mut col) = (self.line, self.col);
      let mut last_acc = TokenKind::_Err;
      let mut state = 0;
      let mut i = 0;
      while i < self.string.len() {
        let ch = index!(self.string, i);
        let ec = index!(EC, ch);
        let nxt = index!(index!(DFA_EDGE, state), ec);
        let acc = index!(ACC, nxt);
        if acc != TokenKind::_Err { last_acc = acc };
        state = nxt;
        if nxt == 0 { // 出错，不能消耗掉当前字符，它属于下一个token
          let piece = &self.string[..i];
          self.string = &self.string[i..];
          if last_acc != TokenKind::_Eps {
            return Token { ty: last_acc, piece, line, col };
          } else {
            line = self.line;
            col = self.col;
            last_acc = TokenKind::_Err;
            state = 0;
            i = 0;
          }
        } else {
          // 维护行号列号
          // 有些字符其实宽度不一定是1(如tab)，但是简单起见这里统一用1表示了
          if ch == b'\n' {
            self.line += 1;
            self.col = 1;
          } else {
            self.col += 1;
          }
          i += 1;
        }
      }
      // 文件结尾
      let piece = &self.string[..i];
      self.string = b"";
      return if last_acc != TokenKind::_Eps && i != 0 {
        Token { ty: last_acc, piece, line, col }
      } else {
        Token { ty: TokenKind::_Eof, piece: b"", line: self.line, col: self.col }
      };
    }
  }
}

// lr分析中对于一个lookahead字符的几种动作
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum Act { Shift(u8), Reduce(u8), Acc, Err }

impl<'p> Parser {
  pub fn parse<'l: 'p>(&mut self, lexer: &mut Lexer<'l>) -> Result<i32, Token<'l>> {
    // PROD表示产生式的(左端项编号，右端项数目)
    static PROD: [(u8, u8); 9] = [一张巨大的表，这里不列了];
    // lr分析的动作表
    static ACTION: [[Act; 12]; 18] = [一张巨大的表，这里不列了];
    // lr分析的goto表
    static GOTO: [[Option<u8>; 2]; 18] = [一张巨大的表，这里不列了];
    let mut value_stk: Vec<StackItem<'p>> = vec![];
    let mut state_stk: Vec<u8> = vec![0];
    let mut state = 0; // state永远与栈顶相等，只是为了减少一些访存
    let mut token = lexer.next(); // lookahead符号
    println!("{:?}", token); // log_token的作用，输出一个刚解析出的token
    // 标准的lr分析循环
    loop {
      let act = index!(index!(ACTION, state), token.ty as u32 - 2); // - 2是因为非终结符的编号都>= 2
      match act {
        Act::Shift(s) => {
          // 移进，把token压入value stack，把shift的目标状态压入state stack
          value_stk.push(StackItem::_Token(token));
          state_stk.push(s);
          state = s;
          // 获取新的lookahead符号
          token = lexer.next();
          println!("{:?}", token); // 还是log_token的作用，输出一个刚解析出的token
        }
        Act::Reduce(r) => {
          // 规约，先从state stack上弹出产生式右端项那么多个的state
          let prod = index!(PROD, r);
          for _ in 0..prod.1 { match state_stk.pop() { Some(_) => {} None => impossible!() }; }
          // 然后从value stack上弹出产生式右端项那么多个的value用于执行语法动作
          let value = match r {
            0 => {
              println!("Expr -> Expr Add Expr"); // log_reduce的作用，输出产生式
              let r = match value_stk.pop() { Some(StackItem::_0(x)) => x, _ => impossible!() };
              let _op = match value_stk.pop() { Some(StackItem::_Token(x)) => x, _ => impossible!() };
              let l = match value_stk.pop() { Some(StackItem::_0(x)) => x, _ => impossible!() };
              // 这个 l + r 就是用户编写的语法动作，嵌到这里来了
              StackItem::_0({ { l + r } })
            }
            // 这里省略类似的Sub Mul Div Mod...
            // 最后的一次规约，把用户定义的目标非终结符规约到增广语法中新定义的非终结符
            8 => {
              println!("_Expr -> Expr");
              let _1 = match value_stk.pop() { Some(StackItem::_0(x)) => x, _ => impossible!() };
              StackItem::_0({ _1 })
            }

            _ => impossible!(),
          };
          // 然后在value stack上压入新生成的value，并且通过访问goto表得知state stack上需要压入的新state
          value_stk.push(value);
          let cur = index!(state_stk, state_stk.len() - 1);
          let nxt = match index!(index!(GOTO, cur), prod.0) { Some(nxt) => nxt, None => impossible!() };
          state_stk.push(nxt);
          state = nxt;
        }
        Act::Acc => {
          // 接受，将栈顶作为最终结果返回
          match state_stk.pop() { None => impossible!(), Some(_) => {} };
          let res = match value_stk.pop() { Some(StackItem::_0(r)) => r, _ => impossible!() };
          return Ok(res);
        }
        // 出错，返回导致出错的token
        Act::Err => return Err(token),
      }
    }
  }
}
```

来跑一个实际的例子：

```rust
assert_eq!(Parser.parse(&mut Lexer::new(b"1 - 2 * (3 + 4 * 5 / 6) + -7 * -9 % 10")), Ok(-8));
```

结果显然是正确的，可以看一下`#[log_token]`和`#[log_reduce]`的输出：

```
Token { ty: IntLit, piece: [49], line: 1, col: 1 }
Token { ty: Sub, piece: [45], line: 1, col: 3 }
Expr -> IntLit
Token { ty: IntLit, piece: [50], line: 1, col: 5 }
Token { ty: Mul, piece: [42], line: 1, col: 7 }
Expr -> IntLit
Token { ty: LPar, piece: [40], line: 1, col: 9 }
Token { ty: IntLit, piece: [51], line: 1, col: 10 }
Token { ty: Add, piece: [43], line: 1, col: 12 }
Expr -> IntLit
Token { ty: IntLit, piece: [52], line: 1, col: 14 }
Token { ty: Mul, piece: [42], line: 1, col: 16 }
Expr -> IntLit
Token { ty: IntLit, piece: [53], line: 1, col: 18 }
Token { ty: Div, piece: [47], line: 1, col: 20 }
Expr -> IntLit
Expr -> Expr Mul Expr
Token { ty: IntLit, piece: [54], line: 1, col: 22 }
Token { ty: RPar, piece: [41], line: 1, col: 23 }
Expr -> IntLit
Expr -> Expr Div Expr
Expr -> Expr Add Expr
Token { ty: Add, piece: [43], line: 1, col: 25 }
Expr -> LPar Expr RPar
Expr -> Expr Mul Expr
Expr -> Expr Sub Expr
Token { ty: Sub, piece: [45], line: 1, col: 27 }
Token { ty: IntLit, piece: [55], line: 1, col: 28 }
Token { ty: Mul, piece: [42], line: 1, col: 30 }
Expr -> IntLit
Expr -> Sub Expr
Token { ty: Sub, piece: [45], line: 1, col: 32 }
Token { ty: IntLit, piece: [57], line: 1, col: 33 }
Token { ty: Mod, piece: [37], line: 1, col: 35 }
Expr -> IntLit
Expr -> Sub Expr
Expr -> Expr Mul Expr
Token { ty: IntLit, piece: [49, 48], line: 1, col: 37 }
Token { ty: Add, piece: [43], line: 1, col: 40 }
Expr -> IntLit
Expr -> Expr Mod Expr
Expr -> Expr Add Expr
Token { ty: IntLit, piece: [49], line: 1, col: 42 }
Token { ty: _Eof, piece: [], line: 1, col: 43 }
Expr -> IntLit
Expr -> Expr Add Expr
```

比较枯燥，其实也没啥看的必要，只有出错的时候用于调试可能才有意义。

最后看一下那几个文件中都输出了什么内容。先看最简单的dfa的图形，大概是这样的：

![dfa](/files/-LpInpIeYeKiia38yZJd)

再看一个巨大的lr fsm(美观起见，我把`Add`等终结符换成了对应的符号，`_Eof`替换成了`#`)：

![fsm](/files/-LpInpIgEPhJGUqeU2-e)

值得注意的是这个lr fsm是没有经过解决冲突的处理的，例如图中的这一处：

![conflict](/files/-LpInpIi8FJp1GLJwNor)

显然是有移进-规约冲突的。

但是文本表示的verbose信息中体现了冲突的解决，这个片段对应于`verbose.txt`中的：

```
State 12:
  Expr -> Expr.Add Expr
  Expr -> Expr Add Expr.
  Expr -> Expr.Sub Expr
  Expr -> Expr.Mul Expr
  Expr -> Expr.Div Expr
  Expr -> Expr.Mod Expr

  Div => Shift(8) (✓) # 遇到/时移进，因为/优先级比+高
  Div => Reduce(0) (-)
  Add => Shift(5) (-)
  Add => Reduce(0) (✓) # 遇到+时规约，因为+左结合
  RPar => Reduce(0) (✓)
  Mul => Shift(7) (✓) # 遇到*时移进，因为*优先级比+高
  Mul => Reduce(0) (-)
  Mod => Shift(9) (✓) # 遇到%时移进，因为%优先级比+高
  Mod => Reduce(0) (-)
  Sub => Shift(6) (-)
  Sub => Reduce(0) (✓) # 遇到-时规约，因为+和-优先级一样高，而+左结合
  _Eof => Reduce(0) (✓)
```

可见这里所有冲突选择都被优先级和结合性的约束给消除了。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mashplant.gitbook.io/decaf-doc/pa1a/lalr1-shi-yong-zhi-dao/yi-ge-wan-zheng-de-li-zi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.