3.1 介绍

句法分析(syntax analysis,也叫 parsing)将会使用词符作为输入,用来创建一个树状中间层,从而表示词符流的语法结构。

解析算法有两个大类。

自上而下:将输入流与语法生成式进行预测匹配。(推导)

自下而上:从单词序列进行累加,直到显然地与生成式匹配(规约)

3.2 句法的表示

对于多数语言,句法使用 CFG 表示。

为什么不用 RE

RE 只能记忆有限个状态,因此对于类似括号匹配这样状态无限的问题,规则式无能为力。

CFG

歧义问题

如 if-then-else 语句

Stmt -> if Expr then Stmt else Stmt
      | if Expr then Stmt
      | Asmt
      | ...(others)

语句:

if Exp1 then if Exp2 then Asmt1 else Asmt2

会产生歧义,两种理解方式如下:

if Exp1 then
    if Exp2 then
        Asmt1
    else
        Asmt2
if Exp1 then
    if Exp2 then
        Asmt1
else
    Asmt2

因此必须增加规则来消歧义。

例如下面的规则:

Stmt -> if Expr then Stmt
     |  if Expr then WithElse else Stmt
     | Asmt
WithElse -> if Expr then WithElse else WithElse
          | Asmt

这样相当于让 else 就近匹配。

运算符优先级的实现

规则:

[图]

增加优先级:

图 3.1

CFG 的分类

CFG 包含 LR (1) 包含 LL (1) 包含 RG

LL 解析器:一类自上而下的解析器,将输入从左向右解析,进行最左推导。

最左推导,即总是展开最左边的展开非终结符

LL (k) 中,k 表示前瞻符号的数量。

前瞻符号(Lookahead symbol):也就是除了目前处理到的输入符号之外,还得再向右引用几个符号

LR:是一类自下而上的解析器。即从左到右读入文本,然后从最右进行反向推导。能够在线性时间内无回溯地进行解析。

LR (k) 中 k 表示前瞻符号的数量

移位归约解析器(Shift-reduce parser):一种表驱动的自下而上解析器。

正规 LR 解析器(Canonical LR parser):即 LR (1) 解析器。

这些目前不好理解,先别管,往下学了就懂了。

3.3 自上而下解析

自上而下分析从解析树的根开始,向下扩展树,直到叶匹配扫描器返回的已分类的的单词。在每个时刻,都可以认为是在构建一棵部分树。

最左推导(Leftmost Derivation)

总是选择每个句型的最左非终结符进行替换。比如有一个句型 $E \to E + E$,要匹配 $\text {id} + (\text {id} + \text {id})$,则从替换箭头右边的(最左边)第一个 $E$ 开始:$E \to \text {id} + E$,这种过程是 最左推导。同理有最右推导。

如果 $S {\Rightarrow {}}^{*}_{\operatorname {lm}} \alpha$,则 $\alpha $ 是当前文法的 最左句型。(lm 表示最左推导)

最左规约是自下而上的解析中的规范规约,最右推导是其规范推导。

最左推导是唯一的

因为推导的每一步,当前生成式体的最左非终结符是唯一的(不存在无法抉择选择哪一个非终结符展开的问题)

自上而下解析的通用形式

递归下降分析:由一组过程(函数)组成,每个过程对应一个非终结符。

比如 $A \to X_1 X_2$,则:

function A(){
    // 下面假设 A 只有一种形式 A->X1X2X3...X
    // 也可能不止一种,那么就需要算法选择恰当的生成式,或者回溯分析
    for (let i: 1 to len(A)){
        // 是非终结符,则展开
        if (is_unterm(X[i])){
            call X[i]()
        }
        // 当前符号匹配成功
        else if(X[i] == currentToken){
            readNextToken()
        } else {
            throw SyntaxError()
        }
    }
}

预测分析

X 为了避免回溯,就需要向前提前拿到下一个词符,用来帮助选择合适的生成式。这叫做预测分析,提前拿到的词符称为前瞻符号(lookahead token)。

例子:

对下面文法,解析 id + id * id

$$ \begin{aligned} E \rightarrow & E+T \\ &\mid E-T \\ &\mid T \\ T \rightarrow & T * F \\ &\mid T / F \\ &\mid F \\ F \rightarrow & (E) \\ &\mid \text { id } \end{aligned} $$

由于 $E \to E + T$, $E$ 自依赖,导致无穷调用 $E$ 的 procedure。

这种情况称为 左递归。左递归可能是迭代多次才出现,这叫做间接左递归。

消除左递归

假设规则:$P\to Pa \mid b$,我们反复将 $Pa\mid b$ 代入其中的 $P$。

第一次得到 $(Pa|b) a|b$,去掉不确定的部分($Pa$)得到 $ba | b$

第二次得到 $((Pa\mid b) a|b) a|b$,去掉不确定的得到 $(ba|b) a|b$,也即 $baa|ba|b$。

后面不用算了,说白了就是 baaaaaaaaaa|baaaa|…..|baa|ba|b,规则式为 ba*

则 $P \to b | P^n a$,即 $P \to b^n a^*$,按教科书写法就是:

$$ P \to bT\\T\to aT \mid \varepsilon $$

这里非常蛋疼地拆成了两步,只是为了表示出匹配 0 或 N 次这个意思。

总结:左递归转右递归算法

$A \to A \alpha \mid \beta $,表示 $\beta \alpha ^*$,记作

$$ \begin{align} \alpha \to & \beta T \\ T \to & \alpha T \mid \varepsilon \\ \end{align} $$

推广:

对于 $A \to A \alpha _1 \mid A \alpha _2 \mid \cdots A \alpha _n \mid \beta _1 \mid \beta _2 \mid \cdots \beta _m$ 可转换为:

$$ \begin{align} \begin{aligned} &A \rightarrow \beta_{1} T\left|\beta_{2} T\right| \ldots \mid \beta_{m} T \\ &T \rightarrow \alpha_{1} T\left|\alpha_{2} T\right| \ldots\left|\alpha_{n} T\right| \varepsilon \end{aligned} \end{align} $$

【例子】消除左递归之于 E ::= E + T | E - T | T

解:

第一步把 E 变成 E' E ::= E' + T | E' - T | T

第二步把没 E 的扯到左边去:E ::= TE'

第三步把有 E 的扯到左边去:E ::= TE' E' ::= + T E' | - T E'

第四步加上 $\varepsilon$:E ::= TE' E' ::= + T E' | - T E' |""

image-20211118221402692

提取左公因子法(Left Factoring)

例如: $S \to aAd \mid aBe$ 改写为 $S \to a T; T \to Ad \mid Be$

3.4 自上而下的 LL (1) 文法

S 文法(简单的确定性文法):

  • 任何产生式体最左均为终结符
  • 任何非终结符的各候选式无相同的首终结符。

First 集合

文法符号串 $\alpha $ 的串首终结符集 $\operatorname {First}(\alpha)$ 定义为从 $\alpha $ 可以(直接或间接)推导出的所有串首终结符构成的集合 。

即,若 $\alpha \to ^* t \beta $,则 $\alpha $ 可以推出一个 $t$ 开头的串,因此我们认为 $t \in \operatorname {First} (\alpha) $

据此定义 First 集合:

$$ \operatorname{First}({X})=\left\{\mathrm{t} \mid \mathrm{X} \rightarrow^{*} \mathrm{t} \alpha\right\} \cup\left\{\varepsilon \mid \mathrm{X} \rightarrow^{*} \varepsilon\right\} $$

Follow 集合

Follow (A) 集合表示哪些终结符能出现在 $A$ 的后面。

若 $A \to \alpha \wedge \alpha \to ^+ \varepsilon \wedge S \to ^+ \beta A t \delta $ ,即这种情况:

  • 栈顶是 $A$ ,输入是 $t$,而 $A$ 无法导出 $t$。此时,我们必须得跳过 $A$,具体做法就是让 $A \to \varepsilon $
  • 什么情况下可以这么做?必须要让 $t$ 能够出现在 $A$ 的后面
  • 这种情况用数学语言表示就是 $t \in \operatorname {Follow}(A)$

据此定义 Follow 集合:

$$ \operatorname{First}({X})=\left\{\mathrm{t} \mid \mathrm{X} \rightarrow^{*} \mathrm{t} \alpha\right\} \cup\left\{\varepsilon \mid \mathrm{X} \rightarrow^{*} \varepsilon\right\} $$

Select 集合

$\operatorname {Select}(A \to \beta)$ 表示用 $A \to \beta $ 进行推导时,哪些符号可以作为起始符号(不含 $\varepsilon $)。

$\operatorname{Select}(A \rightarrow \mathrm{a} \beta)=\{\mathrm{a}\}$

$\operatorname{Select}(A \rightarrow \varepsilon)=\operatorname{Follow}(A)$

相同头部的各个产生式,如果它们的 Select 集合不相交,则可以做出确定的分析

q 文法

q 文法

  • 每个产生式体只能是 $\varepsilon $ 或 non-term
  • 相同头部的各式,其 Select 集合不相交

重要性质

  • $\varepsilon \in \operatorname{First} ( \alpha ) \Rightarrow \operatorname{Select} ( A \to \alpha ) = ( \operatorname{First}(\alpha ) - \{\varepsilon \} ) \cup \operatorname{Follow} (A) $

  • $\varepsilon \not\in \operatorname{First} ( \alpha ) \Rightarrow \operatorname{Select} ( A \to \alpha ) = \operatorname{First} ( \alpha ) $

求解 First 和 Follow 集合

FIRST(α)是指符号串 α 能够推导出的所有符号串中,处于串首的终结符号组成的集合。

举个例子,如果 $a\to bC | dE|f$,那么 assert (First (a) == {b, d, f})

例子:$G:A\to (A) A \mid \varepsilon$

拢共有哪些终结符?( ) epsilonFIRST 集合显然是 (

FOLLOW(A)是指在文法 G [S] 的所有句型中,紧跟在非终结符 A 后的终结符号的集合。

举个例子,如果 TOKEN1 -> KEYWORD1 ;TOKEN2 -> KEYWORD1 {EXPR} ,则 Follow (KEYWORD1)== {';', '{'}

例子:$G:A\to (A) A \mid \varepsilon$,显然 A 后面可以有 )

LL1 文法

对于文法 $G$ 的任意两个具有相同头部的产生式 $A \to \alpha \mid \beta $,如果满足:

  • 对于不能推导出 $\varepsilon $ 的 $\alpha ,\beta $ (即各自的 Select 集等于 First 集),有 $\operatorname {First}(\alpha) \cap \operatorname {First}(\beta) = \emptyset $ (从而 Select 集互不相交,确保规约时能选择唯一的生成式,避免回溯)
  • $\neg (\alpha \to^* \varepsilon \vee \beta \to^* \varepsilon)$ ,即 $\alpha , \beta $ 至多有一个能导出 $\varepsilon $ (如果都能推出空串,会导致 Select 集合相交,因为都包含了 $\operatorname {Follow}(A)$)
  • $\alpha \to ^* \varepsilon \Rightarrow \operatorname {First}(\beta) \cap \operatorname {Follow}(A) = \emptyset $ (如果 $\alpha \to ^* \varepsilon $,则 $\operatorname {First}(\alpha) \supseteq \operatorname {Follow}(A)$ ,此时若是不能确保 $\operatorname {First}(\beta) \cap \operatorname {Follow}(A) = \emptyset $,就会导致 $\operatorname {Select}(\alpha) \cap \operatorname {Select}(\beta) \neq \emptyset $)
  • $\beta \to ^* \varepsilon \Rightarrow \operatorname{First}(\alpha ) \cap \operatorname{Follow}(A) = \emptyset $

一言以蔽之:一定要确保 $\color {red}{\operatorname {Select}(\alpha) \cap \operatorname {Select}(\beta) = \emptyset}$

满足此条件的文法称为 LL (1) 文法,即最左推导(Leftmost),从左扫描,且有 1 个前瞻符号

如何计算 First 集合

例子:

$$ \begin{aligned} &E \rightarrow T E^{\prime} \\ &E^{\prime} \rightarrow+T E^{\prime} \mid \varepsilon \\ &T \rightarrow F T^{\prime} \\ &T^{\prime} \rightarrow * F T^{\prime} \mid \varepsilon \\ &F \rightarrow(E) \mid \text { id }\\ \end{aligned} $$
查看答案

image-20211114231827777

注意到 $E'$ 可以为 $\varepsilon $,那么能跟在 $E$ 后面的符号,也可以跟在 $T$ 后面。因此将 $\operatorname {Follow}(E)$ 中的符号添加到 $\operatorname {Follow}(T)$ 中

? First(?) Follow
$E $ $\star , \varepsilon $ $\
$$ | | $E'$ | $ +, \\varepsilon $ | | | $T $ | $(, \\text{id}$ | $+,\ $$
| | $T'$ | $\\star , \\varepsilon $ | | | $F $ | $(, \\text{id}$ | |

由于 $E \to TE'$,最结尾是 $E'$,所以能跟在 $E$ 后面的符号一定能跟在 $E'$ 后面:

? First(?) Follow
$E $ $\star , \varepsilon $ $\
$$ | | $E'$ | $ +, \\varepsilon $ | $\ $$
| | $T $ | $(, \\text{id}$ | $+,\
$$ | | $T'$ | $\\star , \\varepsilon $ | | | $F $ | $(, \\text{id}$ | |

3.5 LL (1) 文法的分析

判断是否是 LL (1) 文法

摘自 Joan Tsao https://www.zhihu.com/question/53105355/answer/365345823

根据LL (1) 文法的定义来判断,分三步走:

(1) 文法不含左递归

(2) 对文法中的任一个非终结符 A 的各个产生式的侯选首终结符集两两不相交,即:若

A->α1|α2|…|αn ,则

**First(αi)∩ First(**αj) = φ ( i j )

(3) 对文法中的每个非终结符 A, 若它的某个首终结符集含有ε ,则

**First(A)∩Follow(**A) = φ

LL (1) 分析表的构建

首先构建出 Select 集,然后根据 Select 集填表:

image-20211114143950495

image-20211114144007582

递归的预测分析法

递归调用非终结符对应的过程,从而完成分析。

例如,对

(1) <PROGRAM> → program <DECLIST> :<TYPE> ; <STLIST> end
(2) <DECLIST> → id <DECLISTN>
(3) <DECLISTN> → , id <DECLISTN>
(4) <DECLISTN> → ε
(5) <STLIST> → s <STLISTN>
(6) <STLISTN> → ; s <STLISTN>
(7) <STLISTN> → ε
(8) <TYPE> → real
(9) <TYPE> → int

进行递归下降分析。

首先求解出(4),(7)语句的 Select 集:SELECT (4)={:} SELECT (7)={end}

program DESCENT;
begin
GETNEXT(TOKEN);
PROGRAM (TOKEN); // 注意这里,调用了 PROGRAM 过程
GETNEXT(TOKEN);
if TOKEN≠’$’ then ERROR;
end

> GETNEXT (TOKEN); 表示获取下一个词符

PROGRAM 过程 的设计如下:

> 对照:生成式(1)<PROGRAM> → program <DECLIST> :<TYPE> ; <STLIST> end

procedure PROGRAM(TOKEN);
begin
if TOKEN≠’program’ then ERROR;
GETNEXT(TOKEN);
DECLIST(TOKEN);
if TOKEN≠’:’  then ERROR;
GETNEXT(TOKEN);
TYPE(TOKEN);
GETNEXT(TOKEN);
if TOKEN≠’;’  then ERROR;
GETNEXT(TOKEN);
STLIST(TOKEN);
if TOKEN≠’end’ then ERROR;
end

可以发现, PROGRAM 过程PROGRAM 的生成式是一一对应的。而对于非终结符 DECLIST, TYPE, STLIST,又调用了其对应的三个过程进行分析。

非递归的预测分析法

非递归的预测分析不需要为每个非终结符编写递归下降过程。而是根据预测分析表构造一个自动机,也叫表驱动的预测分析

假设有分析表:

image-20211114145401790

我们对 id+id*id 的分析如下:

栈		    剩余输入     输出         // 初始状态,将 E 压栈
E$			id+id\*id$			    // 注意到剩余输入的开头是 id,查表 Tbl [E,id] = E->TE',因此将栈顶置换为 TE':
TE'$		id+id\*id$	E->TE'		 // 栈顶:T,查 Tbl [T,id] = T->FT',因此用 T->FT' 置换栈顶
FT'E'$       id+id\*id$   T->FT'        // 栈顶:F,查 Tbl [F,id] = F->id,置换栈顶
idT'E'$      +id\*id$     F->id         // 注意!这里栈顶是终结符,让它出栈
T'E'$        +id\*id$     T'->e          // Tbl[T',+] = T'->e
E'$          +id\*id$     E'->+TE'
+TE'$         +id\*id$    .................

总结:遇到栈顶是终结符,就让它出去。否则就查表 查表 Tbl [top, input] 替换。

递归、表驱动两种方法的比较

image-20211114150624498

预测分析中的错误处理

两种情况下可以检测到错误

  • 对不上:栈顶的终结符和当前输入符号不匹配
  • 找不到:栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

如何从错误恢复:

  1. 可以跳过,继续往后读直到某个词符。(这种词符称为同步词符 synchronizing token)
  2. 如果终结符在栈顶,可以弹出不管,然后继续分析。

3.6 自下而上的分析

自上而下采用最左推导,而自下而上采用最左规约。

Shift-Reduce 规约框架

例子:

文法

  1. E → E+E
  2. E → E*E
  3. E → (E)
  4. E → id

image-20211114151925122

说白了就是,不停地读入字符,直到可以套公式(生成式),就套,等套到根生成式了,分析树也就构建好了。

句柄 每次归约的符号串称为 “句柄”(每次套公式用的串就是句柄)

规范句型 在任何时刻,栈内符号串 + 剩余输入的连接后字符串是一个规范句型。上面的例子中共有 7 个规范句型。

S-R 分析的问题在于:可能有多个产生式,满足当前栈的规约条件

例如:有规则:

(2) <IDS>→i
(3) <IDS>→<IDS>,i

则对于 var <IDS> , i,可以规约为 (2),也可以规约为(3). 造成了歧义。为了解决此问题,引入 LR 分析法。

LR 分析法

  • L 表示从左到右扫描输入词符串
  • R 表示从右到左构造出一个最右推导序列。

移入、待约、规约状态

我们用一个小点 "$\cdot$ " 来分隔 已经识别的未识别的 输入串。

$S\to \cdot bBB$ 这种状态,称为移进状态

$S\to b \cdot BB$ 等点儿在中间的,称为 待约状态

$S\to bBB \cdot$ 称为规约状态

3.7 LR 文法的分析

LR 自动机,拥有一个分析表,这个分析表包括两部分:

  • 动作表(Action)
  • 转移表(GoTo)

分析表的构建细节,后面再说。先说用法。

LR 分析表怎么用

维护:状态栈、输入栈、剩余串

  • 初始状态为 0,输入串为空,剩余串为输入串

然后查表开始运行。

$sN$ 表示将移进,然后状态 $N$ 压栈,并执行对应的操作

使用示例:

分析表 文法
$S\to BB\\B\to aB\\B\to b$

输入串 $bab$

status
stack		remain
// 初始状态为 0
0
$			bab$
// 将 b 压栈,并且移动到状态 4 (查表,得到 s4,表示将状态 4 压栈)
04
$b			 ab$
// 状态 4 时,输入 a,查表得到 r3,表示用产生式 3 进行规约,即用 B -> b 替换栈顶,状态 4 出栈。
0
$B			 ab$
// 0 状态遇到 B 输入,输出 2,所以将状态 2 压栈。移入 a
02
$B			 ab$
// 2 状态遇到 a 输入,得到 s3,表示将状态 3 压栈
023
$Ba			  b$
// 3 状态遇到 b 输入,得到 s4
0234
$Bab           $
// 4 状态遇到 $ 输入,得到 r3,表示用产生式 3 规约【注意这步,$ 输入也要处理】注意规约时状态 4 连同 b 一起出栈
023
$BaB           $
// 3 状态遇到 B 输入,输出 GoTo 6,移入 $
0236
$BaB$
// 6,$ => r2,将 【aB】 连同状态一起出栈,换成 B
02
$BB            $
// 2,B => GoTo 5
025
$BB            $
// 5,$ => r1,将【BB】 连同状态一起出栈,换成 S
0
$S             $
// 0,S => GoTo 1
01
$S             $
// 1,$ => Accept 结束

下面学习 LR (0) 分析表的构建。

LR (0) 自动机 / 分析表的构建

基本概念

LR (0) 项目 右部某位置标有圆点的产生式称为相应文法的一个 LR (0) 项目(简称为项目)

项目描述了句柄识别的状态。产生式 A→ε 只生成一个项 A→・

增广文法 若 $G: S\to \cdots$,则增广文法就是套个皮 $G': S'\to S; S\to \cdots$

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边 ,从而使得分析器只有一个接受状态 分析器只有一个接受状态。

等价项目:通过替换之后完全一致的状态,是等价状态的不同项目。

后继项目(Successive Item):

  • 同属于一个产生式的项目,但圆点的位置只相差一个符号,则称后者是前者的后继项目
  • A→α・Xβ 的后继项目是 A→αX・β

项目集闭包(Closure of Item Sets):等价的项目放到同一个集合,这个集合就是项目集闭包。

自动机的构建

LR0 自动机的构造过程

例子:构建下面文法的 DFA:

image-20211114193713434

我们首先来构建初始状态 $I_0$。

I0
S'->·S

・S 表示等待 S。而 $S\to BB$,所以就等价于 $S'\to \cdot BB$:

I0
S'->·S
S'->·BB

观察 S'->・BB,注意到 后面是 B。那我们从文法中把 B 的抄进来就行

I0
S'->·S
S'->·BB
B->·aB
B->·b

所以第一步得到:

image-20211114200130486

对于 S'->・S 让它向前进一步,进入状态 $I_1$

I1
S'->S·

注意到 之后不再有符号,所以到此即可。

image-20211114200253510

我们再看 S->・BB,进一步得到 S->B・B

I2
S->B·B

加上等价项目。我们看点儿后面是 B,把 B 抄进来就行:

I2
S->B·B
B->·aB
B->·b

image-20211114200340534

后面也类似,想知道细节自己去看哈工大网课。

自动机到表的转化

有了这个图我们怎么转化成表呢?

  • 输入非终结符:I0 状态,输入 S 转换到了 I1 状态。因此 GOTO (0,S)=1
  • 输入终结符: I0 状态,输入 a 转换到了 I3 状态,因此 ACTION (0,a)=s3
  • 没有箭头伸出:I5 状态,I4 I5 I6 没有箭头伸出,并且内容都是单生成式,所以 ACTION (4,a|b|c)=r3,这里 rX 取决于它是文法中的第几个产生式。
  • S'->S・:I1 状态,往后就没有要处理的了,所以 ACTION (I1, $) = Accept

image-20211114201022787

移进 - 规约冲突:说白了就是分析表中,一个 Action 格子里出现两种操作。

怎么判断是不是 LR (0) 文法

  • 如果 LR (0) 分析表中没有语法分析动作冲突,那么给定的文法就称为LR (0) 文法

活前缀识别 DFA

活前缀

规范句型的组成 一个合法句子,每次归约后得到的句型,都是规范句型,其由已归约部分剩余部分构成。

规范前缀 一个规范句型的一个前缀称为规范前缀,如果该前缀后面的符号串不包含非终极符。

例如:

  • $Z \to AB b$,规范前缀为 $AB,ABb$
  • $Z\to ^+ Acb$,规范前缀为 $A,Ac,Acb$

从这个角度,规范句型 = 规范前缀 +$\varepsilon$ 或终结符串

可归前缀 用哪个产生式继续归约,只取决于当前句型的前部,这种前部称为可归前缀。

活前缀 把在规范句型中形成可归前缀之前,包括可归前缀在内的所有前缀都称为活前缀。

规范活前缀 (viable prefix):满足如下条件之一的规范前缀称为规范活前缀:

  • 该规范前缀不包含简单短语;或者
  • 该规范前缀只包含一个简单短语,而且是在该规范前缀的最后 (这个简单短语就是句柄);
  • 换句话说,规范活前缀不含句柄之后的任何符号

例如 $Z \to AB b$,规范前缀为 $AB,ABb$。其中 $AB$ 是规范活前缀(不含任何简单短语),$ABb$ 也是 (包含一个简单短语且在最后)

例如:$Z \to ^+ abcb$ 规范前缀为 a, ab, abc, abcb

规范活前缀: a (包含一个简单短语且在最后) ab, abc, abcd 都不是规范活前缀

活前缀识别机的构建

3.8 SLR 文法的分析

SLR 即 Simple LR (1) 文法,思想在于:通过 1 个前瞻符号,化解 LR (0) 文法的冲突。

这种方法有效性的前提是 Follow 集不相交

例如:若有 $E \to E + T \cdot $ 与 $T\to T \cdot \star F$ 冲突,则求出 $\operatorname {Follow}(T)$ 和 $\operatorname {Follow}(E)$,前瞻符号属于哪一个集合,就执行哪个生成式的操作。如果前瞻符号同时属于两个集合,则依旧冲突。

3.9 LR (1) 文法的分析

考虑下面的状态:(其中 $\operatorname {Follow}(R) =\{=,\$}$) $$

\begin{aligned} &S \rightarrow L\cdot=R \
&R \rightarrow L\cdot \end{aligned}

$$ 则当输入 `=` 时,对于第一个生成式是满足的,对于第二个生成式,依据其 Follow 集,也是满足的。于是依旧冲突。而实际上可以依据上下文选择正确的操作,对此,LR (1) 文法可以做到。

LR (1) 项目 形如 $A→α・β, t$ 的项称为 LR (1) 项,其中 $A→αβ$ 是产生式,$t$ 是终结符 (这里将 $ 视为一个特殊的终结符) 它表示在当前状态下,A 后面必须紧跟的终结符,t 称为 Lookahead 符号(前瞻符号)。

如何求前瞻符号?

$S' \to S$ 的前瞻符号是 $

如何求 LR1 项的等价项?

要注意前瞻符号可以继承。例如文法

  1. $S^{\prime} \rightarrow S$
  2. $S \rightarrow L=R$
  3. $S \rightarrow R$
  4. $L \rightarrow * R$
  5. $L \rightarrow$ id
  6. $R \rightarrow L$

则构建 $I_0$

I0:
S' -> ·S,$

将 S 为头的产生式抄过来,并继承 S' ->・S,$ 中的前瞻符号(关键步骤):

I0:
S' -> ·S,$
S -> ·L = R,$
· -> ·R, $

同心项:两个项若除了前瞻符,其余(其实就是生成式)完全一样,则二者是同心关系(identical kernel)。

如果LR (1) 分析表中没有语法分析动作冲突,那么给定的文法就称为 LR (1) 文法。

步骤

  1. 增广
  2. FOLLOW
  3. 分析初始状态、之后的状态(注意,前瞻符号要么来自继承,要么来自冲突时恰当选择下个可能输入的符号

《编译原理》LR 分析法与构造 LR (1) 分析表的步骤 - 例题解析 - xpwi - 博客园 (cnblogs.com)

3.10 LALR 文法的分析

LALR(Lookahead LR)基本思想:同心合并

  • 寻找具有相同核心的 LR (1) 项集,并将这些项集合并为一个项集。 所谓项集的核心就是其第一分量的集合
  • 然后根据合并后得到的项集族构造语法分析表

这种合并不能保证歧义,所以会降低分析能力。

> LALR (1) 分析器的功能比 LR (1) 分析器要弱一些;但是却比 SLR (1) 分析器强。

例题

考虑文法:

bexpr->bexpr or bterm | bterm
bterm->bterm and bfactor | bfactor
bfactor -> not bfactor | (bexpr) | true | false

分析:

消除左递归(bexpr->bexpr or bterm | bterm)

我们把 or bterm 看作一个终结符,所以结果就是 bexpr -> bterm (or bterm)*。按课本写法就是:

bexpr -> bterm TMP
TMP -> or term | epsilon

提取公因式(bexpr->bexpr or bterm | bterm) 得到 bexpr-> bterm {or bterm}}

同样的方法消除左递归(bterm->bterm and bfactor | bfactor) 得到 bterm-> bfactor (and bfactor)*,即 bfactor-> bfactor {and bfactor}

第三个生成式不是左递归,不用化简。

伪代码如下:

def bexpr():
bterm()
while lookahead == OR:
match(OR)
bterm()
return

def bterm():
bfactor()
while lookahead == AND
match(AND)
bfactor()
return

def bfactor():
if lookahead == NOT:
match(NOT)
bfactor()
return
if lookahead == LPAR
match(LPAR)
bexpr()
match(RPAR)
return
if lookahead == TRUE
match(TRUE)
return
if lookahead == FALSE
match(FALSE)
return
throw UnexpectedTokenException

image-20211017205545194

FIRST: (

FOLLOW: ),$\varepsilon$

  1. 显然不含左递归
  2. 只有一个非终结符,所以不存在相交
  3. FIRST 和 FOLLOW 不相交

因此是 LL1 文法。

image-20211017205554536

解答:

消除左递归 (L -> LE | E) => L -> E+,即 L -> E {E}

first(A) = num, id

first(B) = (

first(E) = first(A) + first(B) = num, id, (

first(L) = first(E) = num, id, (

fo(A) = $

Fo(L) = Fr(E) = num, id, (;

Fo(B) = $

Fo(E) = Fr(E) = num, id, (;

证明 LL1:

  1. 不含左递归
  2. E 的候选式 A, B。Fr (A) 交 Fr (B) = 空
  3. 不存在 unterminal X s.t. epsilon in FIRST (X)

因此是 ll1 文法

LL1 分析表:

num id ( )
E E->A E->A E->B
A A->num A->id
B B->(L)
L L->E L->E L->E

$4.9$ 考虑如下文法 $G:$ $$

\begin{aligned} &S \rightarrow A S \mid b \
&A \rightarrow S A \mid a \end{aligned}

$$ (1) 构造该文法的 $\\mathrm {LR}(0)$ 项目集规范族及识别其所有活前缀的 $\\mathrm {DFA}$ 。 (2) 该文是 SLR (1) 文法吗?为什么? (3) 构造该文法的 $\\mathrm {LR}(1)$ 项目集规范族,该文法是 $\\mathrm {LR}(1)$ 文法吗?

解:

增广文法为

S' -> S
S  -> AS
| b
A  -> SA
| a

DFA 如下:

image-20211105234612266

不是 SLR (1). 对于 $A \to SA \cdot $,A 的后继符号为 $\{a,b\}$,M [5,b] = reduce A->SA, 与 M [5,b] = shift 4 冲突

由于输入 SA 后,$[\mathrm {A} \rightarrow \mathrm {SA} \cdot, \mathrm {a} / \mathrm {b}] $, $[\mathrm {A} \rightarrow \cdot \mathrm {a}, \mathrm {a} / \mathrm {b}] $ 存在 SR 冲突,所以不是 LR (1)

4.14 对于文法 $$

\begin{array}{|l|l|l|} \hline & {\text { FIRST }} & {\text { FOLLOW }} \
\hline \text { S } & \text { a, b } & $ \
\hline \text { A } & \varepsilon & \text { a, b } \
\hline \text { B } & \varepsilon & \text { a, b } \
\hline \end{array}

$$ LL1(1) TABLE: $$

\begin{array}{|l|l|l|l|} \hline & {\mathrm{a}} & {\mathrm{b}} & {$} \
\hline \mathrm{S} & \mathrm{S} \rightarrow \mathrm{AaAb} & \mathrm{S} \rightarrow \mathrm{BbBa} & \
\hline \mathrm{A} & \mathrm{A} \rightarrow \varepsilon & \mathrm{A} \rightarrow \varepsilon & \
\hline \mathrm{B} & \mathrm{B} \rightarrow \varepsilon & \mathrm{B} \rightarrow \varepsilon & \
\hline \end{array}

$$ 无冲突,因此是 LL (1) 文法。

而增广文法的 $\mathrm {FOLLOW}(\mathrm {A})=\mathrm {FOLLOW}(\mathrm {B})=\{\mathrm {a}, \mathrm {b}\}$,存在 R-R 冲突,不是 SLR (1)

4.16 $$

\begin{aligned} &S \rightarrow(S R \mid a \
&R \rightarrow, S R \mid) \end{aligned}

$$ 增广文法:
S' -> S
S  -> (SR
|  a
R  -> ,SR
|  )

是 LR0 文法

LR0 分析: $$

\begin{array}{|c|c|c|c|c|c|c|c|} \hline {\text { state }} & a & , & ( & ) & # & S & R \
\hline 0 & \text { S2 } & & \text { S3 } & & & 1 & \
\hline 1 & \text { r1 } & \text { r2 } & \text { r1 } & \text { r1 } & \text { acc } & & \
\hline 2 & \text { r3 } & \text { r3 } & \text { r3 } & \text { r3 } & \text { r3 } & & \
\hline 3 & \text { S2 } & & \text { S3 } & & & 4 & \
\hline 4 & & \text { S5 } & & \text { S7 } & & & 9 \
\hline 5 & \text { S2 } & & \text { S3 } & & & 6 & \
\hline 6 & & \text { S5 } & & \text { S7 } & & & 8 \
\hline 7 & \text { r5 } & \text { r5 } & \text { r5 } & \text { r5 } & \text { r5 } & & \
\hline 8 & \text { r4 } & \text { r4 } & \text { r4 } & \text { r4 } & \text { r4 } & & \
\hline 9 & \text { r2 } & \text { r2 } & \text { r2 } & \text { r2 } & \text { r2 } & & \
\hline \end{array} $$

短语:假定 $abd$ 是文法 G 的一个句型。如果 ${S} \stackrel {*}{\Rightarrow} a {A} b$ 且 $A \stackrel {+}{\Rightarrow} b$ ,则称 $b$ 是 $abd$ 关于非终结符 $A$ 的短语。如果条件换成 $A \stackrel {}{\Rightarrow} b$ 则是 直接短语

https://www.cnblogs.com/xpwi/p/11066989.html

例如句型 T*P↑(T*F) 对于文法

G[T]:
T → T*F|F
F → F↑P|P
P → (T)|i

的语法树为

image_up_16407811940215a272.jpg

子树和对应的短语(一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语。)为:

image_up_1640781207f34759e9.jpg

直接短语只有 PT*F。因为它们都是最简单的二层子树。

句型的最左直接短语称为句型的句柄。因为 P 相对 T*F,在语法树上的左侧,所以句柄是 P。

LR (k) Item:由两部分组成。如 A -> ab, a1a2...ak

  • A -> ab 是 LR (0) 项目
  • a_i 是终结符号
  • a1a2…ak 是前瞻符号串

只有分析时,前瞻符号与本 Item 一样,才能做规约。