文章 47
评论 4
浏览 11474
编译原理笔记(4)

编译原理笔记(4)

第四章

  1. 语法分析的前提

    1. 使用正规式和有限自动机描述了单词符号
    2. 使用上下无关文法描述了语法规则
  2. 语法分析的任务

    1. 分析一个句子的语法结构
    2. 根据语言的语法规则,判断输入的字符流能否构成一个句子
  3. 语法分析的方法

    1. 自下而上
      • 从输入串(语法树的叶子结点)开始进行规约,直到文法的开始符号
      • 算符优先分析法
      • LR分析法
    2. 自上而下
      • 从文法开始符号开始,反复使用各种产生式,寻找合适的推导
      • 从树的根节点开始构造语法树
  4. 文法左递归的消除

    • 直接左递归消除
      1. 形如P -> Pa | b的文法存在左递归
      2. 观察文法,发现该文法描述的是句子是:ba......a 其中a的个数为0-N
      3. 将左递归转化为右递归P -> bQ , Q-> aQ | ε
      4. 推广至形如P -> Pa1 | Pa2 | Pa3 ..... | Pan | b1 ..... | bm的文法则可转化为 P -> b1Q | b2Q ..... |bmQ , Q-> a1Q | a2Q | a3Q ..... | anQ
    • 间接左递归消除
      1. 形如S -> Qa | a , Q -> Rb | b , R -> Sc | c的文法存在间接左递归
      2. 依次替换非终结符S -> Rba | ba | a , S -> Scba | cba | ba | a
      3. 这时就从间接递归转换为直接递归,再将直接左递归转化为右递归
  5. 文法回溯的消除

    • 对于某些非终结符可以推出多个句型,匹配字符串时,并不知道该选择哪个句型进行匹配,如果匹配失败就必须进行回溯。
    • 所以必须对每个非终结符,求出他们的First集合和Follow集合
  6. First集合

    • 要求非终结符A的所有候选首符集两两不相交,这时在非终结符匹配一个字符a时, 就可以准确指派一个候选进行匹配
    • 要达到这种要求,就需要提取左公共因子image.png
  7. Follow集合

    • 有时候非终结符有ε候选,那么这时候是否进行替换,就需要根据Follow集合的内容进行替换
  8. LL(1)文法

    1. 文法不含左递归
    2. 对于每个非终极符的每个产生式的候选首符集两两不相交,若有相交则需要进行提取左公共因子进行化简,但是不一定会化简成功。
    3. 如果非终结符A可以推导出ε,那么要求First(A) Λ Follow(A) = ф
  9. 匹配LL(1)文法

    1. 对于一个字符a,若a ∈ First(A) ,则用A进行匹配
    2. 若没有首符集可以匹配
      1. A -> ε 并且 a ∈ Follow(A),则用A的ε候选进行匹配
      2. 否则匹配错误
  10. First集合求法
    3.jpg

  11. Follow集合求法
    2.jpg

  12. 自上而下语法分析

    1. 消除左递归
    2. 提取左公共因子,消除回溯
    3. 计算First集合和Follow集合
    4. 判断文法是否是LL(1)文法,如果是则用LL(1)匹配的方法,进行匹配
  13. 递归下降分析器

    • 每个非终极符对应一个子程序,每个终结符直接匹配

    • 例如A -> BcD匹配A时,首先调用识别B的子程序,再对c直接进行匹配,再调用识别D的子程序匹配

    • 其他

      • Advance 指针指向将要匹配的字符
      • Sym 待匹配字符
      • Error 出错处理
    • 例如文法 A -> TE | BC | ε

      FUNC A
      BEGIN
          IF Sym in First(T)
          BEGIN
              T;
              E;
          END
      
          ELSE IF Sym in First(B)
          BEGIN
              B;
              C;
          END
      
          ELSE IF Sym in Follow(A)
          BEGIN END
          ELSE 
              Error;
      END
      
    • 上述代码中

      ELSE IF Sym in Follow(A)
          BEGIN END
          ELSE 
              Error;
      

      这部分代码可以删去,这部分代码是在处理将A替换成ε的情况,ε相当于什么也不匹配,如果什么都不做,就相当于处理了空字ε。当前Sym表示的字符会交给后续的子程序进行匹配。

  14. 扩展的巴斯科范式
    image.png


标题:编译原理笔记(4)
作者:llym
地址:https://www.wendau.com/articles/2020/03/28/1585371721310.html

闻道

取消