阅读本文前需要对Parser Combinator和自顶向下文法有一定了解。
本文使用的语言是F#，需要用到库FParsec。
左递归文法造成无限递归
Parser Combinator本质上是一种自顶向下的Parser，因此在遇到左递归文法时会产生无限递归。举例如下：
简单的整数加减法文法：
Expr: Expr '+' Expr | Expr '-' Expr | Num;
Num: 整数;
实际代码：
let pExpr, pExprRef = createParserForwardedToRef<int, unit>() // 此函数是为了实现循环引用
let pNum: Parser<int, unit> =
pint32
let pAdd: Parser<int, unit> =
parse {
let! left = pExpr
let! _ = pchar '+'
let! right = pExpr
return left + right
}
let pSub: Parser<int, unit> =
parse {
let! left = pExpr
let! _ = pchar '-'
let! right = pExpr
return left - right
}
do pExprRef :=
pAdd <|> pSub <|> pNum
测试代码：
[<EntryPoint>]
let main argv =
let res = run pExpr "1+2-3"
match res with
| Success (expr, _, _) -> printfn $"{expr}"
| Failure (msg, _, _) -> printfn $"{msg}"
0
测试字符串："1+2-3" 合法输出：0
实际输出：*
改写文法
Expr: Expr '+' Expr | Expr '-' Expr | Num;
Num: 整数;
对于左递归文法，在使用自顶向下的方式处理"1+1"时的无限递归过程：
1. Expr
2. Expr ('+' Expr | '-' Expr)
3. (Expr ('+' Expr | '-' Expr)) ('+' Expr | '-' Expr)
4. ((Expr ('+' Expr | '-' Expr)) ('+' Expr | '-' Expr)) ('+' Expr | '-' Expr)
5. ...
因此我们需要将左递归文法改写为右递归：
Expr: ExprT [Op Expr];
ExprT: Num;
Op: "+" | "-";
Num: 整数;
改写后的Parser处理过程：
1. Expr
2. ExprT [Op Expr]
3. 1 [Op Expr]
4. 1 + Expr
5. 1 + (ExprT [Op Expr])
6. 1 + (1 [Op Expr])
7. 1 + (1)
8. 1 + 1
考虑到这个递归的展开过程是这样的：
ExprT Op (ExprT Op (ExprT Op (ExprT ...)))
我们可以移动括号，将递归嵌套改为链式：
ExprT (Op ExprT) (Op ExprT) (Op ExprT) ...
修改为链式后的文法：
Expr: ExprT (Op ExprT)*;
ExprT: Num;
Op: "+" | "-";
Num: 整数;
使用chainl1实现Parser
根据上述文法实现的代码：
let pNum: Parser<int, unit> =
pint32
let pOperator: Parser<int -> int -> int, unit> =
parse {
let! op = anyOf "+-"
if op = '+' then
return (fun l r -> l + r)
else
return (fun l r -> l - r)
}
let pExprT: Parser<int, unit> =
pNum
let pExpr: Parser<int, unit> =
chainl1 pExprT pOperator
测试字符串："1+2-3" 合法输出：0
实际输出：0
chainl1函数的定义为：
val chainl1: Parser<'a, 'u> -> Parser<('a -> 'a -> 'a), 'u> -> Parser<'a, 'u>
'u我们不用管它，可以看成：
val chainl1: (p: Parser<'a>) -> (op: Parser<('a -> 'a -> 'a)>) -> Parser<'a>
chainl1的第一个参数是p，第二个参数是op。它所parse的文法是p (op p)*，这与我们的定义的Expr: ExprT (Op ExprT)*等同，因此Expr的parser可以用chainl1实现。
第一个参数p不难理解，但是第二个参数op就比较迷惑，为什么它的类型是Parser<('a -> 'a -> 'a)>？下边将演示工它的作过程来解释它的意义：
我们定义let pExpr: Parser<int> = chainl1 pExprT pOperator，其中pExprT用于parse表达式中的数字并返回，pOperator用于parse运算符并根据运算符返回处理函数。
对于输入"1"，pExpr会得到一个数字1。后续没有内容了，直接返回数字1。
对于输入"1+2"，pExpr会得到两个数字和一个处理函数：1、(let f = (fun l r -> l + r)、2)，并且从左到右的应用函数(1 f 2)，也就是(1 + 2)得到结果3并返回。
对于输入"1+2-3"，pExpr会得到三个数字和两个处理函数：1、(let f = (fun l r -> l + r)、2)、(let g = (fun l r -> l - r)、3)，并且从左到右的应用函数((1 f 2) g 3)，也就是((1 + 2) - 3)得到结果0并返回。
使用chainr1定义右结合运算符
不难看出，使用chainl1定义的运算符是左结合的，如果要定义右结合的运算符，可以用chainr1。定义let pExpr: Parser<int> = chainr1 pExprT pOperator，它的工作过程将会是这样
对于输入"1+2-3"，pExpr会得到三个数字和两个处理函数：1、(let f = (fun l r -> l + r)、2)、(let g = (fun l r -> l - r)、3)，并且从右到左的应用函数(1 f (2 g 3))，也就是(1 + (2 - 3))得到结果0并返回。因为+和-都满足结合律，所以此处运算符的左右结合并不影响结果。
运算符优先级
上文介绍的方法无法处理运算符的优先级，例如带乘法加法的文法：
Expr: ExprT (Op ExprT)*;
ExprT: Num;
Op: "+" | "*";
Num: 整数;
使用chainl1处理"1+2*3"，得到：1、(let f = (fun l r -> l + r)、2)、(let g = (fun l r -> l * r)、3)，从左到右应用函数((1 f 2) g 3)，也就是((1 + 2) * 3)结果为9，这并不符合运算符的优先级。
我们只能对文法进行修改，这里有个诀窍就是：
“只要把优先级高的运算（比如乘法）的结果作为优先级低的运算（比如加法）的元素就好了”
Expr: AddExpr;
AddExpr: MulExpr ("+" MulExpr)*
MulExpr: ExprT ("*" ExprT)*
ExprT: Num;
Num: 整数;
对应的代码是：
let pNum: Parser<int, unit> =
pint32
let pExprT: Parser<int, unit> =
pNum
let pMulExpr: Parser<int, unit> =
chainl1 pExprT (pchar '*' >>. preturn (fun l r -> l * r))
let pAddExpr: Parser<int, unit> =
chainl1 pMulExpr (pchar '+' >>. preturn (fun l r -> l + r))
let pExpr: Parser<int, unit> =
chainl1 pExprT pOperator
测试字符串："1+2*3" 合法输出：7
实际输出：7
参考文献：