老师的PPT里面说消除左递归时也要消除$\epsilon$ϵ产生式，我对此存疑

概念

下推自动机(PDA)

预测分析

预测分析技术不是万能的

• 目的：一种确定性的、无回溯的分析技术, 在每一步都能够选择正 确的产生式
• 不是所有二型文法都能满足这个要求
• 有多个可能的产生式时预测分析法无能为力 — 可能需要回溯
  注意：不同Parsing技术只能分析CFG的一个子集

我们需要根据读头去选择特定的产生式，比如当前读头是a,占内符号是S，产生式有
$S\longrightarrow Ab$S⟶Ab$S\longrightarrow Ba$S⟶Ba$A\longrightarrow a|\epsilon$A⟶a∣ϵ$B\longrightarrow b$B⟶b
这个时候分析第一个产生式的Predict={a,b}，第二个产生式Predict={b}，所以选择第一个产生式进行替换。

• Predict集: 是相对于产生式而言的，指该产生式经过经过有限次替换，栈顶最先出现的终结符可能是什么。

• First($\alpha$α)

  • 输入$\alpha$α：由任意文法符号($V_T or V_N$VT​orVN​)组成的符号串(即产生式的右部)
  • 返回：可从$\alpha$α推导得到的串的首符号集合
  • Formal Definition: First($\alpha$α) = {a | $\alpha \Longrightarrow^* a\beta$α⟹∗aβ*, $a\in V_T$a∈VT​}, 特别地，如果 $\alpha \Longrightarrow^* \epsilon$α⟹∗ϵ 则 First($\alpha$α)= First($\alpha$α) $\cup$∪ {$\epsilon$ϵ}

• Follow(A) :

  • 输入A：非终结符号
  • 返回：可能在某些句型中紧跟在A右边的终结符号集合
  • 例如 S=>*αAaβ，终结符a就在Follow(A)中，c就在First(A)中

两种实现自顶向下语法分析的方法

• 递归下降法
• LL(1)法

LL(1)

向前只预测一个符号

• LL(1)语法充分必要条件
  • 一个文法G是LL(1)的， 当且仅当G中对A的任意两条产生式， A→α|β满足下面条件：
    • 不存在终结符号a使得α和β都可以推导出以a开头的串
    • α和β中最多只有一个可以推导出空串
    • 如果β=>*ε, 那么α不能推导出任何以Follow(A)中某个终结符开头的 串；类似地，如果α =>*ε, 那么β不能推导出任何以Follow(A)中某个 终结符开头的串
  • LL(1)：无二义，无左递归，无ε产生式
    其实就是：predict(A→ α)$\cap$∩ predict(A→ β)=$\varnothing$∅

LL(1)分析表

文法的改造

当文法的产生式存在左递归或公共前缀时，在无回溯的预测分析的时候会产生冲突， 需要对其进行变换，使之可以应用自顶向下的语法分析方法进行分析

• 提取左公因子
• 消除左递归(直接左递归和间接左递归)
• 消除$\epsilon$ϵ产生式

无ε产生式的CFG满足：要么P中不含有ε产生式，要么只有 S$\longrightarrow$⟶ ε; 若存在S$\longrightarrow$⟶ ε, 则S不出现在任何产生式右部
老师的PPT里面说消除左递归时也要消除$\epsilon$ϵ产生式，我对此存疑

• 文法简化

子问题

First 集计算

Follow集计算

Predict集计算

例：

消除左公因子

例： 对于$A\longrightarrow aS|ab$A⟶aS∣ab,改造成
$A\longrightarrow aA'$A⟶aA′$A'\longrightarrow S|b$A′⟶S∣b

消除直接左递归

例：

消除间接左递归

例：

消除$\epsilon$ϵ产生式

• 无ε产生式的CFG满足：要么P中不含有ε产生式，要么只有 S$\longrightarrow$⟶ ε; 若存在S$\longrightarrow$⟶ ε, 则S不出现在任何产生式右部
• 消除$\epsilon$ϵ产生式: 代入所有的$\epsilon$ϵ产生式
  
• 例：
• 

工作流