第四章 语法分析
第四章 语法分析 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开 词 法 分析器 记 号 取下一个记号 第四章 语法分析 词 法 分析器 记 号 取下一个记号 源程序 分析树 前端的 其余部分 中间表示 符号表 本章内容 上下文无关文法 自上而下分析和自下而上分析 围绕分析器的自动生成展开
上下文无关文法 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 直接左递归 AAa |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 ->xy 又称 上下文无关文法! ⑶ 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)的两个句子构造最右推导 这个文法产生的语言是什么?