确定文法是否满足 LL(1) 要求
Determining if grammar meets LL(1) requirements
我有一个用于递归下降解析器的 BNF。解决这个问题的步骤之一是验证语法是否为 LL(1),但我一直想验证它不是。
有问题的 BNF,或者更具体地说,我遇到问题的确切区域:
<S> -> start <vars> <block>
<block> -> begin <vars> <stats> end
<vars> -> e | id = number <vars>
<stats> -> <if> | <block> | <loop> | <assign>
还有更多内容,但我相信这些是与这个问题相关的唯一作品。
我解决这个问题的方法是计算那些有选择的作品右侧的第一个。如果别无选择,我会跳过,因为我知道它们已经是 k=0.
FIRST(e | id = number <vars>) = {e, id} // Since it produces the empty set, I must also compute follow.
FOLLOW( e | id = number <vars> ) = FOLLOW(<vars>)
非终结符 'vars' 出现在 2 个作品中: and , 后面跟着两个非终结符:'block' 和 'stats'
FIRST(<block>) = {begin}
FIRST(<stats>) = { ... begin ... } // contains all terminals
现在,我的问题。在计算 FOLLOW() 时,我发现了两个开始标记,这让我说这个语法不是 LL(1)。但是,我不认为这个练习的答案是不可能创建递归下降解析器,所以我相信我在某处犯了错误或者我错误地执行了算法。
谁能指出我正确的方向?
所以你正确地发现 FOLLOW(var) = FIRST(block) ∪ FIRST(stats )。这些都是集合,因此当您计算前两个集合(每个集合包含 begin
)的并集时,您最终只会得到一个 begin
。只要这些集合都不包含 id
,一切都很好,你的语法仍然是 LL(1).
我有一个用于递归下降解析器的 BNF。解决这个问题的步骤之一是验证语法是否为 LL(1),但我一直想验证它不是。
有问题的 BNF,或者更具体地说,我遇到问题的确切区域:
<S> -> start <vars> <block>
<block> -> begin <vars> <stats> end
<vars> -> e | id = number <vars>
<stats> -> <if> | <block> | <loop> | <assign>
还有更多内容,但我相信这些是与这个问题相关的唯一作品。
我解决这个问题的方法是计算那些有选择的作品右侧的第一个。如果别无选择,我会跳过,因为我知道它们已经是 k=0.
FIRST(e | id = number <vars>) = {e, id} // Since it produces the empty set, I must also compute follow.
FOLLOW( e | id = number <vars> ) = FOLLOW(<vars>)
非终结符 'vars' 出现在 2 个作品中: and , 后面跟着两个非终结符:'block' 和 'stats'
FIRST(<block>) = {begin}
FIRST(<stats>) = { ... begin ... } // contains all terminals
现在,我的问题。在计算 FOLLOW() 时,我发现了两个开始标记,这让我说这个语法不是 LL(1)。但是,我不认为这个练习的答案是不可能创建递归下降解析器,所以我相信我在某处犯了错误或者我错误地执行了算法。
谁能指出我正确的方向?
所以你正确地发现 FOLLOW(var) = FIRST(block) ∪ FIRST(stats )。这些都是集合,因此当您计算前两个集合(每个集合包含 begin
)的并集时,您最终只会得到一个 begin
。只要这些集合都不包含 id
,一切都很好,你的语法仍然是 LL(1).