first集_编译原理中FIRST集和FOLLOW集是什么东西?
时间: 2024-03-30 09:38:33 浏览: 23
在编译原理中,FIRST集和FOLLOW集是用于描述文法的一种符号集合。
首先,FIRST集表示一个文法符号能够推导出的所有可能的字符串的首字符集合。对于一个文法符号,它的FIRST集包括以下内容:
1. 如果这个符号是一个终结符(即不再能够被进一步推导的符号),那么它的FIRST集就是该终结符本身。
2. 如果这个符号能够推导出一个或多个以终结符开头的字符串,那么它的FIRST集就包括这些字符串的首字符。
3. 如果这个符号能够推导出一个或多个以非终结符开头的字符串,那么它的FIRST集就包括这些非终结符的FIRST集。
其次,FOLLOW集表示一个文法符号在某个产生式中的右侧能够紧随其后的所有可能的符号集合。对于一个文法符号,它的FOLLOW集包括以下内容:
1. 如果这个符号是文法的开始符号,那么它的FOLLOW集就包括文法的结束符号。
2. 如果这个符号在某个产生式的右侧能够紧随其后,那么它的FOLLOW集就包括该产生式左侧符号的FOLLOW集。
3. 如果这个符号在某个产生式的右侧能够紧随其后,且该符号右侧的字符串能够推导出 ε(即空串),那么它的FOLLOW集就包括该产生式左侧符号的FOLLOW集。
相关问题
编译原理中first集follow集和FIRSTVT,LASTVT区别及举例
首先,First集和Follow集是在语法分析中用到的概念,而FIRSTVT和LASTVT是在语义分析中用到的概念。
First集表示一个产生式的右部第一个终结符号集合,Follow集表示一个非终结符号在其所在产生式右部的后继位置上可能出现的终结符号集合。它们的作用是帮助语法分析器确定应该使用哪个产生式来扩展当前的非终结符号。
举个例子,假设有如下产生式:
```
E -> T + E | T
T -> int * T | int
```
则有:
- First(T) = {int}
- First(E) = {int}
- Follow(E) = {$, +}
- Follow(T) = {+, $}
FIRSTVT和LASTVT是用于计算三地址码中符号的值集合,它们的作用是帮助语义分析器确定表达式中各个符号的值。对于一个给定的运算符号,我们可以用FIRSTVT来计算它的左操作数的值集合,用LASTVT来计算它的右操作数的值集合。
举个例子,假设有如下三地址码:
```
1. t1 = a + b
2. t2 = t1 * c
3. d = t2
```
则有:
- FIRSTVT(1) = {a, b}
- LASTVT(1) = {a, b}
- FIRSTVT(2) = {t1}
- LASTVT(2) = {c}
- FIRSTVT(3) = {t2}
- LASTVT(3) = {t2}
通过计算FIRSTVT和LASTVT,我们可以得到每个运算符的左右操作数的值集合,从而确定表达式中各个符号的值。
编译原理 文法First集Follow集求解算法动态演示
文法的First集和Follow集是编译原理中的重要概念,它们可以用来帮助分析和处理文法,对于学习编译原理的同学来说是非常重要的。下面是一个简单的算法来求解文法的First集和Follow集:
1. First集求解算法动态演示
输入:文法G
输出:文法G的所有非终结符和对应的First集
步骤:
1. 初始化每个非终结符的First集为空集
2. 对于文法G中的每个终结符a,将a加入到对应的非终结符的First集中
3. 对于文法G中的每个产生式A -> B1B2...Bn,按照以下规则求出A的First集:
a. 如果B1是终结符或者空串,则将B1加入到A的First集中
b. 如果B1是非终结符,则将B1的First集中除空串之外的所有元素加入到A的First集中
c. 如果B1可以推出空串,则将B2的First集中除空串之外的所有元素加入到A的First集中
d. 重复上述过程,直到Bn的First集被处理完毕
4. 返回所有非终结符的First集
2. Follow集求解算法动态演示
输入:文法G和开始符号S
输出:文法G的所有非终结符和对应的Follow集
步骤:
1. 初始化每个非终结符的Follow集为空集
2. 将S的Follow集中加入$符号
3. 对于文法G中的每个产生式A -> B1B2...Bn,按照以下规则求出B1、B2、...Bn的Follow集:
a. 如果B1是非终结符,则将A的Follow集中除空串之外的所有元素加入到B1的Follow集中
b. 如果B1可以推出空串,则将A的Follow集中的所有元素加入到B2的Follow集中,重复此过程直到Bn的Follow集被处理完毕
c. 如果B1是终结符,则无需处理
4. 对于文法G中的每个产生式A -> B1B2...Bn,按照以下规则求出B2、B3、...Bn的Follow集:
a. 如果Bi是非终结符,则将Bi+1的First集中除空串之外的所有元素加入到Bi的Follow集中
b. 如果Bi可以推出空串,则将A的Follow集中的所有元素加入到Bi的Follow集中,重复此过程直到Bn的Follow集被处理完毕
c. 如果Bi是终结符,则无需处理
5. 返回所有非终结符的Follow集