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

第三章 语法分析概况

  • 格式：ppt
  • 大小：842.50 KB
  • 文档页数：33

下载文档原格式

  / 33

合集下载

第3章 语法分析-编译原理及实践教程(第3版)-黄贤英-清华大学出版社

第3章 语法分析-编译原理及实践教程(第3版)-黄贤英-清华大学出版社
• 文法是被用来精确而无歧义地描述语言的句子的构成方式. • 文法描述语言的时候不考虑语言的含义。
3.2.1 文法的定义
例1：有如下规则
<句子><主语><谓语> <主语><代词>|<名词> <代词>我 <名词>大学生 <谓语><动词><直接宾语> <动词>是 <直接宾语><代词>|<名词>
(表示由…组成)
• 归约:推导的逆过程。
• 直接归约：直接推导的逆过程
几个概念的形式定义
• 直接推导: 如果αβ是文法 G=（Vn,Vt,P,S）
的产生式，γ和δ是Ｖ*中的任意符号，若有符号 串v,w满足： v=γαδ,w=γβδ,则说v直接产生w，(w是v的 直接推导)记作：v=>w 例：S01, 0S0=>0010(直接推导γ＝０,δ＝０) • 如果存在v=>w0=>w1=>w2...=>Wn=w(n>0)，则 称v推导出w（长度为n），记作v+=>w(至少一步) • 若有ｖ=>w或v=w，则记作v*=>w(0步或若干步)
一个非终结符号，β∈V*)
–上例中： G=（Vn,Vt,P,<句子>）
Vn=（<句子>，<主语>，<谓语>，<代词>，<动词>，
<名词>，<直接宾语>）
Vt= (我，是，大学生)
P=
<句子><主语><谓语>
<主语> <代词>|<名词>

03-第3章-语法分析-编译原理-中国科技大学(共13讲)

03-第3章-语法分析-编译原理-中国科技大学(共13讲)
VT : VN : S: P : 终结符集合 非终结符集合 开始符号，非终结符中的一个 产生式集合， 产生式形式 : A expr (expr) expr id op
• 例 ( {id, +, , , (, )}, {expr, op}, expr, P )
expr expr op expr expr expr op +
3.2 语言和文法
• 无二义的文法 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
3.2 语言和文法
expr expr + term | term term term factor | factor factor id | (expr)
expr term
term expr factor id term factor id expr + term * factor id id + id id 分析树
3.2 语言和文法
3.2.3 验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合 • 按串长进行归纳：配对括号串可由S推出
–归纳基础： S – 归纳假设：长度小于2n的都可以从S推导出来 – 归纳步骤：考虑长度为2n(n 1)的w = (x) y S (S)S * (x) S * (x) y
编译原理和技术
中国科学技术大学 计算机科学与技术学院 陈意云

编译原理及实现技术：7.语法分析__语法树、二义性文法

编译原理及实现技术：7.语法分析__语法树、二义性文法
一个现有文法是否为二义性文法。 常用的经验性判断:
SSS|a 可以推导出SSS串，必有二义性 SS+S 可以推导出S+S+S，必有二义 性
10
2.2 文法二义性的判定和利用
文法二义性的利用 对二义性文法进行修改，消除其二义性
会导致文法的复杂程度和符号数目迅速升 高。 可以利用二义性文法状态少，分析快的 特点，使用二义性文法，对具体问题加入 语义规则，约束其二义性即可。
16
若干历年考试题
设有一个文法G[S]: S->V V->T|ViT T->F|T+F F->V*|[
F+Fi[
句型F+Fi[的短语，简 单短语和句柄分别为： 首F,F+F, F+Fi[, [ 首F,[； 首F。
17
14
若干历年考试题
构造一个文法G，使 L(G)={anbmck|m=n+k,n≥1,m>1,k≥1}
G[S]: SAB AaAb| ab BbBc| bc
15
若干历年考试题
已知文法G[Z]: ZWV WaB | aW | a Bb | bB VbV | dD Dd | dD
判断文法G[Z]是否为二义性文法，如果是请举 例 句子abdd有两棵语法树。
语法树：设G是给定的语法，称满足下列条
件的树为G的一棵语法树： 1. 树的每个节点都标有G的一个语法符号，且根
节点标有初始符S。 2. 如果一个非叶节点A按从左到右顺序有n个儿子
节点B1、B2、…、Bn，则: AB1B2…Bn 一定是 G的一个产生式.
2
1.1 语法树的定义
例子：有文法
E
E E+T E T T T *F

第3章 语法分析

第3章 语法分析
计算机科学与技术学院 29
第3章 语法分析
2．1型文法与1型语言(对应线性界限自动机， 自然语言)
文法G的每一个产生式α→β，均在0型文法 的基础上增加了字符长度上满足∣α∣≤∣β∣的 限制，则称文法G为1型文法或上下文有关文法， 记为CSG。 1型文法相应的语言称为1型语言或上下文有 关语言，它的识别系统是线性界限自动机。
计算机科学与技术学院 5
第3章 语法分析
有了规则以后，可以按照如下方式用它们 去推导或产生句子: 符号⇒称为 <句子> ⇒ <主语> <谓语> “推导”， ⇒ <代词> <谓语> 它的含义是， ⇒ 我<谓语> 使用一条规 ⇒ 我<动词> <直接宾语> 则，代替⇒ 左端的某个 ⇒我是 <直接宾语> 符号，产生⇒ ⇒我是 <名词> 右端的符号 串。 ⇒我是大学生
计算机科学与技术学院 18
第3章 语法分析
用S表示“字母数字串”类，由于T是一字 母或数字，ST也是字母数字串。 则有： S→T∣ST
其中，产生式S→T∣ST是一种左递归形 式，由它可以产生一串T。 用I表示“标识符”类，它或者是一单个 字母，或者为一字母后跟字母数字串。 则有： I→L∣LS
计算机科学与技术学院 19
计算机科学与技术学院 28
第3章 语法分析
1. 0型文法与0型语言(对应图灵机)
如果文法G的每一个产生式具有下列形式： α→β 其中，α V* VN V* , β V* , V=VT∪VN 。 0型文法又叫短语文法，记为PSG。0型文 法相应的语言称为0型语言或称递归可枚举集， 它的识别系统是图灵（Turing）机。

第三篇语法分析

第三篇语法分析

E→E+E |E*E |（E） | -E | id
（1） （2） （3） （4） （5）
(G3.2)
E => -E
by(4)
=> -(E) by(3)
=> -(E+E) by(1)
=> -(id+E) by(5)
=> -(id+id) by(5)
13
3.2.2 CFG产生语言的基本方法－推导（续1）
19
3.2.3 推导、分析树与语法树（续3）
更多的情况下，仅关注句型结构，而忽略推导过程。
定义3.6 对CFG G的句型，表达式的语法树被定义为具有下
述性质的一棵树:
（1） 根与内部节点由表达式中的操作符标记；
（2） 叶子由表达式中的操作数标记；
（3）用于改变运算优先级和结合性的括弧，被隐含在语
法树的结构中。
句型是一个相当广泛的概念，根据定义3.3可知，α1和 α6同样也是句型。
E→E+E |E*E |（E） | -E | id
（1） （2） （3） （4） （5）
(G3.2)
16
3.2.3 推导、分析树与语法树
对于推导： E => -E => -(E) => -(E+E) => -(id+E) => -(id+id)
编译时想要准确诊断语义或逻辑错误有时是很困难的。
<2> 语法错误处理的目标
对语法错误的处理，一般希望达到以下基本目标： 1. 清楚而准确地报告错误的出现，地点正确、不漏报、 不错报也不多报； 2. 迅速从每个错误中恢复过来（以便分析继续进行）； 3. 不应使对语法正确源程序的分析速度降低太多。

编译原理(3)语法_4(自顶向下语法分析：LL(1)分析法)

编译原理(3)语法_4(自顶向下语法分析：LL(1)分析法)
2first集确定了每一个非终结符在扫描输入串时所允许遇到的输入符号及所应采用的推导产生式集确定了每一个非终结符在扫描输入串时所允许遇到的输入符号及所应采用的推导产生式该非终结符所对应的产生式中的哪一个候选式33自顶向下的语法分析式中的哪一个候选式3follow集是针对文法中形如a这样的产生式的即在使用这样的产生式的即在使用a的产生式进行推导时面临输入串中哪些输入符号时有一空字的产生式进行推导时面临输入串中哪些输入符号时有一空字即匹配而不出错
课本例题3.8 第二步：计算非终结符的FOLLOW集合
G[E]: E→TE' E'→ + TE' | ε T→FT' T'→*FT' | ε F→(E) | i ③由E→TE' 知FOLLOW(E) ⊂ FOLLOW(E' )， 即FOLLOW(E' ) = {),#}； 由E→TE ' 且E ' → ε知FOLLOW(E)FOLLOW(T)，即 FOLLOW(T) = {+,),#}；
特别是当Y1～Yk均含有ε产生式时，应把ε也加到FIRST(X)中。
课本例题3.8 第一步：计算非终结符的FIRST集合 例3.8 试构造表达式文法G[E]的LL(1)分析表，其中： G[E]: E→TE' E'→ + TE' | ε T→FT' T'→*FT' | ε F→(E) | i
[解答] 首先构造FIRST集，步骤如下： ① FIRST(E') = {+, ε}； FIRST(T') = {*, ε}； FIRST(F) = {(, i}； ② T→F… 和E→T…知:FIRST(F) ⊂ FIRST(T) ⊂ FIRST(E) 即有FIRST(F) = FIRST(T) = FIRST(E) = {(,i}。

第三章 语法分析3精品PPT课件

–在分析到某一步时，既可以移进，又可以归约。 上例第9)步可以移进*，也可以按产生式E→E+T 进行归约。
②归约-归约冲突
–存在两个可选的句柄可对栈顶符号进行归约。 例如上述第12)步，可以用T→F进行归约，又可 以按T→T*F进行归约。
各种分析方法中处理冲突的技术不同！
3.5 LR分析法
• 本节重点：
为了识别非终结符A，就要识别符号 串aBc。为此，构造一个DFA如图3-27所 示。
栈 输入 ＃S ＃
【例】文法G[S]: SaAcBe 待分析的句子为：abbcde
分析栈 # #a #ab #aA
输入串 abbcde#
bbcde# bcde# bcde#
A bAb B d
动作 移进 移进 归约 A b 移进
分析栈 #aAb #aA #aAc #aAcd #aAcB #aAcBe #S
关键：如何识别可归约的符号串？ 通过不同的自下而上的分析算法来解释，不同 的算法对可归约串的定义是不同的，但分析过 程都有一个共同的特点：边移进边归约。
规范归约：使用句柄来定义可归约串
算符优先：使用最左素短语来定义可归约串
自下而上语法分析主要有以下三种方法 ①简单优先分析法(规范归约)——文法按 一定原则规定文法符号的优先关系。 ②算符优先分析法(非规范归约)——规定 算符之间的优先关系。 ③ LR分析法（规范归约）—— LR(0)、 LR(1)、SLR(1)和LALR(1)。
• 句型→ 短语→ 直接短语 →句柄
注: 采用规范归约的算法，每次归约的部分就是分析为句柄 的字符串。 因此，在规范归约中，关键问题就转化为如何识别句柄?
练习பைடு நூலகம்
有文法如下: (1)E→E+T|T (2)T→T*F|F (3)F→(E)|id

语言学概论语法PPT


语语法学家对语法所做的主观描写。
语法学以语法为基础和研究对象。广义的语法还包括语法学的意思。
语法对所有社会成员来说是共同的。语法学是少数人研究的结果，因而远不止一个。
第一节 语法概说
语法的特点
抽象性 我们学习语法 小玲爱科学 施+动+受 解放军保卫祖国
运用词形变化表示事物的数目的类别。
世界语言中常见的数范畴有：单数、 复数 、双数 teacher—teachers、pen—pens
汉语中的“们”是复数标记吗？ 我们、你们、他/她们、它们 学生们、老师们
数
格是表示词语之间结构关系和语义关系的语法范畴。
一般用名词和代词的形态变化表示各种不同的格，有些语言中形容词和数词也有与名词相应的格。
世界语言中常见的格范畴：主格、宾格、通格、作格、与格、属格、旁格。
汉语“的”是否是领格标记？
格
时
时表示动作行为的发生时间与说话时间之间的时序关系。
世界语言中的时范畴一般有：过去时、现在时和将来时。
汉语中有时范畴吗？英语中有将来时吗？
体
体是通过动词的词形变化表现出来的事件或动作的状态（已经完成、正在进行、刚刚开始、即将结束、结果状态正在持续）。
1
戏台上摆着鲜花→鲜花摆在戏台上
6
台上坐着主席团→主席团坐在台上
5
墙上挂着画 →画挂在墙上
4
门上贴着对联 →对联贴在门上
A 式
台上演着京戏→台上正在演京戏
门外敲着锣鼓→门外正在敲锣鼓
外面下着大雨→外面正在下大雨
大厅里跳着舞→大厅里正在跳舞
教室里上着课→教室里正在上课
炉子上熬着粥→炉子上正在熬粥
B式
级
把具有共同特征的语法形式概括起来形成的类，就叫语法手段。

编译原理教程第五版课后答案

编译原理教程第五版课后答案第一章：引言问题1答：编译器是一种将高级编程语言源代码转换为目标机器代码的软件工具。

它由多个阶段组成，包括词法分析、语法分析、语义分析、中间代码生成、代码优化和代码生成等。

问题2答：编译器的主要任务包括以下几个方面： - 词法分析：将源代码划分为词法单元，如标识符、关键字、操作符等。

- 语法分析：根据语法规则，将词法单元组成语法树。

- 语义分析：对语法树进行语义检查，如类型匹配、变量声明等。

- 中间代码生成：将语法树转换为中间代码表示形式。

- 代码优化：对中间代码进行优化，以提高程序的效率。

- 代码生成：将优化后的中间代码转换为目标机器代码。

第二章：词法分析问题1答：词法单元是编译器在词法分析阶段识别的最小的语法单位，它由一个或多个字符组成。

常见的词法单元包括关键字、标识符、常量和运算符等。

问题2答：识别词法单元的方法包括以下几种： - 正则表达式：通过正则表达式匹配字符串，识别出各类词法单元。

- 有限自动机：构建有限状态自动机，根据输入字符的不同状态转移，最终确定词法单元。

- 递归下降法：使用递归下降的方式，根据语法规则划分出词法单元。

第三章：语法分析问题1答：语法分析是编译器的一个重要阶段，它的主要任务是根据给定的语法规则，将词法单元序列转换为语法树。

语法分析有两个主要的方法：自顶向下的分析和自底向上的分析。

问题2答：自顶向下的分析是从文法的起始符号开始，根据语法规则逐步向下展开，直到生成最终的语法树。

常见的自顶向下的分析方法包括LL(1)分析和递归下降分析。

问题3答：自底向上的分析是从输入串开始，逐步合并词法单元，最终生成语法树。

常见的自底向上的分析方法包括LR分析和LALR分析。

第四章：语义分析问题1答：语义分析的主要任务是对语法树进行语义检查和类型推断。

语义分析阶段会检查变量的声明和使用是否合法，以及类型是否匹配等。

问题2答：常见的语义错误包括变量未声明、类型不匹配、函数调用参数不匹配等。

编译原理第三章语法分析

void T() { F(); T’(); } void T’() { if(lookahead= =’*’) { match(‘*’); F(); T’(); } }
递归下降程序:
void F() { if(lookahead= =’i’) match(‘i’); else if(lookahead= =’(’) { match(‘(’); E(); if(lookahead= =’)’) match(‘)’); else error(); } else error(); }
输入串
id+id*id;# id+id*id;# id+id*id;# id+id*id;# id+id*id;# +id*id;# +id*id;#
动作
pop(L),push(E;L) pop(E),push(TE’) pop(T),push(FT’) pop(F),push(id) pop(id),next(ip) pop(T’)
形式语言分类
定义：若文法G=(N,T,P,S)的每个产生式α→β中，均有 α∈(N∪T)*N(N∪T)*,且至少含有一个非终结符， β∈(N∪T)*,则称G为0型文法（短语文法）。 ①1型文法（上下文有关文法）：G的任何产生式α→β(S→ε 除外)均满足|α|≤| β| (|x|表示x中文法符号的个数)； ②2型文法（上下文无关文法）：G的任何产生式形如A→β， 其中A∈N，β∈(N∪T)*； ③3型文法（正规文法、线性文法）：G的任何产生式形如A→a 或者A→aB(或者A→Ba）,其中A,B∈N,a∈T*。
定义：将产生式A→γ的右部代替文法符号序列αAβ 中的A得到αγβ的过程，称为αAβ直接推导 出αγβ，记作：αAβαγβ。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第三章 语法分析 3.6 有文法G[S]: S→aAcB|Bd A→AaB|c B→bScA|b
【解答】 (1) 分别画出对应句型aAaBcbbdcc和aAcbBdcc
的语法树如图3-4的(a)、(b)所示。
S a A c B a A S c B
A a B b S c A B d b (a) c
b S c A B d (b) c
个非终结符写出不带回溯的递归子程序。 【解答】 消除文法G[S]的左递归： S→(T) | a+S | a T→ST' T'→,ST' | ε 改写规则 A→Aα∣β 改写为
A→βA' A'→α A' |ε
第三章 语法分析
提取公共左因子：
S→(T) | aS' S'→+S | ε
T→ST'
T'→,ST' | ε
第三章 语法分析 3.3 已知文法 G[S] 为 S→aSb|Sb|b ，试证明文法 G[S] 为二义文 法。 【解答】 由文法G[S]：S→aSb|Sb|b ，对句子aabbbb 可对应如 图所示的两棵语法树。 S S
a S b a S b S b b S b a S b a S b b
因此，文法G[S]为二义文法。
【解答】 (2) 句子acabcbbdcc的最左推导如下：
SaAcB aAaBcB acaBcB
S a A c B
acabcB
acabcbScA acabcbBdcA acabcbbdcA acabcbbdcc
A a B b S c A c b B d c b
第三章 语法分析 3.7 对于文法G[S]: S→(L)|aS|a L→L,S|S (1) 画出句型(S,(a))的语法树； (2) 写出上述句型的所有短语、直接短语、句柄、素 短语和最左素短语。
S
S
b b
a
S S b
b b
第三章 语法分析 3.3 已知文法 G[S] 为 S→aSb|Sb|b ，试证明文法 G[S] 为 二义文法。 【解答 2】 由文法 G[S] ： S→aSb|Sb|b ，对句子 abbb 存 在两种不同的最右推导：
S aSb aSbb abbb
S Sb aSbb abbb 因此，文法G[S]为二义文法。
第三章 语法分析
3.7 对于文法G[S]: S→(L)|aS|a L→L,S|S 【解答】 (1) 句型(S, (a))的语法树如图3-5所示。
S ( L ) L , S S ( L ) S a
图3-5 句型(S,(a))的语法树
第三章 语法分析 3.7 对于文法G[S]: S→(L)|aS|a L→L,S|S
SaAcB
aAcbScA aAcbScc aAcbBdcc aAcbbdcc
退六步： aAaBcbbdcc 退五步： AaB，bbdcc 退四步： AaB，bd，c
退三步： AaB，bd
退两步： AaB，b 退一步：Abbdcc的短语：AaB，b，bd，c， bbdcc， aAaBcbbdcc 句型aAaBcbbdcc的直接短语： AaB，b，c 句型aAaBcbbdcc的句柄： AaB
图3-4 习题3.6的语法树 (a) aAaBcbbdcc; (b) aAcbBdcc
第三章 语法分析
对树(a)，直接短语有3个：AaB、b和c，而AaB为最 左直接短语(即为句柄)。对树(b)，直接短语有两个： Bd和c，而Bd为最左直接短语。
第三章 语法分析 3.6 有文法G[S]: S→aAcB|Bd A→AaB|c B→bScA|b
第三章 语法分析 3.6 有文法G[S]: S→aAcB|Bd A→AaB|c B→bScA|b 【解答】 (1)句型aAcbBdcc的最右推导
SaAcB
aAcbScA aAcbScc aAcbBdcc
退四步： aAcbBdcc 退三步： bBdcc 退两步： Bd，c
退一步：Bd
句型aAcbBdcc的短语：Bd，c， bBdcc ， aAcbBdcc 句型aAcbBdcc的直接短语： Bd，c 句型aAcbBdcc的句柄： Bd
S
【解答】(2) 由语法树可知： 短语：S、a、(a)、S,(a)、(S,(a))； 直接短语：a、S； 句柄：S； 素短语：a
( L ) L , S S ( L ) S a
第三章 语法分析 3.9 考虑文法G[S]: S→(T) | a+S | a T→T,S | S
消除文法的左递归及提取公共左因子，然后对每
第三章 语法分析 3.6 有文法G[S]: S→aAcB|Bd A→AaB|c
B→bScA|b
(1) 试求句型aAaBcbbdcc和aAcbBdcc的句柄； (2) 写出句子acabcbbdcc的最左推导过程。
第三章 语法分析 3.6 有文法G[S]: S→aAcB|Bd A→AaB|c B→bScA|b 【解答】 (1)句型aAaBcbbdcc的最右推导
不带回溯的递归子程序如下：
void match (token t) {
(对句子abbb也可画出 两棵不同语法树)
第三章 语法分析 3.3 已知文法 G[S] 为 S→aSb|Sb|b ，试证明文法 G[S] 为 二义文法。 【解答 1】 由文法 G[S] ： S→aSb|Sb|b ，对句子 abbb 可 对应如图所示的两棵语法树。
S a S b
因此，文法G[S]为二义文法。
第三章 语法分析 3.4 已知文法 G[S] 为 S→SaS|ε ，试证明文法 G[S] 为二义文法。
【解答1】 由文法G[S]：S→SaS|ε，句子aa的语法树如图所示。
S S a S S a S (a) S S a S S a S (b)
因此，文法G[S]为二义文法。
第三章 语法分析 3.4 已知文法 G[S] 为 S→SaS|ε ，试证明文法 G[S] 为二义文法。 【解答2】 由文法G[S]：S→SaS|ε，句子aa存在两种不同的最 右推导： S SaS Sa SaSa Saa aa S SaS SaSaS SaSa Saa aa 因此，文法G[S]为二义文法。