第四章++语法分析(1)

1、1第四章 语法分析2本章内容本章内容o上下文无关文法o适于手工实现的技术n自顶向下分析nLL文法o用于自动化工具（Yacc）的算法n自底向上分析nLR文法3词词 法法分析器分析器记记 号号取下一个取下一个记号记号源程序源程序语法语法树树前端的前端的其余部分其余部分语法分语法分析器析器中间中间表示表示符号表符号表4.1 语法分析器的作用语法分析器的作用4o处理文法的语法分析器n通用的，但效率低nTop-downnBottom-up5文法的重要性o文法给出了程序设计语言的精确、易懂的语法规则o对于某些类型文法，可以自动构造出高效率的语法分析器o正确设计的文法给出了语言的结构o文法有助于语言的设计、

2、演化、开发64.2 上下文无关文法oRE的局限性 n正规式来定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复。例：a(ba)5, a(ba)*n正规式不能用于描述配对或嵌套的结构例：配对括号串的集合， wcw | w是a和b组成的符号串 包含递归结构的条件语句可以用产生式表示： stmt if expr then stmt else stmt74.2.1 上下文无关文法的定义上下文无关文法的定义上下文无关文法是四元组（VT , VN , S, P）VT : 终结符集合VN : 非终结符集合S : 开始符号P :产生式集合， 产生式形式为：A ，A VN, (VNVT )

3、*组成串的基本符号表示串的集合的语法变量S表示的串集合是文法生成的语言描述将终结符号和非终结符号组成串的方法8例例4.1 简单算术表达式的文法简单算术表达式的文法94.2.2 符号的使用约定符号的使用约定o我们一般用大写字母表示非终结符，小写字母表示终结符，(P114)oTerminals: na, b, c, +, -, punc, 0, 1, 9, Black strings: id, ifoNon Terminals: nA, B, C, S, italic stringso文法符号： X, Y, Zo终结符号串： u, v, z in VT*o文法符号串： , in (VT VN)*1

4、0符号的使用约定符号的使用约定oAlternatives of production rules: A 1; A 2; ; A k; A 1 | 2 | | k oFirst NT on LHS of 1st production rule is designated as start symbol !11例例4.2 定义算术表达式的文法定义算术表达式的文法124.2.3 推导o把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。o例： E E + E | E * E | (E ) | E | id E E (E) (E + E) (id + E) (id + id)替换序列称

5、为推导推导。 (id + id)是文法的句子句子。13推导推导定义定义：设有文法G = ( VT, VN, S, P)，称串A直接直接推导推导出，如果A P，且, (VTVN)*，并记作A 。 直接归约直接归约到A。如果存在一个直接推导序列： 0 1 . n (n0), 则称0推导推导出n，记作0n（推导长度为n）。记作或nnn*00014推导推导表示一步推导(直接推导)表示零步或多步推导对任意串如果 表示一步或多步推导*，。，则，且*15句型、句子、语言句型、句子、语言对开始符号为S的文法G，wL(G)，当且仅当称w为G的句子。对开始符号为S的文法G，如果，则称为G的句型。句子是不含非终结符

6、的句型。仅含终结符号的句型是一个句子句子。语言语言L(G)是由文法G产生的所有句子的集合：wS*S|)(*TVSGL且16若文法G1和文法G2所产生的语言相同，即L(G1) = L(G2)，则称文法G1和文法G2等价等价。 17 S aSb aaSbb a3Sb3 an-1Sbn-1 anbn显然，L(G1) = anbn n1 。例：已知文法G1 = ( a, b, S, S, P )，其中 P：S aSb ab 18问：文法G2 ：S bA A aA a 定义了一个什么样的语言？L(G2 )=ban|n=1 L(G2) = 以b开头后跟一个或多个a的串19问：文法G3 ：S AB A aA

7、 a B bB b定义了一个什么样的语言？L(G3)=anbm | n,m=1 20问：文法G4 ：S aSb定义了一个什么样的语言？L(G3)=anbn | n=1 21最左推导最左推导o最左推导：推导过程中任何一步推导 都是对中的最左非终结符进行替换。o如果 是最左推导，可以记为o如果 ，则称是文法的左句型。)()()()(ididEidEEEEElmlmlmlmlmlm*lmS22最右推导最右推导o类似的，可以定义最右推导：推导过程中任何一步推导 都是对中的最右非终结符进行替换。o最右推导也称作规范推导。)()()()(idididEEEEEErmrmrmrmrm23短语和句柄短语和句柄

8、o设有上下文无关文法G = (VT, VN, S, P)，串是文法G的句型，若有A+，且串A也是文法G的句型，则称是句型中关于非终结符号A的短语短语。 o若A ，则称为直接短语直接短语。o最左直接短语称为句柄句柄(handle)。24归约归约定义（定义（归约归约reduce）：设和均为句型，若*，则称可以归约为。规范（最右）推导的逆过程，称为规范归约规范归约。语法分析的核心问题就是，对于一个终结符号串x，设法从S推导出x，或者反过来，设法将x归约为S。254.2.4 分析树和推导分析树和推导分析树是推导的图形表示。26-(id+id)的分析树的分析树EE ()EEE+idid27例例4.3 从

9、最左推导构造的分析树从最左推导构造的分析树EEE EE ()EEE ()EEE+EE ()EEE+idEE ()EEE+idid28句型与分析树的关系句型与分析树的关系o设串是文法G的句型，则至少存在一棵分析树，它的叶子从左至右排列恰好就是。 o注意，分析树的形状与推导顺序无关，而与在推导时，所选择的对句型中的非终结符号进行替换的产生式有关。o每棵分析树都有与之对应的唯一的最左推导和最右推导。o但是，每个句子不一定只有唯一的分析树。294.2.5 二义性二义性o二义性的一些例子nI saw a man in the hill with a telescope.n球拍卖完了。n父在子先亡。30句

10、子id * id + id有两个不同的最左推导：E 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 + id31二义性用分析树表示比较直观二义性用分析树表示比较直观E 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 + idEEE*+EEidididEEidE*+EEid

11、id32文法的二义性文法的二义性o如果一个文法的句子存在两棵分析树，那么，该句子是二义性的。o如果一个文法包含二义性的句子，则说这个文法是二义性文法；否则说该文法是无二义性文法。o文法的二义性源于这样的事实，在一个句型中，存在一个非终结符号A，对于它有两条产生式可用于替换，但A的这些推导最终都产生相同的句型。33文法的二义性文法的二义性o二义性是文法的性质。程序设计语言是无二义的。（自然语言本质是二义的，在一定语境下没有二义）o文法的二义性的消除：改写文法344.2.6 验证文法产生的语言q文法和语言的关系：文法G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成354.2.6 验证文

12、法产生的语言例4.5 G : S (S) S | L(G) = 配对的括号串的集合o按推导步数进行归纳：推出的是配对括号串n归纳基础： S n归纳假设：少于n步的推导都产生配对的括号串n归纳步骤：n步的最左推导如下：S (S )S * (x) S * (x) y36o按串长进行归纳：配对括号串可由S推出n归纳基础： S n归纳假设：长度小于2n的都可以从S推导出来 n归纳步骤：考虑长度为2n(n 1)的w = (x) yS (S )S * (x) S * (x) y374.2.7 正规式和上下文无关文法o正规语言(RL)是上下文无关语言(CFL)的真子集，正规表达式所描述的语言可以用上下文无关

13、文法描述。o将NFA转换为等价的CFG。38ijaij 构造规则oEach State i has non-terminal Ai oIf then Ai a AjoIf then Ai AjoIf i is an accepting state, Ai oIf i is a starting state, Ai is the start symbol39正则表达式正则表达式(a|b)*abb 对应的文法对应的文法1starta0abb3b2A0 a A0 | b A0 | a A1 A1 b A2A2 b A3A3 40正规文法o若文法G = (VT, VN, S, P)中的每一个产生式形如

14、： A aB 或 A a其中A, BVN, aVT ，则称G为右线性文法。o若文法G=(VT, VN, S, P)中的每一个产生式形如： A Ba 或 A a则称G为左线性文法。o右线性文法和左线性文法都称为3型文法(正规文法)。41o语言L =anbn | n 1 S aSb | ab是不能用正规式描述的语言的一个范例是不能用正规式描述的语言的一个范例 n若存在接受若存在接受L的的DFA D，状态数为，状态数为k个。个。n 设设D读完读完 , a, aa, , ak 分别到达状态分别到达状态s0, s1, , skn至少有两个状态相同，例如是至少有两个状态相同，例如是si和和sj，则，则aj

15、bi属于属于L3 sifs0标记为标记为ai的路径的路径标记为标记为bi的路径的路径标记为标记为aj i的路径的路径424.3 文法的设计文法的设计o文法的优点 n文法给出了精确的，易于理解的语法说明n自动产生高效的分析器n可以给语言定义出层次结构n以文法为基础的语言的实现便于语言的修改o文法的问题n文法只能描述编程语言的大部分语法434.3.1 词法分析和语法分析o正规语言(RL)是上下文无关语言(CFL)的真子集，正规表达式所描述的语言可以用上下文无关文法描述。44为什么要用正规式定义词法为什么要用正规式定义词法?o为什么不用CFG定义词法 n词法规则非常简单，不必用上下文无关文法。n对于

16、词法记号，正规表达式描述简洁且易于理解。n从正规表达式构造出的词法分析器效率高。o把词法分析从语法分析中分离出来的理由 n简化设计n编译器的效率会改进n编译器的可移植性加强n便于编译器前端的模块划分 454.3.2 消除二义性消除二义性stmt if expr then stmt | if expr then stmt else stmt | other 46Form 1:stmtstmtstmtexprE1S2thenelseifexprE2S1thenifstmtstmtexprE1thenifstmtexprE2S2S1thenelseifstmtstmtForm 2:句型if E1 t

17、hen if E2 then S1 else S2的分析树47 改写为无二义的文法改写为无二义的文法（else与最近的then匹配）stmt matched _stmt | unmatched_stmtmatched_stmtif expr then matched_stmt else matched_stmt | otherunmatched_stmt if expr then stmt | if expr then matched_stmt else unmatched_stmt484.3.3 消除左递归o文法左递归A+Aa o消除直接左递归|21212121AAAAAAAAAAAAmnn

18、m替换成：49E E + T | TT T * F | FF ( E ) | id消除左递归后文法 E TE E +TE | T FT T *FT | F ( E ) | id例: 算术表达文法50o非直接左递归S Aa | b A Sd | o先变换成直接左递归S Aa | bA Aad | bd | o再消除左递归S Aa | bA bd A | A A adA | 51间接左递归的消除间接左递归的消除S Acc A BbbB Saa将 B 代入，得到：A Sababb将 A 代入，得到：S Sabcabcbcc再消除直接左递归：S abcSbcScS S abcS52Algorithm4

19、.8 消除左递归消除左递归Input: Grammar G with no cycles or -productionsOutput: An equivalent grammar with no left recursionArrange the non-terminals in some order A1,A2,Anfor i := 1 to n do begin for j := 1 to i 1 do begin replace each production of the form Ai Aj by the productions Ai 1 | 2 | | k where Aj 1|

20、2| k are all current Aj productions; end eliminate the immediate left recursion among Ai productions1. end53例例4.9 Apply the algorithm to: S Aa | bA Ac | Sd | i = 1: For A1 there is no left recursion i = 2: A2 A1d becomes A2 A2ad | bdNow, whats left: A1 A2a | bA2 A2 c | A2 ad | bd | A1 A2a | b A2 A2c

21、 | A1d | remove A2 left recursion :A1 A2a | bA2 bdA3 | A3 A3 cA3 | adA3544.3.4 提左因子不确定选择哪个规则来替换非终结符，例如： stmt if expr then stmt else stmt | if expr then stmt 改写产生式。55改写有左因子的文法改写有左因子的文法o对于所有形如 A 1 | 2| | n | o提左因子改写为A A| A 1 | 2 | n 56悬空else的文法stmt if expr then stmt else stmt | if expr then stmt | oth

22、er提取左因子，得到：stmt if expr then stmt optional_else_part | otheroptional_else_part else stmt | 574.3.5 非上下文无关的语言结构oL1 = wcw | w属于属于(a | b)*n检查标识符的声明应先于其引用的抽象 oL2 = anbmcndm | n 0, m 0 n检查形参个数和实参个数应该相同的抽象 oL3 = anbncn | n 0 n打字机打印下划线字符的抽象58注意：一些类似的语言却是注意：一些类似的语言却是CFG。oL1 = wcwR | w (a|b)* S aSa | bSb | c

23、 oL2 = anbmcmdn | n 1, m 1 S aSd | aAdA bAc | bcoL2 = anbncmdm | n 1，m 1 S ABA aAb | abB cBd | cd59oL3 =anbn | n 1 S aSb | abL3 是不能用正规式描述的语言的一个范例是不能用正规式描述的语言的一个范例 n若存在接受若存在接受L3 的的DFA D，状态数为，状态数为k个。个。n 设设D读完读完 , a, aa, , ak 分别到达状态分别到达状态s0, s1, , skn至少有两个状态相同，例如是至少有两个状态相同，例如是si和和sj，则，则ajbi属于属于L3 sifs0标记为标记为ai的路径的路径标记为标记为bi的路径的路径标记为标记为aj i的路径的路径60L3anbncn| n 1是上下文有关文法S aSBC S aBC CB BCaB ab bB bbbC bccC ccanbncn的推导过程如下：