4. 语法分析_输入:键盘输入待分析的符号串 输出:采用递归下降子程序法时输出分析结果;采用预测

4. 语法分析

语法分析器的任务

早期：检查输入的记号中包含的语法是否合法

后期：生成的抽象语法树便于语义分析器或者代码生成器进一步的处理

输入：记号流 输出：抽象语法树中间表示

研究给定记号流输入是否合法：满足语言的语法规则（YES/NO）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PhsPjUPh-1641910962075)(…/picture/96.png)]

语法分析：

数学理论（上下文无关文法）（CFG）

• 自顶向下分析
• • 递归下降分析算法（预测分析算法）
  • LL分析算法
• 自底向上分析
• • LR分析算法

CFG（上下文无关文法）

表示

非终结符：大写

终结符：小写

开始符号：第1个终结符

推导：给定文法G，从G的开始符号S开始，用产生式的右部替换左侧的非终结符

过程中的串称为句型，最终的串称为句子

最左推导：每次总是选择最左侧的符号进行替换

S -> NVN
  -> sVN
  -> sdN
  -> sds
1
2
3
4

==最右推导：==每次总是选择最右侧的符号进行替换

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-koRTp7UQ-1641910962076)(…/picture/97.png)]

给定文法G和句子s，语法分析的任务：

是否存在对句子s的推导

分析树与二义性

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0aI6c7ky-1641910962077)(…/picture/98.png)]

• 推导表达成树状结构
• • 和推到所用的顺序无关（最左，最右，其他）
• 特点：
• • 树中的每个内部节点代表非终结符
  • 每个叶子节点代表终结符
  • 每一步推导代表如何从双亲结点生成它的直接孩子节点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nF13OQta-1641910962078)(…/picture/99.png)]

二义性

给定文法G，如果存在句子s，它有两棵不同的分析树，那么称G是二义性文法。

二义性文法存在的问题：

• 同一个程序会有不同的含义
• 因此程序运行的结果不是唯一的

解决方案：文法的重写

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BCMOIaGg-1641910962081)(…/picture/100.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lFfNfCya-1641910962082)(…/picture/101.png)]

左递归对应于左结合

右递归对应于右结合

自顶向下分析

思想：从G的开始符号出发，随意推导出某个句子t，比较t和s

对应于分析树自顶向下的构造顺序

从根开始构建语法树，并使树向叶子的方向增长

每一步

• 在树的下边缘选择一个表示某个非终结符的结点
• 用一个子树来扩展该结点
• 子树表示了重写该非终结符时所用产生式的右侧部分

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F8fX9L1R-1641910962082)(…/picture/102.png)]

这个过程用一个栈来维护

产生式右部先压栈

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8u7KvhWD-1641910962083)(…/picture/103.png)]

算法过程：

1. 关注的符号是非终结符：由该符号处向下扩展语法分析树
2. 关注的符号是终结符：与输入流中的单词进行比较。如果相同，继续考察边缘的下一个符号；首先看规则有哪些备选；若用尽，在分析树上继续向上回溯；无法匹配的话进行报错。

算法需要回溯，复杂度过高。

我们需要线性时间（避免回溯的）算法

• 递归下降分析算法
• LL（1）分析算法

用前看符号避免回溯

选择产生式右侧进行替换时，同时考虑下一个输入符号，称为前瞻符号。

注意：若有多条候选式开始符号相同，那也有可能产生回溯

比如说：$N\to g|gN$

递归下降分析

也称为预测分析

• 分析高效（线性时间）
• 容易实现（方便手工编码）
• 错误定位和诊断信息准确

算法基本思想：

• 每个非终结符构造一个分析函数
• • 实际不一定为每个非终结符构造分析函数
• 用前看符号指导产生式规则的选择

采用分治法

算法的一般框架

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6VhNB4ZQ-1641910962084)(…/picture/104.png)]

实例：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ok4y30Ee-1641910962085)(…/picture/106.png)]

通过改写文法（提取左公因子）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Cr69R0oB-1641910962086)(…/picture/105.png)]

LL（1）分析算法

LL（1）：从左（L）向右读入程序/输入串，最左（L）推导，采用一个（1）前看符号

• 分析高效（线性时间）
• 错误定位和诊断信息准确
• 有很多开源或商业的生成工具

算法基本思想：

• 表驱动的分析算法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xMQUt801-1641910962088)(…/picture/107.png)]

采用不用回溯的方式。

一次性将正确的产生式右部放入栈中。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KO0U9Wa4-1641910962089)(…/picture/108.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KXODGdQM-1641910962089)(…/picture/109.png)]

First集

定义：

First（N）：从非终结符N开始推导得出的句子开头的所有可能终结符集合

$$

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MUtZDkTO-1641910962090)(…/picture/110.png)]

$p:N\to {\beta }_1{\beta }_2\dots {\beta }_n$

如果First_S集是 { x 1 , … , x n } \{x_1,\dots,x_n\} {x1​,…,xn​}

把$p$填到表$[N,x_i],x_i$是前看符号

若表中每个项最多只有一个元素，叫做$LL(1)$文法；

否则叫做冲突，不是$LL(1)$类型的文法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mxF7O5RU-1641910962090)(…/picture/111.png)]

冲突检测：对两条产生式规则$N\to \beta$和$N\to \gamma$，要求 F i r s t _ S ( β ) ∩ F i r s t _ S ( γ ) = { } First\_S(\beta) \cap First\_S(\gamma)=\{\} First_S(β)∩First_S(γ)={}，否则发生冲突

此时对于4，5 F I R S T _ S ( w ) ∩ F I R S T _ S ( w V ) = { w } FIRST\_S(w) \cap FIRST\_S(wV)=\{w\} FIRST_S(w)∩FIRST_S(wV)={w}

NULLABLE集合

非终结符X属于集合NULLABLE，当且仅当：

• 基本情况：

• • $X\to \epsilon$

• 归纳情况：

• • $X\to Y_1\dots Y_n$
  • $Y_1,\dots Y_n$是n个非终结符，且都属于NULLABLE集

即：若$X{\to }^{\ast }\epsilon$，X属于集合NULLABLE

FIRST集合的完整计算公式

• 基本情况
• • $X\to a$
  • F I R S T ( X ) ∪ = { a } FIRST(X) \cup=\{a\} FIRST(X)∪={a}
• 归纳情况：
• • $X\to Y_1{Y}_2\dots Y_n$
  • $First(X)\cup =First(Y_1)$
  • $if(Y_1\in NULLABLE),FIRST(X)\cup =FIRST(Y_2)$
  • $if(Y_2\in NULLABLE),FIRST(X)\cup =FIRST(Y_3)$

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YJlpXlcb-1641910962091)(…/picture/112.png)]

FOLLOW集计算

FOLLOW(N)：在包含N的句子中，N后面可以跟哪些终结符号

对于每一个产生式$p:N\to {\beta }_1{\beta }_2\dots {\beta }_n$：（每一次从${\beta }_n\to {\beta }_1$逆向查找）

temp = FOLLOW(N) 注意：赋初值

• 基本情况：${\beta }_i=a$
• • temp = {a}
• 归纳情况：${\beta }_i=M$
• $FOLLOW(M)\cup =temp$
• • 如果M不是NULLABLE $temp=FIRST(M)$
  • 如果M是NULLABLE $temp\cup =FIRST(M)$

计算FIRST_S集合

对于每一个产生式$p:N\to {\beta }_1{\beta }_2\dots {\beta }_n$：（每一次从${\beta }_1\to {\beta }_n$正向查找）

• 基本情况：${\beta }_i=a$
• • F I R S T _ S ( p ) = { a } FIRST\_S(p)=\{a\} FIRST_S(p)={a} 结束
• 归纳情况：${\beta }_i=M$
• • $FIRST\_S(p)\cup =FIRST(M)$
  • • 如果M不是NULLABLE 结束
    • 如果M是NULLABLE继续循环
  • 如果程序都没有中途结束，那么他需要最后$FIRST\_S(p)\cup =FOLLOW(N)$

LL(1)分析表的构造

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lMdUFrrF-1641910962091)(…/picture/113.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Xw1j2ZKz-1641910962092)(…/picture/114.png)]

注意：压栈的时候需要按照右部逆序压栈

得到冲突的LL（1）分析表，有可能发生回溯，不合适。

需要通过变换，满足LL（1）的要求，去除冲突。

方式一：消除左递归

• 直接左递归：$A\to A\beta$

• 间接左递归：$A\to B\beta ,B\to A\alpha$

• • 也就是$A\to A\alpha \beta$

任何有左递归的文法都不是LL（1）文法

消除直接左递归：

• 引入新的非终结符，变为右递归

一般形式：

$A\to A{\alpha }_1|A{\alpha }_2|\dots |{\beta }_1|{\beta }_2$

转化为：

$A={\beta }_1{A}^{\prime }|{\beta }_2{A}^{\prime }|\dots$

$A^{\prime }={\alpha }_1{A}^{\prime }|{\alpha }_2{A}^{\prime }|\dots |\epsilon$

消除间接左递归

• 先通过产生式非终结符置换，变为直接左递归
• 在消除直接左递归
• 去掉无用产生式（不可到达的非终结符），加入原来的产生式

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EnyMeDxN-1641910962093)(…/picture/115.png)]

循环递归进行排序：排序再越前面的，越早被消掉。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jt6D0hZK-1641910962108)(…/picture/116.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NKPUOayv-1641910962109)(…/picture/117.png)]

方式二：提取左公因子

原始：$A\to \alpha {\beta }_1|\alpha {\beta }_2|\dots |{\gamma }_1|{\gamma }_2|\dots$

替换后：

$A\to \alpha A^{\prime }|{\gamma }_1|\dots |{\gamma }_m$

$A^{\prime }={\beta }_1|{\beta }_2|\dots$

有以下的情况：左公因子是隐式的

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mFVUe6ED-1641910962109)(…/picture/118.png)]

变换产生无用产生式与无用符号

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JTiYvqwx-1641910962110)(…/picture/119.png)]

不能在有限步骤内提完

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QvYSVaD3-1641910962110)(…/picture/120.png)]

LL（1）文法特点

• 右递归、无回溯
• 若文法中含有左递归的非终结符，则它必然是非LL（1）文法
• LL（1）分析表中每个项最多只有一个元素，否则叫做冲突。
• • 判断：相同左部的产生式的First_S集的交集是否为空
• 转换方式
• • 消除左递归，提取左公因子（但转换完未必是LL（1））

lookahead：全局量，存放当前所扫描单词符号

MatchToken（）：匹配当前终结符和正在扫描单词符号的函数

构造递归下降分析程序

根据产生式和First_S进行构造

• 首先根据lookahead判断First是啥？
• 然后根据产生式，非终结符调用子程序，和终结符调用MatchToken

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9Y453oEe-1641910962111)(…/picture/121.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TCSmPyJz-1641910962111)(…/picture/122.png)]

LL（1）分析法：

分析表+驱动代码

优点：

算法运行高效

有现成的工具可用

缺点：

能分析的文法类型受限

往往需要文法改写

LR（0）分析算法

LR分析算法（移进、规约算法）

• 算法运行高效
• 有现成的工具可用
• 广泛的一类语法分析器的自动生成器中采用的而算法

比LL（1）分析文法范围广、不需要改写

采用自底向上分析：

从叶子节点开始构建语法树，并使树向根的方向增长

• 每一步
• • 在语法分析树上边缘处识别出一个连续的子串
  • 该字串与某个产生式的右侧匹配
  • 构建一个节点表示该产生式的左侧，并将其连接到树中

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RE11xVlS-1641910962112)(…/picture/123.png)]

为了方便标记语法分析器已经读入了多少输入，我们引入一个点记号·

点之前表示已经读入的，点之后表示剩余的输入

逆序的最右推导需要两个步骤

• 移进 去一个记号到栈顶上，或者
• 归约 栈顶上的n个符号（某产生式的右部）到左部的非终结符

对产生式$A\to {\beta }_{1}dots{\beta }_n$

如果${\beta }_n\dots {\beta }_1$在栈顶，弹出后，压入A

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-40owSM9d-1641910962113)(…/picture/124.png)]

项A->· XYZ表明我们希望接下来在输入中看到一个从XYZ推导得到的串。

项A->X· YZ说明我们刚在输入中看到了一个可以由X推导得到的串，希望接下来看到一个能从YZ推导得到的串。

项A->XYZ· 表示我们已经看到了产生式体XYZ，是时候把XYZ归约到A了。

构造方框的时候注意：

首先加入$S’ \to ·S$$

如果点号后面是非终结符，则需要把该非终结符的所有产生式写进该方框中。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yN4PunzB-1641910962113)(…/picture/125.png)]

例题：10P31

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NOWLFjgM-1641910962114)(…/picture/126.png)]

s：shift移进。s后面的数字表示状态（读入终结符）

g：goto转移。g后面的数字表示状态（读入非终结符）

r：reduce归约。r后面的数字表示规则编号

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tEUaxZq8-1641910962114)(…/picture/127.png)]

分析栈注意：

最底下是一个（$，1）

每一次入栈都是（字符，状态号）两个一起入栈

点号在最后时，对于任何终结符都进行规约

特殊情况$S^{\prime }\to S\cdot$，输入是$$$时，设为accept

填表时注意：

s、g接受字符转移到对应状态

r不管接受任何字符（终结符），都是根据表达式进行规约（只要点号在最后面）

·在$前面输出accept

优点：

容易实现

缺陷：

从左向右读入程序，采用最右推导，不用前看符号

能分析的文法有限

对所有读入非终结符都进行归约，会延迟错误发现时机

LR（0）分析表中可能包含冲突

注意：严格的LR（0）分析表没有移进规约冲突

所以考虑SLR分析算法

SLR分析算法

• 和LR（0）分析算法基本步骤相同
• 仅区别于对归约的处理
• 对于状态i上的项目$X\to \alpha$
• • 仅对$y\in FOLLOW(X)$添加$ACTION[i,y]=rk$

例题11P27

优点：

有可能减少需要归约的情况

有可能去除需要移进-规约冲突

缺点：

仍有冲突出现的可能

因为简单考察下一个输入符号y是否$y\in FOLLOW(X)$

但$y\in FOLLOW(X)$只是进行规约的一个必要条件，而非充分条件

不是对FOLLOW(X)中的所有符号都应该进行规约

LR（1）文法

需要在项目中加入超前扫描符号/向前搜索符/后继符/前看符号的信息

• $[X\to \alpha \cdot \beta ,a]$

• • $\alpha$在栈顶上
  • 剩余的输入能够匹配$\beta a$

• 当归约$X\to \alpha \beta$时，a是前看符号

• • 把reduce by $X\to \alpha \beta$填入ACTION[s,a]

其他与LR（0）相同，仅闭包的计算不同：

• 对项目$[X\to \alpha \cdot Y\beta ,a]$
• • 添加$[Y\to \gamma ,b]$到项目集
  • 其中$b\in FIRST\_S(\beta a)$

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0ldUvy8V-1641910962115)(…/picture/128.png)]

两个项目集相同，只有前看符号不同，则称这两个项目集同心

例题：11P50

LR（1）分析法特点：

• 对搜索符的计算方法比较确切，可以解决SLR方法解决不了的问题
• 但对同心集的分裂使状态数目剧烈增长，导致存储容量的急剧增加

LALR（1）分析法

• 把LR（1）中类似的项目集（同心集）进行合并

• • 同心集：具有相同核心的项目集，即第一部分一样

• 需要修改ACTION表和GOTO表，以反映合并的效果

• 若合并同心集后不产生新的冲突，则为LALR（1）项目集

• 若有冲突（只可能是归约-归约冲突），不能成为LALR（1）文法

• • 规约规约冲突：
  • • 不同产生式有相同的右部
    • 或产生式的右部是另一个产生式的后缀

• 合并同心集后，会推迟错误的发现

合并之后项目的核心不会发生变化，只是超前搜索符的集合为各同心集超前搜索符集合的并集

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NsUVYsIr-1641910962116)(…/picture/129.png)]

LALR（1）特点

形式上与LR（1）相同

大小上与LR（0）/ SLR相当

SLR < LALR(1) < LR(1)

合并后的前看符集合仍为FOLLOW集的子集

二义性文法

任何一个二义性文法不是LR类文法，也不是LL（k）文法

不存在与其相对应的语法分析器

人为给出优先级、结合性的规定，构造更优越的LR分析器

两个项目集相同，只有前看符号不同，则称这两个项目集同心

例题：11P50

LR（1）分析法特点：

• 对搜索符的计算方法比较确切，可以解决SLR方法解决不了的问题
• 但对同心集的分裂使状态数目剧烈增长，导致存储容量的急剧增加

LALR（1）分析法

• 把LR（1）中类似的项目集（同心集）进行合并

• • 同心集：具有相同核心的项目集，即第一部分一样

• 需要修改ACTION表和GOTO表，以反映合并的效果

• 若合并同心集后不产生新的冲突，则为LALR（1）项目集

• 若有冲突（只可能是归约-归约冲突），不能成为LALR（1）文法

• • 规约规约冲突：
  • • 不同产生式有相同的右部
    • 或产生式的右部是另一个产生式的后缀

• 合并同心集后，会推迟错误的发现

合并之后项目的核心不会发生变化，只是超前搜索符的集合为各同心集超前搜索符集合的并集

[外链图片转存中…(img-NsUVYsIr-1641910962116)]

LALR（1）特点

形式上与LR（1）相同

大小上与LR（0）/ SLR相当

SLR < LALR(1) < LR(1)

合并后的前看符集合仍为FOLLOW集的子集

二义性文法

任何一个二义性文法不是LR类文法，也不是LL（k）文法

不存在与其相对应的语法分析器

人为给出优先级、结合性的规定，构造更优越的LR分析器