词法分析

前面的课程没有笔记，在这里补一下哈，主要参考国防科技大学的编译原理MOOC
简单来说就是判断一个字符串是否是合法单词
正规式的等价性:
b(ab)*=(ba)*b
即：
MOOC

确定的有限自动机(DFA)

M=(S,Σ,f,S?,F)

S：有穷状态集
Σ：输入字母表
f：状态转换函数，后继唯一
S?：S? ∈ S，是唯一的一个初态
F：F ∈ S，终态集(可以为空)

MOOC

tips:

  • DFA每个顶点射出的弧上的标记符不同
  • DFA M所识别的字的全体为L(M)

非确定的有限自动机

M=(S,Σ,f,S?,F)

S：有穷状态集
Σ：输入字母表
f：状态转换函数，可以是字符，字，正规式
S?：S? ∈ S，非空初态集
F：F ∈ S，终态集(可以为空)
NFA与DFA区别：
MOOC

MOOC

DFA与NFA识别能力相同：

  • 对于每一个NFA，有一个DFA与该NFA识别能力相同

NFA到DFA的转换(NFA的确定化)

MOOC
如上图，NFA的确定化就是要消除这三个方面的差异

  1. 消除初始状态的差异
  • 引进新的初态结点X和终态结点Y，X经过ε到S?(初始状态集)中任意结点，Y经过ε到F(终态集)中的任意结点

NFA by MOOC
INSERT XY by MOOC

  1. 消除弧上标记差异和转换差异
    子集法: 解决 ε 弧和转换关系
  • 引入定义ε-闭包，即ε-closure(I)为:
    • 若S ∈ I，则S ∈ ε-closure(I)；
    • 若S ∈ I，则从S出发经过任意条 ε 弧所能到达的任何状态 S′ 都属于ε-closure(I)。

偷下懒，直接放图
定义Ia如图：
MOOC
即：
MOOC
MOOC
得到转换表:
MOOC
注意即使Ia或者Ib是空集若满足条件也要放入I计算下去
话说计算 J 中间能经过 ε 吗？应该是不能的(若有错误请联系我订正)，而且只能经过一个a|b。

放个例子：
MOOC
转换表编号后变成DFA：
MOOC

DFA化简( 待补 )：
先划分为终态和非终态；
再对两个子集细分直到无法再分：
即子集中每个元素的move结果不同的要区分开来，具体见MOOC 6.1 第4个视频

语法分析

简单理解为判断一个输入串是否是一个句子
分析方法

回顾上下文无关文法

四元组
一些定义

  • 开始符S能推导出的叫做句型，句型只有终结符组成叫句子, 文法的所有句子的集合叫语言

自上而下分析

示例如图：

从文法开始符号S开始推导,S只有一个右部，取 S -> xAy 进入下一层，x匹配成功，A匹配失败且A有下一层，取右部(从左到右取),A下一层是两个※号,第一个 * 匹配成功，第二个 * 匹配失败，回溯,
取A -> * ，匹配成功，y匹配成功，完成。
下面介绍下一些可能遇到的问题。

回溯问题

如上例，匹配成功可能是暂时的，出错时就得回溯

文法左递归问题

即可能存在 P =+=> Pα，即P推导出的句型中又有P开头
左递归
构建语法树的过程中可能不断遇到使用左递归式的问题，这会导致语法树一直构建下去而未继续读入任何字符，陷入死循环

消除文法左递归

消除直接左递归

例如： P -> Pα|β (β不以P开头)
简单直接左递归
而右递归因为有字符会不断被读入并匹配，所以右递归不会产生死循环
下面是一个复杂点的 m个左递归
复杂直接左递归

消除间接左递归

如：
S -> Qc|c
Q -> Rb|b
R -> Sa|a
没有直接左递归，但其实S,Q,R都是左递归的，例如存在 S => Qc => Rbc => Sabc

现在来消除间接左递归
但是有前提条件

  • 不含以 ε 为右部的产生式
  • 不含回路，即不能自己推自己(P =+=> P)


通过不断带入来打破循环
算法 ：
所有非终结符P = { P1…Pn }按顺序排列

1
2
3
4
5
6
n=10
for i in range(1,n+1):
    for j in range(1,i):
        pass
        # 把(Pi) -> (Pj)α 改写为 (Pi) -> (β1)α|(β2)α|(β3)α...|(βk)α
        # 示例见下图

同一个文法
S -> Qc|c
Q -> Rb|b
R -> Sa|a
排列：R,Q,S
首先R，R以S开头，但S顺序在R后面，故R不处理；然后Q，Q以R开头，R在Q前面，所以把R用R的右部代替即 Q -> Sab|ab|b ,
R的右部现在没有按照顺序在它前面的非终结符开头的了，所以完成；开始S，Q在S之前，Q要替换成Q的右部即 S -> Sabc|abc|bc|c
注意了！！！ ,S有有直接左递归，按照消除左递归的方法消除它：S -> abcS’ | bcS’ | cS’ and S’ -> abcS’ | ε
然后！！！ 可以看到从S出发到S’, S’ 又到 S’,Q和R无用，删掉

消除回溯

即保证在构建分析树的时候输入一个字符串，对于每一个非终结符，如果它有多个候选A -> α|β|σ 选择必须是正确唯一的，这样就不需要回溯。

我们这样想，我们要扩展A就要选择A的右部中 以当前匹配字符a开头的 或者 经过若干步推导以a开头的
但是A的右部有多个以当前匹配字符a开头的怎么办？依旧有回溯啊？
于是引入FIRST集，这个FIRST集是针对所有非终结符(例如上面的A)的右部的每个式子而产生的
这样就能解决上面提出的问题


示例：

匹配 i+i ，在末尾加个结束符#，从开始符E开始，E只有一个右部，扩展；T只有一个右部，扩展；F要匹配i，(E) 的首符集是左括号，i的首符集是i，所以F选择推导到i而不是(E);
对于T’ 因为另一个首符集是星号，只能选择 ε。后面略。

但是我们同时也看到在第一个T’时，T’只能取 ε，且+号跟在 T’ 后面,…我也半知半解…
总之，引入FOLLOW集，即从开始符S能推出的所有句子中，A后面跟着的那个字符组成的集合就是A的FOLLOW集

例如上图，若A要匹配a但a不在A的FIRST集里，所以只能取ε，但取了后是否就能匹配呢，这要看FOLLOW集。

FIRST集及其构造方法
  • 为了消除公共左公因子产生的回溯问题
    左公因子产生式举例：
    A -> αβ1 | αβ2
    即某个非终结符的多个候选式具有相同前缀，上式αβ1和αβ2具有相同前缀α

构造方法：
对于每一个X ∈ V_t ∪ V_n , 使用如下规则直到每个FIRST集不再增大：

  • 若X ∈ V_t，则FIRST(X)={X}
    若X是终结符，则其FIRST集就是其本身
  • 若X ∈ V_n，X是非终结符，那么有
    • 若X -> a… ，则 a ∈ FIRST(X)，这里 a 可以是 ε
    • 若X -> Y… ，则 FIRST(Y) - {ε} ∈ FIRST(X)
    • 若X -> Y?Y?Y?..Ym…Yn , Y(1-m) 即 前m个Y 都是非终结符.
      • 若FIRST(Yj) 1 <= j <= m 都含有ε，则把FIRST(Ym+1)中的非ε元素加入FIRST(X),直白点就是前面m个都可以为空，那就把他们取成空来算后面那个。
      • 若FIRST(Yj) 1 <= j <= n 都含有ε，则把ε加入FIRST(X).

若在构造过程中有FIRST(X)发生变化，从头开始
例：
G_S:
S -> aA
S -> d
A -> bAS
A -> ε
有FIRST集
FIRST(S) = {a,d}
FIRST(A) = {b,ε}
FIRST(aA) = {a}
FIRST(d) = {d}
FIRST(bAS) = {b}
FIRST(ε) = {ε}

FOLLOW集及其构造

对于A ∈ V_t，有 FOLLOW(A) = {a | S =*=> …Aa… , a ∈ V_t }

若S =*=> …A ,则规定 # ∈ FOLLOW(A)
这里用#作为输入串的结束符，也叫输入串符号

构造方法：
对于每个非终结符A，使用如下规则直到每个FOLLOW集不再增大：

  • 首先，若S为文法开始符号，{ # } ∈ FOLLOW(S)
  • 若 B -> αAβ 是一个产生式,则FIRST(β)-{ε} ∈ FOLLOW(A)
  • 若 B -> αA 或者 B -> αAβ且β =*=> ε，则FOLLOW(B) ∈ FOLLOW(A)
    例：
    A -> BCc|gDB
    B -> bCDE|ε
    C -> DaB|ca
    D -> dD|ε
    E -> gAf|c
    有
非终结符 FIRST集 FOLLOW集
A { a,b,c,d,g } { f,# }
B { b,ε } { a,c,d,g,f,# }
C { a,c,d } { c,d,g }
D { d,ε } { a,b,c,g,f,# }
E { c,g } { a,c,d,g,f,# }

LL(1)文法

L - 从左到右扫描字符串
L - 最左推导
1 - 每次分析根据当前单词向前看一个符号
图
满足上面三条的是LL(1)文法

LL(1)分析法

LL1分析法

预测分析表的构造

SELECT集

其实就是上面LL(1)分析法，用select作为中介方便写，不容易出错。
对于待输入字符a，我们现在匹配a，所以找到 a ∈ FIRST(A->α)

  • 若 α 不能推导出 ε ，那么 SELECT(A->α) = FIRST(α)
  • 若 α 能推导出 ε ，那么 SELECT(A->α) = (FIRST(α)-{ε}) ∪ FOLLOW(A)，其实就是 α 能推出 ε，所以还要考虑α = ε的情况啦，这时候(α = ε)匹配a的就应该是A后面跟的字符。
构造预测分析表

百度文库-构造
百度文库-示例

自下而上分析

语法分析的方法

图

图

短语和直接短语(算符优先分析)

图
图

算符优先分析法

句子可能有几种不同的归约方法，导致结果不同。如果事先规定算符的优先次序，并按照优先级进行归约，则这个归约过程就会是唯一的。
如，对于文法G[E]: E -> i | E+E | E-E | E*E | E/E | (E), 有句子i+i-i*(i+i)
其归约过程如下：
i+i-i*(i+i) E -> i
E+i-i*(i+i) E -> i
E+E-i*(i+i) E -> E+E
E-i*(i+i) E -> i
E-E*(i+i) 这一步涉及到算符优先级，需要先算乘法，而乘法算符后面是括号，括号优先级更高，应该先算括号表达式
E-E*(E+E) E -> i 两次
E-E*(E) E -> E+E
E-E*E E -> (E)
E-E E -> E*E
E E -> E-E
归约完成
但我们知道文法本身没有规定算符优先级，我们再看一个例子，同样对于上面的句子进行归约
图
归约过程中你会发现并不需要考虑算符优先级，这个句子依旧被正确地归约。 实际上我们是可以看出该文法优先级关系的。

算符优先关系

图
注意此关系与数学上的 < , = , > 是不同的，它表示左边的算符a与右边的算符b之间的关系，有前后顺序。
如对于 + 算符，数学上当然是两个加号相等的，不会出现大于小于关系(不考虑大于等于，小于等于)，但在算符优先关系上是可以规定优先级的，即可以规定左部的加号优先级小于右边的加号。
且图

算符优先文法

我们规定算符文法：
图
上面的计算的两个文法都是算符文法
继续规定:
图
怎么理解？
小写字母是终结符，大写字母是非终结符

  1. 如对于E -> (E) ，左( 和 右) 的优先级相等
  2. 对于E -> E?+E? ，这里用下标区分位置，又有E? -> E?*E?，所以 左+ 优先级小于 右*
  3. 对于E -> E?*E?,这里用下标区分位置,又有E? -> E?+E?，所以 左+ 优先级大于 右*

我们看到2与3似乎是矛盾的，但我们已经在上面的计算中发现该文法具有二义性，不能唯一地归约一个句子，所以这个矛盾恰恰说明其不是算符优先文法
我们规定：
图

例子：
图
得到算符优先关系表：
图

构造算符优先关系表

  1. 对于相等优先关系，我们只需要考虑产生式右部中各个候选式，连续出现的终结符的优先关系就行，不需要考虑非终结符的推导

  2. 大于小于优先关系则需要考虑非终结符的推导
    其简单理解就是P的所有推导式的最左的终结符和最右的终结符

构造FIRSTVT(P)的算法：

构造LASTVT(P)的算法：

构造关系表

句柄和规范归约(LR分析)

L: 从左到右扫描输入串
R: 自下而上进行归约
一个句型的最左直接短语叫句柄

例：

LR分析法

LR分析表：


空白表示报错



举例：

右边LR分析表的构造会在后面提到

LR(0)项目集规范族、DFA和分析表的构建

概念

例子:
文法：
S --> BB
B --> aB
B --> b

步骤:

  1. 拓展文法
    S’ --> S
    S --> BB
    B --> aB
    B --> b

  2. 求出项目集规范族
    Item0 = CLOSURE({S’ --> .S}) = {S’ --> .S，S --> .BB，B --> .aB，B --> .b}
    Item1 =GO(Item0,S) = CLOSURE({S’ --> S.}) = {S’ --> S.}
    Item2 = GO(Item0,B) = CLOSURE({S --> B.B}) = {S --> B.B，B --> .aB，B --> .b}
    Item3 = GO(Item0,a) = CLOSURE({B --> a.B}) = {B --> a.B，B --> .aB，B --> .b}
    Item4 = GO(Item0,b) = CLOSURE({B --> b.}) = {B --> b.}
    至此Item0已经遍历完，开始遍历下一个，由于Item1圆点已经到达末尾，所以跳过Item1。
    Item5 = GO({Item2,B) = CLOSURE({S --> BB.}) = {S --> BB.}
    由于 GO(Item2,a) 和 GO(Item2,b) 重复，所以去掉。
    Item6 = GO(Item3,B) = CLOSURE({B --> aB.}) = {B --> aB.}
    由于 GO(Item3,a) 和 GO(Item3,b) 重复，所以去掉。
    至此，项目集闭包不再增加，所以项目集规范族构造完毕！

  3. 构造DFA
    !

  4. 构造LR(0)分析表(根据DFA图将分析表填充)
    输入：文法G的扩展文法G’
    输出：G’的LR(0)分析表（即 Action表和Goto表）
    步骤：
    1、 本例中Item2 --B–> Item5，则在 状态号为2的行，列名为B的格中填入状态5
    (转移条件为非终结符，填充Goto表，填入状态号， 转移条件为终结符，填充Action表,
    填入Sn，Sn表示移进，移进符号并且移进状态号n)
    Item2 --a–> Item3 ，则在状态号为2的行，列名为a的格填入S3。
    2、 对于圆点在右部最右边：
    if A --> α. ∈ Itemk (0<k<n) & A --> α 为G的第 j 个产生式，
    then for 任意 a ∈ T U { # } do
    Action[k,a] = Rj
    （Rn表示归约，不移进符号，用第n个产生式的右部替换符号栈的X）
    3、 if S’ --> S. ∈ Itemk (0<k<n) then Action[k,#] = acc.

SLR(1)分析

见CSDN

LALR(1)分析

见CSDN