爲什麼最多隻能看到1個輸入令牌？

Question

我目前正在嘗試實現LL解析器，但我有一個問題。 需要我最多預測1個輸入令牌，以驗證用戶的輸入 在語法上是正確還是出於其他原因？

Answer 1

有很多種不同的解析算法。你所描述的那個叫做LL（1），根據定義它只是使用一個前瞻符號。不過，還有其他的解析算法比這更使用更多的前瞻。例如，LL（2）解析器使用兩個令牌向前看，而一個LL（*）分析器則具有不受限制的向前看。有一些語法只能使用一個前瞻標記（即，LL（2），而不是LL（1））的語法。這裏有一個例子：

S → n | n + S

試着弄清楚爲什麼一個標記的lookahead是不夠的，但兩個標記足夠。

解析算法試圖保持低先行令牌數量的原因是爲了簡單和高效。隨着先行令牌的數量增加，驅動解析器所需的解析表的大小也增加，建立這些表的複雜度也會增加。