什么是前瞻符号？

Question

在语法中（例如LL(1)），1表示lookahed符号。实际上我不明白这个符号是什么。为了理解，我需要一个简单实用的例子。

Answer 1

LL(1)语法可帮助您立即决定将使用哪种语法规则。这个先行标记意味着您只需从您正在阅读的当前字符中读取下一个字符。

LL(1)语法可帮助您降低O(n)解析输入的复杂性并且没有回溯。

维基百科示例

让%成为您正在阅读的字符和要输入的字符串( a + a )

LL(1) 语法：

S -> F (Rule1)

S -> ( S + F ) (Rule2)

F -> a (Rule3)

解析表是：

    (   )   a   +   $
S   2   -   1   -   -
F   -   -   3   -   -

然后你有：

%( a + a ) （读取字符串的开头和lookahead是（，所以根据解析表决定应用Rule2）

抽象语法树现在是：

            S
        / / | \ \
       (  S + F  )

然后你消费(。你继续同样的方式。

第2步：

            S
        / / | \ \
       (  S + F  )
          |
          F
          |
          a

第 3 步：

            S
        / / | \ \
       (  S + F  )
          |   |
          F   a
          |
          a

您可以看到 Wikipedia 示例，它以完全相同的方式使用堆栈，而不是抽象语法树。