跳转至

算符优先文法及优先表构造

[!note] 算符文法 一个文法，如果其任一产生式的右部都不含有两个相继的非终结符，即不含有如下形式的产生式右部：\(\(\cdots QR\cdots\)\) 则，该文法被称为算符文法。

image.png

  • 编译原理重点 从算符优先文法G构造优先关系表的算法：

    • 通过检查G的每个产生式的每个候选是，可以找出所有满足\(a = b\)的终结符对
      1. \(a=b\)当且仅当文法G中含有形如\(P\rightarrow\cdots ab \cdots\)或\(P\rightarrow \cdots a Q b \cdots\)的产生式

    • 编译原理重点 确定满足\(<\)和\(>\)的所有终结符对：

      1. 首先需要对G的每个非终结符P构造两个集合\(FIRSTVT(P)\)和\(LASTVT(P)\)
        • \(FIRSTVT(P)=\{a|P\stackrel{+}{\Rightarrow}a\cdots,或P\stackrel{+}{\Rightarrow}Qa\cdots,a\in V_T而Q\in V_N\}\)
        • \(LASTVT(P)=\{a|P\stackrel{+}{\Rightarrow}\cdots a,或P\stackrel{+}{\Rightarrow}\cdots aQ, a\in V_T 而 Q\in V_N\}\)
      2. 获得了这两个集合后，就可以通过检查每个产生式的候选式确定满足关系\(<\)和\(>\)的所有终结符对：
        1. 假定有个产生式的一个候选形为：\(\(\cdots aP\cdots\)\)则对于\(b\in FITSTVT(P)\)，有\(a < b\)
        2. 假定有个产生是的一个候选形为：\(\(\cdots Pb\cdots\)\)则对于\(a\in LASTVT(P)\)，有\(a > b\)

    • 编译原理重点 \(FITSTVT\)和\(LASTVT\)的构造方法：

      • \(FIRSTVT\)：
        1. 若有产生式\(P\rightarrow a \cdots\)或\(P\rightarrow Q a\cdots\)，则\(a\in FIRSTVT(P)\)
        2. 若\(a\in FIRSTVT(Q)\)，且有产生式\(P\rightarrow Q\cdots\)则\(a\in FIRSTVT(P)\)
      • \(LASTVT\)（方法与\(FIRSTVT\)正好相反）：
        1. 若有产生式\(P\rightarrow \cdots a\)或\(P\rightarrow \cdots a Q\)，则\(a\in LASTVT(P)\)
        2. 若\(a\in LASTVT(Q)\)，且有产生式\(P\rightarrow \cdots Q\)，则\(a\in LASTVT(P)\)

算符优先分析算法

  • 设计：
    • 通过比较终结符间的优先关系来实现
    • 根据优先分析的原理：语法分析程序的任务是不断移进输入符号，识别可归约串并进行归约

      [!question] 如何识别可归约串？ 分析的基本方法：根据优先关系“高于”来识别可归约串的尾，根据优先关系“低于”识别可归约串的头 分析栈存放已经识别的部分，比较栈顶和下一输入符号的关系 如果是可归约串的尾，则眼栈顶乡下寻找可归约串的头，找到后弹出可归约串，归约为非终结符。 注：各种优先关系已经存在于优先关系表中。

[!note] 可归约串、句型、短语、直接短语、句柄、规范归约 - 一个文法G的句型的素短语是指：其至少含有一个终结符，并且，除它自身之外不在含有任何更小的素短语 - 最左素短语：值处于句型最左边的那个素短语

  • 特点：
    • 优点：简单、快速
    • 缺点：可能错误接收非法句子，能力有限

[!attention] 注意 - 算符优先分析只关心句型中自左向右的终结符序列的优先关系，不涉及终结符之间可能存在的非终结符，即可认为这些非终结符是同一个符号 - 算符优先分析比规范归约快，跳过了所有形如\(P\rightarrow Q\)的产生式所对应的归约步骤（这也是可能会出错的原因）