yasp 开发日记【1】提到了我遇到关键字 ambiguous 的问题,这个问题在lalrpopPrecedence of fixed strings章节也有所描述,并提供了解决方法。

SQL语言是一个流行的关键字大小写不敏感的语言,例如:

1
2
select uta from sakura;
SeLecT uta fRom sakura;

这两句SQL的语义实际上是一样的,但是如果我们这么写一个简陋的lexer:

1
2
3
4
5
6
7
8
9
Name: String = r"\w+" => <>.into();
SELECT: &'input str = "select" => <>;
FROM: &'input str = "from" => <>;
pub Expr: Expr = {
SELECT <field: Name> FROM <table: Name> => Expr::Select(SelectNode{
field,
table,
})
};

那么这个lexer对于select uta from sakura来说没问题;但是对于SeLecT uta fRom sakura来说,SeLecTfRom不能够被匹配成关键字。

需要注意的另一点是,根据Precedence of fixed strings的描述,固定的字符串拥有比正则表达式更高的匹配优先级,所以这个词法分析器不存在歧义。

为了匹配SeLecTfRom关键字,我们将lexer改成:

1
2
3
4
5
6
7
8
9
Name: String = r"\w+" => <>.into();
SELECT: &'input str = r"(?i)select" => <>;
FROM: &'input str = r"(?i)from" => <>;
pub Expr: Expr = {
SELECT <field: Name> FROM <table: Name> => Expr::Select(SelectNode{
field,
table,
})
};

此时,lalrpop会认为我们所描述的语法存在歧义

1
error: ambiguity detected between the terminal `r#"\\w+"#` and the terminal `r#"(?i)from"#`

好吧,lalrpop不会处理推断多个正则表达式之间的优先级,相应的,文档中也给出了处理方式——预处理输入。

需要这样修改lexer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
match {
r"(?i)select" => "SELECT",
r"(?i)from" => "FROM",
} else {
_
}

Name: String = r"\w+" => <>.into();
SELECT: &'input str = "SELECT" => <>;
FROM: &'input str = "FROM" => <>;
pub Expr: Expr = {
SELECT <field: Name> FROM <table: Name> => Expr::Select(SelectNode{
field,
table,
})
};

虽然lalrpop不会自动推断多个正则表达式之间的优先级,但是在match else中,我们可以手动指定这些token的优先级。另外,这个写法也将关键词罗列在了一起,让代码可读性变的更强。