共翁号
共翁号 > 经验 > select集怎么求

select集怎么求

原创2025-06-20 06:50:52

求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集合。

返回:经验

相关阅读

    最新文章
    猜您喜欢
    热门阅读