第4章 语法分析和语法分析程序

1、编编 译译 原原 理理第四章 语法分析和语法分析程序本章内容本章内容v自顶向下分析和自底向上分析自顶向下分析和自底向上分析v围绕分析器的自动生成展开围绕分析器的自动生成展开难难 重重 点点语法分析是编译程序的核心部分。语法分析是编译程序的核心部分。 语法分析的作用是识别由词法分析给出的单语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程词符号序列是否是给定文法的正确句子（程序）序） 目前语法分析常用的方法有自顶向下（自上目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两而下）分析和自底向上（自下而上）分析两大类。大类。v自顶向下分析法：自顶向

2、下分析法：从文法的开始符号出发，反复使用文法从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推的产生式，寻找与输入符号串匹配的推导。导。v自底向上分析法：自底向上分析法：从输入符号串开始，逐步进行归约，直至从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。归约到文法的开始符号。自底向上的语法分析自底向上的语法分析v例：文法例：文法G： S cAd A ab A a识别输入串识别输入串w=cabd是否是该文法的句子是否是该文法的句子 S AA c a b d c a b d c a b dv关健：句柄的确定关健：句柄的确定自顶向下分析的语法分析 例：例： 文法文法S a

3、Cb C cd | c 为输入串为输入串w = acb建立分析树建立分析树SSSaCbaaCCbbcdc试探试探的过程的过程v问题：会产生回溯问题：会产生回溯 导致效率低导致效率低自自顶向下分析法的另一问题下分析法的另一问题 若有文法若有文法G6S: (1) SSa (2) Sb推导推导baa#v问题：左问题：左递归递归可可能导致死能导致死循环循环SbSSaSSabSSaSaSSaSab自自顶向下分析法需要解决的问题 左递归左递归 对文法进行改造对文法进行改造 回溯回溯 如何唯一地确定所采用的产生式？如何唯一地确定所采用的产生式？ LL(1)文法文法 当拒绝当拒绝w时时,只能知道只能知道w不是

4、句子不是句子,不知出何错不知出何错及出在何处及出在何处v本节将主要介绍确定的自顶向下分析思想和本节将主要介绍确定的自顶向下分析思想和对文法的要求。确定的自顶向下分析要求文对文法的要求。确定的自顶向下分析要求文法满足法满足LL(1)文法。文法。本节主要介绍内容为：本节主要介绍内容为： LL(1) 文法的定义和判别文法的定义和判别 非非LL(1)文法的等价变换文法的等价变换 确定的自顶向下分析方法确定的自顶向下分析方法 递归子程序法递归子程序法 预测分析方法预测分析方法4.1 自顶向下的语法分析自顶向下的语法分析 消除文法的左递归消除文法的左递归 带回溯的递归子程序带回溯的递归子程序 回溯的消除及

5、回溯的消除及LL（1）文法）文法4.1.1 消除文法的左递归消除文法的左递归 例：例：AA | A的解是：的解是： * 引入新的非终结符引入新的非终结符A,令其产生令其产生 *,则有则有: A AA A| 4.1.2 带回溯的递归子程序带回溯的递归子程序 对于文法的每个非终结符，根据其各候选式的结构对于文法的每个非终结符，根据其各候选式的结构,为其建立一个递归的子程序为其建立一个递归的子程序(函数函数)，用于识别该非，用于识别该非终结符所表示的语法范畴终结符所表示的语法范畴 例如例如,产生式产生式E+TE ，相应的子程序相应的子程序(函数函数)为为expr_prime( )expr_prime

6、( ) if(match(PLUS) if(match(PLUS)advance( );advance( );term( );term( );expr_prime( );expr_prime( ); 4.1.3 回溯的消除及回溯的消除及LL（1）文法）文法 基本原理基本原理 First集及集及Follow集的构造集的构造 分析器的构造分析器的构造 例：例： ETE E ATE| TFT T MFT| F(E)|i A+|- M* | / (4.1) 对对i+ii进行预测分析的过程进行预测分析的过程4.1.4 某些非某些非LL(1)文法的改造文法的改造 方法：方法： 消除左递归消除左递归 反复提

7、取左因子反复提取左因子 例：例： EE+T | TT(E) | a(E) | a 经改造后可得文法经改造后可得文法： ETE E+TE| TaT | (E)T (E) | 这是一个这是一个LL(1)文法文法关于关于LL(1)的一些结论的一些结论 能由能由LL(1)文法产生的语言称为文法产生的语言称为LL(1)语言。它们已被证明具语言。它们已被证明具有许多重要特性，主要有：有许多重要特性，主要有： (1) 任何LL(1)文法都是无二义性的； (2) 左递归文法是非LL(1)的； (3) 存在一种算法,它能判定任意文法是否为LL(1)的； (4) 存在一种算法,它能判定任意两个LL(1)文法是否等

8、价； (5) CFL是否是LL(1)语言是不可判定的； (6) 非LL(1)语言是存在的。 若在分析过程中，每步向前扫描若在分析过程中，每步向前扫描k个符号来确定选用的产生个符号来确定选用的产生式，此分析方法称为是式，此分析方法称为是LL(k)分析分析。此法极少用此法极少用，故从略故从略。习题习题判断下列文法是否是判断下列文法是否是LL(1)文法，如果是，请文法，如果是，请写出写出LL(1)分析表；如果不是，请改造成分析表；如果不是，请改造成LL(1)文法文法。S aFA | +aFAA +aFA |+B| F *aBB F | 4.2 自底向上的语法分析自底向上的语法分析 优先分析法及优先分

9、析法及LR分析法分析法 问题：问题： 如何确定句型的句柄如何确定句型的句柄 如何正确地选择产生式进行归约如何正确地选择产生式进行归约 建立语法树建立语法树4.2.1 优先文法优先文法 简介简介4.2.2 LR分析法分析法: 自左至右扫描的自底向上的分析自左至右扫描的自底向上的分析 LR分析对文法要求很少分析对文法要求很少,效率极高效率极高,且能及时且能及时发现错误发现错误,是目前最广泛使用的方法是目前最广泛使用的方法;一般用一般用CFG描述的语言均可用描述的语言均可用LR分析法 先介绍先介绍LR分析器的逻辑结构及工作原理分析器的逻辑结构及工作原理,再再分别介绍几种分别介绍几种LR分析器分析器(

10、即即LR(0),SLR(1)和和LR(1)的构造的构造（一）（一）LR分析器的逻辑结构及工作原理分析器的逻辑结构及工作原理 LR分析器分析器=输入符号串输入符号串+分析栈分析栈+总控程序总控程序+分析表分析表 例：文法例：文法GL: 1. LE,L 2. LE3. Ea4. Eb 分析表分析表状态状态ACTIONGOTOab，#LE0s3s4 121 acc 2 s5r2 3 r3r3 4 r4r4 5s3s4 626 r1 v例：对符号串例：对符号串“a,b,a”的分析过的分析过程程v四个四个分析动作分析动作：移进、移进、归约、接受、报错归约、接受、报错对符号串对符号串“a,b,a”的分析过

11、程的分析过程步骤步骤状态状态栈中符号栈中符号余留符号余留符号分析动作分析动作下一状态下一状态10#a,b,a#s33203#a,b,a#r3GOTO0,E=2302#E,b,a#s554025#E,b,a#s4450254#E,b,a#r4GOTO5,E=260252#E,E,a#s55702525#E,E,a#s338025253#E,E,a#r3GOTO5,E=29025252#E,E,E#r2GOTO5,L=610025256#E,E,L#r1GOTO5,L=6110256#E,L#r1GOTO0,L=11201#E# （二）（二）LR(0)分析表的构造分析表的构造 一些术语一些术语 规

12、范句型的活前缀规范句型的活前缀 将栈内符号与未扫描的输入串拼接起来将栈内符号与未扫描的输入串拼接起来,可得一可得一规范规范句型句型.即栈内符号串总是即栈内符号串总是规范句型的前缀规范句型的前缀,且且不含句柄不含句柄右侧的符号右侧的符号. 把具有上述性质的符号串称为把具有上述性质的符号串称为 LR(0)项目（看详细内容）项目（看详细内容）LR(0)项目项目 活前缀：活前缀： 包含全部句柄，则：进行归约包含全部句柄，则：进行归约: A, 记为记为A ; 句柄中，则：句柄中，则：应移进应移进(句柄的后半部分句柄的后半部分), A1 2 不含句柄，则：不含句柄，则：期望移进一产生式的右部期望移进一产生

13、式的右部: A 我们把右部添加了一个我们把右部添加了一个“ ”的产生式的产生式,称为称为 LR(0)项目：项目： 归约项目：归约项目： A 接受项目：接受项目： SS 移进项目：移进项目： A X , ( X VT, 可以是空串可以是空串) 待约项目：待约项目： A X , ( X VN, 可以是空串可以是空串)识别所有规范句型全部活前缀的识别所有规范句型全部活前缀的DFA 例：文法例：文法GS： SA|B AaAb|c, BaBb|d LR(0)分析表的构造分析表的构造I0:SSSASBAaAbAcBaBbBdI1: SSSI2: SAAI3: SBBI4:AaAbAaAbAcBaBbBaB

14、bBdaI5: AcccI6: AdddaI7: AaAbI9: BaBbI8: AaAbI10: BaBbBAbb识别识别全部活前缀的全部活前缀的GS的的LR(0)分析表分析表 ACTIONGOTOabcd#SAB0s4 s5s6 1231 acc 2r1r1r1r1r1 3r2r2r2r2r2 4s4 s5s6 795r4r4r4r4r4 6r6r6r6r6r6 7 s8 8r3r3r3r3r3 9 s10 10r5r5r5r5r5 习题习题 文法文法GB是否是是否是LR(0)文法？如果是，请画文法？如果是，请画出出LR(0)分析表；如果不是，请说明原理：分析表；如果不是，请说明原理： B

15、bD;SeDD;d|d Ss;S|sSLR(1)分析表的构造分析表的构造习题习题 文法文法GS是否是是否是LR(0)文法？如果是，请画文法？如果是，请画出出LR(0)分析表；如果不是，请说明原理：分析表；如果不是，请说明原理： SCbBA AAab|ab BC|Db Ca Da LR(1)分析表的构造分析表的构造I0:S S, #SCbBA, #C a, bI1: S S , #SI3: Ca , baI2: S CbBA, #CI4:SCbBA, #BC, aB Db, aC a, aD a, bbI5:SCbBA, #AAab, #/aA ab, #/aI6: BC , aBCI8: Ca , aD a , baI7: BD b, aI9: BDb