编译原理(2)语法分析

正文索引 [隐藏]

编译原理:语法分析

一、抽象模型:PDA

Pushdown Automation,下推自动机,和有限自动机相比,除了有限状态组成部分外,还包括一个长度不受限制的栈,状态迁移不但包括有限状态的变迁,还包括一个栈的出栈或入栈过程,所以 PDA 也分为确定 PDA(DPDA) 和非确定 PDA,分别对应 DFA 和 NFA

1. 构成

$$
(Q,\Sigma,\Gamma, \delta, q_0, Z_0, F)
$$

  • Q:有穷状态集和

  • Σ:输入字母表

  • Γ:栈字母表(新增)

  • δ:迁移函数

    δ(现态,输入字符,弹出栈顶) = {(次态,压入栈顶)}, 比如:
    $$
    \delta(q, 0, Z_0) = {(q,XZ_0)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
    $$

  • q0:初始状态

  • Z0:开始符号(新增)

  • F:终结状态集合

2. 状态图

和 DFA, NFA 的状态转移图很像,仅仅是在输入字母后面加上了对栈的操作,“/” 左边表示栈顶弹出符号,右边表示压入栈符号 ,下面是一个典型的无法用有限自动机表示的语言(R 表示串反序排列):
$$
L = {w#w^R, w\in {0, 1}^*}
$$
分析下,这个东西无法使用有限自动机翻译的原因是有限自动机记不住之前自己干了啥,而 PDA 利用栈就能轻松解决这个问题:

PDA举例

上面的实现核心要领是当接收到 # 的时候 PDA 知道要换状态了,那么如果是这样的:
$$
L = {ww^R, w\in {0, 1}^*}
$$
其实也很好实现,空转移大法好:
PDA举例2

再来一个感受一下:
$$
L = {0^n1^m0^m1^n\ |\ n \ge 0, m \ge 0}
$$
PDA举例3

总结:PDA 的关键就是在寻找“转折点”,每到转折点就会跳转到另一个状态进行其他操作,如果转折点不好找也可以使用空转移代替,PDA 本质上仅仅是 DFA、NFA 加了一个栈用来存储前的操作而已。

3. 不同的终结方式

再仔细看看上面构造 PDA 的套路,一开始将一个 \$ 压入栈,最后将 \$ 弹出进入终结状态,可以理解这样做是为了扫描栈是否为空(\$ 代表着“栈底”这个概念)。

那么如果一开始不将 \$ 压入,最后也就不用弹出,虽然这样会缺少终结状态,但是只要判断栈是否为空就行(为空接受,反之拒绝),这样就可以看出有两种不同的终结方式:

  • 以终结状态定义 Pf
  • 以空栈定义 Ps

Pf -> Ps

  1. Pf 进入终态时栈不空

    引入一个新的状态,完成清栈工作

  2. Pf 未进入终态,栈空

    将 \$ 压入栈作为栈底避免发生这种事情

4. 瞬时描述(ID,Instantaneous Description)

这个东西就是用来描述某个瞬间 PDA 处于什么状态的
$$
(q, w, \alpha)
$$

  • q:当前状态
  • w:剩余输入串
  • α:栈,栈顶在最左边
  • |-:转移,描述一次操作

举个例子,PDA 如下(这个是以 Z0 作为栈底的):
$$
\ \ \ \ \ \ \ \ \delta(q, 0, Z_0) = {(q,XZ_0)}
$$

$$
\ \ \ \ \ \delta(q, 0, X) = {(q,XX)}
$$

$$
\delta(q, 1, X) = {(p,\varepsilon)}
$$

$$
\delta(p, 1, X) = {(p,\varepsilon)}
$$

$$
\ \ \ \ \ \ \delta(p, \varepsilon, Z_0) = {(f,Z_0)} \
$$
那么0001111的推导过程如下:
$$
(q,0001111,Z_0)
|-\ (q,001111,XZ_0)
|-\ (q,01111,XXZ_0)
|-\ (q,1111, XXXZ_0)
$$
$$
|-\ (p, 111, XXz_0)
|-\ (p, 11, XZ_0)
|-\ (p, 1, Z_0)
|-\ (f, 1, Z_0)
$$
拒绝,栈空而串未消耗完

二、语法模型:上下文无关文法(CFG)

1. 构成

和正则文法类似,上下文无关文法(CFG, Content Free Language)也长这样:
$$
(V,T,P,S)
$$

  • V:变量(非终结符)
  • T:终结符
  • P:产生式
  • S:开始符号

只不过这种文法是通过 PDA 定义的

2. 最左与最右推导

由于上下文无关文法比正则文法复杂得多,一个产生式中会出现多个非终结符,那么在分析的时候,先推导哪个非终结符就成了一个问题,最常用的两种模式是最左推导、最右推导,分别从最左(最右)边的非终结符开始推导,假设有文法:
$$
S\rightarrow SS\ |\ (S)\ |\ ()
$$
最左推导:
$$
S=>SS=>(S)S=>(())S=>(())()
$$
最右推导:
$$
S=>SS=>S()=>(S)()=>(())()
$$
可以发现,最左推导、最右推导的推导步骤是等长的,事实上,所有最左推导和相应的最右推导都是等长的

3. 语法树/分析树

语法树是一种使用树状结构表现分析过程的树:

  • 叶子:终结符或者 ε
  • 结点:变量
  • 根:开始符号
  • 产物:从左到右将叶子连起来

比如:
$$
S\rightarrow SS\ |\ (S)\ |\ ()
$$
分析 (())() 这个串的过程就可以表示为
语法树

这也解释了为什么最左推导和最右推导等长的问题,因为分析过程都是这一颗树。

当一个文法对每个合法串进行分析的时候有且只有一棵分析树的时候,这个文法就是无二义性的,否则文法就存在二义性,比如,上面的文法就是有二义性的,它对 ()()() 的分析存在两个分析树:
二义性文法
这种情况将会很大程度上影响之后的语法分析,因为计算机只认识一条路,所以希望我们的文法都是无二义性的

4. CFG 的化简 与 CFG 标准化

在CFG的定义中,没有对产生式的右部做任何限制。

事实上,在某些情况下,产生不良的影响。(对语法分析树的产生及成员判定算法的设计)

因此对文法的产生式的形式进行一定的限制,会对实际应用带来方便。
另一方面,也可简化文法。

1. 消除无用产生式

无用产生式在分析的时候不可能用得上,消除无用产生式可以简化文法表达

无用符号: 非生成变量 + 不可达变量

  • 非生成变量:推导不出来完整字符串的变量
  • 不可达变量:无法从开始符号推导出来的变量

消除无用产生式的步骤

step1. 消除非生成符

核心思想是找到生成符,算法如下:
消无用产生式1

然后,直接删除非生成符的产生式

step2.消除不可达符

核心思想是找到可达符号,算法如下:
消无用产生式2

然后,直接删除不可达符号的产生式

!!!注意,一定先删除非生成符再删除不可达符,否则无用符合可能删不干净

2. 消 ε 产生式

消去 ε 产生式能够方便文法的设计, 利于文法规范化,除了文法不能产生字符串 ε 外,不会影响到原文法相应的语言中其它字符串的产生.

ε 产生式:能推出 ε 的产生式

可置空符号:单次或多次推导能够产生 ε 的产生式

消除 ε 产生式的步骤

step1. 找出可置空符号集 N'

step2. 构造新文法的产生式
消空产生式

举例
消空产生式2
注意,消除 ε 产生式后的文法和原文法并不等价,差别有且仅有不能产生空字符串

3. 消单产生式

单产生式可消除文法二义性,但是大量单产生式将增加分析的步骤,消除单产生式可以提升文法的效率

单产生式:单一变量推导出单一变量的产生式,如 A -> B

单元偶对:变量 A 经过单次或多次推导能产生的单一变量都是 A 的单元偶对(包括 A 自身)

消除单产生式的步骤

step1. 寻找单元偶对 N

step2. 构造新文法产生式
消单产生式

举例
消单产生式2

4. Chomsky 范式

定义
Chomsky范式

构成步骤

step1. 消除无用符号、ε 产生式、单产生式

step2. 构建范式
Chomsky范式2

举例
Chomsky范式3

三、自上而下的语法分析设计

自上而下的含义是语法分析器在工作时,一开始是一个开始符号,逐步推导,直到推导出目标串(目标串合法的情况下),自上而下分析就是最左推导的过程

1. LL(1) 文法

当一个文法是 LL(1) 的时候才方便构造器相应的语法分析器,如果文法不是 LL (1) 的,就需要转化成 LL(1) 的再进行接下来的操作,而要理解这个文法,理解 FIRST 和 FOLLOW 集这两个概念是至关重要的:

FIRST 集合 和 FOLLOW 集合

FIRST 集合
$$
FIRST(\alpha)={b\ |\ \alpha =>^*\ b}
$$
表达意思是非终结符的下一步推导出来的第一个终结符的集合,LL(1) 分析的时候要判断当前变量要向哪个方向推导,使用的办法就是看当前分析串首字符在哪个 FIRST 集合中,从而判断使用什么产生式进行推导。

求取方法:
求FIRST集合

FOLLOW 集合
$$
FOLLOW(A) = {a\ |\ S => ^ \alpha Ab\beta,\ b\in T,\ \alpha,\ \beta\ \in V^}
$$
表达的意思是未来紧接着这个非终结符后面的终结符的集合,这个东西是用在如果一个变量推导为空串的情况,这个时候字符串首字母就不会在这个变量 FIRST 集合中,而是会在紧接着这个变量的下一个变量的 FIRST 集合中,也就是当前变量的 FOLLOW 集合中

求取方法:
求FOLLOW集合

LL(1) 文法的条件

LL(1) 文法分析的关键在于“预测”,那么就要求分析器能够根据当前情况判断出唯一的一条推导路线,那么一个 LL(1) 文法就一定不能有以下冲突,用一条简单的具有代表性的产生式举例:
$$
A \rightarrow \alpha\ |\ \beta
$$

① FIRST & FIRST 冲突

这个冲突的出现一般表现是文法出现回溯,也就是 FIRST(α) ∩ FIRST(β) ≠ Φ,比如说 FIRST(α),FIRST(β) 都有一个终结符 a,那么当变量 A 碰到 a 的时候是使用 A->α 还是 A->β ?如果出现这种文法,一般可以通过消除左递归、回溯的方法消除 FIRST & FIRST 冲突

② FIRST & FOLLOW 冲突

这个冲突是指当 ε ∈ FIRST(A) 的时候,FIRST(A) ∩ FOLLOW(A) ≠ Φ ,这个问题是在说明,比如说 FIRST(A),FIRST(B) 都有一个终结符 a,那么当变量 A 碰到 a 的时候是使用 A 中的某条产生式还是将 A 推导成 ε 然后使用 A 后面紧接着的变量推导出 ε?

文法转化为 LL(1) 文法

下面的两种方法仅仅是尝试消除冲突,如果方法用完后还存在冲突,文法多半是存在二义性的,就得考虑重构文法消除二义性后再进行转化

i. 左递归

产生式 P -> Pα 在分析推导的时候无限循环(重复使用这个产生式得到.....PPPPPPPPPPα),这个东西就比较麻烦,需要消除

step 1. 消除直接左递归

原规则:
$$
P \rightarrow P\alpha_1\ |\ P\alpha_2\ |\ ...|\ P\alpha_m\ |\beta_1\ |\beta_2\ |\ ...\ |\beta_n\
$$
消除直接左递归:
$$
P \rightarrow \beta_1P'\ |\ \beta_2P'\ |\ ...|\ \beta_nP'\ \ \ \ \ \ \
P' \rightarrow \alpha_1P'\ |\ \alpha_2P'\ |\ ...|\ \alpha_nP'\ |\ \varepsilon
$$
要领就是原本无左递归的部分后接 P’,有左递归的部分移到 P’ 后接 P’,P’ 一定包含 ε

step 2. 消除间接左递归

  1. 排序:把文法 G 所有非终结符按照任意顺序排列
  2. 依次代入:按照 1 中的顺序把非终结符依此代入,并且消去直接左递归
  3. 化简:消去不可达状态

举例:

文法:
消左递归1

  1. 排序:R,Q,S

  2. R 代入 Q,无直接左递归

    消左递归2

  3. Q 代入 S
    消左递归3

  4. 消直接左递归
    消左递归4

  5. 消不可达状态
    消左递归5

ii. 回溯

​ 回溯这种情况相当普遍,当文法对应的 PDA 出现不确定性的时候就会出现回溯,因为这种情况相当于出现了"岔路",计算机要遍历这些“岔路”才能决定真正走哪条路分析(抑或是所有路都不通,则拒绝串,表现为语法错误)

​ 一般通过对变量的终结首符集(FIRST 集合)的观察判断文法是否存在回溯,FIRST 集合定义如下(α 表示任意非终结符):
$$
FIRST(\alpha)={b\ |\ \alpha =>^*\ b}
$$
表达意思是非终结符的下一步推导出来的第一个终结符的集合

那么无回溯的条件就是:
$$
若 A \rightarrow \alpha_i\ |\ \alpha_j,\ 则: \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ FIRST(\alpha_i) \cap FIRST(\alpha_j) = \emptyset
$$
道理是,所有 A 的候选经过多次推导后得到的终结符集合都不一样,这样保证了每条路线的“未来”不会交织,就一定没有回溯

**如何消回溯?——提取公共左因子原规则:
$$
A\rightarrow \delta\beta_1\ |\ \delta\beta_2\ |\ ...\ |\ \delta\beta_n\ |\ \gamma_1\ |\ \gamma_2\ |\ ...\ |\ \gamma_m
$$
改写后:
$$
A\rightarrow \delta A'\ |\ \gamma_1\ |\ ...\ |\ \gamma_m\
A'\rightarrow \beta_1\ |\ \beta_2\ |\ ...\ |\ \beta_n
$$

2. 预测分析法实现语法分析

当一个文法符合 LL(1) 条件之后,就能够构造出来一个预测分析程序用来分析语法了,而这个预测分析程序的核心是一张预测分析表,这个表长这个样子
预测分析表

使用的时候没别的就是查表,看看最左边的变量是啥,再瞅瞅输入字符是啥,查表就知道要怎么推导了,那么这张神奇的表是怎么构造的呢?

i. 预测分析表的构造

构造的基本思想非常朴素:假设 A -> α 是一个产生式,a ∈ FIRST(α),则当 A 位于栈顶且输入符号为 a 的时候,α 就是 A 唯一合适的全权代表,体现在预测表中的(A,a)格中;而如果 ε ∈ FIRST(α) 时,说明这个变量可能推导向空串,那么此时输入符号 b 如果是紧挨着 α 的第一个终结符的话也是符合语法的,也可以这么推导。

根据上述思想,我们这么求预测分析表

  1. 把文法化成 LL(1) 的
  2. 列出文法中所有变量的 FIRST、FOLLOW 集合
  3. 对文法的每个产生式执行 4、5 步
  4. 对每侧终结符 a ∈ FIRST(α),把 A -> α 加到 M[A, a] 中
  5. 若 ε ∈ FIRST(α),则对任何 b ∈ FOLLOW(A),把 A -> α 加到 M[A, b] 中
  6. 所有表格中所有无定义的空白格是为“出错”

举个栗子:

对下面的文法 G:
上下无关文法示意

  1. 计算每个非终结符的 FIRST 和 FOLLOW
  2. 证明这个文法是 LL(1) 的
  3. 构造其预测分析表

解:

构造 FIRST

FIRST示例

构造 FOLLOW (诀窍是盯着生成式的右边看)

FOLLOW示意

预测分析表

预测分析表

诀窍:先扫一遍 FIRST 中的终结符,把该填的填了;然后把有 $\varepsilon$ 的变量找出来,看他们的 FOLLOW 集合,将这些交点全部填:
$$
V_T \rightarrow \varepsilon
$$

ii. 预测分析表的使用

根据以下预测分析表分析 i1 + i2 + i3
预测分析表2

分析过程
预测分析

3. 递归下降法实现语法分析

预测分析法规避了回溯这样的问题,直接查表的速度也很快,但是构造者的工作量就比较大,如果手头上设计编译器的编程语言支持递归(也就是能够回溯),就有一种很赖皮的办法了,不用动脑子直接无脑翻译就行了,把每个产生式的动作解释一遍,嵌套调用,这招叫做递归下降法,比如刚才构造预测分析法的例题:
上下无关文法示意

我们用 C++ 设计一个递归下降程序,非常容易,不过注意下当翻译 ε 有关的产生式的时候,写条件时只考虑 FOLLOW 集合中的就行,可以提升算法效率和代码难度:

void E(){
    T();
    E_();
}
void E_(){
    if (sym == '+'){
        advance();
        E();
    }
    else if (sym != ')' && sym !='#')
        erro();
}
void T(){
    F();
    T_();
}
void T_(){
    if (sym != '+' && sym !=')' && sym != '#')
        T();
}
void F(){
    P();
    F_();
}
void F_(){
    if (sym == '*'){
        advance();
        F_();
    }
    else if (sym != '(' 
             && sym != 'a' 
             && sym !='b'
             && sym !='^'
             && sym !=')'
             &&sym !='+'
             &&sym !='#')
        error();
}
void P(){
    if (sym == '('){
        advance();
        E();
        if (sym != ')')
            error();
    }
    else if (sym == 'a' 
             || sym == 'b'
             || sym == '^'){
        advance();
    }
    else
        error();
}

四、自下而上的语法分析设计

自下而上的含义是语法分析器在工作时,一开始就是整个字符串(终结符串),逐步归约,直到归约成出开始符号(目标串合法的情况下),自下而上的分析过程时最右推导的逆过程(因为是分析时是最左归约)
PS:这里的归约均指规范规约

1. 规范归约

人通过主观进行最右推导然后逆向以下就得到了规范归约(最左归约)的过程,但是给计算机一个串它是不知所措的,得想些办法让计算机也能进行规范规约,要理解怎么规范规约,得先了解以下几个概念:

​ 令 G 是一个文法,S 是开始符号,aβδ 是一个句型,若有
$$
S =>^{*}aA\delta\ 且\ A=>^{*}\beta
$$
​ 则 β 是句型 aβδ 相对于变量 A 的短语,特别是,若
$$
A=>\beta
$$
​ 则是直接短语,最左直接短语(分析树最左边的直接短语)称为句柄

Tips:找短语句柄画分析树比较好找

举例子分辨下:
句柄举例

一旦找到句柄,那计算机就可以操作了,每次只要归约句柄肯定没错:
规范规约举例

但是句柄不也是人为画个分析树然后靠直觉找出来的嘛,得像个办法让计算机自己找句柄,LR 分析法应运而生

2. LR 分析法实现语法分析

和自上而下分析中的预测分析法一样,也是编一张表,告诉计算机该如何归约,这个表比预测分析表复杂一些,先来了解它的用法,再来研究如何构造

PS: LR(0), SLR 的方法构造简单但是解决冲突的能力弱,LR(1), LALR 的方法非常麻烦但是是现在实际使用的编译器设计方法,由于学校期末考试不考,只总结 LR(0) 和 SLR

i. LR 分析表

LR分析表

ACTION[s, a]: 状态 s 面临输入字符 a 时的动作

  • 移进:某一栏写的是 sn,只需要移入字符,然后增加状态即可
  • 归约:某一栏写的是 rn,根据第 n 个产生式归约,注意状态栈也要根据 GOTO 栏转化
  • 接受:某一栏写的是 acc
  • 报错:空白栏

分析过程:分析输入串 i * i + i
LR分析举例

ii. LR(0) 法构造 LR 分析表

注意所有 LR 文法一定是没有二义性的!

首先了解一下活前缀,不含句柄之后任何符号的前缀(分析的时候栈中符号只要构成的是活前缀,就证明没有分析错,因为第一个归约的是句柄嘛,活前缀意味着还没有归约,而一旦不是活前缀了就意味着该归约了)

那我们就用点点来表示已经扫描的变量,然后判断已经扫描的是不是活前缀、该不该归约,比如:
$$
A\rightarrow .XYZ
$$
$$
A\rightarrow X.YZ
$$

$$
A\rightarrow XY.Z
$$

$$
A\rightarrow XYZ.
$$

可以看到扫描完成的时候就该将 XYZ 归约成 A 了,相当于这一个产生式有 4 个状态(这里称为项目),多个产生式之间进行有限状态的变化,想到了什么?就是有限状态机,我们请 NFA 帮助我们完成构造(务必要理解这里的 NFA 和编译过程一点关系都没有,是用来设计语法分析器这个 PDA 的),构造过程如下:

  • 开始符号 S’:仅在第一个产生式的左部出现

  • 终止状态:任何圆点在最右边的状态(识别为活前缀)

  • 状态迁移

    • 如果状态 i 和 j 出自同一个产生式,且状态 j 的圆点只落后于状态 i 的圆点一个位置,则从状态 i 或一条标志为 Xi 的弧到状态 j

    • 如果 i 圆点之后的符号为非终结符,如状态i:X -> α.Aβ,则从状态 i 画 ε 弧到所有 A-> . γ 状态

  • 确定化:将 NFA 转化为 DFA

举个栗子:
LR(0)构造举例1
LR(0)构造举例2
LR(0)构造举例3
LR(0)构造举例5

不过这么十几个状态 DFA 转换 NFA?Are you kidding ?私以为用下面这种惰性创建的办法比较好:

  1. 增加表达式 S' -> S (弄一个新的开始符号),这个产生式称为初态
  2. 求初态的闭包得到初态项目集,即求 CLOSURE(S' -> S)
  3. 对所得项目集 I 和文法 G 的每个文法符号 X(包括 T 和 V)计算 GO(I,X) = CLOSURE(J),得到新的项目集,其中 J = {任何形如 A -> α . X β ∈ I}

通过上面的步骤能得到一大堆项目(产生式集合)、GO 函数(点点向后扫描一个 X 会得到的项目),使用这些就能够构造 LR 分析表,构造方法如下:
LR(0)构造举例4
解释一下:

  • a、反正点点没有扫完一个句柄,不能归约,就进行移入操作
  • b、点点扫完啦,赶紧归约
  • c、都归约到开始符号了,当然接受了
  • d、完成归约表示点点已经扫过这个变量了,看看下一个状态是什么
  • e、没定义的状态表示错误、不接受

iii. SLR 分析法构造 SLR 分析表

LR(0) 的分析能力很弱,比如这样的冲突就没有办法解决:
$$
I ={X\rightarrow \alpha .b\beta,\ A\rightarrow\ \alpha .,\ B\rightarrow\alpha.}
$$
GG,扫描完 α 后,是继续移入字符呢,还是归约成 A 呢,还是归约成 B 呢?这就是 移入-归约 冲突和 归约-归约 冲突,SLR 可以有效地解决 归约-归约冲突。

基本思路:使用 FOLLOW 集合,考察下面一个输入符号(展望),确定具体 ACTION。上里中考察 FOLLOW(A) FOLLOW(B),若两个集合不相交,且都不包含 b,那么就可以进行如下归约

  • 若 下一个符号 = b,则使用第一个项目
  • 若 下一个符号 ∈ FOLLOW(A),则使用第二个项目
  • 若 下一个符号 ∈ FOLLOW(B),则使用第三个项目
  • 此外,报错

所以,项目集都不用改,只要在构造 SLR 分析表的时候将 b、 改为这样就行:
SLR 分析表构造
这就是归约完成之后简单进行了一下展望,看看 FOLLOW 集合判断该如何归约

SLR 的局限性还是很大的,比如移入-归约冲突、FOLLOW 集合交叉的 归约-归约冲突都无法解决,所以令人惊艳的 LR(1) 分析以及对它进行优化的 LALR 分析横空出世,大程度上解决了这类冲突问题,不过计算量 emmm,人手算是会死人的!我敬爱的老师布置了几道 LR(1) 的题让手算我去哦,一道题三小时,十几页稿纸,答案还不对,掀桌子,我就不作死总结了,期末狗命要紧

3. 算符优先分析法实现语法分析

不同于 LR 全家桶系列,算符有限分析法压根就不理会句柄那回事,是一个新的思路——靠比较运算符的优先级别进行归约,来看一看

i. 算符优先文法

算符文法:任一产生式的右部都不含两个相继(并列)的非终结符,即不含以下形式产生式右部:
$$
...QR...
$$
算符优先文法:如果一个算符文法的任何终结符对都至多满足下述三种关系之一:

  1. a = b,当且仅当产生式为以下形式的时候
    $$
    P\rightarrow ...ab... or ...aQb...
    $$

  2. a < b,当且仅当
    $$
    P\rightarrow ...aR... ,and\ R=> ^*Qb...or\ b...
    $$

  3. a > b,当且仅当
    $$
    P\rightarrow ...Rb... ,and\ R=> ^*aQ...or a...
    $$

直观理解下,在分析树离根结点越远的非终结符优先级别越高,因为它要多进行数次归约才能到达根部,所以当然应该先进行归约

ii. 优先表的构造

  1. 遍历候选式,找出所有 a = b 关系

  2. 构造 FIRSTVT 和 LASTVT
    $$
    FIRSTVT(P) = {a\ |\ P=>^{*} Qa...\ or\ a...,\ a\in V_T\ and\ Q\in V_N}
    $$
    $$
    FIRSTVT(P) = {a\ |\ P=>^{*} Qa...\ or\ \ ...a,\ a\in V_T\ and\ \ Q\in V_N}
    $$

    FIRSTVT:就是生成式从左向右第一个终结符

    LASTVT:就是生成式从右向左第一个终结符

    递归构造,很快就能得到

  3. 把 2 中的集合排个序

    假设有个产生式的候选形为
    $$
    ...aP...
    $$
    对任何 b ∈ FIRSTVT(P),都有 a < b

    假设有个产生式的候选形为
    $$
    ...Pb...
    $$
    对任何 a ∈ FIRSTVT(P),都有 a > b

实操一遍比啥都强,上例题:
算符优先分析1
算符优先分析2
算符优先分析3

iii. 使用优先函数代替优先表

实际应用中,不使用优先表而是用优先函数 f(入栈优先函数) 和 g(比较优先函数),每个终结符 θ 都对应一个 f 和一个 g,作用机理是这样的
$$
\theta_1 <\theta_2,\ then\ f(\theta_1)<g(\theta_2)
$$

$$
\theta_1 =\theta_2,\ then\ f(\theta_1)=g(\theta_2)
$$

$$
\theta_1 >\theta_2,\ then\ f(\theta_1)>g(\theta_2)
$$

  • 思路:将终结符与自然数对应,变得两两可以比较(但是这样做也会将原来不可比较的两个终结符变得可比,需要通过检查栈顶和输入符号来发现这种错误)

  • 构造方法

    算符优先分析4

附:语法分析器的自动产生工具 YACC

YACC 这个东西据说就是根据 LR 分析做的,不过是自动化的,感觉挺厉害的,考完研究考完研究。

传送门:[这个也还没建好呐]()