编译器,查找FIRST语法集

Question

我正在阅读着名的紫龙书第2版,并且无法从第65页获得关于创建FIRST集的示例:

我们有以下语法(终端加粗):

stmt → expr;
| if(expr)stmt
| for(optexpr; optexpr; optexpr)stmt
| 其他

optexpr→ε
| EXPR

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

FIRST(stmt)→{ expr,if,for,other } //就此达成一致

FIRST(expr;)→{ expr } //这是从哪里来的？

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

Answer 1

教科书中没有错误.

FIRST定义了该功能(第64页,增加了重点):

让α是一个语法符号串(终端和/或终结符号).我们定义FIRST(α)为一组终端,它们作为从α生成的一个或多个终端串的第一个符号出现.

在这个例子中,expr ; 是由两个终端组成的一串语法符号,因此它是α的可能值.由于它不包含非终结符,因此它不仅可以自己生成; 因此,从该α值产生的唯一一串终端是精确的expr ; ,唯一出现的终端FIRST(α)是该字符串中的第一个符号expr.

这可能都是显而易见的,但它引出了一个重要的注释,就在你引用的例子中:

FIRST如果有两个作品A → α,必须考虑这些集合A → β.暂时忽略ε-产生,预测解析需要FIRST(α)和FIRST(β)不相交.

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