第4章语法分析和程序

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

从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导。自底向上分析法：

从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。自底向上的语法分析例：文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否是该文法的句子

S A A cabd cabd cabd关健：句柄的确定自顶向下分析的语法分析例：文法 SaCb Ccd|c

为输入串w=acb建立分析树SSSaCbaaCCbbcdc试探的过程问题：会产生回溯–导致效率低自顶向下分析法的另一问题若有文法G6[S]:

(1)S→Sa

(2)S→b

推导baa#

问题：左递归—可能导致死循环SbSSaSSabSSaSaSSaSab自顶向下分析法需要解决的问题左递归对文法进行改造回溯如何唯一地确定所采用的产生式？－LL(1)文法当拒绝w时,只能知道w不是句子,不知出何错及出在何处本节将主要介绍确定的自顶向下分析思想和对文法的要求。确定的自顶向下分析要求文法满足LL(1)文法。

本节主要介绍内容为：

LL(1)文法的定义和判别

非LL(1)文法的等价变换

确定的自顶向下分析方法

递归子程序法

预测分析方法4.1自顶向下的语法分析消除文法的左递归带回溯的递归子程序回溯的消除及LL（1）文法4.1.1消除文法的左递归例：AA|A的解是：*引入新的非终结符A’,令其产生*,则有:AA’ A’A’|4.1.2带回溯的递归子程序对于文法的每个非终结符，根据其各候选式的结构,为其建立一个递归的子程序(函数)，用于识别该非终结符所表示的语法范畴例如,产生式E’+TE’，相应的子程序(函数)为expr_prime(){ if(match(PLUS)){ advance(); term(); expr_prime(); } }4.1.3回溯的消除及LL（1）文法基本原理First集及Follow集的构造分析器的构造例：ETE’E’ATE’|ε TFT’T’MFT’|ε

F(E)|iA+|-M*|/(4.1)’对i+ii进行预测分析的过程4.1.4某些非LL(1)文法的改造方法：消除左递归反复提取左因子例：EE+T|T T(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)文法是否等价；(5)CFL是否是LL(1)语言是不可判定的；(6)非LL(1)语言是存在的。若在分析过程中，每步向前扫描k个符号来确定选用的产生式，此分析方法称为是LL(k)分析。此法极少用，故从略。习题判断下列文法是否是LL(1)文法，如果是，请写出LL(1)分析表；如果不是，请改造成LL(1)文法。SaFA|+aFAA+aFA|+B|F*aBBF|4.2自底向上的语法分析优先分析法及LR分析法问题：如何确定句型的句柄如何正确地选择产生式进行归约建立语法树4.2.1优先文法 简介4.2.2LR分析法LR分析:自左至右扫描的自底向上的分析LR分析对文法要求很少,效率极高,且能及时发现错误,是目前最广泛使用的方法;一般用CFG描述的语言均可用LR分析法先介绍LR分析器的逻辑结构及工作原理,再分别介绍几种LR分析器(即LR(0),SLR(1)和LR(1))的构造（一）LR分析器的逻辑结构及工作原理LR分析器=输入符号串+分析栈+总控程序+分析表例：文法G[L]:1.LE,L 2.LE 3.Ea 4.Eb分析表状态ACTIONGOTOab，#LE0s3s4

121

acc

2

s5r2

3

r3r3

4

r4r4

5s3s4

626

r1

例：对符号串“a,b,a”的分析过程四个分析动作：移进、归约、接受、报错对符号串“a,b,a”的分析过程步骤状态栈中符号余留符号分析动作下一状态10#a,b,a#s33203#a,b,a#r3GOTO[0,E]=2302#E,b,a#s554025#E,b,a#s4450254#E,b,a#r4GOTO[5,E]=260252#E,E,a#s55702525#E,E,a#s338025253#E,E,a#r3GOTO[5,E]=29025252#E,E,E#r2GOTO[5,L]=610025256#E,E,L#r1GOTO[5,L]=6110256#E,L#r1GOTO[0,L]=11201#E#

（二）LR(0)分析表的构造一些术语规范句型的活前缀将栈内符号与未扫描的输入串拼接起来,可得一规范句型.即栈内符号串总是规范句型的前缀,且不含句柄右侧的符号.把具有上述性质的符号串称为规范句型的活前缀LR(0)项目（看详细内容）LR(0)项目活前缀：包含全部句柄，则：进行归约:A,记为A;句柄中，则：应移进(句柄的后半部分),A12不含句柄，则：期望移进一产生式的右部:A我们把右部添加了一个“”的产生式,称为LR(0)项目LR(0)项目：归约项目：A→接受项目：S’→S移进项目：AX,(XVT,可以是空串)待约项目：AX,(XVN,可以是空串)识别所有规范句型全部活前缀的DFA例：文法G[S]：

S→A|BA→aAb|c,B→aBb|dLR(0)分析表的构造I0:S’→·SS→·AS→·BA→·aAbA→·cB→·aBbB→·dI1:S’→S·SI2:S→A·AI3:S→B·BI4:A→a·AbA→·aAbA→·cB→a·BbB→·aBbB→·daI5:A→c·ccI6:A→d·ddaI7:A→aA·bI9:B→aB·bI8:A→aAb·I10:B→aBb·BAbb识别G[S]全部活前缀的DFAG[S]的LR(0)分析表

ACTIONGOTOabcd#SAB0s4

s5s6

1231

acc

2r1r1r1r1r1

3r2r2r2r2r2

4s4

s5s6

795r4r4r4r4r4

6r6r6r6r6r6

7

s8

8r3r3r3r3r3

9

s10

10r5r5r5r5r5

习题文法G[B]是否是LR(0)文法？如果是，请画出LR(0)分析表；如果不是，请说明原理：B→bD;Se D→D;d|d S→s;S|sSLR(1)分析表的构造习题文法G[S]是否是LR(0)文法？如果是，请画出LR(0)分析表；如果不是，请说明原理：S→CbBAA→Aab|abB→C|DbC→aD→aLR(1)分析表的构造I0:S’→·S,#S→·CbBA,#C→·a,bI1:S’→S·,#SI3:C→a·,baI2:S→C·bBA,#CI4:S→Cb·BA,#B→·C,aB→·Db,aC→·a,aD→·a,bbI5:S→CbB·A,#A→·Aab,#/aA→·ab,#/aI6:B→C·,aBCI8:C→a·,aD→a·,baI7:B→D·b,aI9:B→Db·,aDbI11:A→a·b,#/aI12:A→ab·,#/aabI10:S→CbBA·,#A→A·ab#/aAI13:A→Aa·b,#/aI14:A→Aab·,#/aab文法G[S]的LR(1)项目集及DFA分析表实例状态ACTIONGOTOabcSABCD0s3

1

2

1

acc

2

s4

3