我們可以把它分成兩部分。有一個用於括號表達式的規則,另一個用於乘法。
而不是維基百科文章,這是故意爲了解釋的目的而簡化的文章,我會按照Parsing Expressions by Recursive Descent這個更詳細的例子來處理括號內的表達式。
這是我用我的解析器可以與隱含乘法工作的代碼。我有多字母變量名稱,並使用空格來分隔不同的變量,所以你可以有「2 pi r」。
protected void expression() throws ParseException {
prefixSuffix();
Token t = it.peekNext();
while(t!=null) {
if(t.isBinary()) {
pushOp(t);
it.consume();
prefixSuffix();
}
else if(t.isImplicitMulRhs()) {
pushOp(implicitMul);
prefixSuffix();
}
else
break;
t=it.peekNext();
}
while(!sentinel.equals(ops.peek())) {
popOp();
}
}
這需要一些其他功能。
我使用一個單獨的標記化步驟,其破壞了輸入到離散的令牌。 Tokens
類有許多方法,尤其是Token.isBinary()
測試如果運算符是二元運算符,如+,=,*,/。另一種方法Token.isImplicitMulRhs()
測試令牌是否可以出現在隱式乘法的右側,這對於數字,變量名稱和左括號是成立的。
的Iterator<Token>
用於輸入流。 it.peekNext()
查看下一個令牌,並且it.consume()
移至輸入中的下一個令牌。
pushOp(Token)
將令牌推入運算符堆棧,popOp
刪除一個和。pushOp具有處理不同運算符優先級的邏輯。彈出操作者如果它們具有較低的優先級特別值得注意
protected void pushOp(Token op)
{
while(compareOps(ops.peek(),op))
popOp();
ops.push(op);
}
的是implicitMul
人工令牌具有相同優先級的乘法,其被壓入操作棧。
prefixSuffix()
處理表達式,它可以是數字和帶有可選前綴的後綴運算符的變量。這將識別「2」,「x」,「-2」,「x ++」,從輸入中刪除令牌並將其添加到輸出/運算符堆棧中。
我們可以認爲這個程序在BNF作爲
<expression> ::=
<prefixSuffix> (<binaryOp> <prefixSuffix>)* // normal binary ops x+y
| <prefixSuffix> (<prefixSuffix>)* // implicit multiplication x y
處理括號prefixSuffix()
完成。如果檢測到左括號,則它將遞歸調用expression()
。爲了檢測匹配的右括號,特殊的哨兵令牌被壓入操作員堆棧。當在輸入中遇到右括號時,主循環會中斷,並且操作員堆棧上的所有操作員都會彈出,直到遇到標記並且控制返回到prefixSuffix()
。代碼可能類似於
void prefixSuffix() {
Token t = it.peekNext();
if(t.equals('(')) {
it.consume(); // advance the input
operatorStack.push(sentinel);
expression(); // parse until ')' encountered
t = it.peekNext();
if(t.equals(')')) {
it.consume(); // advance the input
return;
} else throw Exception("Unmatched (");
}
// handle variable names, numbers etc
}