编译原理的FIRST集算法
时间: 2023-11-10 21:19:40 浏览: 121
编译原理中的求first集的方法
5星 · 资源好评率100%
编译原理中的FIRST集算法是用来计算文法符号的FIRST集的一种方法。它的基本思想是对于每个非终结符,找到它可能推导出的终结符的集合,即该非终结符所对应的所有产生式右侧第一个符号所对应的终结符的集合,并将其作为该非终结符的FIRST集的一部分。
具体的算法步骤如下:
1. 如果X是一个终结符,则FIRST(X)={X}。
2. 如果X是一个非终结符,则将其所有产生式右侧第一个符号所对应的终结符加入FIRST(X)中,直到找到一个产生式右侧的符号不是非终结符。如果该符号是一个空串,则将其 FOLLOW集也加入FIRST(X)中。
3. 如果X能够推导出空串,则将空串也加入FIRST(X)中。
4. 如果存在一个产生式A->α,其中α是一串符号序列,且α能够推导出空串,则将FIRST(α)中除去空串之外的所有终结符都加入FIRST(A)中。
5. 重复执行步骤2~4,直到所有FIRST集都稳定不变为止。
这样,就可以得到所有文法符号的FIRST集。通过FIRST集,可以方便地进行语法分析和语法制导翻译等操作。
阅读全文