《第四章语法分析》由会员分享，可在线阅读，更多相关《第四章语法分析（39页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 语法分析语法分析第四章第四章 语法分析语法分析v本章内容本章内容上下文无关文法上下文无关文法自上而下自上而下分析和自下而上分析分析和自下而上分析围绕分析器的自动生成展开围绕分析器的自动生成展开词词 法法分析器分析器记记 号号取下一个取下一个记号记号源程序源程序分析分析树树前端的前端的其余部分其余部分分析器分析器中间中间表示表示符号表符号表上下文无关文法4.14.34.1 上下文无关文法上下文无关文法4.1.1 上下文无关文法的定义上下文无关文法的定义正则式能定义一些简单的语言正则式能定义一些简单的语言，能表示给定结构能表示给定结构的固定次数的重复或者没有指定次数的重复的固定次数的
2、重复或者没有指定次数的重复例：例：a (ba)5, a (ba)*正则式不能用于描述配对或嵌套的结构正则式不能用于描述配对或嵌套的结构例例1：配对括号串的集合配对括号串的集合例例2：wcw | w是是a和和b的串的串 4.1 上下文无关文法上下文无关文法v上下文无关文法上下文无关文法是四元组（是四元组（VT , VN , S, P）VT : : 终结符终结符集合集合VN : : 非非终结符终结符集合集合S : : 开始符号，非终结符中的一个开始符号，非终结符中的一个P : :产生式产生式集合，集合， 产生式形式产生式形式 : : A v例例 ( id, +, , , (, ), expr, o
3、p, expr, P )expr expr op expr expr (expr)expr expr expr idop + op 4.1 上下文无关文法上下文无关文法v简化表示简化表示expr expr op expr | (expr) | expr | idop + | 简化表示简化表示E E A E | (E ) | E | idA + | 4.1 上下文无关文法上下文无关文法v文法书写上的约定终结符v字母表中的小写字母，如 a，b，cv黑体串，如 id, whilev数字 0, 1, , 9v标点符号，如括号，逗号等v运算符号，如+, -等非终结符v字母表中的大写字母，如A, B, C
4、v字母S，并且通常代表开始符号v小写字母的名字（斜体），如expr, stmt4.1 上下文无关文法上下文无关文法v文法书写上的约定字母表中后面的大写字母，如X，Y，Z，可以是终结符或非终结符字母表中后面的小写字母，如u，v z 可代表终结符号串小写希腊字母，如，可代表文法的符号串对于A 1，A 2，. A n可以写成 A 1 | 2 | | n4.1 上下文无关文法上下文无关文法4.1.2 推导（自顶向下自顶向下） 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替v例 E E + E | E E | (E ) | E | id E E (E) (E + E) (id + E
5、) (id + id) v概念S *、 S + w ，于是v *v * b， 且 b , 则 * 4.1 上下文无关文法上下文无关文法4.1.2 推导推导 v概念概念上下文无关语言上下文无关语言vA, 且、b是任意符号串，则A Ab bv由上下文无关文法生成的语言是上下文无关语言等价的等价的文法文法v如果两个文法产生同样的语言，则两个文法等价句型句型v文法G的开始符为S，S * ， 可能含有非终结符，则 叫做文法G的句型。4.1 上下文无关文法上下文无关文法v例例 E E + E | E E | (E ) | E | id v最左最左推导推导E lm E lm (E) lm (E + E) l
6、m (id + E) lm (id + id)v最右最右推导推导E rm E rm (E) rm (E + E) rm (E + id) rm (id + id)4.1 上下文无关文法上下文无关文法4.1.3 分析树分析树例例 E E + E | E E | (E ) | E | idEE ()EEE+idid4.1 上下文无关文法上下文无关文法4.1.4 二义性 id id + idE E E E E + E id E E E +E id E + E id E + E id id + E id id + E id id + id id id + id两个不同的最左推导4.1 上下文无关文法上
7、下文无关文法4.1.4 二义性 id id + idE E E E E + E id E E E +E id E + E id E + E id id + E id id + E id id + id id id + id两棵不同的语法树EEE*+EEidididEEidE*+EEidid4.2语言和文法语言和文法 v文法的优点文法的优点 文法给出了精确的，易于理解的语法说明文法给出了精确的，易于理解的语法说明自动产生高效的分析器自动产生高效的分析器可以给语言定义出层次结构可以给语言定义出层次结构以文法为基础的语言的实现以文法为基础的语言的实现便于语言的修改便于语言的修改v文法的问题文法的问题
8、文法只能描述编程语言的大部分语法，不能描述文法只能描述编程语言的大部分语法，不能描述语言中上下文有关的语法特征语言中上下文有关的语法特征4.2 语言和文法语言和文法 4.2.1 正则式和上下文无关文法的比较正则式和上下文无关文法的比较v正则式正则式(a|b)*abv文法文法A0 a A0 | b A0 | a A1A1 b A2A2 12开始开始a0abb4.2 语言和文法语言和文法 4.2.2 分离词法分析器理由分离词法分析器理由v为什么要用正则式定义词法为什么要用正则式定义词法 词法规则非常简单，不必用上下文无关文法词法规则非常简单，不必用上下文无关文法对于词法记号，正则式描述简洁且易于理
9、解对于词法记号，正则式描述简洁且易于理解从正则式构造出的词法分析器效率高从正则式构造出的词法分析器效率高4.2 语言和文法语言和文法 v从软件工程角度看，词法分析和语法分析的从软件工程角度看，词法分析和语法分析的分离有如下好处分离有如下好处简化设计简化设计编译器的效率会改进编译器的效率会改进编译器的可移植性加强编译器的可移植性加强便于编译器前端的模块划分便于编译器前端的模块划分 4.2 语言和文法语言和文法 v能否把词法分析并入到语法分析中，直接从能否把词法分析并入到语法分析中，直接从字符流进行语法分析字符流进行语法分析若把词法分析和语法分析合在一起，则必须将语若把词法分析和语法分析合在一起，
10、则必须将语言的注解和空白的规则反映在文法中，文法将大言的注解和空白的规则反映在文法中，文法将大大复杂大复杂注解和空白由自己来处理的分析器，比注解和空注解和空白由自己来处理的分析器，比注解和空格已由词法分析器删除的分析器要复杂得多格已由词法分析器删除的分析器要复杂得多4.2 语言和文法语言和文法 4.2.3 验证文法产生的语言验证文法产生的语言G : S (S) S | L(G) = 配对的括号串的集配对的括号串的集合合4.2 语言和文法语言和文法 4.2.3 验证文法产生的语言验证文法产生的语言G : S (S) S | L(G) = 配对的括号串的集合配对的括号串的集合v按推导步数进行归纳按
11、推导步数进行归纳：推出的是：推出的是配对括号串配对括号串归纳基归纳基础：础： S 归纳假设：归纳假设：少于少于n步的推导都产生配对的括号串步的推导都产生配对的括号串归纳步骤：归纳步骤：n步的最左推导步的最左推导如下：如下：S (S)S * (x) S * (x) y4.2 语言和文法语言和文法 4.2.3 验证文法产生的语言验证文法产生的语言G : S (S) S | L(G) = 配对的括号串的集合配对的括号串的集合v按串长进行归纳按串长进行归纳：配对括号串可由配对括号串可由S推出推出归纳基归纳基础：础： S 归纳假设：归纳假设：长度小于长度小于2n的都可以从的都可以从S推导出来推导出来归纳
12、步骤：归纳步骤：考虑长度为考虑长度为2n(n 1)的的w = (x) yS (S)S * (x) S * (x) y4.2 语言和文法语言和文法 4.2.4 适当的表达式文法适当的表达式文法用一种层次观点看待表达式用一种层次观点看待表达式id id (id+id) + id id + id4.2 语言和文法语言和文法 4.2.4 适当的表达式文法适当的表达式文法用一种层次观点看待表达式用一种层次观点看待表达式id id (id+id) + id id + idid id (id+id) 文法文法expr expr + term | termterm term factor | factor f
13、actor id | (expr)4.2 语言和文法语言和文法 expr expr + term | termterm term factor | factor factor id | (expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid + id id分析树分析树 id id id分析树分析树 4.2 语言和文法语言和文法 4.2.5 消除二义性消除二义性stmt if expr then stmt | if expr then stmt else st
14、mt | other 句型句型：if expr then if expr then stmt else stmt两个最左推导：两个最左推导：stmt if expr then stmt if expr then if expr then stmt else stmtstmt if expr then stmt else stmt if expr then if expr then stmt else stmt 4.2 语言和文法语言和文法 v 无二义的文法无二义的文法stmt matched _stmt | unmatched_stmtmatched_stmt if expr then mat
15、ched_stmt else matched_stmt | otherunmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt4.2 语言和文法语言和文法 4.2.6 消除左递归消除左递归消除左递归A A | A RR R | 4.2 语言和文法语言和文法 4.2.6 消除左递归消除左递归v文法文法左递归左递归A+A v直接左递归直接左递归AA | 串的特点串的特点 . . . . . . v消除直接左递归消除直接左递归A A A A | 4.2 语言和文法语言和文法 v例例 算术表达文法算
16、术表达文法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 | F ( E ) | id4.2 语言和文法语言和文法 v非直接左递归非直接左递归S Aa | b A Sd | v先变换成直接左递归先变换成直接左递归S Aa | bA Aad | bd | v再消除左递归再消除左递归S Aa | bA bd A | A A adA | 4.2 语言和文法语言和文法 4.2.7 提左因子提左因子有左因子的文法有左因子的文法A 1 |
17、2提左因子提左因子A A A 1 | 2 4.2 语言和文法语言和文法 v例 悬空else的文法 stmt if expr then stmt else stmt | if expr then stmt | other提左因子stmt if expr then stmt optional_else_part | otheroptional_else_part else stmt | 形式语言 产生式形式为：xAy -xy 产生式形式为：A-aB , A-a , A- 产生式形式为：A - 2 型语言 由 2型文法定义 1 型语言 由 1型文法定义 0 型语言 由 0型文法定义 产生式形式为：
18、- 3 型语言 由 3型文法定义又称 无限制文法！又称 上下文有关文法！又称 上下文无关文法！又称 正规文法！【注】 四类语言为 包含关系，且有 L0 L1 L2 L3；编译处理中，主要应用后两种文法！乔姆斯基v艾弗拉姆诺姆乔姆斯基（英语：Avram Noam Chomsky，1928年12月7日）v美国哲学家、语言学家、认知学家、逻辑学家、政治评论家。乔姆斯基是麻省理工学院语言学的荣誉退休教授，他的生成语法被认为是20世纪理论语言学研究上的重要贡献。句法结构v句法结构是乔姆斯基介绍转换生成语法的语言学理论的逻辑结构一书的精华版。这一理论认为说话的方式（词序）遵循一定的句法，这种句法是以形式的
19、语法为特征的，具体而言就是一种不受语境影响并带有转换生成规则的语法。v儿童被假定为天生具有适用于所有人类语言的基本语法结构的知识。这种与生俱来的知识通常被称作普遍语法。练习v文法S-aSbS | bSaS | 产生的语言是什么？该文法是否有二义性？v下面的二义文法描述命题验算公式的语法，为他写一个等价的非二义文法vS-S and S | S or S| not S| p | q | (S)练习v文法R-R|R | RR | R* | (R) | a | b产生字母表a,b上所有不含的正则式。为该文法写一个等价的非二义文法。练习v考虑文法S-(L) | aL-L,S | Sv建立句子(a,(a,a)和(a,(a,a),(a,a)的分析树v为（a）的两个句子构造最左推导v为（a）的两个句子构造最右推导v这个文法产生的语言是什么？
