当前位置：文档之家 › 第7课 第3章_文法和语言_推导&类型&语法树

第7课 第3章_文法和语言_推导&类型&语法树

  • 格式：ppt
  • 大小：162.50 KB
  • 文档页数：17

下载文档原格式

  / 17

合集下载

编译原理第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[〈表达式〉]是二义的。

编译原理课后习题答案+清华大学出版社第二版

编译原理课后习题答案+清华大学出版社第二版
也称基地址。 SL： 静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，
用以引用非局部（包围它的过程）变量时，寻找该变量的地址。 DL： 动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放
数据空间时，恢复调用该过程前运行栈的状态。 RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地
编译程序大致有哪几种开发技术？
答案：
（1）自编译：用某一高级语言书写其本身的编译程序。 （2）交叉编译：A 机器上的编译程序能产生 B 机器上的目标代码。 （3）自展：首先确定一个非常简单的核心语言 L0，用机器语言或汇编语言书写出它的编
译程序 T0，再把语言 L0 扩充到 L1，此时 L0⊂ L1 ,并用 L0 编写 L1 的编译程序 T1，再把语 言 L1 扩充为 L2，有 L1 ⊂ L2 ,并用 L1 编写 L2 的编译程序 T2，……，如此逐步扩展下 去， 好似滚雪球一样，直到我们所要求的编译程序。 （4）移植：将 A 机器上的某高级语言的编译程序搬到 B 机器上运行。
(main).
答案： 程序执行到赋值语句 b∶=10 时运行栈的布局示意图为：
1
《编译原理》课后习题答案第二章
第 3题 写出题 2 中当程序编译到 r 的过程体时的名字表 table 的内 容。
name
kind
level/val
adr
size
答案：
题 2 中当程序编译到 r 的过程体时的名字表 table 的内容为：
盛威网（）专业的计算机学习网站
2
《编译原理》课后习题答案第一章
合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行 中间代码程序，最后得到运行结果。

编译原理(清华)第三章文法和语言

编译原理(清华)第三章文法和语言

例 文法G： S→0S1，S→01 有直接推导： 0S1 00S11 （ S→0S1 ） 00S11 000S111 （ S→0S1 ） 000S111 00001111 （ S→01 ） S 0S1 （ S→0S1 ）
推导和归约 若存在v=w0 w1 ... wn=w ,(n>0) 则称v推导出w，或w归约到v,记为v=+>w 若有v =+>w，或v=w，则记作v=*>w
2. 符号串 – 定义:由字母表中的符号组成的任何有穷序列 – 例： 0,00,10是字母表∑={0‚1}上的符号串 a,ab,aaca是Α={a‚b，c}上的符号串 – 在符号串中，符号是有顺序的，顺序不同,代 表不同的符号串，如:ab和ba不同 – 不含任何符号的符号串称为空串，用ε表示 注意:{ε}并不等于空集合{ } – 符号串长度: 符号串中含有符号的个数 如: |abc|=3 | ε|=0
3.3 文法和语言的形式定义
1．文法的定义 2．文法的简化表示法 3．推导与归约 4．句型、句子、语言的定义 5．文法的等价
1．文法的定义
产生式（规则） 产生式是一个有序对(α,β)，通常写作 α→β（或α::=β ） 文法定义: 文法G(Grammar)定义为四元组（VN，VT，P，S） VN (Nonternimal)：非终结符集 VT (Terminal)：终结符集 P (Production)： 产生式（规则）集合 S： 开始符号或识别符号
第三章
文法和语言
学习目标: 掌握：自上而下与自下而上的分析方法 理解：文法的形式定义，推导，归约，句 型，句子，语言，上下文无关文法，规范 句型，语法树，短语，直接短语，句柄 了解：文法的类型，文法使用中的限制， 文法的二义性

chapter3文法和语言.ppt

chapter3文法和语言.ppt
19
例：算术表达式的文法 递归定义——中缀表示
标识符(id)（常数、变量）是表达式(E)； 表达式加一个表达式是表达式； 表达式乘一个表达式是表达式； 表达式加上括号后是表达式；
20
例：算术表达式的文法
考虑简单算术表达式组成的语言
G =({id，+，*，(，)}，{E}，P，E)
8
3.2 符号和符号串
符号串s的头、尾、固有头、固有尾（前缀、后缀、 真前缀、真后缀）： 如果s=xy是一符号串，则x是s 的头，y是s的尾；如果x非空，则y是固有尾，如果y 非空，则x是固有头。对于符号串banana
ε b ba ban bana banan banana均是前缀，且前六个为 真前缀
4
形式语言与自动机理论的产生
语言学家Chomsky最初从产生语言的角度研究语言。
1956年，通过抽象，他将语言形式地定义为是由一个字母 表中的字母组成的一些串的集合。可以在字母表上按照一定 的规则定义一个文法（Grammar），该文法所能产生的所 有句子组成的集合就是该文法产生的语言。
克林（Kleene）在1951年到1956年间，从识别语言 的角度研究语言，给出了语言的另一种描述。
关于语言 符号和符号串 文法和语言的形式定义 文法的类型 上下文无关文法及其语法树 上下文无关文法的句型分析 有关文法实用中的一些说明
2
3.1 关于语言
语言是由句子组成的集合，是由一组符 号串所构成的集合。
汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体
P: E→E + E

E→E * E

第三章文法和语言

第三章文法和语言

集合{ab,aabb,aaabbb,…,anbn,…}
或{w|w∈Σ *且w=anbn,n≥1}为字母表上的一 个语言。
集合{a,aa,aaa,…}
或{w|w∈Σ *且w=an,n≥1} 为字母表上的一
个语言。
ε 是一个语言。
即 是一个语言。
13
语言上的运算
设L是（上的）一个语言,M是（上的）一个语 言,
16
文法 数学系统
一个形式数学系统可由下列基本成分来刻 画：一组基本符号，一组形成规则，一组 公理，一组推理规则。
17
文法和语言的形式定义
文法的定义 推导的定义 句型、句子、语言的定义
18
文法的定义
文法G定义为四元组（VN，VT，P，S）
VN ：非终结符集 VT ：终结符集 P：产生式（规则）集合 S：开始符号
6
预备知识 -----形式语言
如果不考虑语义和语用，即只从语法这一侧 面来看语言，这种意义下的语言称作形式语 言。形式语言抽象地定义为一个数学系统。 “形式”是指这样的事实：语言的所有规则 只以什麽符号串能出现的方式来陈述。形式 语言理论是对符号串集合的表示法、结构及 其特性的研究。是程序设计语言语法分析研 究的基础。
G可写成G[S]，S是开始符号
G：S→aAb A→ab A→aAb A→ε
G[S]： A→ab A→aAb A→ε S→aSb
缩写形式 G[S]：
A→ab |aAb |ε
S→aSb
注意：元符号和源符号 22
例3.2 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…, <字母>→z <数字>→0,…, <数字>→9 } S=<标识符>

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

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

2020/9/28
14
字母表：是元素的非空有穷集合，把字 母表中的元素称为符号，因此字母表也 称符号集。例，{a，b，c，+，﹒}就是 含有5个元素的一个字母表。一般用∑和 V来表示
符号：是语言当中最基本的不可再分的 单位
2020/9/28
15
符号串：字母表中的符号所组成的任何 有穷序列。例，V={a，b，c}是一个字母 表，则a，b，c，aa，ab，bc，abc等等都 是V上的符号串
符号串的连接：设和是符号串，它们 的连接是把的符号写在的符号之后得 到的符号串。例，若=NPU， =1108，则 =NPU1108， =1108NPU
2020/9/28
18
符号串的方幂：设是符号串，把自身 连接n次得到符号串，即=…， 称为符号串的方幂，写作=n。
符号串集合：若集合A中的一切元素都是 某字母表上的符号串，则称A为字母表上 的符号串集合。
词法
– 单词符号
语言中具有独立意义的最基本结构
– 词法规则
词法规则规定了字母表中哪些字符串是单词符号 单词符号一般包括：常数、标识符、基本字、算
符、界限符等
– 我们用正规式和有限自动机理论来描述词法 结构和进行词法分析
语法
– 单词符号 – 语法单位
表达式、子句、语句、函数、过程、程序
2020/9/28
26
3.3 文法和语言的形式定义
前面已经对规则(或产生式)的概念进 行了非形式化的说明，我们已经对其有了 一个直观的了解。下面将对其进行形式化 说明，并在此基础上抽象地定义文法和语 言。
2020/9/28
27
定义3.1
文法G定义为四元组（VN，VT，P，S）
– VN ：非终结符集 – VT ：终结符集 – P：产生式（规则）集合 – S：开始符号（或识别符号）

编译原理 文法和语言-PPT精品文档

3
3.2 符号和符号串
1、字母表
字母表是符号的非空有穷集合。任何程序语言都有 自己的字母表，例如: 1.计算机语言：由符号“0”和“1”组成的字 母表, ∑={0，1} 2. ASCII字符集； 3. Pascal字母表为： ∑={AZ, az, 09, +, -, *, /, <, =, >,:, ',', ; ，.， , (, ), {, }, [, ]}
2
3.1 文法的直观概念
如何来描述一种语言？ 如果语言是有穷的(只含有有穷多个句子)，可以将句子逐 一列出来表示； 如果语言是无穷的，语言的有穷表示有两个途经:
• 生成方式(文法):语言中的每个句子可以用严格定义的规则 来构造。
• 识别方式(自动机):用一个过程，当输入的一任意串属于语 言时，该过程经有限次计算后就会停止并回答“是”，若 不属于，要么能停止并回答“不是”，要么永远继续下去。 参见课本句子组成的实例。
4
3.2 符号和符号串
2、符号串
一. 符号串的定义
(1)ε 是∑上的一个符号串。
(2)若x是∑上的符号串，而a是∑的元素,则xa是∑
上的符号串。
(3)y是∑上的符号串,当且仅当它由(1)和(2)导出。
由字母表中的符号所组成的的任何有穷序列被称之
为该字母表上的符号串,也称作"字"。
5
3.2 符号和符号串
二 术语
设s是符号串
前缀: 移走s的尾部的零个或多于零个符号 后缀: 删去s的头部的零个或多于零个符号 子串: 从s中删去一个前缀和一个后缀 子序列: 从s中删去零个或多于零个符号(这些符号不要求 是连续的） 逆转: 将s中的符号按相反次序写出而得到的符号串。 长度: 是该符号串中的符号的数目。例|aab|=3,|ε |=0。

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


2015-1-15
北京化工大学信息科学与技术学院计算机系
2
3.1 预备知识
一、字母表和符号串 字母表：符号的非空有限集 例：={a，b，c} 符号： 字母表中的元素 例： a，b，c 符号串：符号的有穷序列 例：a,aa,c,abc，.. 空符号串：无任何符号的符号串(ε ) 符号串集合：由符号串构成的集合。
2015-1-15 北京化工大学信息科学与技术学院计算机系 13
例如：G[<无符号整数>] (1) <无符号整数> → <数字串> ； (2) <数字串> → <数字串> <数字> (3) <数字串> → <数字>
请问根据文法G能否推导出10？
(4) <数字> →0; (5) <数字> →1; ………… (13) <数字> →9;
定义7. G和G’是两个不同的文法，若 L(G) = L(G’) , 则G和G’为等价文法。
2015-1-15
北京化工大学信息科学与技术学院计算机系
18
3.3 文法和语言的形式定义
编译感兴趣的问题是:
给定x, G, 求x L(G) ?
G
y
x 算法1
x L(G) ?
算法2 出错处理
停机
n
2015-1-15
2015-1-15 北京化工大学信息科学与技术学院计算机系 6
3. 由规则推导句子： 有了一组规则之后，可以按照一定的方式用它们去 推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应 规则的右部来替代规则的左部，每次仅用 一条规则去进行推导。
说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。 (2) 从一组规则可推出不同的句子。

第3章 文法和语言

集合的正闭包和集合的闭包：设A为一个集合，则 集合A的正闭包用A+表示，定义为：
A+ =A1 ∪ A2 ∪ …. ∪ A n ∪…
集合A的闭包用A*表示，定义为： A* =A 0 ∪ A+ , 显然有 A+=AA*=A*A 例如：A = {a，b}， 则A+ ={a,b,aa,ab,ba,bb,aaa,aab,…}
P：
I→L | IL | ID
L→a | b |… | z
D→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
29

例3.2：生成语言 L={a n b m | n, m 1} 的文法
<无符号整数>→{<数字>}13
与 < 无符号整数 >→< 数字 >|< 数字 >< 数字 >|< 数字 >< 数字 >< 数字 > 相同
而字母打头、后面可跟数字或字母的不超过 8 个字符的标识符文法 则为：
<标识符>→<字母>{<字母>|<数字>}07
17
文法的EBNF表示
例如： <IF语句>→IF <布尔表达式> THEN <语句> [ELSE <语句>]
译程序的构造有着重大的作用。

形式工具--“形式”是指这样的事实：语言的所有规则
只以什么符号串能出现的方式来陈述
2
3.1 文法的引入

自然语言：英语——符合相应规则——合法句子
（字母表） （语法） （含义-语义）

编程语言：

教案3-4

第3章文法和语言。

第1讲讲授内容：文法的直观概念，符号和符号串，文法和语言的形式定义，文法的类型，上下文无关文法及其语法树。

本讲重点：推导过程和语法树的对应，句型与语法树的对应。

讲授方法：由于学生没有接触过文法的概念，所以首先举一个汉语文法的例子作为引导，使学生对文法有一个感性的认识，然后引出文法的形式定义。

作业：P44 1，4，6，8，11，12，133．1 文法的直观概念一种语言可以用一组规则来定义。

以自然语言为例，可以用一组规则定义句子。

如“我是大学生”。

汉语的句子由主语，谓语组成，谓语由动词和直接宾语组成。

我们可以用下列规则定义句子。

《句子》→《主语》《谓语》《主语》→《代词》|《名词》《代词》→我|你|他《名词》→王明|大学生|工人|英语《谓语》→《动词》|《直接宾语》《动词》→是|大学生《直接宾语》→《代词》|《名词》这就是一个文法。

每一行称作一个产生式（或规则）。

其中：《》：《》之内的符号为非终结符。

例如，《句子》，《主语》等，而我，王明等则是终结符。

→：定义为|：或者这三个符号称为元语言符号，用类描述文法符号之间的关系，其它符号为文法符号。

有了以上的文法，我们可以推导出若干个句子。

以→为界，产生式的左边称作产生式的左部，右边称作右部。

第一行的左部称为文法的开始符号。

例《句子》=> 《主》《谓》=> 《代》《谓》=> 我《谓》=> 我《动》《直宾》=> 我是《直宾》=> 我是大学生显然，还可以产生若干个句子，我们用有限的规则不仅严格地定义了句子的结构，还描述出该语言的全部句子。

这就是CHOMSKY建立形式语言的基本思想。

3．2符号，符号串字母表：元素的非空集合。

符号串：右字母表中的符号组成的任意有穷序列。

设字母表∑={0，1}，则 01，001，011，00000111，等都是符号串。

A ={a，b，c}，则a，aa，aabbbc，等都是符号串。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
E E + E E * E a a a
共17页
E E * E a E + E a a
11
一个二义性程序语句

条件语句的二义文法：


S if expr then S S if expr then S else S S 其他语句（此处不再详细定义） if e1 then if e2 then s1 else s2
共17页
9
二义(Ambiquity)文法
若一个文法存在某个句子对应两棵不同 的语法树，则称这个文法是二义的 或者， 若一个文法存在某个句子有两个不同的 最左（右）推导，则称这个文法是二义 的

共17页
10
二义文法的例 E → a | E+E | E*E | (E)
非CFG在程序语言中的应用

在我们使用的程序语言中,有些语言结构 并不是总能用上下文无关文法描述的。 例：L1={wcw|w∈{a,b}+}。 aabcaab就 是L1的一个句子。

这个语言是检查程序中标识符的声明应先于 引用的抽象 它是检查过程声明的形参个数和过程引用的 参数个数一致问题的抽象。
通过对产生式施加不同的限制， Chomsky将文法分为四种类型： 0、1、2、3
共17页
4
Noam ·Chomsky
乔姆斯基(1928- )，美国语言学家，1972 年当选为国家科学院院士 他用类似数学公式的式子，来建立生成语 法体系，并以此来描写自然语言。 Chomsky的成果在心理学、医学、哲学、 逻辑学以及计算机学上都有很重要的应用

共17页 7
语法树的结果及其定理

从左到右读出叶子的标记，这样构成的 序列称为该语法树的结果 CFG的语法树结果定理 若G为CFG，对于α ≠ε ，有S =>* α ， 当且仅当文法G有以α 为结果的一棵语法 树(推导树)
共17页
8
关于语法树的几点说明


语法树的结构反映了句型的语法结构 一棵语法树可以对应一个句型的多个推 导过程 有的句型可能对应多棵语法树（二义文 法）
第3章 文法和语言
湖南师范大学《编译原理》 授课教师：罗迅
推导

Derive
推导就是替换，用规则的右边去替换规则 的左边 一步推导只能使用一条规则

归约，也是替换
共17页
2
语言的例子
S → 0S1 | 01

这个产生式所定义的语言是如下集合：

L(G) = {0n1n|n≥1}
共17页
3
文法的类型
之二
if e1 then if e2 then s1 else s2 S S if expr then S S if expr then S else S S 其他语句（此处不再 详细定义）
if expr e1 if
then
S
else S s2
expr e2
then
S s1
共17页 15

共17页
5
文法的类型的关系
四种文法之间的逐级“包含”关系
0型文法 1型文法 2型文法 3型文法
共17页
6
语法树
设G=( VN,VT,P,S)为一CFG，若一棵树满足 下列4个条件，则此树称作G的语法树(推导树)：
每个结点都有一个标记，此标记是V的一个符号 根的标记是S 若一结点n是内部结点，并且有标记A，则肯定 A∈VN 如果结点n有标记A,其直接子孙结点从左到右的 次序是n1，n2，…，nk，其标记分别为A1， A2，…，Ak，那么A→A1A2，…，Ak一定是P中 的一个产生式
共17页 13
两棵语法树之一
if e1 then if e2 then s1 else s2 S if expr e1 if expr e2 then S s1 else S s2
共17页 14
then
S
S if expr then S S if expr then S else S S 其他语句（此处不再 详细定义）
共17页 16

例：L2={anbmcndm|n,m≥0}。

课后作业

教材第3章第7、9题
共17页
17

条件语句的二义语句

共17页
12
C语言中的if语句
二义语句：if e1 then if e2 then s1 else s2 if e1 { if e2 s1; else s2; } if e1 {if e2 s1;} else {s2;} 注意：C语言中没有“then”这个符号，多了花括号