Bonky Zhu
If someone is able to show me that what I think or do is not right, I will happily change, for I seek the truth, by which no one was ever truly harmed. It is the person who continues in his self-deception and ignorance who is harmed.

编译原理 – 语法分析之自上而下的语法分析

image-20190926052411038

基本概念

对于语法分析,我们需要时刻考虑两个问题:对那个非终结符进行替换以及用哪个产生式进行替换

最左推导和最右推导很好理解,就是我们每次替换的是最左边的或者最右边的非终结符。同样地,最左和最右规约从左边或者右边对终结符进行规约,最右 (左) 规约可以看作对最左 (右) 推导的逆过程。最左推导和最右推导是唯一的,因为在当前推导过程中,最左非终结符和最右非终结符是唯一的。

因此,那什么是自上而下的语法分析呢?

  • 从推导的角度看,从开始符号出发,使用最左推导,试图推导出与输入符号串相同的句子。
  • 从语法树的角度看,从根节点出发,反复使用所有可能的产生式,谋求输入串的匹配,试图向下构造一棵语法树,其末端节点正好与输入符号串相同

自上而下的语法分析算法有:递归下降分析算法,LL(1)预测分析法。

自下而上的算法有算符优先分析法,LR分析法。自我们可以自上而下的语法分析是一种推导(Induction),而自下而上为是一种归约(Reduction)。

自上而下分析又可分为确定的和不确定的两种:

  • 不确定的分析方法称为带回溯的分 析方法,这种方法实际上是一种穷举的试探方法
  • 确定的分析方法不用回溯,需对文法有一定的限制,要求文法不能含有左递归,如LL(1)文法。

递归向下分析

每一个终结符都对应一个下面这样的函数:

image-20191104215341748

但是上面这种有一个缺点就是, 可能需要回溯,导致效率较低(因为可能有多个选择,比如有多个以 a 开头的,需要一个个试,直到证明不可行,即同一非终结符的多个候选式存在共同前缀,将导致回溯现象)

PS:下面是我编译实验课所写的一个代码的框架,可以看到一共有 E A B C 四个终结符,每个终结符就和上面所说,对应了一个类似的函数:

屏幕快照 2019-11-04 下午9.54.58

左递归

例如有这么一个文法:

E → E + T | E – T | T
T → T * F | T / F | F
F → (E) | id


输入串是这样子的:

id + id * id
?? 


一开始输入指针指向第一个id,程序会一直找,直到碰到终结符id。首先,程序先执行 E → E + T,然后发现还没到终结符id,然后继续递归 E → E + T + T,因为程序直到碰到了错误的终结符才会返回,但不过这样子一直碰不到终结符,然后程序一直不会返回,就会一直递归下去,所以要消除左递归。

消除简单左递归的方法

其实就是把左递归转换为右递归

# 直接左递归
A → Aα|β

# 右递归
A → βA’ 
A’ → αA’|ε


理解:由A可以推出一个β打头的字符串,所以由A最后推出的满足 A → βαα....。首先改成 A → βA’ 这样的右递归形式,然后根据右递归式可以得到 A’ 的式子 A’ → αA’|ε

一般形式如下:

image-20191104230931419

消除间接左递归

image-20191010084545815

消除步骤如下:(前提是不包含循环推导和空产生式)

image-20191010085056884

提取左公共前缀

S → aAd | aBe 可以改写为 S → aS' 和 S' → Ad | Be


image-20191104231645684

LL(1) 文法

在递归向下分析中,很容易出现回溯的情况,如果在分析的每一步我们都能预测出正确的选择,就不会有出现回溯的情况。 这样的分析方法叫做预测分析法,下面是预测分析法的定义:

预测分析法是从文法开始符号出发,在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a,选择正确的A的产生式。为保证分析的确定性,选出的候选式必须是唯一的。

S_文法

为了能够使用预测分析法,我们希望文法满足以下两个条件:

  • 每个产生式的右部都以终结符开始
  • 同一非终结符的各个候选式的首终结符都不同

这样的文法叫做S_文法,这样选出的终结符。注意,S_文法的产生式不包含空产生式。如果存在空产生式的情况,则会可能因为使用了空产生式而产生回溯。(任何输入指针指向的字符都可以匹配上空产生式,就说明有多种选择了)

那么我们在什么时候使用空产生式?

如果当前某非终结符A与当前输入符a不匹配时,若存在A→ε,可以通过检查a是否可以出现在A的后面,来决定是否使用产生式A→ε

假设有文法如下:

① S → aBC    ② B → bC     ③ B → dB  ④ B → ε
⑤ C → c    ⑥ C → a    ⑦ D → e


因为 B 后面的 C 只能取 a 和 c,所以说当输入符不为 a,c 的时候 B 不能取空产生式。这就是 FOLLOW集产生的意义,其中 FOLLOW(B) = {a, c}

FOLLOW集

非终结符A的后继符号集,即FOLLOW集,是在某个句型中紧跟在A后边的终结符a的集合

SELECT集

产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为SELECT( A→β )

q_文法

  • 每个产生式的右部为ε ,或者终结符开始
  • 具有相同左部的产生式有不相交的SELECT集,如下面的就是没有相交的SELECT集

屏幕快照 2019-11-05 上午12.17.53

注意,q_文法不含右部以非终结符打头的产生式。为了解决这个问题,出现了功能更强大的LL(1)文法。

FIRST集

串首第一个符号,并且是终结符。简称串首终结符。

给定一个文法符号串 α , α 的串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。如果 α 最终可以推出空产生式,那么 ε 属于 FIRST(α)

  • 如果 ε 不属于 FIRST(α) , 那么 SELECT(A→α) = FIRST(α) (不可能选择为空产生式)
  • 如果 ε 属于 FIRST(α), 那么 SELECT(A→α) = ( FIRST(α) - {ε} ) ∪ FOLLOW(A) (排除了产生空产生式的可能性)

LL(1)文法

文法G是LL(1)的,当且仅当G的任意两个具有相同左部的产生式 A → α | β 满足下面的条件(其实就是满足不相交的SELECT集的推导出来的结论,同一个终结符不能有多种选择):

  • 如果 α 和 β 均不能推导出 ε ,则 FIRST (α) ∩ FIRST (β) = Φ
  • α 和 β 至多有一个能推导出 ε (如果两个都能,说明他们的 SELECT 集都包含 FOLLOW(A) ,SELECT集一定有相交)
  • 如果 β 最终能推出 ε,则 FIRST(α) ∩ FOLLOW(A) = Φ,因为 β 的 SELECT 集包含 FOLLOW(A),因此,α 的SELECT 集不包含 FOLLOW(A),即交集为空。同理如果 α 最终能推出 ε,则 FIRST (β) ∩ FOLLOW(A) =Φ

所以我们知道,第一个 L 表示从左向右扫描输入,第二个 L 表示产生最左推导,“1” 表示在每一步中只需要向前看一个输入符号来决定语法分析动作。

语法分析的求解

文法符号FIRST集的求法

① E → TE'
② E' → +TE' | ε     
③ T → FT ' 
④ T' → *FT' | ε 
⑤ F → (E) | id


首先我们先找所有开头为终结符的,如 E'T'F

FIRST(E)  = {  }
FIRST(E') = { + }
FIRST(T)  = {  }
FIRST(T') = { * }
FIRST(F)  = { ( , id }


然后,如果能有空产生式,那么把 ε 加入产生式:

FIRST(E)  = {  }
FIRST(E') = { +, ε }
FIRST(T)  = {  }
FIRST(T') = { *, ε }
FIRST(F)  = { ( , id }


最后我们消除第一个为非终结符的元素:对于T,直接 FIRST(T) = FIRST(F) ,对于 E ,直接 FIRST(E) = FIRST(T),然后我们就可以得到每个元素的 FIRST 集如下:

FIRST(E)  = { ( , id }
FIRST(E') = { +, ε }
FIRST(T)  = { ( , id }
FIRST(T') = { *, ε }
FIRST(F)  = { ( , id }


串的FIRST 集的求法

  • FIRST(X1, X2, … ,Xn) 加入FIRST(X1)中所有的非ε符号,如果 ε 在 FIRST(X1) 中,再加入 FIRST(X2) 中的所有非 ε 符号;
  • 如果 ε 在 FIRST(X1)FIRST(X2) 中,再加入 FIRST(X3) 中的所有非ε符号,以此类推
  • 最后,如果对所有的 i,ε 都在 FIRST(Xi) 中,那么将 ε 加入到 FIRST(X1,X2,…,Xn)

非终结符A的FOLLOW(A)

还是上面的那个文法,求出的 FISRT 集如下:

FIRST(E)  = { ( , id }
FIRST(E') = { +, ε }
FIRST(T)  = { ( , id }
FIRST(T') = { *, ε }
FIRST(F)  = { ( , id }


我们首先先记住求 FOLLOW 集的一般步骤:

  • 取一条产生式,对产生式的每一个非终结符分析:
    • 对于非最右边的非终结符,FOLLOW 集加上下一个的终结符,或者下一个非终结符的 FIRST 集减去 ε
    • 如果下一个非终结符的 FIRST 集包括 ε,那么 FOLLOW 集再加上下一个非终结符的 FOLLOW
    • 对于为最右边的非终结符,FOLLOW 集加上结束符 #,产生式左边的 FOLLOW 集等于最右边非终结符的 FOLLOW 集,如 E → TE' ,恒有 FOLLOW(E) = FOLLOW(E') (能跟在E后面的,展开之后肯定也能跟在 E' 后面)
  • 继续向下取产生式,取到最底重新从头开始取产生式,直到各非终结符的 FOLLOW 集不在变化

SELECT集

  • 产生式右部第一个为终结符: SELECT 集就为这个终结符
  • 产生式右部第一个为 ε: SELECT 集就为产生式左部的 FOLLOW
  • 产生式右部第一个为非终结符:
    • 如果第一个的 FIRST 集不存在 ε, SELECT 集等于第一个的 FIRST
    • 如果第一个的 FIRST 集存在 ε, SELECT 集等于 (FIRST - {ε}) ∪ FOLLOW(A)

对于所有相同左部的产生式的 SELECT 集互不相交,那么这个文法是 LL(1) 文法 (每个非终结符展开都有唯一的选择)

预测分析表

屏幕快照 2019-11-06 上午12.29.15

Share

You may also like...

发表评论