求SELECT集的方法如下:
定义
给定上下文无关文法 \(A \rightarrow \alpha\), \(A \in V_N\), \(\alpha \in V^*\), 若\(\alpha\)不能推导出\(\epsilon\),则\(\text{SELECT}(A \rightarrow \alpha) = \text{FIRST}(\alpha)\);
如果\(\alpha\)能推导出\(\epsilon\),则\(\text{SELECT}(A \rightarrow \alpha) = (\text{FIRST}(\alpha) - \{\epsilon\}) \cup \text{FOLLOW}(A)\)。
求解步骤
情况1:如果\(\alpha\)不能推导出\(\epsilon\),则\(\text{SELECT}(\alpha) = \text{FIRST}(\alpha)\)。
情况2:如果\(\alpha\)能推导出\(\epsilon\),则\(\text{SELECT}(\alpha) = \text{FIRST}(\alpha) - \{\epsilon\} \cup \text{FOLLOW}(A)\)。
注意事项
SELECT集是针对产生式而言的。
示例
假设有文法 \(G = \{S \rightarrow aSb, S \rightarrow \epsilon\}\),求\(\text{SELECT}(S \rightarrow aSb)\)。
分析
\(\alpha = aSb\)
\(\text{FIRST}(aSb) = \{a\}\)(因为\(a\)是第一个符号)
\(\text{FOLLOW}(S) = \{b\}\)(因为\(S\)在\(\epsilon\)之后)
应用公式
\(\text{SELECT}(S \rightarrow aSb) = (\text{FIRST}(aSb) - \{\epsilon\}) \cup \text{FOLLOW}(S)\)
\(\text{SELECT}(S \rightarrow aSb) = \{a\} \cup \{b\} = \{a, b\}\)
因此,\(\text{SELECT}(S \rightarrow aSb) = \{a, b\}\)。
建议
在求解SELECT集时,首先要明确每个产生式的左部非终结符和右部符号串。
然后根据FIRST和FOLLOW集合的定义,分别计算每个右部符号串的FIRST集合和整个产生式的FOLLOW集合。
最后根据公式计算SELECT集合。