语法分析

语法分析器

作用

• 基本作用

  • 从词法分析器获取词法单元的序列, 确认该序列是否可以由语言的文法生成
  • 对于语法错误的程序, 报告错误信息
  • 对于语法正确的程序, 生成语法分析树(语法树, 通常生成的是抽象语法树AST)

• 前端的其余部分

  • 将词法单元的信息收集到符号表中, 类型检查和其他类型的语义分析, 生成中间代码等

上下文无关文法

程序设计语言构造的语法可使用上下文无关文法(Context-Free Grammar, CFG)或BNF表示法来描述

上下文无关文法包含四个部分

• 终结符号: 组成串的基本符号(词法单元名字)
• 非终结符号: 表示串的集合的语法变量

给出了语言的层次结构, 是语法分析和翻译的关键

• 产生式: 描述将终结符号和非终结符号组成串的方法
  • 形式: 头(左)部 -> 体(右)部
  • 头部是一个非终结符号, 体部是一个符号串
• 起始符号: 某个被指定的非终结符号

它对应的串的集合就是文法的语言

eg:

• E: expression, T: term, F: factor

E -> E + T
  | E - T
  | T
T -> T * F / F | F
F -> ( E ) | id

这个|符号是元符号(文法描述中的符号, 不是文法符号), 表示"或", 表示一个非终结符号可以有多个产生式

这里的左括号和右括号不是元符号, 是终结符

符号表示的约定

推导

• 将待处理的串中的某个非终结符号替换为这个非终结符号的某个产生式的体部
• 从起始符号出发, 不断进行上面的替换, 就可以得到文法的不同句型

eg:

E -> -E
  | E + E
  | E * E
  | ( E )
  | id

推导序列: E => -E => -(E) => -(id)

句型/句子/语言

• 句型
  • 如果$S{\Rightarrow }^{\ast }w$, 则称串w是文法G的一个句型
  • 可能既包含非终结符号, 又包含终结符号, 也可以是空串
• 句子
  • 文法的句子就是只包含终结符号/空串的句型
• 语言
  • 文法G的语言就是G的句子的集合, 记为L(G)
  • w在L(G)中当且仅当w是G的句子, 即$S{\Rightarrow }^{\ast }w$

语言是从文法的起始符号出发, 能推导得到的所有句子的集合

eg:

• 文法G: S -> aS | a | b, L(G) = $\{a^i(a|b),i>0\}$
• 文法G: S -> aSb | ab, L(G) = $\{a^n{b}^n,n>=1\}$
• 文法G: S -> (S)S | ε, L(G) = {所有具有对称括号对的串}

最左/最右推导

eg:

给定文法:

E -> E + E 
  | E * E 
  | -E
  | ( E )
  | id

那么串-(id+id)是这个文法的一个句子:

• 最左推导
  • E => -E => -(E) => -(E+E) => -(id+E) => -(id+id)
• 最右推导
  • E => -E => -(E) => -(E+E) => -(E+id) => -(id+id)

语法分析树

• 推导的图形表示形式
  • 根结点的标号是文法的起始符号
  • 每个叶子结点的标号是非终结符号, 终结符号或ε
  • 每个内部结点的标号是非终结符号
  • 每个内部结点表示某个产生式的一次应用

结点的标号为产生式头, 其子结点从左到右是产生式的体

• 树的叶子组成的序列是根的文法符号的一个句型
• 一颗语法分析树可对应多个推导序列

但只有唯一的最左推导及最右推导

eg:

E -> E + E 
  | E * E 
  | -E
  | ( E )
  | id

句子: -(id+id)

设计文法

上下文无关文法比正则表达式的能力更强.

无穷vs有穷

文法能够描述程序设计语言大部分语法.

在进行语法分析前, 需要对文法进行处理:

• 消除二义性
• 消除左递归
• 提取左公因子

二义性

如果一个文法可以为某个句子生成多棵语法分析树, 这个文法就是二义的.

eg:

E -> E + E
  | E * E
  | -E
  | ( E )
  | id

对于id + id * id, 可以:
1. E => E + E => id + E => id + E * E => id + id * E => id + id * id
2. E => E * E => E + E * E => id + E * E => id + id * E => id + id * id

同样是最左推导, 但是得到的语法树却不同

程序设计语言的文法通常是无二义的, 否则就会导致一个程序有多种正确的解释

消除

二义性的根源: 多种正确的推导处于文法同一层.

因此消除二义性的惯用技术是分层:

• 改造文法, 将真正想要的推导提取出来放到更深层次.
• 最左推导中, 更深层的非终结符总是会被优先替换

eg:

E -> E + E
  | E * E
  | ( E )
  | id
改为
E -> E + T | T
T -> T * F | F
F -> ( E ) | id

改后的id + id * id的最左推导:
E => E + T => T + T => F + T => id + T => id + T * F => id + F * F => id + id * F => id + id * id

语法分析技术

自顶向下

为输入串构造语法分析树

• 从分析树的根结点(文法的起始符号)开始, 自顶向下, 按照先根次序, 深度优先地创建各个结点
• 对应于最左推导
• 关键步骤: 应用产生式创建新的子结点

E => E + E | E * E | -E | ( E ) | ... | id

问题: 如何选择合适的产生式?

procedure visit(node N) {
    for (从左到右遍历N的每个子结点C) {
        visit(C);
    }
    
    按照结点N上的语义规则求值;
}

每个非终结符号对应一个过程/函数, 该过程负责扫描此非终结符号对应的结构

• S -> ... => bool S()
• A -> ... => bool A()

程序执行从开始符号对应的过程开始, 当扫描整个输入床时宣布分析成功完成

关键步骤: 应用产生式. 依次猜测每个产生式, 猜对就结束, 猜错就回溯.

• A -> t(终结符)

bool A() {
    if (nextToken == t) {
        consume(nextToken);
        return true;
    }

    return false;
}

• A -> XYZ

如果X/Y/Z是终结符, 则展开X()成识别终结符的代码

bool A() {
    if (X() && Y() && Z()) {
        return true;
    }

    return false;
}

特殊情况: A -> Aa, 会出现:

bool A() {
    if (A() && a()) {
        return true;
    }
    
    return false;
}

这种情况就是左递归.

• A -> X | Y | Z

bool A() {
    if (X()) return true; else backtrack;
    if (Y()) return true; else backtrack;
    if (Z()) return true; else backtrack;
    return false;
}

// 类似使用else if, 但是会回溯状态(如果X(), Y(), Z()会改变状态的话)

eg:

文法: S -> cAd, 其中A -> ab|a

输入串: cad

步骤:

1. 调用函数S, 选择唯一的产生式S->cAd
2. 输入中的c与举行中的c匹配, 继续调用函数A
3. A首先选择产生式A->ab, a与输入的a匹配, 但b和输入的d不匹配
4. 回溯, 选择下一个产生式A->a, 与输入的a匹配, 对函数A的调用返回到S的调用
5. S->cAd中最后的d与下一个输入d匹配, 结束

因此cad是S的句子

左递归

如果一个文法中有非终结符号A使得$A={>}^{+}Aa$, 这个文法就是左递归的.

• 直接左递归(规则左递归): 文法中存在一个形如$A->Aa$的产生式

自顶向下的语法分析技术不能处理左递归的情况, 因此需要消除; 自底向上的技术可以处理左递归.

消除

假设非终结符号A存在:

$$A->A{a}_1|...|A{a}_m|{\beta }_1|...|{\beta }_n$$

可替换为

• $A->{\beta }_1{A}^{\prime }|...|{\beta }_n{A}^{\prime }$
• $A^{\prime }->a_1{A}^{\prime }|...|a_m{A}^{\prime }|\epsilon$

观察: 由A生成的串以某个${\beta }_i$开头, 然后跟上零个或多个$a_j$

A -> Aa | B

=>

A -> BA'
A' -> aA' | ε

// 原: A -> Aa | B
bool A() {
    if (A() && a()) return true;
    if (B()) return true;
    return false;
}

// 新:
// A -> BA'
// A' -> aA' | ε

bool A() {
    if (B() && A1()) return true;
    return false;
}

bool A1() {
    if (nextToken == a) {
        consume(nextToken);
        return A1();
    }
    return false;
}

eg:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

=>
E -> T E'
E' -> + T E' | ε

T -> F T'
T' -> * F T' | ε

F -> ( E ) | id

递归下降分析的特点

• 易于实现

• 需要回溯(影响效率)

基于预测的语法分析

基本步骤:

• 确定对句型中最左边的非终结符号应用那个产生式
• 然后对该产生式与输入符号进行匹配

根据下一字符预测正确的产生式, 避免回溯

预测分析法试图从开始符号推导出符号串, 每次为最左边的非终结符号选择适当的生产式.

通过查看下一个输入符号来选择这个产生式

提取公因子的文法变换

输入: 文法G

输出: 等价的提取了左公因子的文法

方法: 对于每个非终结符号A, 找出它的两个或者多个可选产生式体之间的最长公共前缀

• A -> αβ1 | αβ2 | ... | αβn | y
• A -> αA' | y, A' -> β1 | β2 | ... | βn

其中y不以α开头

预测分析法LL(k)

• L: 从左到右扫描
• L: 最左推导
• k: 向前看k个符号

通常k=1

每次为最左边的非终结符号选择产生式时, 向前看1个输入符号, 预测要使用的产生式

若当前句型是xAB, 输入时xa..., 选择产生式$A->\alpha$的必要条件是下列之一

• $\alpha ={>}^{\ast }a...$
• $\alpha ={>}^{\ast }\epsilon$且B以a开头
• 如果按照这两个条件选择时能够保证唯一性, 就可以避免回溯

FIRST

FIRST(a)

• 可以从a推导得到串的首符号的集合
• 如果$a={>}^{\ast }\epsilon$, 则ε也在FIRST(a)中

FIRST函数的意义:

• A的产生式$A->\alpha |\beta$, 且$FIRST(\alpha )$和$FIRST(\beta )$不相交
• 下一个输入符号是a, 若$a\in FIRST(\alpha )$, 则选择产生式$A->\alpha$, 若$a\in FIRST(\beta )$, 则选择产生式$A->\beta$

计算FIRST(X):

• X是终结符号, 那么添加X
• X是非终结符号, 且$X->Y_1{Y}_2...Y_k$
  • 如果a在FIRST($Y_i$)中, 且ε在FIRST($Y_1$), ..., FIRST($Y_{i-1}$)中, 则添加a
  • 如果ε在FIRST($Y_1$), ..., FIRST($Y_k$)中, 则添加ε
• 如果X是非终结符号且X->ε, 则添加ε

计算FIRST($X_1{X}_2{X}_3...X_N$)

• 加入FIRST($X_1$)中所有非ε符号
• 若ε在FIRST($X_1$), 则加入FIRST($X_2$)中所有非ε符号...
• 若ε在所有FIRST($X_i$)中, 则加入ε

FOLLOW

FOLLOW(A)

• 可能在某些句型中紧跟在A右边的终结符号的集合

eg: $S->\alpha Aa\beta$, 终结符号$a\in FOLLOW(A)$

FOLLOW函数的意义

• 如果$A->\alpha$, 当$\alpha =>\epsilon$, FOLLOW(A)可以帮助选择恰当的产生式

FOLLOW(S)的计算

• 将输入结束标记$加入到FOLLOW(S)中
• 迭代, 直到所有的FOLLOW集合都不再增长
  • 如果存在产生式$A->\alpha B\beta$, 那么FIRST($\beta$)中所有非ε的符号都加入FOLLOW(B)中
  • 如果存在产生式$A->\alpha B$, 或者$A->\alpha B\beta$且FIRST($\beta$)包含ε, 那么FOLLOW(A)中所有符号都加入到FOLLOW(B)中

eg:

文法:
E -> T E', E' -> + T E' | ε
T -> F T', T' -> * F T' | ε
F -> ( E ) | id

FIRST集合的计算

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

FIRST(TE') = {(, id}
FIRST(+TE') = {+}
FIRST(*FT') = {*}
FIRST((E)) = {(}

FOLLOW集合的计算

FOLLOW(E) = {), $}
FOLLOW(E') = {), $}
FOLLOW(T) = {+, ), $}
FOLLOW(T') = {+, ), $}
FOLLOW(F) = {*, +, ), $}

LL(1)文法

对文法的任意两个产生式$A->\alpha |\beta$

1. 不存在终结符号a是的$\alpha$和$\beta$都可推导出以a开头的串
2. $\alpha$和$\beta$最多只有一个可推导出空串
3. 如果$\beta$可推导出空串, 那么$\alpha$不能推导出以FOLLOW(A)中任何终结符号开头的串

<=>

1. FIRST($\alpha$)与FIRST($\beta$)不相交
2. 如果$\beta =>$* ε$,\mathrm{那}\mathrm{么}FOLLOW(A)\mathrm{与}FIRST($\alpha$)不相交, 反之亦然

eg

产生式:

stmt -> if (exp) stmt else stmt
      | while (exp) stmt
      | a

输入
if (exp) while (exp) a else a

1. 根据输入id, 选择产生式stmt -> if (exp) stmt else stmt, 得到句型

if (exp) stmt else stmt

2. 根据输入while, 把句型的第一个stmt展开, 选择产生式stmt -> while (exp) stmt, 得到句型

if (exp) while (exp) stmt else stmt

3. 输入a, 选择产生式展开下一个stmt -> a, 得到句型

if (exp) while (exp) a else stmt ...

预测分析表构造算法

输入: 文法G

输出: 预测分析表M

• 二维表: 非终结符(行) X 终结符(列) -> 产生式
• 展示非终结符时, 根据输入终结符选择相应的产生式

方法:

1. 对于文法G的每个产生式$A->\alpha$

• 对于FIRST($\alpha$)中的每个终结符号a, 将$A->\alpha$加入到M[A, a]中
• 如果ε在FIRST($\alpha$)中, 则对于FOLLOW(A)中的每个符号b, 将$A->\alpha$也加入到M[A, b]中

2. 最后在所有空白条目中填入error

eg

文法:
E -> T E', E' -> + T E' | ε
T -> F T', T' -> * F T' | ε
F -> ( E ) | id

FIRST集合

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

FOLLOW集合

FOLLOW(E) = {), $}
FOLLOW(E') = {), $}
FOLLOW(T) = {+, ), $}
FOLLOW(T') = {+, ), $}
FOLLOW(F) = {*, +, ), $}

预测分析表M:

非终结符\终结符	id	+	*	(	)	$
E	E -> T E'	error	error	E -> T E'	error	error
E'	error	E' -> + T E'	error	error	E' -> ε	E' -> ε
T	T -> F T'	error	error	T -> F T'	error	error
T'	error	T' -> ε	T' -> * F T'	error	T' -> ε	T' -> ε
F	F -> id	error	error	F -> ( E )	error	error

LL(1)文法的递归下降分析

递归下降语法分析程序由一组过程组成, 每个非终结符号对应一个过程.

可以使用当前的输入符号来唯一地选择产生式.

// A -> X | Y | Z
bool A() {
    p = M[A, nextToken];
    if p is A -> X return X();
    if p is A -> Y return Y();
    if p is A -> Z return Z();
    return false; // error
}

非递归的预测分析

递归下降分析输入太大时, 容易导致栈溢出.

在自顶向下分析的过程中, 我们总是

• 匹配掉句型中左边的所有终结符号
• 对于最左边的非终结符号, 选择适当的产生式展开
• 匹配成功的终结符号不会再被考虑, 因此只需要记录句型的余下部分, 以及尚未匹配的输入终结符号串
• 由于展开的动作总是发生在余下部分的左端, 可以用栈来存放这些符号

处理过程:

• 初始化栈: 仅包含开始符号S(和输入结束标记$)
• 如果栈顶元素是终结符号, 那么跟输入进行匹配
• 如果栈顶元素是非终结符号
  • 使用预测分析表来选择适当的生产是
  • 在栈顶用产生式右部替换产生式左部

算法:

输入: 串w, 预测分析表M

输出: 如果w是句子, 输出w的最左推导, 否则报错

• 初始化: 输入缓冲区为w$,\mathrm{栈}\mathrm{为}S$, ip指向w的第一个符号
• 令X = 栈顶符号, ip指向输入符号a

if (X == a) X出栈, ip向前移动; // 匹配成功
else if (X是终结符号) error();
else if (M[X, a]是报错条目) error();
else if (M[X, a] = X->Y_1Y_2...Y_k) {
    输出产生式X->Y_1Y_2...Y_k;
    弹出栈顶符号X, 并将Y_k, Y_{k-1}, ..., Y_1依次压入栈中;
}

• 不断执行第二步, 直到要么报错, 要么栈为空

eg:

非终结符\终结符	id	+	*	(	)	$
E	E -> T E'	error	error	E -> T E'	error	error
E'	error	E' -> + T E'	error	error	E' -> ε	E' -> ε
T	T -> F T'	error	error	T -> F T'	error	error
T'	error	T' -> ε	T' -> * F T'	error	T' -> ε	T' -> ε
F	F -> id	error	error	F -> ( E )	error	error

输入串: id + id * id

开始: 栈: E$, 输入缓冲区: id + id * id$, ip指向id
M[E, id]存在, 取出M[E, id] = E -> T E', 将E弹出, 将E'和T依次压入栈
栈: T E' $, 输入缓冲区: id + id * id$, ip指向id
M[T, id]存在, 取出M[T, id] = T -> F T', 将T弹出, 将T'和F依次压入栈
栈: F T' E' $, 输入缓冲区: id + id * id$, ip指向id
M[F, id]存在, 取出M[F, id] = F -> id, 将F弹出, 将id压入栈
栈: id T' E' $, 输入缓冲区: id + id * id$, ip指向id
栈顶id与输入符号id匹配, 弹出id, ip向前移动
栈: T' E' $, 输入缓冲区: + id * id$, ip指向+
M[T', +]存在, 取出M[T', +] = T' -> ε, 将T'弹出
栈: E' $, 输入缓冲区: + id * id$, ip指向+
M[E', +]存在, 取出M[E', +] = E' -> + T E', 将E'弹出, 将E', T, +依次压入栈
栈: + T E' $, 输入缓冲区: + id * id$, ip指向+
栈顶+与输入符号+匹配, 弹出+, ip向前移动
栈: T E' $, 输入缓冲区: id * id$, ip指向id
M[T, id]存在, 取出M[T, id] = T -> F T', 将T弹出, 将T'和F依次压入栈
栈: F T' E' $, 输入缓冲区: id * id$, ip指向id
M[F, id]存在, 取出M[F, id] = F -> id, 将F弹出, 将id压入栈
栈: id T' E' $, 输入缓冲区: id * id$, ip指向id
栈顶id与输入符号id匹配, 弹出id, ip向前移动
栈: T' E' $, 输入缓冲区: * id$, ip指向*
M[T', *]存在, 取出M[T', *] = T' -> * F T', 将T'弹出, 将T', F, *依次压入栈
栈: * F T' E' $, 输入缓冲区: * id$, ip指向*
栈顶*与输入符号*匹配, 弹出*, ip向前移动
栈: F T' E' $, 输入缓冲区: id$, ip指向id
M[F, id]存在, 取出M[F, id] = F -> id, 将F弹出, 将id压入栈
栈: id T' E' $, 输入缓冲区: id$, ip指向id
栈顶id与输入符号id匹配, 弹出id, ip向前移动
栈: T' E' $, 输入缓冲区: $, ip指向$
M[T', $]存在, 取出M[T', $] = T' -> ε, 将T'弹出
栈: E' $, 输入缓冲区: $, ip指向$
M[E', $]存在, 取出M[E', $] = E' -> ε, 将E'弹出
栈: $ , 输入缓冲区: $, ip指向$
栈顶$与输入符号$匹配, 弹出$, ip向前移动
栈为空, 分析成功

自底向上

从叶子(输入串的终结符号)出发, 向上到达根结点

实际不一定会构造出相应的分析树 重要的自底向上语法分析的通用框架: 移入-归约(shift-reduce)

归约

自底向上的语法分析过程可以看成是从串w归约为文法开始符号S的过程

归约步骤

• 一个与某产生式体匹配的特定子串被替换为该产生式头的非终结符号

问题:

• 何时归约
• 归约到哪个非终结符号

eg:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

输入 id * id
1. id * id
2. F * id
3. T * id
4. T * F
5. T
6. E

=>
E => T => T * F => F * F => id * F => id * id

归约过程等于一个反向最右推导

句柄

最右句型中和某个产生式体相匹配的字串, 对它的归约代表了该最右句型的最右推导的最后一步

自底向上分析的过程就是识别和归约句柄的过程

eg:

移入归约分析技术

• 使用一个栈来保存归约/扫描移入的文法符号
• 栈中符号(从底向上)和待扫描的符号组成了一个最右句型
• 开始时刻: 栈中只包含了$, 而输入为w$
• 结束时可: 栈中为S$, 而输入为$
• 在分析过程中, 不断移入符号, 并在识别到句柄时进行归约
• 句柄被识别时, 总是出现在栈的顶部

四个操作:

• 移入: 将下一个输入符号移入到栈顶
• 归约: 将句柄归约为相应的非终结符号
  • 句柄总是在栈顶
  • 具体操作时弹出 句柄, 压入被归约的非终结符号
• 接受: 宣布分析过程成功完成
• 报错: 发现语法错误, 调用错误恢复子程序

eg:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

输入 id * id

栈$, 输入id * id$
移入: 栈$id, 输入* id$
归约: 栈$F, 输入* id$
归约: 栈T, 输入* id$
移入: 栈$T *, 输入id$
移入: 栈$T * id, 输入$
归约: 栈$T * F, 输入$
归约: 栈$T, 输入$
归约: 栈$E, 输入$
接受

对于有些不能使用移入-归约分析的文法, 不管用怎么样的移入-归约分析器都会到达这样的格局:

• 即使知道栈中所有内容, 以及后续k个输入符号, 仍然
  • 无法知道是否该进行归约(移入-归约冲突)
  • 无法知道按照什么产生式进行归约(归约-归约冲突)
• 设栈中符号串是AB, 接下来k个符号是x, 产生移入/归约冲突的原因是存在y和y', 使得ABxy是最右句型且B是句柄(需归约), 而ABxy'也是最右句型, 但是句柄还在右边(需移入)

LR语法分析技术

LR(k)的语法分析概念

• L: 最左扫描
• R: 反响构造出最右推导
• k: 最多向前看k个符号

当k增大时, 相应的语法分析器的规模急剧增大, 通常只考虑k<=1的情况

• 优点
  • 由表格驱动, 易于自动生成
  • 对于几乎所有的程序设计语言, 只要写出上下文无关文法, 就能构造出识别该语言的LR语法分析器
  • 最通用的无回溯移入-归约分析技术
  • 能分析的文法比LL(k)文法更多

分析思路

核心任务: 识别句柄, 归约句柄

句柄: 栈中内容的最右可归约子串

维护一个状态, 记录当前句柄识别的进度

项(term): 一个文法产生式加上在其中某处的一个点

• A -> X.Y表示已扫描/归约到了X, 并期望在接下来的输入中经过扫描/归约Y, 然后把XY归约到A
• A -> XY.表示已扫描/归约得到了XY, 可以把XY归约为A
• A -> ε只对于一个项A -> .
• 通常被称为LR(0)项

项既表示过去(已扫描/归约的串), 也预示未来(想要扫描/归约的串)

识别句柄的过程中, 可能有多个可选的产生式, 因此可能同时满足多个项(同时处于多个状态)

LR(0)项集规范族的构造

三个相关定义

• 增广文法(引入起始状态)
• 项集闭包CLOSURE(状态机确定化)
• GOTO函数(定义状态跳转)

---

• 增广文法

  • G的增广文法G'是在G中增加新开始符号S', 并加入产生式S'->S得到的
  • G'和G接受相同的语言, 且安装S'->S进行归约实际上就表示已经将输入符号串归约成为开始符号
  • 方便引入S的项, 表示识别的起始(S'->.S)和结束(S'->S.)

• 项集闭包CLOSURE

  • 如果I是文法G的一个项集, CLOSURE(I)就是根据下列规则从I构造得到的项集
    • 将I中的各项加入CLOSURE(I)中
    • 如果$A->\alpha \dot{B}\beta$在CLOSURE(I)中, 而$B->\gamma$是一个产生式, 且项$B->\dot{\gamma }$不再CLOSURE(I)中, 就将该项加入其中, 不断应用该规则知道没有新项加入
  • 意义
    • $A->\alpha \dot{B}\beta$表示希望看到由$B\beta$推导出的串, 那要先看到B推导出的串, 因此加上B的各个产生式对应的项

SetOfItems CLOSURE(I) {
    J = I;
    repeat {
        for (J中的每个项A->α.Bβ) {
            for (G的每个产生式B->γ) {
                if (B->.γ不在J中) {
                    将B->.γ加入J中;
                }
            }
        }
    } until (J不再增长);
    return J;
}

• GOTO函数(状态跳转表)
  • I是一个项集, X是一个文法符号, 则GOTO(I, X)定义为I中所有形如[A->α.Bβ]的项所对应的项[A->αB.β]的集合的闭包

eg:

I = {
E' -> E.,
E -> E.+T,
}

GOTO(I, +)

I中只有一个项后面跟着+, 对应的项为E -> E + .T
CLOSURE({[E -> E + .T]}) = {
E -> E + .T,
T -> .T * F,
T -> .F,
F -> .( E ),
F -> .id
}

求规范LR(0)项集族的算法

从初始项集开始, 不断计算各种可能的后继, 知道生成所有的项集

输入: 增广文法G'

输出跳转表GOTO(以及相应项集闭包)

void items(G') {
    C = {CLOSURE({[S' -> .S]})};
    repeat {
        for (C中的每个项集I) {
            for (每个文法符号X) {
                if (GOTO(I, X)非空且不在C中) {
                    将GOTO(I, X)加入C中;
                }
            }
        }
    } until (在某一轮中没有新的项集被加入到C中)
}

LR(0)自动机的构造

构造方法

• 基于规范LR(0)项集族可以构造LR(0)自动机
• 规范LR(0)项集族中的每个项集对应于LR(0)自动机的一个状态
• 状态转换: 如果GOTO(I, X) = J, 则从I到J有一个标号为X的转换
• 开始状态为CLOSURE({S' -> .S})对应的项集

LR(0)自动机的作用

假设文法符号串w使LR(0)自动机从开始状态运行到状态(项集)j

如果j中存在项A -> a., 那么

• a是w的后缀, 且是该句型的句柄(对应于产生式A->a)
• 表示可能找到了当前最右句型的句柄, 可以归约
• 在w之后添加一些终结符号可以得到一个最右句型

如果j中存在项B->a.XB, 那么

• 该句型中aXB是句柄, 但还没找到, 还需移入
• 在w之后添加XB和一些终结符号可以得到一个最右句型

作用:

• 移入-归约时, LR(0)自动机被用于识别句型
• 已得到的文法符号序列对应于LR(0)自动机的一条路经 无需每次用该文法符号序列来运行LR(0)自动机
  • 文法符号可省略, 由LR(0)状态可确定相应的文法符号
    • 状态间的转换是唯一的, 转换边上有文法符号
  • 在移入后, 根据原来的栈顶状态可以知道新的状态
    • 根据原栈顶符号和移入符号, 查询GOTO
  • 在归约时, 根据归约产生式的右部长度弹出相应状态, 也可以根据此时的栈顶状态知道新的状态
    • 归约相当于先弹出, 再移入

语法分析器生成工具

YACC的使用方法

YACC源程序的结构

声明
%%
翻译规则
%%
辅助性C语言例程

• 声明
  • 放置C声明和对词法单元的声明
• 翻译规则
  • 指名产生式及相关的语义动作
• 辅助性C语言例程
  • 被直接拷贝到生成的C语言源程序中
  • 可在语义动作中调用
  • 包括yylex(), 这个函数返回词法单元, 可以由Lex生成

翻译规则的格式

<产生式头>: <产生式体1> {<语义动作1>}
            | <产生式体2> {<语义动作2>}
            ...
            ;

• 第一个产生式的头被看作是开始符号
• 语义动作是C语言序列
• $$\mathrm{表}\mathrm{示}\mathrm{和}\mathrm{产}\mathrm{生}\mathrm{式}\mathrm{头}\mathrm{相}\mathrm{关}\mathrm{的}\mathrm{属}\mathrm{性}\mathrm{值},\$i\mathrm{是}\mathrm{产}\mathrm{生}\mathrm{式}\mathrm{体}\mathrm{中}\mathrm{第}i\mathrm{个}\mathrm{文}\mathrm{法}\mathrm{符}\mathrm{号}\mathrm{的}\mathrm{属}\mathrm{性}\mathrm{值}$$

eg:

expr: expr '+' term {
    $$ = createNode('+', $1, $3);
}
    | term {
    $$ = $1;
};

YACC中的冲突处理

缺省处理方法

• 归约/移入冲突: 总是移入(悬空else的解决)
• 归约/归约冲突: 选择列在前面的产生式

通过确定终结符号的优先级/结合性来解决冲突

• 结合性: %left, %right, %nonassoc
• 移入a/按A -> a归约: 比较a和A -> a的优先级再选择
  • 终结符号的优先级按在声明部分的出现顺序而定
  • 产生式的优先级设为它最右的终结符号的优先级, 也可以加标记%prec<终结符号>, 指明产生式的优先级等同于该终结符号

YACC的错误恢复

• 使用错误产生式来完成语法错误恢复
  • A -> error a
• 定义哪些非终结符号有错误恢复动作
• 当语法分析器遇到错误时
  • 不断弹出栈中状态, 直到栈顶状态包含项A -> .error a
  • 分析器将error移入栈中
  • 如果a为空, 分析器直接执行归约, 并调用相关的语义动作; 否则跳过一些符号, 找到可以归约a的串为止.