第四章 语法分析.

Slides:



Advertisements
Similar presentations
2009 套读自考本科简介 —— 抓住机遇,用知识改变命运 目 录 二、提升学历、提升自身素质的途径选择 三、高教自考和套读自考本科介绍 四、我校自考套读本科情况介绍 一、就业状况 五、我校今年招生专业介绍.
Advertisements

1 基北區 103 學年度免試入學志願選填、 超額比序項目、共同就學區規劃說明 臺北市政府教育局 新北市政府教育局 基隆市政府教育處.
高考数学专题之概率 高考数学冲刺 主讲人 : 北京大学光华管理学院 何洋. 北京师范大学京师大厦 9810 室 电话 : 传真 : 写在前面的话 概率是高中数学新教材中新增的内容, 在 实际生活中应用非常广泛, 并且由于概率 论是统计学的基础,
林園高中適性入學 高雄區免試入學 及 特色招生介紹 1. 國中學生 國中教育會考 1 ( 每年五月 ) 特色招生 術科考試 五專 免試入學 ( 每年六月 ) 特色招生 甄選入學 高中高職 免試入學 擇一報到 林園高中適性入學  入學管道流程 2.
实数与代数式是初中数学中重要的基础知识, 是中考的必考内容.这部分知识散布于多个章节之中, 知识点琐碎,但概念性强,在中考试卷中多以填空题、 选择题、化简、探索或求值的形式出现.在复习中, 一定要加强对各个概念、性质和公式的辨析和理 解.注重让学生在实际背景中理解基本的数量关系和 变化规律,注重使学生经历从实际问题中建立数学模.
說 劍 《莊子‧雜篇》─ 第 一 組 賴泊錞 謝孟儒 張維真 羅苡芸
第二节人口的空间变化.
十二年國民基本教育- 104年中投區適性入學宣導
報告人:教育部會計處處長 黃 永 傳 日 期:103 年12 月27 日
第一课 爱在屋檐下 第一节 我知我.
105年桃連區適性入學宣導 桃園市十二年國民基本教育宣導團 宣講講師:龍岡國中 校長 郭玉承 時 間:105年 3 月 9 日 1.
第十二章 小组评估 本章重点问题: 评估的设计 测量工具的选择和资料的收集 与分析.
2 016 陕西广播电视台 餐饮娱乐行业广播投放方案 【第一版】.
第二章 遺傳 2‧4 突變.
2011年10月31日是一个令人警醒的日子,世界在10月31日迎来第70亿人口。当日凌晨,成为象征性的全球第70亿名成员之一的婴儿在菲律宾降生。 ?
第九课时 二元一次方程组 .
合 同 法 主讲人: 教材:《合同法学》(崔建远) 2017/3/10.
七(7)中队读书节 韩茜、蒋霁制作.

9 有理数的乘方.
不会宽容人的人, 是不配受到别人的宽容的。 贝尔奈.
复习回顾 a a×a a×a×a a a×a×a= a×a= 1.如图,边长为a厘米的正方形的面积 为 平方厘米。
初级会计实务 第八章 产品成本核算 主讲人:杨菠.
第四章 现代汉语语法.
第二章 文法和语言 2.1 文法的基本概念 符号和符号串 2.2 句型的分析 文法和语言的形式定义 推导与递归 文法的分类 语法树
巧用叠词,妙趣横生.
中考阅读 复习备考交流 西安铁一中分校 向连吾.
104年振聲國中 志願選填個別序位 說明會 104年06月08日 輔導室關心您.
响沙之王——银肯响沙 响沙之王——银肯响沙.
中央广播电视大学开放教育 成本会计(补修)期末复习
9.5因式分解.
人教版义务教育课程标准实验教科书 小学数学四年级上册第七单元《数学广角》 合理安排时间 248.
5.
第五章 电流和电路 制作人 魏海军
第四章 时间序列的分析 本章教学目的:①了解从数量方面研究社会经济现象发展变化过程和发展趋势是统计分析的一种重要方法;②掌握时间数列编制的基本要求;③理解和掌握水平速度两方面指标的计算及运用④理解和掌握长期趋势分析和预测的方法。 本章教学重点:现象发展的水平指标和速度指标。 本章教学难点:现象变动的趋势分析。
基因分离规律习题课.
“08高考化学学业水平(必修科目)测试的命题和教学对策研究”
中考语文积累 永宁县教研室 步正军 2015.9.
一、液压与气压传动的控制元件分类 1、按用途分类 根据控制元件在系统中的作用,可分为下几类: 方向控制阀 压力控制阀 3) 流量控制阀
第1节 光的干涉 (第2课时).
内蒙古景观与区划 人文景观 人文景观是指有人为因素作用形成(构成)的景观。人为因素主要有文化、建筑等因素。
课标教材下教研工作的 实践与思考 山东临沂市教育科学研究中心 郭允远.
小学数学知识讲座 应用题.
第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案. 第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案.
倒装句之其他句式.
文化生活第三单元 中华文化和民族精神.
大綱: AAA 性質 SAS 性質 SSS 性質 顧震宇 台灣數位學習科技股份有限公司
1-2 正負數的乘除法.
第 22 课 孙中山的民主追求 1 .近代变法救国主张的失败教训: “师夷之长技以制 夷”“中体西用”、兴办洋务、变法维新等的失败,使孙中山
你一定要認識的數學家.
自上而下分析 4.4.
自上而下分析 4.4.
第 二 章 逻 辑 代 数 基 础.
编译原理与技术 词法分析(1) 2018/11/28 《编译原理与技术》讲义.
第三章 词法分析.
第2次课 上下文无关文法
教科版初中九年级物理 第五章 欧姆定律 3 等效电路.
第三课时 匀变速直线运动的位移与时 间的关系
语法分析 本章内容 语法分析器:把词法分析生成的词法单元流翻译成语法分析树(parse tree)
病例对照研究设计 选两组对象,一组是患病者(条件组),另一组是非患病者(对照组),与条件组有着大体相同的身体状况
大綱:整數的加法 整數的減法 蘇奕君 台灣數位學習科技股份有限公司
大綱: 母子相似性質 內、外分比性質 重點複習 顧震宇 台灣數位學習科技股份有限公司
分 解 因 式 保定市第二十六中学 刘彦莉.
第三节 二项式定理.
第一章 集合论 集合是最基本的数学概念,没有定义 集合是所有数学的基础 两种集合论 朴素集合论:直观描述集合的概念,有悖论
§12-5 同方向同频率两个简谐振动的合成 一. 同方向同频率的简谐振动的合成 1. 分振动 : 2. 合振动 : 解析法
1.8 完全平方公式(一) 锦州市实验学校 数学组(3).
畢氏定理(百牛大祭)的故事 張美玲 製作 資料來源:探索數學的故事(凡異出版社).
幂的乘方.
102年人事預算編列說明 邁向頂尖大學辦公室製作.
Presentation transcript:

第四章 语法分析

第四章 语法分析 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号 第四章 语法分析 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 其余部分 中间表示 符号表 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开

上下文无关文法 4.1~4.3

4.1 上下文无关文法 4.1.1 上下文无关文法的定义 正则式能定义一些简单的语言,能表示给定结构的固定次数的重复或者没有指定次数的重复 例:a (ba)5, a (ba)* 正则式不能用于描述配对或嵌套的结构 例1:配对括号串的集合 例2:{wcw | w是a和b的串}

例 ( {id, +, , , (, )}, {expr, op}, expr, P ) 4.1 上下文无关文法 上下文无关文法是四元组(VT , VN , S, P) VT : 终结符集合 VN : 非终结符集合 S : 开始符号,非终结符中的一个 P : 产生式集合, 产生式形式 : A   例 ( {id, +, , , (, )}, {expr, op}, expr, P ) expr  expr op expr expr  (expr) expr   expr expr  id op  + op  

4.1 上下文无关文法 简化表示 expr  expr op expr | (expr) |  expr | id op  + |  E  E A E | (E ) | E | id A  + | 

4.1 上下文无关文法 文法书写上的约定 终结符 非终结符 字母表中的小写字母,如 a,b,c 黑体串,如 id, while 数字 0, 1, … , 9 标点符号,如括号,逗号等 运算符号,如+, -等 非终结符 字母表中的大写字母,如A, B, C 字母S,并且通常代表开始符号 小写字母的名字(斜体),如expr, stmt

4.1 上下文无关文法 文法书写上的约定 字母表中后面的大写字母,如X,Y,Z,可以是终结符或非终结符 字母表中后面的小写字母,如u,v … z 可代表终结符号串 小写希腊字母,如a,b,可代表文法的符号串 对于A  a1,A  a2,... A  an可以写成 A  a1 | a2 | … | an

例 E  E + E | E  E | (E ) |  E | id 4.1 上下文无关文法 4.1.2 推导(自顶向下) 把产生式看成重写规则,把符号串中的非终结符用其产生式右部的串来代替 例 E  E + E | E  E | (E ) |  E | id E  E  (E)  (E + E)  (id + E)  (id + id) 概念 S *、 S + w ,于是  *  * b, 且 b  γ, 则  * γ

4.1 上下文无关文法 4.1.2 推导 概念 上下文无关语言 等价的文法 句型 A→γ, 且a、b是任意符号串,则aAb  aγb 由上下文无关文法生成的语言是上下文无关语言 等价的文法 如果两个文法产生同样的语言,则两个文法等价 句型 文法G的开始符为S,S *, 可能含有非终结符,则叫做文法G的句型。

例 E  E + E | E  E | (E ) |  E | id 最左推导 4.1 上下文无关文法 例 E  E + E | E  E | (E ) |  E | id 最左推导 E  lm E  lm (E)  lm (E + E)  lm (id + E) lm (id + id) 最右推导 E  rm E  rm (E)  rm (E + E)  rm (E + id) rm (id + id)

例 E  E + E | E  E | (E ) |  E | id 4.1 上下文无关文法 4.1.3 分析树 例 E  E + E | E  E | (E ) |  E | id E  E ( E ) E + E id id

4.1 上下文无关文法 4.1.4 二义性 id  id + id E  E  E E  E + E  id  E + E  id  E + E  id  id + E  id  id + E  id  id + id  id  id + id 两个不同的最左推导

4.1 上下文无关文法 4.1.4 二义性 id  id + id E  E  E E  E + E  id  E + E  id  E + E  id  id + E  id  id + E  id  id + id  id  id + id 两棵不同的语法树 E * + id

4.2语言和文法 文法的优点 文法的问题 文法给出了精确的,易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构 以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法,不能描述语言中上下文有关的语法特征

4.2 语言和文法 4.2.1 正则式和上下文无关文法的比较 正则式 文法 (a|b)*ab A0  a A0 | b A0 | a A1 开始 a b

4.2 语言和文法 4.2.2 分离词法分析器理由 为什么要用正则式定义词法 词法规则非常简单,不必用上下文无关文法 对于词法记号,正则式描述简洁且易于理解 从正则式构造出的词法分析器效率高

从软件工程角度看,词法分析和语法分析的分离有如下好处 4.2 语言和文法 从软件工程角度看,词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分

能否把词法分析并入到语法分析中,直接从字符流进行语法分析 4.2 语言和文法 能否把词法分析并入到语法分析中,直接从字符流进行语法分析 若把词法分析和语法分析合在一起,则必须将语言的注解和空白的规则反映在文法中,文法将大大复杂 注解和空白由自己来处理的分析器,比注解和空格已由词法分析器删除的分析器要复杂得多

4.2 语言和文法 4.2.3 验证文法产生的语言 G : S  (S) S |  L(G) = 配对的括号串的集合

G : S  (S) S |  L(G) = 配对的括号串的集合 按推导步数进行归纳:推出的是配对括号串 4.2 语言和文法 4.2.3 验证文法产生的语言 G : S  (S) S |  L(G) = 配对的括号串的集合 按推导步数进行归纳:推出的是配对括号串 归纳基础: S   归纳假设:少于n步的推导都产生配对的括号串 归纳步骤:n步的最左推导如下: S  (S)S * (x) S * (x) y

G : S  (S) S |  L(G) = 配对的括号串的集合 按串长进行归纳:配对括号串可由S推出 4.2 语言和文法 4.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

4.2 语言和文法 4.2.4 适当的表达式文法 用一种层次观点看待表达式 id  id  (id+id) + id  id + id

4.2 语言和文法 4.2.4 适当的表达式文法 用一种层次观点看待表达式 id  id  (id+id) + id  id + id id  id  (id+id) 文法 expr  expr + term | term term  term  factor | factor factor  id | (expr)

4.2 语言和文法 expr  expr + term | term term  term  factor | factor factor  id | (expr) expr id term factor * expr + id factor term * id  id  id 分析树 id + id  id 分析树

句型:if expr then if expr then stmt else stmt 两个最左推导: 4.2 语言和文法 4.2.5 消除二义性 stmt  if expr then stmt | if expr then stmt else stmt | other 句型:if expr then if expr then stmt else stmt 两个最左推导: stmt  if expr then stmt  if expr then if expr then stmt else stmt stmt  if expr then stmt else stmt

4.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

4.2 语言和文法 4.2.6 消除左递归 消除左递归 A  A α | β A  β R R  α R | ε

4.2 语言和文法 4.2.6 消除左递归 文法左递归 A+Aa 直接左递归 AAa |b 消除直接左递归 A  b A 串的特点 ba . . . a 消除直接左递归 A  b A A a A | 

4.2 语言和文法 例 算术表达文法 E  E + T | T ( T + T . . . + T ) T  T  F | F ( F  F . . .  F ) F  ( E ) | id 消除左递归后文法 E  TE  E   + TE  |  T  FT  T    F T  | 

4.2 语言和文法 非直接左递归 S  Aa | b A  Sd |  先变换成直接左递归 A  Aad | bd |  再消除左递归 A  bd A | A A  adA | 

4.2 语言和文法 4.2.7 提左因子 有左因子的文法 A 1 | 2 提左因子 A   A A  1 | 2

stmt  if expr then stmt else stmt | if expr then stmt | other 提左因子 4.2 语言和文法 例 悬空else的文法 stmt  if expr then stmt else stmt | if expr then stmt | other 提左因子 stmt  if expr then stmt optional_else_part optional_else_part  else stmt | 

形式语言 ⑴ 0 型语言 由 0型文法定义 又称 无限制文法! 产生式形式为: ->  又称 上下文有关文法! ⑴ 0 型语言 由 0型文法定义 又称 无限制文法! 产生式形式为: ->  又称 上下文有关文法! ⑵ 1 型语言 由 1型文法定义 产生式形式为:xAy ->xy 又称 上下文无关文法! ⑶ 2 型语言 由 2型文法定义 产生式形式为:A ->  又称 正规文法! ⑷ 3 型语言 由 3型文法定义 产生式形式为:A->aB , A->a , A-> 【注】 四类语言为 包含关系,且有 L0 ⊃L1 ⊃ L2 ⊃ L3; 编译处理中,主要应用后两种文法!

乔姆斯基 艾弗拉姆·诺姆·乔姆斯基(英语:Avram Noam Chomsky,1928年12月7日-) 美国哲学家、语言学家、认知学家、逻辑学家、政治评论家。乔姆斯基是麻省理工学院语言学的荣誉退休教授,他的生成语法被认为是20世纪理论语言学研究上的重要贡献。

句法结构 《句法结构》是乔姆斯基介绍转换生成语法的《语言学理论的逻辑结构》一书的精华版。这一理论认为说话的方式(词序)遵循一定的句法,这种句法是以形式的语法为特征的,具体而言就是一种不受语境影响并带有转换生成规则的语法。 儿童被假定为天生具有适用于所有人类语言的基本语法结构的知识。这种与生俱来的知识通常被称作普遍语法。

下面的二义文法描述命题验算公式的语法,为他写一个等价的非二义文法 练习 文法 S->aSbS | bSaS | ε 产生的语言是什么?该文法是否有二义性? 下面的二义文法描述命题验算公式的语法,为他写一个等价的非二义文法 S->S and S | S or S| not S| p | q | (S)

练习 文法 R->R'|'R | RR | R* | (R) | a | b

建立句子(a,(a,a))和(a,((a,a),(a,a)))的分析树 为(a)的两个句子构造最左推导 为(a)的两个句子构造最右推导 练习 考虑文法 S->(L) | a L->L,S | S 建立句子(a,(a,a))和(a,((a,a),(a,a)))的分析树 为(a)的两个句子构造最左推导 为(a)的两个句子构造最右推导 这个文法产生的语言是什么?