parsing - 编译器，找到语法的第一组

Question

我正在阅读著名的紫龙书第二版，但无法从第 65 页获取有关创建第一组的示例:

我们有以下语法(终端以粗体显示):

stmt → expr;
| if ( expr ) stmt
| for ( optexpr ; optexpr ; optexpr ) stmt
| other

optexpr → ε
| expr

书上建议以下是 FIRST 的正确计算:

FIRST(stmt) → {expr, if, for, other} // agree on this

FIRST(expr ;) → {expr} // Where does this come from?

正如评论所暗示的，第二行来自哪里？

Answer 1

课本上没有错误。

定义了FIRST函数(在第64页，添加了强调):

Let α be a string of grammar symbols (terminals and/or nonterminals). We define FIRST(α) to be the set of terminals that appear as the first symbols of one or more strings of terminals generated from α.

在这个例子中，expr ;是一串由两个终结符组成的语法符号，因此它是α的一个可能值。由于它不包含非终结符，因此它不能只生成自身；因此，从该 α 值生成的唯一终结符字符串正是 expr ;，并且是出现在 FIRST(α) 中的唯一终结符是该字符串中的第一个符号，expr。

这似乎都在强调显而易见的事情，但它引出了您引用的示例下的重要注释:

The FIRST sets must be considered if there are two productions A → α and A → β. Ignoring ε-productions for the moment, predictive parsing requires FIRST(α) and FIRST(β) to be disjoint.

由于 expr ; 是 stmt 可能的右侧之一，我们需要计算它的 FIRST 集合(即使在这种情况下，计算是微不足道的)，以便测试这个先决条件。