本文是一篇翻译，太悲伤了，不知道怎么翻，机翻还是太好用了，出处：

Simple but Powerful Pratt Parsing

简单强大的Pratt 解析

这篇文章是一个语法解析的monad教程。关于Pratt解析的文章很多，甚至这里有一个合集blog

我写这篇文章的目的是：

  • 说明左递归问题是容易解决的
  • 用另一种方式代替不好识别中缀表达式的BNF
  • 给出Pratt的算法描述和具体实现，并聚焦重点，不引入DSL-y的抽象
  • 希望这是我最后一次理解这个算法，之前写过一次，但是写完之后就忘了QAQ

本文假设读者对解析操作有基本的理解，知晓基本术语，比如上下文无关语法

导入

解析(parser)是编译器将标记的序列转为语法树表示的过程：

1
2
3
4
5
                           Add
                Parser     / \ 
"1 + 2 * 3"    ------->   1  Mul
                             / \
                            2   3

实现这个过程有很多方式，我们一般分为两类：

  • 使用DSL定义一个语言的抽象语法
  • 手动实现解析

BNF

语法分析的作用就是将token流解析为树结构，其中最重要的方法就是使用上下文无关语法来记录（一般用BNF语法）

1
2
3
4
5
6
7
Item =
    StructItem
  | EnumItem
  | ...
StructItem =
    'struct' Name '{' FieldList '}'
...

自然语言和程序语言结构十分地相似，这让我很激动，BNF可以做到解析它们。但是当我尝试解析表达式的时候，BNF就不好用了。我们先看看自然语言表达式的表达：

1
2
3
4
5
Expr =
    Expr '+' Expr
  | Expr '*' Expr
  | '(' Expr ')'
  | 'number'

这样写是没什么问题的，但是还需要考虑运算符的优先级和结合性，所以BNF会变成这样：

1
2
3
4
5
6
7
8
9
Expr =
    Factor
  | Expr '+' Factor
Factor =
    Atom
  | Factor '*' Atom
Atom =
    'number'
  | '(' Expr ')'

这样再看，就会感觉它很不“表达式”。而且很难写，在我能写出来这种语法之前，我多学了至少3，4课才学会。

这就是为什么我喜欢Pratt解析（基于递归下降而又比它强），它使用自然语言中的优先级和关联性来解析表达式，而不是语法混淆技术(存疑？)

递归下降和左递归

下面是使用递归下降实现的上面那个例子的代码，它是用一组嵌套递归的函数来实现的，所以叫递归下降：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn item(p: &mut Parser) {
    match p.peek() {
        STRUCT_KEYWORD => struct_item(p),
        ENUM_KEYWORD   => enum_item(p),
        ...
    }
}
fn struct_item(p: &mut Parser) {
    p.expect(STRUCT_KEYWORD);
    name(p);
    p.expect(L_CURLY);
    field_list(p);
    p.expect(R_CURLY);
}
...

书上说这种方法有一个缺点，那就是左递归。因而它带来了更高级的LR解析技术。可以看看下面这个有问题的例子：

1
2
3
Sum =
    Sum '+' Int
  | Int

写成代码呢：

1
2
3
4
5
6
7
8
fn sum(p: &mut Parser) {
    // 第一个选项
    sum(p); 
    p.expect(PLUS);
    int(p);
    // 如果失败，选第二个选项
    ...
}

在第三行，sum§会无限递归导致栈溢出

所以我们一般在实践中用循环代替递归：

1
2
3
4
5
6
fn sum(p: &mut Parser) {
    int(p);
    while p.eat(PLUS) {
        int(p);
    }
}

Pratt解析标准模板

如果只有循环，前缀表达式就不能解析。所以，Pratt用循环和递归一起实现解析操作：

1
2
3
4
5
6
7
8
fn parse_expr() {
    ...
    loop {
        ...
        parse_expr()
        ...
    }
}

它把表达式放进循环，还能解析优先级和关联性

优先级与绑定能力

我经常把高优先级和低优先级搞混。在a+b*c中加法的优先级较低，但是它在语法树的顶端。所以我们可以引入绑定能力这个概念：

1
2
表达式:   A       +       B       *       C
绑定能力:     3       3       5       5

在这个例子中，*更强，所以它绑定左右内容的能力更强，因此整个表达式先组合BC，然后组合A和BC

那相关性呢？如果是A+B+C，每个运算符都是一样的，那要怎么判断是(A+B)+C还是A+(B+C)，但是绑定能力也可以表示这个特性：

1
2
表达式:      A       +       B       +       C
绑定能力: 0      3      3.1      3      3.1     0

这里我们把+的右侧的绑定能力增加了，这样可以让+运算符后面的数和+联系得更紧密。然后在左右加0说明两边没有操作符。对于B来说，左边的+比右边的+的绑定能力更强，所以它和左边的+优先结合，因此，可以化简为：

1
2
表达式:      (A + B)     +     C
绑定能力:  0          3    3.1    0

然后就顺理成章了，第二个+更喜欢后面那个数，所以在它连接C时，A和B被第一个+捕获了，这是很清晰的。

Pratt解析需要在读取从左到右的token流的同时来实现上面的过程。这无疑是比邻居搜索算法(存疑？)更好的。基本原理已经OK了，只剩写代码。但是我们还需要表示一个右结合的语法，我们用 . 来表示，假设数字为f，g和h：

1
2
  f     .    g     .    h
0   8.5    8   8.5    8   0

它会被解析为：f . (g . h)

最简Pratt解析器

我们传入解析器的参数是单字符的数字和变量，并用标点符号作为运算符，实例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Token {
    Atom(char),
    Op(char),
    Eof,
}
struct Lexer {
    tokens: Vec<Token>,
}
impl Lexer {
    fn new(input: &str) -> Lexer {
        let mut tokens = input
            .chars()
            .filter(|it| !it.is_ascii_whitespace())
            .map(|c| match c {
                '0'..='9' |
                'a'..='z' | 'A'..='Z' => Token::Atom(c),
                _ => Token::Op(c),
            })
            .collect::<Vec<_>>();
        tokens.reverse();
        Lexer { tokens }
    }
    fn next(&mut self) -> Token {
        self.tokens.pop().unwrap_or(Token::Eof)
    }
    fn peek(&mut self) -> Token {
        self.tokens.last().copied().unwrap_or(Token::Eof)
    }
}

为了可以正确识别绑定能力，需要先将中缀表达式变为前缀表达式：

1 + 2 * 3 == (+ 1 (* 2 3))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
use std::fmt;
enum S {
    Atom(char),
    Cons(char, Vec<S>),
}
impl fmt::Display for S {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            S::Atom(i) => write!(f, "{}", i),
            S::Cons(head, rest) => {
                write!(f, "({}", head)?;
                for s in rest {
                    write!(f, " {}", s)?
                }
                write!(f, ")")
            }
        }
    }
}

让我们从+和*开始：

1
2
3
4
5
6
7
8
9
10
11
12
fn expr(input: &str) -> S {
    let mut lexer = Lexer::new(input);
    expr_bp(&mut lexer)
}
fn expr_bp(lexer: &mut Lexer) -> S {
    todo!()
}
#[test]
fn tests() {
    let s = expr("1 + 2 * 3");
    assert_eq!(s.to_string(), "(+ 1 (* 2 3))")
}

所以说，实际就是使用我们处理左递归的方法——解析数字，循环，然后consum操作符，然后做其它的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
fn expr_bp(lexer: &mut Lexer) -> S {
    let lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.next() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        todo!()
    }
    lhs
}
#[test]
fn tests() {
    let s = expr("1"); 
    assert_eq!(s.to_string(), "1");
}

已经可以正常执行了

我们添加上运算符的左右绑定能力，由于两侧都是0，所以运算符的至少为1，对于不同结合性的，可以在对应边+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
fn expr_bp(lexer: &mut Lexer) -> S {
    let lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        let (l_bp, r_bp) = infix_binding_power(op);
        todo!()
    }
    lhs
}
fn infix_binding_power(op: char) -> (u8, u8) {
    match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        _ => panic!("bad op: {:?}", op)
    }
}

现在是最棘手的地方，引入递归，假设下面这个例子：

1
2
a   +   b   *   c   *   d   +   e
  1   2   3   4   3   4   1   2

这里，开始执行时，将a放入lhs，然后呢？很明显不能直接将b和a组合，那是b*c吗？也不是，应该是b*c*d，一共应该分为三个部分：A+B+C，这是因为+的结合性更低，所以，我们引入递归：从b开始，找到比b左边结合性还低的结合性即可，在这里就是e，因此要向main函数添加min_bp参数。bp就是bind power

最后，就是这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
fn expr(input: &str) -> S {
    let mut lexer = Lexer::new(input);
    expr_bp(&mut lexer, 0) 
}
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S { 
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        let (l_bp, r_bp) = infix_binding_power(op);
        if l_bp < min_bp { 
            break;
        }
        lexer.next(); 
        let rhs = expr_bp(lexer, r_bp);
        lhs = S::Cons(op, vec![lhs, rhs]); 
    }
    lhs
}
fn infix_binding_power(op: char) -> (u8, u8) {
    match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        _ => panic!("bad op: {:?}", op),
    }
}
#[test]
fn tests() {
    let s = expr("1");
    assert_eq!(s.to_string(), "1");
    let s = expr("1 + 2 * 3");
    assert_eq!(s.to_string(), "(+ 1 (* 2 3))");
    let s = expr("a + b * c * d + e");
    assert_eq!(s.to_string(), "(+ (+ a (* (* b c) d)) e)");
}
  • 第5行：min_bp十分重要，expr_bp在它的控制下可以解析比它绑定能力大的所有表达式，当看到比它小的表达式时，就会停止。
  • 第17行：停止条件
  • 第20行：这里我们跳过操作符本身，进行递归调用。我们使用l_bp来检测min_bp，r_bp作为递归调用的新min_bp。因此min_bp可以视为当前表达式左侧操作符的绑定能力。
  • 第22行：解析完右侧的表达式后，组合成当前表达式
  • 第3行：开始时，使用0的绑定能力，0表示没有运算符

上面的40行代码就是Pratt核心的解析算法。如果你能理解它，那么其它的内容就是单纯的加法罢了。

额外内容

好了，我们现在可以添加一些奇怪的表达式来展示Pratt算法的强大。首先添加一个高优先的，右结合的成员函数调用运算符 . ：

1
2
3
4
5
6
7
8
fn infix_binding_power(op: char) -> (u8, u8) {
    match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        '.' => (6, 5),
        _ => panic!("bad op: {:?}", op),
    }
}

很不错：

1
2
3
4
5
let s = expr("f . g . h");
assert_eq!(s.to_string(), "(. f (. g h))");

let s = expr(" 1 + 2 + f . g . h * 3 * 4");
assert_eq!(s.to_string(), "(+ (+ 1 2) (* (* (. f (. g h)) 3) 4))");

好的，现在添加负号，也就是一元 - ，它比比特运算符绑定更强，但是比二元的绑定弱，同时如果它是第一个出现的token，那上面的代码就需要修改为先处理一元运算符的版本。由于一元运算符只和右边结合所以只有右结合性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fn prefix_binding_power(op: char) -> ((), u8) { 
    match op {
        '+' | '-' => ((), 5),
        _ => panic!("bad op: {:?}", op),
    }
}
fn infix_binding_power(op: char) -> (u8, u8) {
    match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        '.' => (8, 7), 
        _ => panic!("bad op: {:?}"),
    }
}
  • 第1行：使用()表明这是一个前缀运算符而不是后缀或中缀，所以只能把其它东西放在这个符号后。
  • 第11行：由于我们要在.和*中添加一元减，所以需要修正.的优先级，一般来说，如果运算符是二元的，设置它的优先级为一个奇数，并用这个数+1表示它的结合性。对于一元减来说，则都可以，但是最好设置一个原则。

加到expr_bp之后，得到：

1
2
3
4
5
6
7
8
9
10
11
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        Token::Op(op) => {
            let ((), r_bp) = prefix_binding_power(op);
            todo!()
        }
        t => panic!("bad token: {:?}", t),
    };
    ...
}

不过，我们现在有r_bp了，还没有l_bp，所以直接复制main的一段代码修改出来吧？记住，r_bp是用来递归的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        Token::Op(op) => {
            let ((), r_bp) = prefix_binding_power(op);
            let rhs = expr_bp(lexer, r_bp);
            S::Cons(op, vec![rhs])
        }
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        let (l_bp, r_bp) = infix_binding_power(op);
        if l_bp < min_bp {
            break;
        }
        lexer.next();
        let rhs = expr_bp(lexer, r_bp);
        lhs = S::Cons(op, vec![lhs, rhs]);
    }
    lhs
}
#[test]
fn tests() {
    ...
    let s = expr("--1 * 2");
    assert_eq!(s.to_string(), "(* (- (- 1)) 2)");
    let s = expr("--f . g");
    assert_eq!(s.to_string(), "(- (- (. f g)))");
}

有趣，它直接生效了，你可以想一下为什么会这样。因为操作数被绑定程度更高的运算符结合了，而这里正好有一个解析指定绑定能力更高的表达式的函数。

OK，((), u8) 可以解决前缀式，那后缀式可以用(u8, ()) 来解决吗？现在加个阶乘：

1
2
3
4
5
6
7
8
let (l_bp, ()) = postfix_binding_power(op);
if l_bp < min_bp {
    break;
}
let (l_bp, r_bp) = infix_binding_power(op);
if l_bp < min_bp {
    break;
}

e，不对，解析前缀表达式时，我们能看到后缀或中缀运算符。但是传递没有识别到的运算符时，就不能正常运行了。所以，让postfix_binding_power 返回一个指明是不是后缀的选项：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        Token::Op(op) => {
            let ((), r_bp) = prefix_binding_power(op);
            let rhs = expr_bp(lexer, r_bp);
            S::Cons(op, vec![rhs])
        }
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        if let Some((l_bp, ())) = postfix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            lhs = S::Cons(op, vec![lhs]);
            continue;
        }
        let (l_bp, r_bp) = infix_binding_power(op);
        if l_bp < min_bp {
            break;
        }
        lexer.next();
        let rhs = expr_bp(lexer, r_bp);
        lhs = S::Cons(op, vec![lhs, rhs]);
    }
    lhs
}
fn prefix_binding_power(op: char) -> ((), u8) {
    match op {
        '+' | '-' => ((), 5),
        _ => panic!("bad op: {:?}", op),
    }
}
fn postfix_binding_power(op: char) -> Option<(u8, ())> {
    let res = match op {
        '!' => (7, ()),
        _ => return None,
    };
    Some(res)
}
fn infix_binding_power(op: char) -> (u8, u8) {
    match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        '.' => (10, 9),
        _ => panic!("bad op: {:?}"),
    }
}
#[test]
fn tests() {
    let s = expr("-9!");
    assert_eq!(s.to_string(), "(- (! 9))");
    let s = expr("f . g !");
    assert_eq!(s.to_string(), "(! (. f g))");
}

太好了，这样就都通过了。

现在，我们需要添加括号。这很简单，我们本可以在一开始做，但是这里再处理更有意义。括号表达式只是一个基础表达式，它的处理方式类似于基本的数字标识符等组成的原子表达式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let mut lhs = match lexer.next() {
    Token::Atom(it) => S::Atom(it),
    Token::Op('(') => {
        let lhs = expr_bp(lexer, 0);
        assert_eq!(lexer.next(), Token::Op(')'));
        lhs
    }
    Token::Op(op) => {
        let ((), r_bp) = prefix_binding_power(op);
        let rhs = expr_bp(lexer, r_bp);
        S::Cons(op, vec![rhs])
    }
    t => panic!("bad token: {:?}", t),
};

可惜，失败了：

1
2
let s = expr("(((0)))");
assert_eq!(s.to_string(), "0");

报错来自于下面的循环，我们的终止条件是达到eof，而不是)，所以解决方法是在遇到未知的标识符是返回None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        Token::Op('(') => {
            let lhs = expr_bp(lexer, 0);
            assert_eq!(lexer.next(), Token::Op(')'));
            lhs
        }
        Token::Op(op) => {
            let ((), r_bp) = prefix_binding_power(op);
            let rhs = expr_bp(lexer, r_bp);
            S::Cons(op, vec![rhs])
        }
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        if let Some((l_bp, ())) = postfix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            lhs = S::Cons(op, vec![lhs]);
            continue;
        }
        if let Some((l_bp, r_bp)) = infix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            let rhs = expr_bp(lexer, r_bp);
            lhs = S::Cons(op, vec![lhs, rhs]);
            continue;
        }
        break;
    }
    lhs
}
fn prefix_binding_power(op: char) -> ((), u8) {
    match op {
        '+' | '-' => ((), 5),
        _ => panic!("bad op: {:?}", op),
    }
}
fn postfix_binding_power(op: char) -> Option<(u8, ())> {
    let res = match op {
        '!' => (7, ()),
        _ => return None,
    };
    Some(res)
}
fn infix_binding_power(op: char) -> Option<(u8, u8)> {
    let res = match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        '.' => (10, 9),
        _ => return None,
    };
    Some(res)
}

然后继续，我们来添加数组索引操作符：a[i]。它属于什么缀呢？环绕型？如果只有a[]那就是后缀，如果是[i]，则可以像括号一样。我们可以发现i并没有参与优先级的计算，所以可以这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        Token::Op('(') => {
            let lhs = expr_bp(lexer, 0);
            assert_eq!(lexer.next(), Token::Op(')'));
            lhs
        }
        Token::Op(op) => {
            let ((), r_bp) = prefix_binding_power(op);
            let rhs = expr_bp(lexer, r_bp);
            S::Cons(op, vec![rhs])
        }
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        if let Some((l_bp, ())) = postfix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            lhs = if op == '[' {
                let rhs = expr_bp(lexer, 0);
                assert_eq!(lexer.next(), Token::Op(']'));
                S::Cons(op, vec![lhs, rhs])
            } else {
                S::Cons(op, vec![lhs])
            };
            continue;
        }
        if let Some((l_bp, r_bp)) = infix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            let rhs = expr_bp(lexer, r_bp);
            lhs = S::Cons(op, vec![lhs, rhs]);
            continue;
        }
        break;
    }
    lhs
}
fn prefix_binding_power(op: char) -> ((), u8) {
    match op {
        '+' | '-' => ((), 5),
        _ => panic!("bad op: {:?}", op),
    }
}
fn postfix_binding_power(op: char) -> Option<(u8, ())> {
    let res = match op {
        '!' | '[' => (7, ()), 
        _ => return None,
    };
    Some(res)
}
fn infix_binding_power(op: char) -> Option<(u8, u8)> {
    let res = match op {
        '+' | '-' => (1, 2),
        '*' | '/' => (3, 4),
        '.' => (10, 9),
        _ => return None,
    };
    Some(res)
}
#[test]
fn tests() {
    ...
    let s = expr("x[0][1]");
    assert_eq!(s.to_string(), "([ ([ x 0) 1)");
}
  • 第57行：我们这里把!和[用作相同优先级。一般来说，优先级是不能相等的，否则可能的候选项就有2个或以上。而这里，我们比较的是右绑定能力和左绑定能力，而它们都只是右结合，不会出现多种可能，所以可以这样用。

最后的boss是这个，三元表达式：

1
c ? e1 : e2

如果这样就很好看了：

1
c [ e1 ] e2

这和a[i]差不多，所以把它当作奇怪的括号也未尝不可。既然如此，直接用我们之前解决括号的方法来解决它。那结合性和优先级呢？

1
a ? b : c ? d : e

就像刚刚说的，尝试把b和d看作括号的内容，而它不参与优先级的考虑：

1
a ?: c ?: e

最后就变成这样：

1
(a ?: c) ?: e

或者

1
a ?: (c ?: e)

哪一个更有用呢？？链像这样：

1
2
3
a ? b :
c ? d :
e

右结合的方式更有用，就优先级而言，三元运算符优先级较低。C语言中，只有=和，的优先级比它低。那么，也添加一个=吧。

现在，得到了最后的版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
use std::{fmt, io::BufRead};
enum S {
    Atom(char),
    Cons(char, Vec<S>),
}
impl fmt::Display for S {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            S::Atom(i) => write!(f, "{}", i),
            S::Cons(head, rest) => {
                write!(f, "({}", head)?;
                for s in rest {
                    write!(f, " {}", s)?
                }
                write!(f, ")")
            }
        }
    }
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Token {
    Atom(char),
    Op(char),
    Eof,
}
struct Lexer {
    tokens: Vec<Token>,
}
impl Lexer {
    fn new(input: &str) -> Lexer {
        let mut tokens = input
            .chars()
            .filter(|it| !it.is_ascii_whitespace())
            .map(|c| match c {
                '0'..='9'
                | 'a'..='z' | 'A'..='Z' => Token::Atom(c),
                _ => Token::Op(c),
            })
            .collect::<Vec<_>>();
        tokens.reverse();
        Lexer { tokens }
    }
    fn next(&mut self) -> Token {
        self.tokens.pop().unwrap_or(Token::Eof)
    }
    fn peek(&mut self) -> Token {
        self.tokens.last().copied().unwrap_or(Token::Eof)
    }
}
fn expr(input: &str) -> S {
    let mut lexer = Lexer::new(input);
    expr_bp(&mut lexer, 0)
}
fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        Token::Op('(') => {
            let lhs = expr_bp(lexer, 0);
            assert_eq!(lexer.next(), Token::Op(')'));
            lhs
        }
        Token::Op(op) => {
            let ((), r_bp) = prefix_binding_power(op);
            let rhs = expr_bp(lexer, r_bp);
            S::Cons(op, vec![rhs])
        }
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        if let Some((l_bp, ())) = postfix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            lhs = if op == '[' {
                let rhs = expr_bp(lexer, 0);
                assert_eq!(lexer.next(), Token::Op(']'));
                S::Cons(op, vec![lhs, rhs])
            } else {
                S::Cons(op, vec![lhs])
            };
            continue;
        }
        if let Some((l_bp, r_bp)) = infix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            lhs = if op == '?' {
                let mhs = expr_bp(lexer, 0);
                assert_eq!(lexer.next(), Token::Op(':'));
                let rhs = expr_bp(lexer, r_bp);
                S::Cons(op, vec![lhs, mhs, rhs])
            } else {
                let rhs = expr_bp(lexer, r_bp);
                S::Cons(op, vec![lhs, rhs])
            };
            continue;
        }
        break;
    }
    lhs
}
fn prefix_binding_power(op: char) -> ((), u8) {
    match op {
        '+' | '-' => ((), 9),
        _ => panic!("bad op: {:?}", op),
    }
}
fn postfix_binding_power(op: char) -> Option<(u8, ())> {
    let res = match op {
        '!' => (11, ()),
        '[' => (11, ()),
        _ => return None,
    };
    Some(res)
}
fn infix_binding_power(op: char) -> Option<(u8, u8)> {
    let res = match op {
        '=' => (2, 1),
        '?' => (4, 3),
        '+' | '-' => (5, 6),
        '*' | '/' => (7, 8),
        '.' => (14, 13),
        _ => return None,
    };
    Some(res)
}
#[test]
fn tests() {
    let s = expr("1");
    assert_eq!(s.to_string(), "1");
    let s = expr("1 + 2 * 3");
    assert_eq!(s.to_string(), "(+ 1 (* 2 3))");
    let s = expr("a + b * c * d + e");
    assert_eq!(s.to_string(), "(+ (+ a (* (* b c) d)) e)");
    let s = expr("f . g . h");
    assert_eq!(s.to_string(), "(. f (. g h))");
    let s = expr(" 1 + 2 + f . g . h * 3 * 4");
    assert_eq!(
        s.to_string(),
        "(+ (+ 1 2) (* (* (. f (. g h)) 3) 4))",
    );
    let s = expr("--1 * 2");
    assert_eq!(s.to_string(), "(* (- (- 1)) 2)");
    let s = expr("--f . g");
    assert_eq!(s.to_string(), "(- (- (. f g)))");
    let s = expr("-9!");
    assert_eq!(s.to_string(), "(- (! 9))");
    let s = expr("f . g !");
    assert_eq!(s.to_string(), "(! (. f g))");
    let s = expr("(((0)))");
    assert_eq!(s.to_string(), "0");
    let s = expr("x[0][1]");
    assert_eq!(s.to_string(), "([ ([ x 0) 1)");
    let s = expr(
        "a ? b :
         c ? d
         : e",
    );
    assert_eq!(s.to_string(), "(? a b (? c d e))");
    let s = expr("a = 0 ? b : c = d");
    assert_eq!(s.to_string(), "(= a (= (? 0 b c) d))")
}
fn main() {
    for line in std::io::stdin().lock().lines() {
        let line = line.unwrap();
        let s = expr(&line);
        println!("{}", s)
    }
}

这个代码也可以在这个仓库中找到。

Eof :-)