乐趣区

关于编译原理:编译原理与设计-41-自上而下分析法

jiezi

自上而下分析法

语法树的从左到右叶结点 =#，则 #∈L(G)。

1. 文法的逐级优化

  1. 打消左递归

    • 含有 A→Aa 模式产生式的文法：间接左递归
    • 两步或两步以上：间接左递归

    打消形式：

    • 写正规式→转化为右递归
    • 间接：先代入
  2. 提取左公因子
    通过改写产生式来推延决定

预测分析法的工作过程：
从文法开始符号登程，在每一步推导过程中依据以后句型的最左非终结符 A 和以后输出符号 a，抉择正确的 A - 产生式。为保障剖析的确定性，选出的候选式必须是惟一的。

  1. S_文法（简略的确定性文法）

    • 每个产生式的右部都以 终结符 开始
    • 同一非终结符的各个候选式的 首终结符 都不同
    • 留神：S_文法 不含 \(\varepsilon \)产生式

为了退出 \(\varepsilon \)产生式，须要看非终结符前面能跟什么终结符：FOLLOW 集

新定义：

  • 非终结符 A 的后继符号集

    • 可能在某个句型中紧跟在 A 后边的终结符 a 的汇合，记为 FOLLOW(A)

  • 产生式的可全集

    • 产生式 A→B 的可全集是指能够选用该产生式进行推导时，对应的输出符号的汇合，记为 SELECT(A→B)

      SELECT(A→aB) = {a}
      SELECT(A→\( \varepsilon \)) = FOLLOW(A)

  1. q_文法

    • 每个产生式的右部或 为 \(\varepsilon \)，或 以终结符开始
    • 具备雷同左部的产生式有 不相交的可全集

q_文法不含右部以 非终结符 打头的产生式

新定义：

  • 串首终结符集

    • 给定一个文法符号串 a，a 的串首终结符集 FIRST(a)被定义为，能够从 a 推导出的所有 串首终结符 形成的汇合，包含 \(\varepsilon \)

  • 新 · 产生式的可全集

    • 产生式 A→B 的可全集是指能够选用该产生式进行推导时，对应的输出符号的汇合，记为 SELECT(A→B)

      如果 \(\varepsilon \notin FIRST(a) \)，那么 SELECT(A→a) = FIRST(a)
      如果 \(\varepsilon \in FIRST(a) \)，那么 \(SELECT(A→a) = (FIRST(a)-\varepsilon) \cup FOLLOW(A) \)

  1. LL(1)文法

名称含意

  • 第一个“L”示意从左向右扫描输出
  • 第二个“L”示意产生最左推导
  • “1”示意在每一步中只须要向前看一个输出符号来决定语法分析动作

2. FIRST 集和 FOLLOW 集的计算

每一个都是循环应用，直到不再增大

  1. FIRST 集
    a. 找右侧第一个为终结符或空串
    b. 找右侧，从左至右，非终结符的 FIRST 集
  2. FOLLOW 集
退出移动版