编译-第04章-语法分析（一）

•
Compiler

编译-第4章-语法分析

把词法分析识别出来的token作为输入，输出是抽象语法树

描述体系上下文无关文法，2型文法

从左到右匹配

4.1 自顶向下分析方法

自顶向下分析思想

若Z⇒+S，则$S\in L(G[Z])$

存在的问题：左递归问题(U::=Ut)；回溯问题(U::=Ut|p)

主要的方法：递归子程序方法，LL分析法

自底向上分析思想

存在的问题：句柄的识别问题；若两个规则的右部有相同的符号串且构成句柄，规约的时候选择哪个

方法：算符优先分析法

4.1.1 带回溯的自顶向下分析法

一种试探，构造语法树，反复使用不同规则来匹配输入串

采用最左推导，因为我们对输入串的扫描是从左到右

  • 出现的问题：
    • 左递归必然会导致死循环
    • 回溯问题，影响效率，复杂的句子回溯的量非常大

4.1.2 存在的问题和解决办法

左递归问题

出现左递归文法：$U::=U…\ or \ U=>^+U…$

  • 消除直接左递归

    • 扩充的BNF范式，把递归的部分移到最右侧
      • 规则一（提左部因子）：$U::=xy|xz|…,\ =>\ U::=x(y|z|…)$
        • $U::=x|xy,\ =>\ U::=x(y|\epsilon)$，空放在最后的选择
      • 规则二：$U::=x|y|Uz,\ =>\ U::=(x|y){z}$
    • 把左递归改为右递归
      • $P::=Pa|b,\ =>\ P::=bP’,\ p’::=aP’|\epsilon$

  • 消除一般左递归

    • 调整顺序，下面的规则的右部包含上面规则的左部的非终结符
    • 从上到下的顺序依次消除左递归，然后往下代入
    • 删除多余的规则

    image

回溯问题

  • 某个规则右部有多个选择$U::=\alpha_1|\alpha_2|…$
  • 定义首符号集$FIRST(\alpha_i)={a|\alpha_i \overset{*}\Rightarrow a…,a\in V_t}$
  • 避免回溯：
    • 头符号集不相交
  • 消除回溯：
    • 改写文法
      • 反复对规则右部提取左公因子

        • $U::=xV|xW,\ =>\ U::=Z,\ Z::=V|W$

        • 继续看VW的头符号集

          image

4.2 梯度下降分析法

对文法中每个非终结符都编出一种子程序

4.3 基于递归下降分析法的语法分析程序构造

  1. 先消除左递归
  2. 消除回溯
  3. 设计算法框图
  4. 分析完一个字符后立刻读入下一个符号
    1. 当调用某个分析子程序时，他所要分析的第一个符号已经读进sym中；同样的，在从分析子程序返回报告成功之前，已经把跟在分析过的符号串之后的下一个符号读进sym中了
  5. 出错处理：语法错误