標籤：

PEG.js中如何消除左遞歸？

01-28

在用PEG.js實現逆波蘭表示法（例如1 2 + 4 × 5 + 3 ?）的解析器的過程中，發現需要用到左遞歸，但如果用了，PEG.js解析器會報錯：

Line 10, column 10: Possible infinite loop when parsing (left recursion: Term -&> Term).

，應該如何消除呢？或者如何換種寫法解決？

Term
= Integer
/ head:Term _ tail:Term _ op:Operator {
return buildBinaryExpression(op, head, tail);
}

首先我想說的是，RPN的一個最大的好處是要parse它根本不需要一個傳統意義上的parser，直接做好詞法分析之後線性掃描就出來了。無論是要直接對它求值還是要從它構造AST，都只要在線性掃描的時候帶一個棧即可。

例如說這樣：

function* tokenizeRPN(str) {
let re = /([1-9]d*)|([+-*/])/g
let match;
while ((match = re.exec(str)) !== null) {
if (match[1]) {
yield {
type: Integer,
value: parseInt(match[1])
}
} else if (match[2]) {
yield {
type: Operator,
value: match[2]
}
} else {
// ShouldNotReachHere()
}
}
}

function buildBinaryExpression(op, left, right) {
return {
type: BinaryExpression,
left: left,
right: right,
operator: op
}
}

function evalBinaryExpression(op, left, right) {
switch (op) {
case +: return left + right; break
case -: return left - right; break
case *: return left * right; break
case /: return left / right; break
default:
// ShouldNotReachHere()
}
}

function parseRPN(str, callback) {
let stack = []
for (let token of tokenizeRPN(str)) {
switch (token.type) {
case Integer:
stack.push(token.value)
break;
case Operator: {
let right = stack.pop()
let left = stack.pop()
let newValue = callback(token.value, left, right)
stack.push(newValue)
break;
}
default:
// ShouldNotReachHere()
}
}
return stack.pop()
}

function buildASTFromRPN(str) {
return parseRPN(str, buildBinaryExpression)
}

function evalRPN(str) {
return parseRPN(str, evalBinaryExpression)
}

var str = 1 2 + 3 * 4 5 - +
console.log(evalRPN(str))
console.log(buildASTFromRPN(str))

簡單～

順帶一提，Java位元組碼在表達式層面上就是RPN，所以執行Java位元組碼（概念上）會用到一個「表達式棧」，就是對應上面代碼里的那個stack的作用。這也就是Java位元組碼被叫做「基於（表達式）棧的指令集」的來由。

======================================

題主的RPN語法例子，用PEG.js實現，消除左遞歸之後其實這個樣子就好了：

/*
* Simple Reverse-Polish Notation Grammar
*/

{
function buildBinaryExpression(op, left, right) {
return {
type: BinaryExpression,
operator: op,
left: left,
right: right
}
}

function evalBinaryExpression(op, left, right) {
switch (op) {
case "+": return left + right; break
case "-": return left - right; break
case "*": return left * right; break
case "/": return left / right; break
}
}
}

Expression
= head:Integer tail:ExpressionRest* {
return tail.reduce(function (acc, e) {
return buildBinaryExpression(e.operator, acc, e.right)
}, head)
}

ExpressionRest
= _ right:Expression _ op:("*" / "/" / "+" / "-") {
return {
operator: op,
right: right
}
}

Integer "integer"
= [0-9]+ { return parseInt(text(), 10); }

_ "whitespace"
= [

]*

比題主的回答稍微簡單一點點。

話說其實在PEG（Parsing Expression Grammar）上直接支持左遞歸的研究有好多人都做過，都有實質成果，不知道為啥PEG.js選擇不去實現它…

======================================

然後這邊想演示一下ANTLRv4的情況。

ANTLRv4是一個LL系parser generator，它具體採用的演算法叫做「ALL(*)」（Adaptive LL(*)），它所支持的語法跟PEG頗有相似之處。

題主想要的RPN語法，用ANTLRv4來寫可以是這樣的：

（空白在ANTLR里默認是自動忽略的，所以我沒有像題主那樣顯示聲明空白字元的匹配）

grammar rpn;

prog : expr EOF
;

expr : NUM
| expr expr op
;

op : +
| -
| *
| /
;

NUM : (1 .. 9) (0 .. 9)*
;

可以看到ANTLR雖然是LL系的，但有直接支持左遞歸。這邊我就用了最直觀的左遞歸寫法。

測試輸入：

1 2 + 3 * 4 5 - +

得到的parse tree：

(prog
(expr
(expr
(expr
(expr 1)
(expr 2)
(op +)
)
(expr 3)
(op *)
)
(expr
(expr 4)
(expr 5)
(op -)
)
(op +)
)
&
)

圖形化顯示：

自問自答，貌似可以不通過左遞歸實現。就是把1 2 + 3 * 5 + 6 * 8 + 拆分成 1 2 + 和 [Terms Operator]*。

只是仍然好奇，有沒有辦法通過左遞歸實現？如果 pegjs 不行，那麼別的 peg 實現可以嗎。

{
function buildBinaryExpression(op, left, right) {
return {
type: BinaryExpression,
operator: op,
left: left,
right: right
}
}
}

Expression
= head:Term tails:(SubExpression)* {
return tails.reduce(function(prev, cur){
return buildBinaryExpression(cur.operator, prev, cur.right);
}, head);
}

SubExpression
= _ f:Factor _ op:Operator {
return {
operator: op,
right: f
}
}

Term
= head:Factor _ tail:Factor _ op:Operator {
return buildBinaryExpression(op, head, tail);
}
/ Factor

Factor
= Integer

Operator
= "+"
/ "-"
/ "*"
/ "/"

Integer "integer"
= [0-9]+ {
return parseInt(text(), 10);
}

_ "whitespace"
= " "

推薦閱讀：

※專業書籍，應該怎樣筆記？怎樣看？
※Parser Combinator 在語法解析的當中處於怎樣的位置?
※基於中間代碼的優化中 循環的查找演算法有哪些呢 循環的優化方法又有哪些？
※KLEE到底是靜態分析工具還是動態分析工具？
※如何理解基於CFL-reachability的過程間分析？

TAG:編譯原理 |