Download presentation
Presentation is loading. Please wait.
1
第四章 语法分析
2
第四章 语法分析 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号
第四章 语法分析 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 其余部分 中间表示 符号表 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开
3
上下文无关文法 4.1~4.3
4
4.1 上下文无关文法 4.1.1 上下文无关文法的定义 正则式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复
例：a (ba)5, a (ba)* 正则式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw | w是a和b的串}
5
例 ( {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
6
4.1 上下文无关文法 简化表示 expr expr op expr | (expr) | expr | id op + |
E E A E | (E ) | E | id A + |
7
4.1 上下文无关文法 文法书写上的约定 终结符 非终结符 字母表中的小写字母，如 a，b，c 黑体串，如 id, while
数字 0, 1, … , 9 标点符号，如括号，逗号等 运算符号，如+, -等 非终结符 字母表中的大写字母，如A, B, C 字母S，并且通常代表开始符号 小写字母的名字（斜体），如expr, stmt
8
4.1 上下文无关文法 文法书写上的约定 字母表中后面的大写字母，如X，Y，Z，可以是终结符或非终结符
字母表中后面的小写字母，如u，v … z 可代表终结符号串 小写希腊字母，如a，b，可代表文法的符号串 对于A a1，A a2，... A an可以写成 A a1 | a2 | … | an
9
例 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 γ, 则 * γ
10
4.1 上下文无关文法 4.1.2 推导 概念 上下文无关语言 等价的文法 句型 A→γ, 且a、b是任意符号串，则aAb aγb
由上下文无关文法生成的语言是上下文无关语言 等价的文法 如果两个文法产生同样的语言，则两个文法等价 句型 文法G的开始符为S，S *， 可能含有非终结符，则叫做文法G的句型。
11
例 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)
12
例 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
13
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 两个不同的最左推导
14
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
15
4.2语言和文法 文法的优点 文法的问题 文法给出了精确的，易于理解的语法说明 自动产生高效的分析器 可以给语言定义出层次结构
以文法为基础的语言的实现便于语言的修改 文法的问题 文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法特征
16
4.2 语言和文法 4.2.1 正则式和上下文无关文法的比较 正则式 文法 (a|b)*ab A0 a A0 | b A0 | a A1
开始 a b
17
4.2 语言和文法 4.2.2 分离词法分析器理由 为什么要用正则式定义词法 词法规则非常简单，不必用上下文无关文法
对于词法记号，正则式描述简洁且易于理解 从正则式构造出的词法分析器效率高
18
从软件工程角度看，词法分析和语法分析的分离有如下好处
4.2 语言和文法 从软件工程角度看，词法分析和语法分析的分离有如下好处 简化设计 编译器的效率会改进 编译器的可移植性加强 便于编译器前端的模块划分
19
能否把词法分析并入到语法分析中，直接从字符流进行语法分析
4.2 语言和文法 能否把词法分析并入到语法分析中，直接从字符流进行语法分析 若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂 注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多
20
4.2 语言和文法 4.2.3 验证文法产生的语言 G : S (S) S | L(G) = 配对的括号串的集合
21
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
22
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
23
4.2 语言和文法 适当的表达式文法 用一种层次观点看待表达式 id id (id+id) + id id + id
24
4.2 语言和文法 适当的表达式文法 用一种层次观点看待表达式 id id (id+id) + id id + id id id (id+id) 文法 expr expr + term | term term term factor | factor factor id | (expr)
25
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 分析树
26
句型：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
27
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
28
4.2 语言和文法 4.2.6 消除左递归 消除左递归 A A α | β A β R R α R | ε
29
4.2 语言和文法 4.2.6 消除左递归 文法左递归 A+Aa 直接左递归 AAa |b 消除直接左递归 A b A
串的特点 ba a 消除直接左递归 A b A A a A |
30
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 |
31
4.2 语言和文法 非直接左递归 S Aa | b A Sd | 先变换成直接左递归 A Aad | bd | 再消除左递归 A bd A | A A adA |
32
4.2 语言和文法 4.2.7 提左因子 有左因子的文法 A 1 | 2 提左因子 A A A 1 | 2
33
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 |
34
形式语言 ⑴ 0 型语言 由 0型文法定义 又称 无限制文法！ 产生式形式为： -> 又称 上下文有关文法！
⑴ 0 型语言 由 0型文法定义 又称 无限制文法！ 产生式形式为： -> 又称 上下文有关文法！ ⑵ 1 型语言 由 1型文法定义 产生式形式为：xAy ->xy 又称 上下文无关文法！ ⑶ 2 型语言 由 2型文法定义 产生式形式为：A -> 又称 正规文法！ ⑷ 3 型语言 由 3型文法定义 产生式形式为：A->aB , A->a , A-> 【注】 四类语言为 包含关系，且有 L0 ⊃L1 ⊃ L2 ⊃ L3； 编译处理中，主要应用后两种文法！
35
乔姆斯基 艾弗拉姆·诺姆·乔姆斯基（英语：Avram Noam Chomsky，1928年12月7日－）
美国哲学家、语言学家、认知学家、逻辑学家、政治评论家。乔姆斯基是麻省理工学院语言学的荣誉退休教授，他的生成语法被认为是20世纪理论语言学研究上的重要贡献。
36
句法结构 《句法结构》是乔姆斯基介绍转换生成语法的《语言学理论的逻辑结构》一书的精华版。这一理论认为说话的方式（词序）遵循一定的句法，这种句法是以形式的语法为特征的，具体而言就是一种不受语境影响并带有转换生成规则的语法。 儿童被假定为天生具有适用于所有人类语言的基本语法结构的知识。这种与生俱来的知识通常被称作普遍语法。
37
下面的二义文法描述命题验算公式的语法，为他写一个等价的非二义文法
练习 文法 S->aSbS | bSaS | ε 产生的语言是什么？该文法是否有二义性？ 下面的二义文法描述命题验算公式的语法，为他写一个等价的非二义文法 S->S and S | S or S| not S| p | q | (S)
38
练习 文法 R->R'|'R | RR | R* | (R) | a | b
39
建立句子(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）的两个句子构造最右推导 这个文法产生的语言是什么？
Similar presentations
