当前位置：文档之家 › 第四章语法分析

第四章语法分析

  • 格式：ppt
  • 大小：367.50 KB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

第四章语法分析

第四章语法分析



最右推导
E rm E rm (E) rm (E + E) rm (E + id) rm (id + id)
4.1 上下文无关文法
4.1.3 分析树 例 E E + E | E E | (E ) | E | id
E

E
( E ) E + E id
id
4.1 上下文无关文法

4.2 语言和文法
4.2.7 提左因子

有左因子的文法 A b1 | b2 提左因子 A A A b 1 | b 2

4.2 语言和文法

例 悬空else的文法 stmt if expr then stmt else stmt | if expr then stmt | other 提左因子

无二义的文法
stmt matched _stmt | unmatched_stmt matched_stmt if expr then matched_stmt else matched_stmt | other unmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt
句型 文法G的开始符为S，S *， 可能含有非终结符， 则叫做文法G的句型。
4.1 上下文无关文法

例 E E + E | E E | (E ) | E | id 最左推导
E lm E lm (E) lm (E + E) lm (id + E) lm (id + id)

按串长进行归纳：配对括号串可由S推出

语法分析-自顶向下分析

语法分析-自顶向下分析
例 S::=aABbcd|ε A::=ASd|ε B::=SAh|eC|ε C::=Sf|Cg|ε 求此文法的每一个非终结符号的FIRST集。
解： FIRST(S)=FIRST(aABbcd)∪FIRST(ε) ={a}∪{ε}={a,ε} FIRST(A)=FIRST(ASd)∪FIRST(ε) ={a,d}∪{ε}={a,d,ε} FIRST(B)=FIRST(SAh)∪FIRST(eC) ∪FIRST(ε) ={a,d,h}∪{e}∪{ε}={a,d,h,e,ε} FIRST(C)=FIRST(Sf)∪FIRST(Cg) ∪FIRST(ε) ={a,f}∪{a,f,g}∪{ε}={a,f,g,ε}
4.1自顶向下的分析方法（P61）
开始符号 输入符号串
自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推导出要分析的输入串。即：
开始符号 输入符号串
自底向上的分析方法从输入符号串开始，按最左归约方式向上归约到文法的开始符号。即：
+ 归约 ←
自底向上
文法符号的FIRST集合构造方法：
对于文法中的符号X∈V，其FIRST(X)集合可反复应用下列规则计算，直到其FIRST(X)集合不再增大为止： 若X为终结符，则将X加入FIRST(X)集合中。 若X为非终结符，且具有形如X→aα的产生式(a∈Vt)，或具有形如X→ε的产生式，则把a或ε加进FIRST(X)。 设X为非终结符且有形如X→Y1Y2…Yk的产生式，若Y1∈Vn，则把FIRST(Y1)中的一切非ε符号加进FIRST(X)；对于一切2≤i≤k，若Y1，Y2，…，Yi-1均为非终结符号，且ε∈FIRST(Yj)，1≤j≤i-1，则将FIRST(Yi)中的一切非ε符号加进FIRST(X)；但若对一切1≤i≤k，均有ε∈FIRST(Yi)，则将ε符号加进FIRST(X)。

编译原理-第四章语法分析-4.2上下文无关文法

编译原理-第四章语法分析-4.2上下文无关文法
博客园 用户登录 代码改变世界 密码登录 短信登录 忘记登录用户名 忘记密码 记住我 登录 第三方登录/注册 没有账户, 立即注册
编译原理 -第四章语法
1.形式语言 2.例
二、推导
1.定义 2.基本概念 3.例
三、语法分析树
1.定义 推导的图形表示形式，过滤掉了推导过程中对非终结符 应用产生式的顺序，描述如何从文法的开始符号推导出其语言中的一个语句 2.性质 3.例
四、二义性
1.定义 2.原因 在产生句子的过程中某些直接推导有多于一种选择 3.注意 4.例
五、验证文法产生的语言
六、上下文无关文法和正则表达式
1.文法 2.正则表达式 3.正则表达式到上下文无关文法转换 例：
参考——慕课-苏州大学

第4章 自顶向下的语法分析

第4章 自顶向下的语法分析

6
分析中出现的问题2：回溯问题
从各种可能的选择中随机挑选一种， 并希望它是正确的。 如果以后发现它是错误的，必须退 回去，再试另外的选择这种方式称为回 溯。 回溯代价极高，效率很低。
7
在自上而下的分析方法中如何选择使 用哪个产生式进行推导？ 假定要被替换的最左非终结符号是B， 且有n条规则：B→A1|A2|…|An，那么如何 确定用哪个右部去替代B？ 从文法的开始符号出发，如何根据当前 的输入符号（单词符号）唯一地确定选用哪 个产生式替换相应非终结符往下推导，或构 造一棵相应的语法树。
8
§4.2 FIRST和FOLLOW集合的构造
9
例1:输入串w=pccadd是否是合法的句子？
G：S→pA|qB A→cAd|a B→dB|b
S=>pA=>pcAd=>pccAdd=>pccadd 总结：本题中对于一个非终结符，存在若干 个候选式，即产生式形如：P→α1|α2|……|αn 每个候选式的第一个字符都是终结符， 且都不相同。这时可直接选用与当前输入符 号相同的那个候选式来替换P。
42
3. 若X为一非终结符，则查分析表M。 若M[X，a]中为A—产生式，将A自栈 顶弹出，将产生式右部符号串按逆序逐 一推入栈中；当产生式为A时，则只将 A→ε弹出即可。若M[X，a]中为空,则调 用出错处理程序。
43
算法实现
当前字符匹 配成功。 要对栈顶的 非终结符进 行替换。
44
初始化
注意一 定要逆 序入栈。
48
49
通过表4-9可以看到，每个非终结符对应 产生式的各个候选式的交集如下：
可以验证，此文法是LL(1)文法。
50
递归下降语法分析程序如下：

04 语法分析-自上而下分析

04 语法分析-自上而下分析

待分析的输入串： 待分析的输入串：i+i
只有当a 只有当a是允许出 现在非终结符A 现在非终结符A后 面的终结符时， 面的终结符时， 才可能允许A 才可能允许A自动 匹配。 匹配。
尾随集的定义： VN尾随集的定义：
=*>…Aa Aa…, FOLLOW(A)={a|S =*> Aa , a∈VT}； 特别地，如果S=*> S=*>…A 那么# FOLLOW(A)。 特别地，如果S=*> A，那么# ∈FOLLOW(A)。
例子
文法: S→xAy A→**|* 文法: 输入串：x*y 输入串： S => => => => xAy x**y xAy x*y (S→ xAy) (A→**) 回溯) (回溯) (A→*)
带回溯自上而下分析面临的问题
问题: 问题: 文法的左递归问题 回溯问题 虚假匹配问题 出错位置不确定 低效
实现思想： 实现思想：
分析程序由一组递归过程组成。 分析程序由一组递归过程组成。每一过程 对应于一个非终结符号。 对应于一个非终结符号。 每一个过程的功能是：选择正确的右部。 每一个过程的功能是：选择正确的右部。 在右部中有非终结符号时， 在右部中有非终结符号时，调用该非终结 符号对应的过程。 符号对应的过程。
消除文法的左递归
文法不含回路（形如P=+> P推导 推导） 文法不含回路（形如P=+> P推导） 不含回路 前提： 前提： 不含以ε 也不含以ε 为右部的产生式 结论： 那么可以通过执行消除文法左递 结论： 那么可以通过执行消除文法左递 归的算法消除文法的一切左递归 归的算法消除文法的一切左递归 改写后的文法可能含有以ε （改写后的文法可能含有以ε 为右部的产生式）。 为右部的产生式）。

语法分析

语法分析
23
if(Yi∈VN) { if(i=n or 任一j(i+1≤j≤n)null(Yj)=true) FOLLOW(Yi)=FOLLOW(Yi)∪FOLLOW(A); if(Yi+1∈VT) Yi+1∈FOLLOW(Yi); else for(k=i+1;k<=n;k++) if(k=i+1 or i+1≤j≤k-1)null(Yj)=true ) FOLLOW(Yi)=FOLLOW(Yi)∪FIRST(Yk) }/*end of if*/ }/*end of for*/ } /*end of for*/ while FIRST,FOLLOW,nullable 不再改变
1、思路：对任一输入符号串，通过一切可能的办 法，从树根结点(识别符号)出发，根据文法自 上而下地为输入串建立一棵语法树；或者说， 从识别符号开始，根据文法试图为输入串建立 一个推导序列。 2、特点：是自顶向下分析的一般方法，分析过程 的本质是一种试探过程。
4
例∶假定有文法G[S]:(1)S->cAd (2)A->ab|a 对输入串w=cad。要求自上而下地构造w的语法树。 解决过程： S c a S c A a d A b d －对于输入串w，从文法的开始符号出 发，反复使用不同的产生式谋求匹配 输入串。当用某个非终结符号的候选 式进行匹配失败时，则推翻分析退回 到适当位置再重新试探其它候选式， 直到把所有可能的推导序列都试探完 仍不成功才能确认输入串不是该文法 的句子而报错 。称为带回溯的自顶 向下分析。 －回溯需要推导记住现场，浪费了大量 的时间和空间，必须设法消除。
在推导过程中，可以完全根据向前看符号唯 一决定选择哪个产生式往下推导，因此，分析过 程是完全确定的。这种分析称为确定的自顶向下 分析方法。

第04章-语法分析自上而下分析

否符合语法规则。 ▪ 语法分析器的工作本质：按文法的产生式，识别
输入符号串是否为一个句子。 ▪ 语法分析器在编译器中的地位：
源程序
单词符号
词法分析器
取下一个单 词符号
语法分析器
语法分析树
编译器的 后继部分
2021/4/6
符号表
3
4.1 语法分析器的功能
▪ 语法分析方法
➢ 自上而下分析法
从文法的开始符号出发，反复使用文法的产生式， 寻找与输入符号串匹配的推导。
分析输入串x*y(记为)。
xx**yy
SS
IPIPIP xx A y * **
2021/4/6
7
4.2 自上而下分析面临的问题
▪ 当某个非终结符有多个产生式候选时，可 能带来如下问题：
➢ 1.分析过程中，当一个非终结符用某一个候选 匹配成功时，这种匹配可能是暂时的。这时， 不得不“回溯”。
➢ 2.文法左递归问题。一个文法是含有左递归的 ，如果存在非终结符P
➢ 最后所得的无左递归文法是： S→Qc | c Q→Rb | b R→bcaR | caR |a R R→ bca R |
➢ 不同排序所得的文法的等价性是显然的。
2021/4/6
17
4.3.2 消除回溯、提左因子
▪ 为了消除回溯就必须保证：对文法的任何 非终结符，当要它去匹配输入串时，能够 根据它所面临的输入符号准确地指派它的 一个候选去执行任务，并且此候选的工作 结果应是确信无疑的。
2021/4/6
14
4.3.1 左递归的消除
▪ 例4.3 考虑文法G(S)
S→Qc|c Q→Rb|b R→Sa|a
➢ 令它的非终结符的排序为R、Q、S。 ➢ 对于R，不存在直接左递归。 ➢ 把R代入到Q的有关候选后，把Q的规则变为

编译技术-第4章-语法分析(一)

基本任务：识别符号串S是否为某语法成分。 两大类分析方法：
自顶向下分析 自底向上分析
自顶向下分析算法的基本思想为：
若Z + S 则 S L(G[Z]) 否则 S L(G[Z])
G[Z]
主要问题: ➢ 左递归问题 ➢ 回溯问题
▪ 主要方法: • 递归子程序法 • LL分析法
自底向上分析算法的基本思想为：
第四章 语法分析
• 语法分析的功能、基本任务 • 自顶向下分析法＞ • 自底向上分析法＞
复习：第一章 概述
编译过程是指将高级语言程序翻译为等价的目标程 序的过程。 习惯上是将编译过程划分为5个基本阶段：
词法分析 语法分析 语义分析、生成中间代码 代码优化 生成目标程序
4.1 语法分析概述
功能：根据文法规则，从源程序单词符号串中识别出语法 成分，并进行语法检查。
若有规则：U∷=x|xy 则可以改写为：U∷=x(y|ε) 注意：不应写成U∷=x(ε|y)
使用提因子法，不仅有助于消除直接左递归，而且有 助于压缩文件的长度，使我们能更有效地分析句子。
规则二
若有文法规则：U∷=x|y|……|z|Uv
其特点是：具有一个直接左递归的右部并位于最后， 这表明该语法类U是由x或y……或z其后随有零个 或多个v组成。
若Z + S
G[Z]
则 S L(G[Z]) 否则 S L(G[Z])
主要问题: ➢ 句柄的识别问题
▪ 主要方法: • 算符优先分析法 • LR分析法
4.2 自顶向下分析
4.2.1 自顶向下分析的一般过程
给定符号串S，若预测是某一语法成分，则可根据该 语法成分的文法,设法为S构造一棵语法树， 若成功,则S最终被识别为某一语法成分,即

第四章 语法分析——自上而下分析


解二： 规定顺序：S、Q、R
则等价的无左递归的文法： SQc | c QRb| b RbcaR’ | caR’ | aR’ R’bcaR’ |
RSa | a RQca | ca | a
RRbca|bca | ca | a
RbcaR’|caR’ | aR’ R’ bcaR’|
（因为不需要试探某个候选式，而是准确地指派 某个候选式）
17
终结首符集FIRST
令文法G不含左递归，对它的所有非终结符的每 个候选式定义终结首符集 FIRST(): * FIRST()={a | a , a∈VT }
特别地 * 若 ，则规定 ∈ FIRST()
显然， FIRST()是从推导出的所有可能的开头终 结符a或 。
3
§4.2 自上而下分析面临的问题
一、带‚回溯‛的自上而下分析方法：
自上而下分析方法，就是对任何输入串，试 图用一切可能的方法，从文法的开始符号出发， 自上而下地为输入串建立一个语法树（或最左推 导）。 这种分析过程实质上是一种试探过程，即反 复使用不同的产生式以求能匹配输入串。
4
例4.1 设有文法： SxAy
解： S iCtSA | a
A | eS
C b
22
4.3.3 LL（1）分析条件 当一个文法不含左递归，并且满足每个非终结 符的所有候选首符集两两不相交，是不是一定能进 行有效的自上而下的语法分析呢？
若存在 ∈ FIRST() ，则问题较复杂，需要进 一步考虑。 定义：非终结符A的 FOLLOW 集：
* FOLLOW（A）= { a| S …Aa… ，a∈VT } 特别地， * 若S …A，则规定，构造FIRST（X）
a) 若X∈VT，则 FIRST(X)={X}。

917405-编译技术-电子教案-第4章-语法分析(一)


北京航空航天大学计算机学院
5
4.2 自顶向下分析
4.2.1 自顶向下分析的一般过程
给定符号串S，若预测是某一语法成分，则可根据该 语法成分的文法,设法为S构造一棵语法树， 若成功,则S最终被识别为某一语法成分,即
SL(G[Z])，其中G[Z]为某语法成分的文法 若不成功, 则 SL(G[Z])
• 可以通过一例子来说明语法分析过程
26
2.超前扫描
当文法不满足避免回溯的条件时，即各选择的首符号相 交时，可以采用超前扫描的方法，即向前侦察各输入符 号串的第二个、第三个符号来确定要选择的目标
这种方法是通过向前多看几个符号来确定所选择的目 标，从本质上来讲也有回溯的味道，因此比第一种方 法费时，但是假读仅仅是向前侦察情况，不作任何语 义处理工作。
a. 改写以后的文法消除了左递归。 b. 可以证明，改写前后的文法是等价的，表现在
L(G改前) = L(G改后)
如何改写文法能消除左递归，又前后等价， 可以给出两条规则:
北京航空航天大学计算机学院
12
规则一（提因子）
若：U∷=xy|xw|….|xz 则可改写为：U∷=x(y|w|….|z) 若：y=y1y2, w=y1w2 则 U∷=x(y1(y2|w2)|….|z)
改写文法： <程序> ∷= begin （<说明串>；<语句串> end | <语句串> end ）
引入 <程序*> <程序> ∷= begin <程序*> <程序*> ∷= <说明串>；<语句串> end | <语句串> end
北京航空航天大学计算机学院
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

字母表中后面的大写字母，如，，，可以是 终结符或非终结符
字母表中后面的小写字母，如， … 可代表 终结符号串
小写希腊字母，如，，可代表文法的符号串
对于 ， ，... 可以写成

…
上下文无关文法
推导（自顶向下）
把产生式看成重写规则，把符号串中的非终结 符用其产生式右部的串来代替
例
()
正则式不能用于描述配对或嵌套的结构 例：配对括号串的集合
上下文无关文法
上下文无关文法是四元组（ , , , ）
: 终结符集合
: 非终结符集合
: 开始符号，非终结符中的一个
: 产生式集合， 产生式形式 :
例 ( {, , , , (, )}, {, }, , )

()


简化表示
注解和空白由自己来处理的分析器，比注解 和空格已由词法分析器删除的分析器要复杂 得多
语言和文法
验证文法产生的语言
: ()
() 配对的括号串的集合
语言和文法
验证文法产生的语言
: ()
() 配对的括号串的集合
按推导步数进行归纳：推出的是配对括号串 归纳基础： 归纳假设：少于步的推导都产生配对的括号串 归纳步骤：步的最左推导如下：
文法的问题 文法只能描述编程语言的大部分语法，不能
描述语言中上下文有关的语法特征
语言和文法
正则式和上下文无关文法的比较
正则式 ()*
a 开始 0 a 1 b 2
文法
b
语言和文法
分离词法分析器理由
为什么要用正则式定义词法 词法规则非常简单，不必用上下文无关文法 对于词法记号，正则式描述简洁且易于理解 从正则式构造出的词法分析器效率高
() ( ) ( ) ( )
概念
* 、 ，于是
*
* ， 且 γ, 则
*γ
上下文无关文法
推导 概念 上下文无关语言 →γ, 且、是任意符号串，则 γ 由上下文无关文法生成的语言是上下文无关语
言 等价的文法 如果两个文法产生同样的语言，则两个文法等
价
上下文无关文法
例
()
最左推导

最右推导

再消除左递归

语言和文法 提左因子 有左因子的文法
提左因子
语言和文法
例 悬空的文法

提左因子

形式语言
⑴ 型语言 由 型文法定义
又称 无限制文法！
• 产生式形式为： > ⑵ 型语言 由 型文法定义
• 产生式形式为： >
⑶ 型语言 由 型文法定义 • 产生式形式为： >
() () 文法
()
语言和文法
()
expr
term
term * factor term * factor id
factor id
id 分析树
expr
expr + term
term term * factor
factor factor
id
id
id
分析树
Байду номын сангаас
消除二义性
语言和文法
句型： 两个最左推导：
语言和文法
章语法分析
第四章 语法分析
源程序
词法 分析器
记号
取下一个 记号
分析器
分析 树
前端的 中间 其余部分 表示
符号表
本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开
上下文无关文法
上下文无关文法
上下文无关文法的定义
正则式能定义一些简单的语言，能表示给定结 构的固定次数的重复或者没有指定次数的重 复 例： (), ()*

()
()
()
()
()
()
()
()
分析树 例
上下文无关文法 ()
()
二义性
上下文无关文法
两个不同的最左推导
二义性
上下文无关文法
E
E* id E
id
E 两棵不同的语法树E
+E
E*
id
id
E
+E E
id id
语言和文法
文法的优点 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改
⑷ 型语言 由 型文法定义
又称 上下文有关文法！
又称 上下文无关文法！
又称 正规文法！
• 产生式形式为：> , > , >
【注】 四类语言为 包含关系，且有 ⊃ ⊃ ⊃ ； 编译处理中，主要应用后两种文法！
乔姆斯基
艾弗拉姆·诺姆·乔姆斯基（英语 ： ，年月日－）
美国哲学家、语言学家、认知学 家、逻辑学家、政治评论家。乔 姆斯基是麻省理工学院语言学的 荣誉退休教授，他的生成语法被 认为是世纪理论语言学研究上的 重要贡献。

上下文无关文法 ()
简化表示

()

上下文无关文法
文法书写上的约定 终结符 字母表中的小写字母，如 ，， 黑体串，如 , 数字 , , … , 标点符号，如括号，逗号等 运算符号，如, 等 非终结符 字母表中的大写字母，如, ,
上下文无关文法
文法书写上的约定
() * () * ()
语言和文法
验证文法产生的语言
: ()
() 配对的括号串的集合
按串长进行归纳：配对括号串可由推出 归纳基础： 归纳假设：长度小于的都可以从推导出来 归纳步骤：考虑长度为( )的 ()
() * () * ()
语言和文法
适当的表达式文法 用一种层次观点看待表达式
()
语言和文法 适当的表达式文法 用一种层次观点看待表达式
无二义的文法



消除左递归 消除左递归
αβ
语言和文法
β αε
语言和文法
消除左递归
文法左递归
直接左递归
串的特点
...
消除直接左递归
语言和文法
例 算术表达文法



()
消除左递归后文法





()
（ ... ） （ ... ）
语言和文法
非直接左递归

先变换成直接左递归
句法结构
《句法结构》是乔姆斯基介绍转换生成语 法的《语言学理论的逻辑结构》一书的精 华版。这一理论认为说话的方式（词序） 遵循一定的句法，这种句法是以形式的语 法为特征的，具体而言就是一种不受语境 影响并带有转换生成规则的语法。
儿童被假定为天生具有适用于所有人类语 言的基本语法结构的知识。这种与生俱来 的知识通常被称作普遍语法。
语言和文法
从软件工程角度看，词法分析和语法分析的 分离有如下好处
简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分
语言和文法
能否把词法分析并入到语法分析中，直接从 字符流进行语法分析
若把词法分析和语法分析合在一起，则必须 将语言的注解和空白的规则反映在文法中， 文法将大大复杂