当前位置：文档之家 › 山东理工大学-编译原理内部课件-第三章：短语直接短语句柄

山东理工大学-编译原理内部课件-第三章：短语直接短语句柄

  • 格式：ppt
  • 大小：621.00 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

编译原理教程-课后习题答案第三章语法分析

编译原理教程-课后习题答案第三章语法分析
第三章 语法分析
第三章 语法分析
3.1 完成下列选择题：
(1) 文法G：S→xSx|y所识别的语言是 。
a. xyx
b. (xyx)*
c. xnyxn(n≥0)
d. x*yx*
(2) 如果文法G是无二义的，则它的任何句子α 。
a. 最左推导和最右推导对应的语法树必定相同
b. 最左推导和最右推导对应的语法树可能不同
能否不画出语法树，而直接由定义(即在句型中)寻 找满足某个产生式的候选式这样一个最左子串(即句柄) 呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描 找到第一个子串AaB，它恰好是满足A→AaB右部的子串； 与树(a)对照，AaB的确是该句型的句柄。是否这一方法 始终正确呢？我们继续检查句型aAcbBdcc，由左至右找 到第一个子串c，这是满足A→C右部的子串，但由树(b) 可知，c不是该句型的句柄。由此可知，画出对应句型 的语法树然后寻找最左直接短语是确定句柄的好方法。
第三章 语法分析
(2) 为了构造字母表Σ ={a,b}上同时只有奇数个a 和奇数个b的所有串集合的正规式，我们画出如图3-3 所示的DFA，即由开始符S出发，经过奇数个a到达状态 A，或经过奇数个b到达状态B；而由状态A出发，经过 奇数个b到达状态C(终态)；同样，由状态B出发经过奇 数个a到达终态C。
第三章 语法分析
3.9 考虑文法G[S]: S→(T) | a+S | a T→T,S | S
消除文法的左递归及提取公共左因子，然后对每 个非终结符写出不带回溯的递归子程序。
【解答】 消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε
第三章 语法分析 提取公共左因子：

《编译原理》幻灯片

《编译原理》幻灯片

文法和语言
➢怎样理解四种文法之间的关系？
➢
四种文法之间的关系是对产生式逐
步做更多的限制而定义的。为此，它们所
定义语言之间的关系依次是：有不是上下
文有关语言的0型语言，有不是上下文无关
语言的1型语言，有不是正那么语言的上下
文无关语言
编译原理 计算机学院 李金厚
几个理论共识
➢结论1：0型文法(短语构造文法)的能力相 当于图灵机，可以表征任何递归可枚举集， 而且任何0型语言都是递归可枚举的
➢
L(G)= {0n1n|n≥1}集合表示形式
编译原理 计算机学院 李金厚
文法、语言和句子
➢ 例 文法G[S]： ➢ ➢ ➢ ➢ ➢ ➢ ➢
〔1〕S→aSBE 〔2〕S→aBE 〔3〕EB→BE 〔4〕aB→ab 〔5〕bB→bb 〔6〕bE→be 〔7〕eE→ee
L(G)={ anbnen | n≥1 }
➢
要对程序设计语言给出准确无二义的语
法描述，严谨、简洁、易读
➢ 形式化工具
➢ “形式化〞是指这样的事实：语言的所有规那 么只以什麽符号串能出现的方式来陈述，形式化 很像是数学的符号化
编译原理 计算机学院 李金厚
文法的直观概念
➢ 以自然语言为例，人们罗列出所有的句子，但人 们可以给出一些规那么，用它们来说明或定义句 子合理的组成构造
➢ 通过观察可以知道，上述文法定义的句子是用符 号a，+，*，( 以及 )构成的算术表达式
编译原理 计算机学院 李金厚
语言、文法和句子
➢例，由文法G生成的语言记为L(G),它是文 法G的一切句子的集合: L(G)={x|S * x，其中S为文法的开场符 号，且x ∈VT*}
➢

《编译原理》课后习题答案第三章第3章文法和语言第1

《编译原理》课后习题答案第三章第3章文法和语言第1

《编译原理》课后习题答案第三章第3 章文法和语言第1 题文法G＝({A,B,S},{a,b,c},P,S)其中P 为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第2 题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案:G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D......D或者：允许0 开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4 题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。

盛威网（）专业的计算机学习网站 1《编译原理》课后习题答案第三章答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={anbn|n>=1}第5 题写一文法，使其语言是偶正整数的集合。

要求：(1) 允许0 打头；(2)不允许0 打头。

答案：(1)允许0 开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0 开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6 题已知文法G：<表达式>::=<项>｜<表达式>＋<项><项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。

（５）i+(i+i)（６）i+i*i盛威网（）专业的计算机学习网站 2 《编译原理》课后习题答案第三章答案：<表达式><表达式> + <项><因子><表达式><表达式> + <项><因子>i<项><因子>i<项><因子>i（ )(5) <表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）<表达式><表达式> + <项><项> * <因子><因子> i<项><因子>ii(6) <表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i盛威网（）专业的计算机学习网站 3《编译原理》课后习题答案第三章第7 题证明下述文法G[〈表达式〉]是二义的。

编译原理第3章文法和语言

编译原理第3章文法和语言

第3章文法和语言第1题文法G＝({A,B,S},{a,b,c},P,S)其中P为：S→Ac|aBA→abB→bc写出L(G[S])的全部元素。

答案：L(G[S])={abc}第2题文法G[N]为：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？答案:G[N]的语言是V+。

V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD....=>NDDDD...D=>D......D或者：允许0开头的非负整数？第３题为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4题已知文法G[Z]：Z→aZb|ab写出L(G[Z])的全部元素。

答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbbL(G[Z])={anbn|n>=1}第5题写一文法，使其语言是偶正整数的集合。

要求：(1)允许0打头；(2)不允许0打头。

答案：(1)允许0开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允许0开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6题已知文法G：<表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子><因子>::=（<表达式>）｜i试给出下述表达式的推导及语法树。

（５）i+(i+i)（６）i+i*i答案：(5)<表达式>=><表达式>＋<项>=><表达式>＋<因子>=><表达式>＋（<表达式>）=><表达式>＋（<表达式>＋<项>）=><表达式>＋（<表达式>＋<因子>）=><表达式>＋（<表达式>＋i）=><表达式>＋（<项>＋i）=><表达式>＋（<因子>＋i）=><表达式>＋（i＋i）=><项>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）(6)<表达式>=><表达式>＋<项>=><表达式>＋<项>*<因子>=><表达式>＋<项>*i=><表达式>＋<因子>*i=><表达式>＋i*i=><项>＋i*i=><因子>＋i*i=>i＋i*i<表达式><表达式>+<项><因子><表达式><表达式>+<项><因子>i<项><因子>i<项><因子>i（)<表达式><表达式>+<项><项>*<因子><因子>i<项><因子>ii第7题证明下述文法G[〈表达式〉]是二义的。

编译原理第三章 文法和语言

编译原理第三章 文法和语言
A={A,B},B={C,D} AB={AB,AD,BC,BD}
方幂：A的n次方幂就是将n个A相乘。 字母表的闭包与正闭包：
字母表A的闭包是A上的所有符号串（包括空字符串） 的集合。* 字母表A的正闭包是A上的所有的非空符号串的集合。 + 无穷集合
3.3 文法和语言的形式定义
使用3.2的术语对3.1中描述汉语句子的规 则加以形式化，然后给出文法和语言的形 式定义。 规则也称为重写规则、产生式或生成式。 规则形如或者::=的（,）有序 对，其中是某字母表V的正闭包V+中的一 个符号，是V*中的一个符号。称为规则 的左部，称为规则的右部。
3.3 文法和语言的形式定义
推导的概念：如果是文法G的规则， 和是V*中的任意符号，若有符号串v和w， 如果存在一个推导序列 定义3.2--3.4 u0=>u1 =>…=>un 并且u0=v，un=w，那么我们说v可以推导到w， 或者w规约到v。
若n=1记作v=>w，称为直接推导; 若n1记作+ => ，称为长度为n(n1)的推导; 若n0记作* => ，称为长度为n(n0)的推导;
L(G[Z])={anbn|n2}
3.4 文法和语言的分类
文法分类的原因： 对计算机科学有深刻的影响，我们在以后 的学习中将会体会到。 Chomsky文法的定义： (VN,VT,P,S)
该定义是我们前面讲的定义的一个更加形式化的表达。 在这个定义中，文法规则的左部可以是一个非空符号 串。 Chomsky文法被分为四类，我们主要用2型和3型文法。 几类文法的差异是对产生式施加不同的限制
一些基本原理、概念
形式化的方法：用一整套带有严格规定的符号体系 来描述问题的方法。
例：s=2*3.1415*r*(r+h)的非形式化描述

第3章 文法和语法(lly)3

第3章 文法和语法(lly)3
3
2、文法 文法：仅仅涉及语言句子的结构描述。 以自然语言为例（用 EBNF 描述一种语言：）
〈句子〉::= 〈主语〉〈谓语〉 〈主语〉::= 〈代词〉|〈名词〉 〈代词〉::= 你 | 我 | 他 〈名词〉::= 王明 | 大学生 | 工人 | 英语 〈谓语〉::= 〈动词〉〈直接宾语〉 〈动词〉::= 是 | 学习 〈直接宾语〉::= 〈代词〉|〈名词〉
思考： 文法的句型与句子的关系？ 文法G能得到哪些句子？
19
5、语言的定义：由文法G生成的语言记为L(G),它是 文法G的一切句子的集合: 即L(G)={x|S * x，其 中S为文法的开始符号，且x ∈VT*} 例：G： S→0S1， S→01 L(G)={0n1n|n≥1}
思考：文法G1[A]：A→0R A→01 R→A1的语言？
0S10011 （v=0S1，w=0011，使用规则S→01，γ =0，δ =1） S 0S1 （v=S，w=0S1，使用规则S→0S1，γ =ε，δ = ε ） 0S100S11 （v=0S1，w=00S11，使用规则？）
16
例 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…, <字母>→z <数字>→0,…, <数字>→9 } S=<标识符> 思考：指出下面直接推导所使用的规则 ？ ① <标识符> <标识符><字母> ② <标识符> <字母> <数字> <字母> <字母> <数字> ③ abc <数字> abc5

编译原理 形式语言ppt课件


表示 ,例如上例5中 步经 的过 推导记为
句子 thm e onk动 ey词 冠词 名词
规那么的简化表示
在前面的语法规那么定义中，有些语法范畴〔如<名 词>、<动词>〕有假设干条不同的规那么来定义它， 为简明起见，我们可以将它们写在同一个左部语法
范畴下，将其定义值用符号“|〞〔读作‘或’〕隔 开。如<名词>、 <动词>、 <冠词>的定义规那么可 简记为
正闭包 A+ = A1∪A2∪A3∪…称为Σ的正闭包 A + 表示上的除ε外的一切用穷长串的
集合
注: Σ* = Σ0∪Σ+ 注: Σ+ = ΣΣ* = Σ* Σ
字母表上的一个言语是上符合某种规那么的一 些符号串的集合 ，是*的一个子集
例如：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} 1. 集合{ab,aabb,aaabbb,…,anbn,…}或 {w|w∈Σ*且w=anbn,n≥1}为字母表上的一个言语 2. 集合{a,aa,aaa,…}或{w|w∈Σ*且w=an,n≥1}为 字母表上的一个言语
<句子> <主语短语><动词短语>
所得符号串<主语短语><动词短语>含有两个语法实体，可 对其中任一个〔例如对<动词短语>〕进展新的推导
<句子> <主语短语><动词短语>
<主语短语><动词><宾语短语>
反复上述过程，可得到一个推导序列〔见下页〕。
推导长度
推导 所用 所得的符号串
步 规那么

编译原理第3讲(第三章)


Ba→aB
C→bCB
Bb→bB
AD→aD
C→a
BD→bD
D→b
Aa→bD
整理ppt
3
2型文法
例：2型（上下文无关）文法
文法G[S]：
S→AB A→BS|0 B→SA|1
整理ppt
4
3型文法
G[S]： S→0A|1B|0
A→0A|1B|0S
B→1B|1|0
G[I]：
I → lT I→l T → lT T → dT T→l T→d
3型文法或正则（正规）文法（ RG ）产生的 语言称为3型语言或正则（正规）语言（和语言
四种文法之间的关系：是将产生式做进一步 限制而定义的。
语言之间的关系依次：有不是上下文有关语 言的0型语言，有不是上下文无关语言的1型语言 ，有不是正则语言的上下文无关语言。
整理ppt
8
根据形式语言理论,文法和识别系统间有这样的关系
0型文法（短语结构文法）的能力相当于图灵机，可以 表征任何递归可枚举集，而且任何0型语言都是递归可 枚举的
1型文法（上下文有关文法）：产生式的形式为 α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时， 才允许β取代A。其识别系统是线性界限自动机。 2型文法（上下文无关文法CFG）：产生式的形式为 A→β，β取代A时与A的上下文无关。其识别系统是不确 定的下推自动机。
语法树---句型推导的直观表示
给定文法G=(VN,VT,P,S)，对于G的任何句型都能构 造与之关联的语法树(推导树) 定理：G为上下 文无关文法，对于α≠ε，有S =>* α，当 且仅当文法G有以α为结果的一棵语法树(推导树)
一棵语法树表示了一个句型的种种可能的(但未必 是所有的)不同推导过程，包括最左(最右)推导。但是， 一个句型是否只对应唯一的一棵语法树呢?一个句型是 否只有唯一的一个最左(最右)推导呢?

编译原理课件-概述

號．？識別規範句型特定首碼(就到句柄為 止)的 DFA.
• 四種技術
– LR(0) SLR(1) LR(1) LALR(1)
文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d
S
AB
A
a b bcd e
步驟 符號棧
1） # 2） #a 3） #ab 4） #aA 5） #aAb 6） #aA 7） #aAc 8） # aAcd 9） #aAcB 10） #aAcBe 11） #S
E E +T
T
F
G[E]：E→E+T|T T→T*F|F F→(E)|i
句型：i*i+i
T* F
i3 短語：i1* i2+ i3， i1* i2 ，
F
i2
i1 ， i2 ， i3 。
i1
直接短語： i1 ， i2 ， i3 。句柄：
i
自下而上的語法分析
在分析程式工作的每一步，都是從當前串中選擇一 個子串，將它歸約到某個非終結符號，該子串稱為 “可歸約串”
cabd
c A bd a
刻畫“可歸約串”
文法G[S] 句型的短語 S =>* αAδ且 A =>+ β，則稱β是句型αβδ
相對於非終結符A的短語 句型的直接短語 若有A β，則稱β是句型αβδ相對於非終結
符A 的直接短語 句型的句柄 一個句型的最左直接短語稱為該句型的句柄
例 ：i*i+i 的短語、直接短語和句柄
• [B]=aAc 令 ={[S’]，[S]，[A]， [B]，a，
A,c} 則方程兩邊都是上的正規式
• [S]=[S’] • [A]=[S]a+[A] • [B]=[S]aAc

编译原理教程-课后习题答案第三章语法分析


第三章 语法分析 来消除左递归。由此，将产生式B→Bb|d改造为
B→dB′ B′→bB′| ε
其次，应通过提取公共左因子的方法来消除G[A]中的回 溯，即将产生式A→aABl|a改造为 A→aA′ A′→ABl | ε
最后得到改造后的文法为 G[A′]：A→aA′ A′→ABl | ε B→dB′ B′→bB′| ε
“A→α · ”动作的一定是 。
a. LALR文法 b. LR(0)文法
c. LR(1)文法 d. SLR(1)文法
第三章 语法分析
(8) 同心集合并有可能产生新的 冲突。
a. 归约
b. “移进”/“移进”
c.“移进”/“归约”
d. “归约”/“归约”
【 解 答 】 (1) c (2) a (3) c (5) b (6) b (7) d (8) d
第三章 语法分析 表3-1 预测分析表
A A′ B B′
第三章 语法分析 (2) 句子acabcbbdcc的最左推导如下： SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc 3.7 对于文法G[S]: S→(L)|aS|a
L→L,S|S (1) 画出句型(S,(a))的语法树； (2) 写出上述句型的所有短语、直接短语、句柄、素
第三章 语法分析
求得：
FIRST(A)={a}
FIRST(A′)={a, ε }
FIRST(B)={d}
FIRST(B′)={b, ε }
对文法开始符号A，有FOLLOW(A)={#}。
由 A′→ABl 得 FIRST(B)\{ ε }FOLLOW(A) ， 即 FOLLOW(A)={#,d}；
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。