文章 44
浏览 11238
编译原理笔记(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 | ε

       1FUNC A
       2BEGIN
       3    IF Sym in First(T)
       4    BEGIN
       5        T;
       6        E;
       7    END
       8
       9    ELSE IF Sym in First(B)
      10    BEGIN
      11        B;
      12        C;
      13    END
      14
      15    ELSE IF Sym in Follow(A)
      16    BEGIN END
      17    ELSE 
      18        Error;
      19END
      
    • 上述代码中

      1ELSE IF Sym in Follow(A)
      2    BEGIN END
      3    ELSE 
      4        Error;
      

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

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


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