day05_编译原理学习

第四章 语法分析

和的计算和定义

• 

  • 定义：被定义为从推导得到的串首符号的集合（其中是任意的文法符号）。
  • 算法：求解的方法：不断应用以下规则，直到没有新的终结符号或空集被加入到任何集合中为止。
    • 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集合的计算从定义来看较为晦涩，可以根据要点中“具体解题思路”再反复刷题和观看视频进行理解！