第四章 语法分析
和的计算和定义
-
- 定义:被定义为从推导得到的串首符号的集合(其中是任意的文法符号)。
- 算法:求解的方法:不断应用以下规则,直到没有新的终结符号或空集被加入到任何集合中为止。
- 1)如果X是一个终结符号,那么;
- 2) 如果X是一个非终结符,且是一个产生式,在中且在所有的中,也就是说,经零步或者多步推导可以得出。如果对于所有的i= 1,2,...,k,在中,那么就将加入到.
- 3)如果是一个产生式,那么将加入到中
- 例子:
- 具体解题思路:求解文法中所有的产生式左部的FIRST集合,只需要看每个左部的所有产生式右部的首字符A。
- 1. 如果A是终结符,那么将其加入到左部对应的 集合中。
- 2. 如果A是非终结符,那么继续求解,并将加入到左部对应的集合中去。
- 3. 如果,那么也将加入其中。
- 注意:如果产生式的右部由“|”连接,对于"|"左右两边的句型运用上述相同的规则。
- 计算的集合
-
- 定义:可能在某些句型中紧跟在A右边的终结符号的集合。
- 求解所有非终结符A的集合时,不断应用以下规则,直到不再有新的终结符可以加入到任意的集合中为止。
- 1) 将(是输入右端的结束标记)放入到集合中,其中S为文法的开始符号
- 2)如果存在一个产生式,那么中除了之外的所有符号都在中。
- 3)如果存在一个产生式,或存在产生式且包含, 那么中的所有符号都在 中.
- 具体解题思路:求解所有非终结符的 集合:
- 1. 先将结束标记 加入到开始符号的 集中,即 = { ,...}。
- 2. 再将所有非终结符中能推导出的非终结符列举到一个集合中。
- 3. 紧接着对于非终结符B,观察文法中所有产生式的右部是否存在B,如果存在,则判断B在产生式中的句型:
- 如果是 ,直接将加入到中
- 如果是 ,则需要继续判断是否是终结符。
- 是 终结符,那么就将其加入到中
- 是 非终结符,那么就将加入到 中,接着判断该非终结符是否在第二步中的非终结符集合中:
- 不在则进行下一轮判断。
- 如果在,就将 加入到 中。
-
根据 和集构造表达式文法的可选集
- (day04)定义回顾:由于各个具有相同的左部的产生式的集不存在交集,故图片中表达式的文法是文法。
-
根据表达式文法的可选集构造预测分析表
附:FIRST和FOLLOW集合的计算从定义来看较为晦涩,可以根据要点中“具体解题思路”再反复刷题和观看视频进行理解!
标签:文法,终结符,加入,day05,编译,如果,集合,原理,左部 From: https://blog.csdn.net/m0_74985290/article/details/141905497