英文:

can't understand this LALR(1) parsing algorithm in aho & Ullman book

问题

The algorithm for computing the lookaheads](https://i.stack.imgur.com/T3Yzb.jpg)](https://i.stack.imgur.com/T3Yzb.jpg)

该算法用于计算前瞻符号。

The algorithm says to compute $CLOSURE( { [A \rightarrow \alpha . \beta , # ]}) $

该算法要求计算 $CLOSURE( { [A \rightarrow \alpha . \beta , # ]}) $。

In the worked out example above, When they compute closure of ${[
S^\prime \rightarrow .S ,#]} $ how come the item $[ L \rightarrow . * R, =/# ] $ has the dummy symbol $#$ as its lookahead when $ FIRST(=R#) = { = } $ contains only the $=$ terminal symbol?

在上述给出的示例中，当计算 ${[
S^\prime \rightarrow .S ,#]} $ 的闭包时，为什么项 $[ L \rightarrow . * R, =/# ] $ 的前瞻符号是虚拟符号 $#$，而 $ FIRST(=R#) = { = } $ 只包含 $=$ 终结符？

The closure algorithm provided in the book says the lookaheads of generated item will be FIRST($\alpha$) where alpha is the string of grammar symbols following the non-terminal from which the item is generated, but in the given example the string contains the terminal $=$ as the first symbol so the lookahead should just be $ = $ but the example shows the lookahead also containing $ # $ in addition to $ = $.

书中提供的闭包算法说生成的项的前瞻符号将是 FIRST($\alpha$)，其中 $\alpha$ 是从生成项的非终结符之后的文法符号字符串，但在给定的示例中，字符串以终结符 $=$ 作为第一个符号，因此前瞻符号应该只是 $ = $，但示例显示前瞻符号还包含了 $ # $ 除了 $ = $。

英文:

The algorithm for computing the lookaheads](https://i.stack.imgur.com/T3Yzb.jpg)](https://i.stack.imgur.com/T3Yzb.jpg)

The algorithm says to compute $CLOSURE( { [A \rightarrow \alpha . \beta , # ]}) $

In the worked out example above, When they compute closure of ${[
S^\prime \rightarrow .S ,#]} $ how come the item $[ L \rightarrow . * R, =/# ] $ has the dummy symbol $#$ as its lookahead when $ FIRST(=R#) = { = } $ contains only the $=$ terminal symbol?

The closure algorithm provided in the book says the lookaheads of generated item will be FIRST($\alpha) where alpha is the string of grammar symbols following the non terminal from which the item is generated, but in the given example the string contains the terminal $=$ as the first symbol so the lookahead should just be $ = $ but the example shows the lookahead also containing $ # $ in addition to $ = $.

答案1

得分: 1

以下是翻译好的部分：

你是正确的，S -> . L = R, # 仅对于 L -> . * R 的前瞻集合贡献了 =。

但是，R -> . L, # 也在 L -> . * R 之前有一个点，因此也导致了 L -> . * R 项目，并为该项目的前瞻集合贡献了 #。

英文:

You are correct that S -> . L = R, # contributes only = to the lookahead set for L -> . * R.

But R -> . L, # also has a dot before the L, so also leads to the L -> . * R item, and it contributes # to that item's lookahead set.