自底向上优先分析

• 优先分析法
  • 简单优先分析法
    • 按一定规则求出该文法所有符号即包括终结符和非终结符之间的优先关系。
    • 实质是一种规范规约。
    • 准确，规范，但效率低。
    • 实用性不大。
  • 算符优先分析法
    • 只规定算符之间的优先关系，即仅终结符之间的优先关系。
    • 不是规范规约。
    • 不准确规范，但效率高。
    • 采用适当方法加以弥补缺点。

简单优先分析法

算符与普通=,>,<区别

算符有顺序，例如a·=b和b·=a不一样。

普通算符无顺序，例如a<b和b>a一样。

优先关系

• X ·= Y(A→…XY…)
  • S→bAa。b ·= A，A ·= a。
• X ·< Y(A → …XB…, B ⇨ Y…)
  • S→bAb，A +⇨ (B, A+⇨a。b ·< (，b ·= a。
• X ·> Y(A → …BD…, B +⇨ …X，D *⇨ Y…)
  • S→bAb，A +⇨ …), A+⇨B,A+⇨a。) ·> b，a ·> b， B ·> b。

定义

1. 在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。
2. 在文法中任意两个产生式没有相同的右部。

步骤

将输入符号串a1a…an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性·>下一个带输入符号aj为止。

栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1<·ak，为止。

由句柄ak…ai在文法产生式中查找右部尾ak…ai的产生式，若找到则用左部代替句柄，若找不到则为出错，断定不合法。

重复1，2，3.直到只剩开始符为止。

算符优先分析法

优先关系

和简单优先分析相比仅有终结符才能有优先级比较。其余优先符关系同于上式。

• a ·= b(A→…ab…或A→…aBb…)
• a ·< b(A → …aB…, B ⇨ b…或B ⇨ Cb…)
• a ·> b(A → …Bb…, B ⇨ …a或B ⇨ …aC)

定义

1. 若一文法G中不存在A→…BC…，其中B,C为非终极符，则G为算符文法。
2. G为不含ε文法，满足算符优先关系。
3. 若a与b之间只存在一种优先关系，则G为算符优先文法。

算符优先关系表构造

FIRSTVT(B) = {b | B +⇨ b…或B +⇨ Cb…}

LASTVT(B) = {a | B +⇨ …a 或B +⇨ …aC}

1. ·=：A→…ab…，若或A→…aBb…,则a·=b
2. ·<：A→…aB…，若b∈FIRSTVT(B)，则a·<b
3. ·>：A→…Bb…，若a∈LASTVT(B)，则a·>b

算符优先分析算法