语法分析

文法分类

  • 0型文法：又称短语文法
  • 1型文法：又称上下文有关文法
  • 2型文法：又称上下文无关文法
  • 3型文法：又称正则表达式

上下文无关文法

  • 结构：(VT,VN,S,P)(V_T,V_N,S,P)，其中VTV_T是终结符集合，VNV_N是非终结符集合，SS是开始符号，PP是产生式集合

  • 上下文无关文法允许产生式右部出现所有在产生式左部出现的非终结符

  • 推导：

    • 最左推导：每次展开都展开最左边的非终结符
    • 最右推导(规范推导)：每次展开都展开最右边的非终结符

  • 分析树：推导的树型表示

  • 二义性：存在多种推导的可能结果，例如产生式集合E→E+E∣E×EE\rightarrow E+E|E\times E

    • 消除二义性：通过引入中间非终结符解决：

      E→E+TT→T×T \begin{align} &E\rightarrow E+T \\&T\rightarrow T\times T \end{align}

    • 一般，优先级高的运算，其产生式应该离根更远

  • 消除左递归：在递归下降分析程序里，由于程序无法看到后续的记号，因此如果存在左递归会存在一个函数递归调用自身而不继续解析的问题

    • 消除直接左递归：A→Aα∣βA\rightarrow A\alpha|\beta

      A→βA′A′→αA′∣ϵ \begin{align} &A\rightarrow \beta A' \\&A'\rightarrow \alpha A'|\epsilon \end{align}

    • 消除间接左递归：{A→Bα∣βB→Aγ∣ϵ\begin{cases}A\rightarrow B\alpha|\beta\\B\rightarrow A\gamma|\epsilon\end{cases}

      实际上可以先转化为直接左递归：

      {A→Bα∣βB→Bαγ∣βγ∣ϵ \begin{cases}A\rightarrow B\alpha|\beta\\B\rightarrow B\alpha\gamma|\beta\gamma|\epsilon\end{cases}

  • 提取公共左因子：存在公共左因子会使程序不知道应该选择哪个，如果定死顺序则很可能出现错误分析

    提取公共左因子非常简单，只需要添加中间的非终结符即可：

    A→αA∣αBA→αCC→A∣B \begin{align} &A\rightarrow \alpha A|\alpha B \\&A\rightarrow \alpha C \\&C\rightarrow A|B \end{align}

分析法

自上而下分析LL(1)

  • LL(1)要求产生式集合没有二义性、没有左递归、没有公共左因子
  • 求first集合：
    • 终结符的first集合只有一个元素：它本身
    • 非终结符的first集合：
      • 先找到所有形如S→aα…S\rightarrow a\alpha\dots的产生式，其右部的开始符号是终结符
      • 再找到所有形如S→Aα…S\rightarrow A\alpha\dots的产生式，其右部的开始符号是非终结符，将first(A)−ϵfirst(A)-\epsilon加入first(S)first(S)
      • 如果在第二步，ϵ∈first(A)\epsilon\in first(A)，那么使first(α)−ϵfirst(\alpha)-\epsilon加入first(S)first(S)，继续本步骤
      • 如果在第三步，遍历到最后的符号且最后的符号的first集包含ϵ\epsilon，那么将ϵ\epsilon加入first(S)first(S)
  • 求follow集合：follow集合不包含ϵ\epsilon
    • 将$加入开始符号的follow集合里
    • 对所有A→αBβA\rightarrow \alpha B\beta，将first(β)−ϵfirst(\beta)-\epsilon加入follow(B)follow(B)
    • 对所有A→αBA\rightarrow \alpha B或A→αBβA\rightarrow\alpha B\beta且ϵ∈first(β)\epsilon\in first(\beta)，则将follow(A)follow(A)加入follow(B)follow(B)
  • 非递归的下降分析：要求构建分析表，则程序分析时不递归而是查找分析表找到对应的产生式
    • 行名为(栈顶的)非终结符，列名为输入符号，表格项为产生式
    • 对每个A→αA\rightarrow\alpha，对∀a∈first(α)\forall a\in first(\alpha)且a≠ϵa\ne\epsilon，使M(A,a)M(A,a)为这个产生式
    • 对每个A→αA\rightarrow\alpha，若ϵ∈first(α)\epsilon\in first(\alpha)，则对∀a∈follow(A)\forall a\in follow(A)使M(A,a)M(A,a)为这个产生式
    • 若运行时遇到表格项为空，说明程序分析出错
    • 若遇到一个表格项包含多个产生式，说明不是LL(1)文法
  • 错误恢复：
    • 词法错误
    • 语法错误
    • 语义错误
    • 逻辑错误
  • 同步选择集合：

自下而上分析

  • 句柄：和某个产生式右部一致的串
  • 移进归约分析：
    • 移进：将下一个符号入栈
    • 归约：将栈顶的整个句柄用对应的产生式归约，用产生式的左部替换这个句柄
    • 接受：到达目标串的结尾且分析表未出错
    • 错误：分析表到达了空表项
  • 移进归约冲突：栈顶的句柄可以继续移进，也可以归约的时候
  • 归约归约冲突：栈顶可以有多种归约可能情况
  • LR(0)(Left-to-right, Rightmost derivation, 0 lookahead)：非常容易产生移进归约冲突和归约归约冲突
    • 项目：一个产生式的右部的符号中间添加·符号
    • 项目集规范族：
      • 引入增广文法（添加产生式E′→EE'\rightarrow E指向开始符号）
      • 对扩展文法新增的产生式求E′→⋅EE'\rightarrow ·E闭包，即只要·后是非终结符则要把这个非终结符为左部的所有产生式加入闭包，递归进行此步骤
      • 对上述闭包可以移进的所有符号，进行移进得到新的项目集
      • 重复第二步和第三步直到构建出DFA
    • 从DFA构建LR(0)分析表：
      • 对Ix->Iy出边为终结符a的情况：ACTION[Ix, a]=sy
      • 对Ix->Iy出边为非终结符A的情况：GOTO[Ix, A]=y
      • 对Ix能够归约的项目(产生式编号为y，产生式左部为A)：对所有终结符a，使ACTION[Ix, a]=ry
      • 对归约项目为增广文法新增的产生式，使表项为acc
      • 使其余所有表项为error
    • 使用LR(0)分析表对输入进行语法分析：
      • 初始状态栈只有一个元素：I0
      • 设当前状态为Ix，输入符号为a，查询ACTION[Ix, a]：
        • 若为sy，则状态变为Iy，输入后移，Iy入栈
        • 若为ry，第y个产生式为A→αA\rightarrow\alpha，则从状态栈出栈，设出栈后栈顶状态为Iz则状态变为GOTO[Iz, A]
        • 若为error，则进入错误恢复程序
        • 若为acc，表示接受输入，语法分析成功
  • SLR分析表(SLR(1))：与LR(0)对比，引入了follow集合，对Ix能够归约的项目(产生式编号为y，产生式左部为A)：对所有a属于follow(A)，使ACTION[x, a]=ry
  • LR(1)分析表：
    • SLR(1)分析仍然会出现移进归约冲突
    • LR(1)分析对项目进行修改：使其带搜索符，例如A→⋅α,aA\rightarrow ·\alpha, a
    • 项目集规范族：
      • 增广文法产生的项目为E′→⋅α,#E'\rightarrow·\alpha, \#
      • 同样对扩展文法新增的产生式求A′→⋅Bα,aA'\rightarrow ·B\alpha, a闭包，即只要·后是非终结符则要把这个非终结符为左部的所有产生式加入闭包，递归进行此步骤，其中它们的搜索符是first(αa)first(\alpha a)
    • 生成分析表的过程和LR(0)的区别是：只对搜索符对应的表项设置为可归约项
  • LALR分析表：LALR在LR(1)的基础上，将略去搜索符后一致的项目族合并，因此和SLR拥有相似数量的项目族，但LALR可能出现归约归约冲突