给定文法G【S】:S→S+S |SS|(S)|S*|a 计算该文法的FIRST和FOLLOW集。(注意:FIRST和FOLLOW的计算对象)
时间: 2023-09-22 22:07:31 浏览: 125
首先,我们需要理解什么是 FIRST 和 FOLLOW 集。
- FIRST 集:对于文法中的每个非终结符,找出它能够推导出的所有字符串的最左边(即最开始)的终结符。如果一个非终结符能够推导出 ε(空串),那么 ε 也应该包含在这个非终结符的 FIRST 集中。
- FOLLOW 集:对于文法中的每个非终结符,找出所有能够紧跟在它后面的终结符。如果一个非终结符在某个产生式的最右边,那么应该把这个非终结符后面的终结符添加到它的 FOLLOW 集中。同时,如果一个非终结符在某个产生式的中间位置,那么应该把它后面所有能够推导出 ε 的非终结符的 FOLLOW 集也加入到它的 FOLLOW 集中。
下面是文法 G【S】的产生式:
S → S + S | S S | (S) | S* | a
接下来分别计算该文法的 FIRST 和 FOLLOW 集。
FIRST 集的计算:
- FIRST(S) = { (, a }
- FIRST(S + S) = { (, a }
- FIRST(S S) = { (, a }
- FIRST((S)) = { ( }
- FIRST(S*) = { (, a }
- FIRST(a) = { a }
FOLLOW 集的计算:
- FOLLOW(S) = { $, ), + }
- FOLLOW(S + S) = { $, ), + }
- FOLLOW(S S) = { $, ), + }
- FOLLOW((S)) = { ), $, + }
- FOLLOW(S*) = { ), $, + }
- FOLLOW(a) = { ), +, $ }
其中,$ 表示输入串的结束符号。
阅读全文