编译原理简明教程（第3版）-课件 第4-6章 词法分析、语法分析-自顶向下、语法分析-自底向上

新工科建设·计算机类系列教材

免费提供编译原理16目录第一章

概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造4词法分析学习目标词法分析是编译过程的第一步，其主要任务是对源程序进行扫描，从中识别出单词，是编译过程中不可缺少的部分。重点：词法分析的过程；单词的形式、种类；词法分析程序的设计方法3

目录4.1词法分析概述4.2词法分析程序4.3词法分析程序的自动生成4.4本章小结44.1词法分析概述4.1.1词法分析的功能词法分析程序的主要功能

输入源程序输出单词符号单词符号（单词）：程序语言具有独立意义的最小语法单位属性字：单词的一种机内表示(反映单词的有关特性).54.1.1词法分析的功能包括处理说明部分·把单词的全部属性都识别出来不必包括处理说明部分·不把单词的全部属性都识别出来词法分析分为两类64.1.1词法分析的功能识别单词从用户的源程序中把单词分离出来;生成属性字把单词转换成机内表示，便于后续处理。词法分析又称为扫描器，任务有两个：74.1.2词法分析的两种处理结构词法分析是主程序:词法分析程序字符串表示的源程序源程序字符字符语法分析是主程序，词法分析是子程序:源程序字符词法分析程序单词回送8符号表语法分析程序4.1.3单词符号的种类保留字(关键字)常数标识符界限符(特殊符号)程序语言定义的具有固定意义的标识符如:Pascal中的begin、end、if、while…。用来表示各种名字.如:变量名、数组名、过程名等。如:128、0.123、3.14E-2…。如:+、-、*、/、>=、<=、》=、《=等。单词符号94.1.4词法分析程序的输出形式

一般采用二元式

一个语言的单词符号分为几类，如何分类、怎样编码,是一个技术性问题，主要取决于处理上的方便。

如：标识符分为一类

常数且按类型（整数、实数）分类

保留字可分为一类，也可一字一类

界限符可分为一类，也可一符一类

单词类别单词符号的属性值对于采用一字一类、一符一类，不需再给出单词的值。10

但若一个类别中含多个单词符号，还需给出相应的值（按某种编码）例如：对于标识符，常把存放它的有关信息的符号表项的指针作为属性值。对于常数，常把存放它的常数表项的指针作为属性值。11标识符保留字常数特殊符号4.2词法分析程序4.2.1词法分析程序的设计与实现初始化读字符是字母?读标识符数字?取数字查常量表生成属性字写到输出流是否分析结束结束特殊符号?出错查特殊符号表生成属性字查保留字表查到?查名字表生成属性字生成属性字YYYYNNNNYN124.2.2单词的识别单词的文法规则:<标识符>→<字母>|<标识符><字母>|<标识符><数字><无符号整数>→<数字>|<无符号整数><数字><特殊符号>→+|-|*|<=|…单词的状态转换图如下13标识符或保留字

整

数实数（无指数部分）带指数的实数

加号

减号

乘号

除号

等于

小于

小于等于

不等于144.2.3无符号数的识别文法规则如下：<无符号数>→<无符号实数>|<无符号整数><无符号实数>→<无符号整数>.<数字串>[E<比例因子>]|<无符号整数>E<比例因子><比例因子>→<有符号整数><有符号整数>→[+|-]<无符号整数><无符号整数>→<数字串><数字串>→<数字>{<数字>}<数字>→0|1|2…|915

设无符号数为：

t=….…E…(整数部分)(小数部分)(指数部分)

令W=…

…1

P=…

e=

则t=W-1

读无符号数的程序流程图见图4.7164.2.4标识符的识别<标识符>→<字母>{<字母>|<数字>}<字母>→A|B|C|…|Z|a|b|…|z<数字>→0|1|2|…|9保留字是特殊的标识符特殊处理事先构造保留字表事先构造保留字树规定保留字在源程序中用分界符括起来

174.3词法分析程序的自动生成4.3.1基本思想通常可通过两种途径来构造词法分析程序：

手工方式和自动生成

1、手工方式根据对语言中各类单词的描述或定义，手工构造词法分析程序。如：可根据文法或状态转换图构造相应的状态矩阵，读状态矩阵同控制程序一起组成了编译程序的词法分析程序。

也可根据文法或状态转换图利用某种语言（汇编或高级语言）直接编写词法分析程序。184.3词法分析程序的自动生成2、自动生成

只要给出某语言各类单词词法结构的文法描述（如正则式），以及各类单词在词法分析时应采取的语义动作，自动生成系统。对上述信息进行加工，即可得到所需的词法分析程序，例：RWORD、LEXLEX是美国Bell实验室1975年用C语言研制的一个词法分析程序的自动生成工具。

LEX源程序LEX编译系统词法分析程序194.3.2LEX源程序结构辅助定义转换规则（识别规则）用户子程序（代码）LEX源程序201、辅助定义在使用LEX语言时，先将高级语言的词法写成辅助定义式（类似宏定义）。例：⑴标识符letter→A|B…|a|b…|zdigit→0|1|…|9ident→letter(letter|digit)*⑵整常数integer→digit(digit)*21⑶一般实常数

sign→+|-|εsigninteger→signintegerdecimal→eger|eger⑷

含指数部分的实数

exprel→(decimal|signinteger)E

signinteger⑸

实常数real→decimal|exprel222.识别规则（规定了相应词法分析程序的功能）{}是定义在υ{,,…,}上的正则表达式—词型{}是语义动作（一个可执行的程序段）例：整常数：digit{val=int(id);求整型值return(16);return(val)}return()子程序;16:单词的类别编码23标识符:

letter

{if(keyword(id)!=0)return(keyword(id));else{return(15);return(id)}}

keyword()查保留字表，=0未查到243.用户子程序（辅助函数部分）

用户编写的函数代码（可被识别规则调用）4.3.3LEX编译程序工作过程

Ⅰ根据每条Pi，构造相应NFAⅡ将各NFA连成一个完整的NFAⅢ由NFA构造状态转换矩阵ⅣNFA→DFAⅤ根据DFA及识别规则构造词法分析程序254.3.4LEX的实现

经LEX编译后得到词法分析程序由两部分组成：

一张状态转换矩阵表(DFA)和一个控制程序可看作是如下形式的有限自动机

P1|P2|…|Pn

当输入的单词与Pj匹配时，就进行相应的动作(返回Ai所定义的单词属性)Pi例P66264.3.5LEX的使用方式

单独使用：开发编辑器、模式识别等

与YACC等结合使用：生成扫描器和语法分析器27284.4本章小结1．词法分析程序的工作是从输入源代码中取得单词，以作为语法分析的输入2．一般单词被分成多种类型，并用二元式表示一个单词的内部形式3．词法分析程序的设计采用程序流程图和状态转换图4．LEX是一种自动生成工具，可以实现词法分析程序的自动生成29总结

本章我们学习了词法分析的基本任务、词法分析程序的设计与实现、词法分析程序的自动生成等内容。

下一章将学习编译过程的第二步----语法分析方法（自顶向下）。THANKSTHANKS新工科建设·计算机类系列教材

免费提供编译原理316目录第一章

概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

并行编译技术325语法分析

----自顶向下分析方法学习目标自上而下语法分析的基本思想自上而下语法分析面临的问题及解决方法消除左递归的方法First集、Follow集、Select集的求法LL（1）分析方法递归子程序分析方法33语法分析是编译过程的核心部分。

-----在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析自顶向下如LL(k)，递归下降分析法等自底向上如LR(K)，简单优先分析法等34

目录5.1自顶向下语法分析技术5.2LL(K)语法分析方法5.3递归下降语法分析方法5.4本章小结355.1自顶向下语法分析技术

从文法的开始符号出发,向下推导,看能否推出待分析的符号串,如果能推出,说明该符号串是符合语言语法的句子,否则不是句子。361231.从文法的开始符号出发2.

向下推导3.推导出句子

5.1.1自顶向下语法分析思想例:文法G[S]:SABAab

Bcd|cBd判断abccdd是否是句子。(1)自顶向下构造语法树SABabcBdcd(2)推导SABAcBd

Accdd

abccdd375.1.2三种终结符号集1.First集(首符号集)

定义:文法G[S]:字汇表V,则符号串β的首符号集

First(β)={a|βay,a∈VT,y∈V*}特别,若β=ε,则First(β)=Φ*例：G[S]：SApSBqAa|cAFirst(dB)={d}Bb|dBFirst(Ap)={a,c}First(Bq)={b,d}38例:G[E]:EE+T|TTT*F|FF(E)|i则:First(E+T)={(,i}First(T)={(,i}First(T*F)={(,i}First(F)={(,i}First((E))={(}First(i)={i}392.Follow集(向前看集)定义:文法G[S],非终结符号U的向前看集

Follow(U)={a|S

…Ua…,a∈VTU{#}}

特别,当a=ε时,视U后面的符号为”#”****∵E

E,E

E+T,E

(E)∴Follow(E)={#,+,)}Follow(T)={#,+,*,)}Follow(F)={#,+,*,)}403.Select集(可选集)定义:文法G[S],有规则A

β

则该规则的可选集为:41例:对于G[E]select(EE+T)=First(E+T)={(,i}select(ET)=First(T)={(,i}select(TT*F)=First(T*F)={(,i}select(TF)=First(F)={(,i}select(F(E))=First((E))={(}select(Fi)=First(i)={i}42例:G[S]:SaBc|bBBbB|d|εSelect(Bε)=Follow(B)={#,c}435.1.3自顶向下语法分析难点1.左递归问题例:G[S]:

SSa|b

分析baaSS

S

S

S

SbSaSaSaSaSa

bSaSaSab…44分析时可能出现:

(1)回溯

(2)死循环,在没有对当前输入符号匹配就进入处理S的过程，无法确定什么时候才用Sb替换,

造成死循环.解决方法:

文法的实用限制(算法6)消除左递归扩充的BNF表示法452.回溯问题

在分析中，假定被代换的最左非终结符A存在n条规则,Ax1|x2|…|xn，难以确定采用哪个规则，若从x1到xn逐个来试,则效率太低。A的候选式:x1,x2,…xn

在自顶向下分析过程中，对候选式的选择可根据当前输入符号来决定.46首先:对每条规则A

β,

First(β)β≠ε求Select(Aβ)=

Follow(A)β=ε当β≠ε时,对于当前输入符号a,若

a∈First(β)则可选Aβ进行推导,但A有n个候选式,∴分两种情况.47

(1)首符号不同例:G[A]:AaB|bA

BbaA|c

{First(aB)={a}}∩{First(bA)={b}}=Φ{First(baA)={b}}∩{First(c)={c}}=Φ

分析符号串bbabaacAbA

bbA

bbaB

bbabaA

bbabaaB

bbabaacFirst(xi)∩First(xj)=Φ(i≠j)若a∈First(xk),则选用Axk来推导48

(2)首符号相同即对于A

αx1|αx2...|αxn改为A

α(x1|x2...|xn)进一步A

αBBx1|x2...|xn

First(xi)∩First(xj)≠Φ(i≠j)解决方法:“左提左因子”修改文法49例:U

αx1|αx2|x3|…|xn

且First(xi)∩First(xj)=Φ,(i,j≥3,i≠j)

First(xi)≠α,(i=3,4,…n)

采用

UαV|x3|…|xn

Vx1|x250例:G[S]:SifBthenS1elseS2|ifBthenS1

改为:

SifBthenS1TTelseS2|ε515.1.4确定的自顶向下语法分析思想52不确定的自顶向下分析思想例:G[S]:SxAy

Aab|a

分析xay是否句子

SxAy

a(3)SxAy

(1)SxAy

ab(2)分析过程:(1)(2)(1)(3)出现回溯.53例:

G[E]:ET|EATTF|TMFF(E)|i分析符号串i+i*iA+|-M*|/54推导:E

T

F

i

T

TMF

FMF

iMF

i*F

i*i

EAT

EAF

TAF

FAF

i+i

TAT

i+T

i+TMF

i+i*i

++推导过程是一个不断试探的过程,出现回溯现象，所以又称带回溯的自顶向下分析方法(效率低，代价高)原因:推导过程中有多个侯选式可供选择.555.2LL(K)语法分析方法

LL(k)是一种确定的自顶向下分析法:扫描输入串,同时从文法的识别符号开始产生句子的最左推导,每一步推导时向前看k个符号,以确定当前应选规则.k=1,即LL(1),简单易懂,应用较多.565.2.1LL(1)语法分析思想例:

G[S]:SaBc|bB

BbB|d

对句子abbdc进行分析.

从左到右扫描abbdc,对照规则，对第一个字符a,只能用

SaBc,第二个符号b,只能用BbB

SaB

cbB

bB

d

由此,LL(1)的基本思想就是根据输入串的当前符号唯一确定所选规则进行推导.

abbBcabbdcSaBc

abBc575.2.2LL(1)语法分析方法的逻辑结构a1a2a3…ai…am#输入串

控制程序分析表分析器x1x2….xn#分析栈输入串a1a2a3…am#,以定界符”#”作为结尾分析表:M[A,a](A为栈中元素,a为输入字符585.2.3LL(1)语法分析方法1.LL(1)文法

对于文法G[S],其每个非终结符的不同规则具有不相交的select集.即对于Ux1|x2|…|xn,有select(Uxi)∩select(Uxj)=Φ,(i≠j)592.LL(1)语法分析表的生成LL(1)分析过程当前句型的右端部分x1x2…xm#(xi∈V)待分析串的右端部分y1y2…yn#(yi∈VT)

x1x2…xm#605.2.3LL(1)分析方法分几种情况:1)当x1∈VN，由y1选择相应规则替换x12)当x1∈VT,若x1=y1≠#,则说明x1与y1匹配,分别删去x1,y1,继续分析.

若x1≠

y1,则说明不匹配，进行出错处理3)若x1=y1=#,说明全部匹配,分析成功.LL(1)分析程序见P77--78615.2.3LL(1)分析方法例:G[A]:AaBc

BbB|eB|d

分析abbdc#设计文法的分析表:

abcdeAAaBcBBbBBdBeB625.2.3LL(1)分析方法分析栈输入符号产生式匹配删除#A abbdc##cBa abbdc# AaBc#cB bbdc#a#cBb bbdc# BbB#cB bdc#b#cBb bdc# BbB#cB dc#b#cd dc# Bd#c c#d# #c63(1)LL(1)分析器工作过程(2)LL(1)语法分析表的构造

LL(1)分析表反映分析栈中元素与输入串中元素的匹配关系.记M[A,a]几个约定:

C:继续读入下一字符

R:重读当前字符RE(β):用β的逆串替换栈顶符号.64构造LL(1)分析表的算法如下:65

66例:G’[A]:AaBc

BbB|eB|d先求各规则的select集Select(AaBc)={a}Select(BbB)={b}Select(BeB)={e}Select(Bd)={d}且c不出现在任何规则右部的首部.67构造LL(1)分析表:abcde#ABc#cB/CB/Cε/CB/Cε/Csucc68分析abbedc的过程分析栈余留输入串 动作#Aabbedc# cB/C#cBbbedc#B/C#cBbedc# B/C#cBedc# B/C#cBdc# ε/C

#cc# ε/C

## succ69例5－6表达式文法G[E]：E→EAT|TT→TMF|FF→(E)|iA→+|-M→*|/消除左递归求select集构造分析表分析符号串70例5－61.消除左递归71例5－62.求select集723.构造分析表734.分析符号串74例文法G[S]S

abB

A

SC|BAA|εVN={S,A,B,C}B

AbAVT={a,b,c}C

B|c75判断此文法是不是LL(1)文法:Select(SabB)={a}Select(ASC)={a}Select(ABAA)={a,b}Select(Aε)={a,b,#}Select(CB)={a,b}Select(Cc)={c}Selcet(BAbA)={a,b}

∴不是LL(1)文法。构造出的分析表含有多重定义。∩=Φ∩≠Φ76注：有些不是LL(1)文法的文法，经过修改（如左提左因子，消除左递归等）可化为LL(1)文法，但并不是所有的非LL(1)文法都能改造为LL(1)文法。77例对于文法G[Z]:

ZAU|BR

AaAU|b

BaBR|b

Uc

Rd

First(AU)∩First(BR)={a,b}≠Φ

所以，不是一个LL(1)文法

785.3递归下降语法分析方法5.3.1递归下降语法分析方法的实现思想是一种确定的自顶向下分析法。又称递归子程序分析法。思想：对文法中每个非终结符（代表语法成分）编写一个子程序（或递归过程），用来识别它所表示的语法范畴。有些语言（如PASCAL)的语法成分都是递归定义的（不含左递归），将其用递归过程来表示，即构成了递归下降语法分析方法。795.3.2递归子程序及其性质80

为了保证子程序的正确返回，必须保护返回地址。81825.3.2递归子程序及其性质5.3.3递归下降语法分析方法例：赋值语句

SV:=E变量

Vi|i(E)表达式

EE+T|E-T|T项

TT*F|T/F|F因子

FF↑P|P初等量

P(E)|i83消除左递归：

SV:=EVi|i(E)ET{(+|-)T}TF{(*|/)F}FP{↑P}P(E)|i递归子程序如图5.8－5.1384赋值语句处理流程图85

变量处理流程图86

表达式处理流程图87

项处理流程图88

因子处理流程图89

初等量处理流程图90915.4本章小结1．自顶向下语法分析方法是寻找输入串的最左推导，从而分析出该输入串的语法结构2．自顶向下语法分析方法需要解决文法的二义性问题、左递归问题、回溯问题3．LL(1)文法是一种确定的自顶向下语法分析方法4．递归下降语法分析方法同样是一种确定的自顶向下分析方法92总结

本章我们学习了自顶向下分析技术、不确定的自顶向下分析技术、确定的自顶向下分析技术、三种终结符号集、LL(1)分析方法和递归下降分析方法等内容。

下一章将学习自底向上的语法分析方法。THANKS93THANKS新工科建设·计算机类系列教材

免费提供编译原理946目录第一章引言第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造95自下而上语法分析的基本思想自下而上语法分析面临的问题及解决方法简单优先分析法算符优先分析法LR(K)四种语法分析方法966语法分析

----自底向上分析方法学习目标

目录6.1自底向上语法分析技术6.2自底向上优先分析方法6.3LR(K)分析方法6.4本章小结976.1自底向上语法分析技术6.1.1自底向上语法分析思想从输入串开始，逐步进行“归约”,直到归约到文法的开始符号。又称为“移进-归约”分析法。

分析过程：采用一个先进后出的分析栈，分析开始后，将输入串自左向右逐个移进分析栈，边移入边分析，一旦栈顶形成某个句型的句柄时，就进行归约，归约后的非终结符入栈，继续分析,直到输入串处理完毕，同时栈中只有文法的开始符号。98例6.1G[S]：S→aAbBA→c|AcB→d|dB分析符号串accbdd99表6.1自底向上分析法对输入串accbdd的分析过程

步骤分析栈句柄输入符号串动作1#accbdd#移进2#a

ccbdd#移进3#ac

cbdd#移进4#aAc

cbdd#归约（A→c）5#aAc

bdd#移进6#aAAc

bdd#归约（A→Ac）7#aAb

dd#移进8#aAbd

d#移进9#aAbdd#移进10#aAbdBd#归约（B→d）11#aAbBdB#归约（B→dB）12#S

aAbB#归约（S→aAbB）100分析符号串#accbdd#分析过程见表6.1,共用了12步,其中”移进7步”,归约5步。规范归约序列:accbddaAcbddaAbddaAbdBaAbBS

构造语法树过程见图

∆∆∆∆∆1.如何确定句柄例：表6.1中第5步栈内符号aAc

栈顶c或Ac可选规则A→c或A→Ac，选择了A→Ac，

同样，在第8步栈顶是d，可用B→d归约但没用，而

是在第9步用A→d归约。∵第5步c不是句柄，第8步d也不是句柄。∴

但不可能依靠事先给出句子的最右推导或语法树来寻找

句柄。6.1.2自底向上分析难点102

2.文法中出现两条以上规则右部相同的规则例：A→eB→eC→e

如何确定选择哪条规则？例：G[S]：S→AB|cA→bA|aB→aSb|c

分析bbaacb

S→cB→cSABbAaSbbAca103

步骤

分析栈

规则

句柄

余留输入串

1

#bbaacb#

2

#bbaacb#

3

#bbaacb#

4

#bbaacb#

5

#bbAAaaacb#

6

#bAAbAbAacb#

7

#AAbAbAacb#

8

#Aacb#

9

#Aacb#

10

#AaSSccb#

11

#AaSb#

12

#ABBaSbaSb#

13

#SSABAB#104

在第8步，a出现在栈顶，能否用A→a归约？

在第9步，c出现在栈顶，能否用B→c归约？1056.2自底向上优先分析方法优先分析方法:简单优先分析方法算符优先分析方法6.2.1简单优先分析方法1061.简单优先关系

文法中两个符号之间的三种优先关系:"=，>，<"。

注：“=、<、>”不同于数学中的“=、>、<”，A>B并不一定意味着B<A，A=B也并不代表B=A。107A=B表示A和B优先关系相等A>B表示A的优先性高于BA<B表示A的优先性低于B三种优先关系的定义：

设A、B是文法G中任意两个符号108++2、简单优先文法

定义6.1：文法G中①任意符号之间至多存在一种优先关系。②任意产生式右部均不相同，则称G为简单优先文法。

例：文法G[S]：S→bAb

A→(B|a

B→Aa)109110（1）求=关系由S→bAb,A→(B,B→Aa)

可得b=A,A=b,(=B,A=a,a=)（2）求<关系由S→bAb,且A(B,Aa得b<(,b<a

由A→(B，且B(B…,Ba…,BA…

得(<(,(<a,(<A（3）求>关系,由S→bAb,且A…),A…B,A…a

得)>b，B>b，a>b

由B→Aa）且A…),Aa,A…B

得)>a,a>a,B>a+++++++++++

上述关系也可用语法树结构表示SSSSbAbbAbbAbbAb

（Ba（B（BAa）Aa）

（BaAa）

B>ba>b)>a,B>a,a>ab<(b<ab<(,(<(,(<A（<a111把文法符号之间的关系用矩阵表示

——优先关系矩阵SbA（Ba

）#S>b=<<>A==(<<=<B>>a>>=)>>#<<=112113

说明:

①文法符号相互之间的优先关系是唯一的。共有四种情况“=、<、>、空”，其中“空”表示两符号之间无相邻关系。

②“#”定界符，“#”<所有符号，所有符号>“#”，当然仅对与“#”有相邻关系的文法符号而言。#S##bAb#.114

例6.2已知文法G[A]：

A→aAb|cd|e试判断该文法是否是简单优先文法。首先，求=、<、>关系.115

.

Aabcde#A

=

a=<

<

<b

>

>c

=d

>

>e

>

>#<<<=例6.2文法的优先关系矩阵3、简单优先分析算法①根据文法构造优先关系矩阵。②设有符号栈S，将输入符号串“#…#”依次压入S栈，同时检查相邻符号与的优先关系，一旦>

出现时，停止入栈。③当前栈顶符号为，从开始向左在栈中查找符号，直到找到<

为止。116④符号串…即为当前句型的句柄，查找规则右部…

的产生式，若找到则将…

归约为左部，若找不到则为出错。⑤重复②~④步，直到分析完所有输入符号，栈中只剩文法的开始符号，则分析成功，否则分析失败。1173、简单优先分析算法例：分析#aeb#步骤S栈优先关系

输入符号串

句柄

1#<aeb#2#a<eb#3#aeb#4#aAb#e5#aAb=#6#A分析成功#>aAb118>6.2.2算符优先分析法

1、简单表达式表示法中缀表示法a+b(a+b)*ca+b/c

前缀表示法+ab*+abc+a/bc（波兰式）

后缀表示法ab+ab+c*abc/+（逆波兰式）基本思想：算符优先分析法是按照终结符的优先关系确定“句柄”并进行归约。算符优先分析法：一种分析速度快，使用较多的自底向上分析方法。事实上，不是一种规范归约，适用于表达式的分析。1191.逆波兰式

无括号，形式简单

运算符次序与运算次序完全相同

逆波兰式：120波兰逻辑学家1929年发明，在编译程序出现之前，已用于算术表达式。逆波兰式易于计算机处理（仅需一个栈，自左向右扫描逆波兰式，遇运算量压栈，遇运算符从栈顶取一个或两个运算量进行运算，运算结果压栈，继续扫描…，直到整个表达式处理完毕）。在编译程序中逆波兰式可作为一种中间语言代码。2.逆波兰式的生成算术运算遵守一定的运算规则：

（，）→↑→*，/→+，-由此可得到一个运算符优先关系矩阵（见下页）。逆波兰表达式生成算法见图6.3关键:比较当前运算符与栈顶运算符的优先关系.当

前的高,当前进栈,栈顶的高,栈顶退栈。例：表达式(a+b）*c/d→ab+c*d/

转换过程如表6.5121运算符优先关系矩阵122关系右左

+-*/

↑（

）+>><<<<>->><<<<>*>>>><<>/>>>><<>↑>>>>><>

（<<<<<<=

）>>>>>>123表达式(a+b）*c/d→ab+c*d/124步骤输入串当前符号运算符栈输出串1(a+b)*c/d((

2a+b)*c/da(a3+b)*c/d+(+a4b)*c/db(+ab5)*c/d)(ab+6*c/d)

ab+7*c/d**ab+8c/dc*ab+c9/d//ab+c*10dd/ab+c*d11

ab+c*d/3.算符优先文法定义6.3:算符优先关系=、<、>a、b∈VT，A、B、C∈VN

①a=b，当且仅当文法中含有形如“A→…ab…”或“A→…aBb…”的产生式。定义6.2：算符文法-文法G中，A、B∈VN,若G中不会有形如“V→…AB…”的产生式。125例：G[E]：E→E+E|E*E|(E)|i算符文法②a<b，当且仅当文法中含有形如“A→…aB…”的产生式，其中Bb…或BCb…。③a>b，当且仅当文法中含有形如“A→…Bb…”的产生式，其中B…a或B…aC。++++126127定义算符优先文法例G[E]:E→E+E|E*E|(E)|i(不是一个算符优先文法)E→E+EE→E*EEE*EEE+E+<*+>*定义6.4：算符优先文法-文法G是一个不含有空产生式的算符文法，且G中的两个终结符之间，至多只有一种优先关系。4.算符优先关系矩阵的构造方法⑴首先对文法G的每个非终结符A构造两个集合。FIRSTVT(A)={a|Aa…或ABa…，其中a∈,B∈}LASTVT(A)={a|A…a或A…aB，其中a∈,B∈}⑵确定终结符对之间的优先关系。++++128＝关系，逐个查看产生式，由A→…ab…或A→…aBb…，找到a＝b。1<关系，查找文法中形“P→…aA…”的产生式，则对任何b∈FIRSTVT(A)，有a<b。2>关系，查找文法中形如“P→…Ab…”的产生式，则对任何a∈LASTVT(A)，有a>b。3129例:G[E]E→E+T|TT→T*F|FF→(E)|i计算FIRSTVT、LASTVT集FIRSTVT(E)={(,i,+,*}FIRSTVT(T)={(,i,*}FIRSTVT(F)={(,i}LASTVT(E)={+,*,),i}LASTVT(T)={*,),i}LASTVT(F)={),i}=关系

由F→(E)得(=)13012<关系由E→E+T+<FIRSTVT(T)即+<{*,(,i}由T→T*F*<FIRSTVT(F)即*<{(,i}由F→(E)(<FIRSTVT(E)即(<{+,*,(,i}3>关系由E→E+TLASTVT(E)>+即{+,*,),i}>+由T→T*FLASTVT(T)>*即{*,),i}>*由F→(E)LASTVT(E)>)即{+,*,),i}>)4131G[E]的算符优先关系矩阵

+*()i#+><<><>*>><><>(<<<=<)>>>>i>>>>#<<<<=1325.算符优先分析算法

算符优先分析法是一种自底向上的方法，但不是规范归约，即归约时不一定是句柄。

定义：素短语——至少包含一个终结符，且除自身不含其它素短语的短语。

最左素短语——句型最左边的素短语。E

E+T

E+TFTT*Fi例：句型：T+T*F+i

短语：T,T*F,iT+T*F,T+T*F+i

素短语：T*F,i

最左素短语：T*F133

#---定界符，终结符，可有可无的非终结符

最左素短语

…

满足：

<

=,=,…,=>

算符优先分析类似于简单优先分析法，只是归

约的不是句柄，而是最左素短语。##…134句型的一般形式

步骤

当前句型

优先关系最左素短语归约符号12345.#T+T*F+i# #<+,+<*,*>+T*F T#T+T+i# #<+,+>+ T+T E#E+i# #<+,+<i,i># i F#E+F# #<+,+># E+F E#E#135表6.7T+T*F+i的分析过程设：…最左素短语中包含，非终结符。

这种分析方法起主导作用的是终结符之间的优先关系，非终结符的名字无所谓，且单个非终结符也不是素短语。所以，归约过程得到一个语法树的树架。

NN+NN+NiN*N

算符优先分析法的流程图见下图（图6.6）

136表6.8句子(i+i)*i的分析过程

137步骤符号栈S[i]优先关系输入符号(a)待分析串1#<(i+i)*i#2#(<i+i)*i#3#(i>+i)*i#4#(N<+i)*i#5#(N+<i)*i#6#(N+i>)*i#7#(N+N>)*i#8#(N=)*i#9#(N)>*i#10#N<*i#11#N*<i#12#N*i>#

13#N*N>#

14#N分析成功1386.优先函数

优先关系矩阵，当文法符号或终结符较多时会变得很大。解决方法：压缩矩阵，去掉空元素。

构造优先函数。定义6.6：优先函数f、g

已知文法G，由算符优先关系矩阵，若文法的每个终结符x、y满足：1）当x>y时，f(x)>g(y)2）当x<y时，f(x)<g(y)3）当x=y时，f(x)=g(y)f—内优先函数（入栈优先函数）g—外优先函数（比较优先函数）1396.优先函数

表6.9G(E

)的优先函数终结符优先函数+*()i#f351551g2461616.3LR(K)分析方法

LR(K)根据分析栈的当前内容以及向前查看k个符号来决定是否移进或归约。141知识回顾自底向上语法分析思想和分析难点简单优先和算符优先分析方法6.3LR(K)分析方法

LR(K)是一种有效的自底向上语法分析方法。它的适应范围广，分析速度快，且能准确及时地发现语法错误，所以是当前最一般的语法分析方法。

LR(K):根据分析栈的当前内容以及向前查看k个符号来决定是否移进或归约。142

LR(0)是基础，但分析能力低，局限性大

SLR(1)“简单LR”实现容易，能力较强，不适合有些文法

LR(1)分析能力最强，适用于大多数文法，但工作量大

LALR(1)能力介于SLR(1)与LR(1)之间，空间节省6.3LR(K)分析方法1431234LR语法分析方法类型6.3.1LR分析思想及逻辑结构1、LR分析思想及逻辑结构基本思想：扫描输入串，进行自底向上分析，在分析每一步记住当前已移进和归约的文法符号，同时向前查看k个输入符号，由此确定栈顶是否出现句柄，从而进行归约或移进，直至分析完毕。144

→输入串

#…

…#

分析表总控程序控制机构……#下推分析栈145LR分析法的逻辑结构

2.

LR分析表组成

两部分：ACTION—分析动作表

GOTO—状态转换表

~为分析器的状态，~为文法终结符和定界

符，~为文法符号

ACTION表：

输入符号状态…ACTION[，]

………ACTION[，]…ACTION[，]146GOTO表:

分析动作表中，ACTION[，]规定栈顶状态为，输入符号为时，所执行的动作，有以下四种：

文法符号状态…GOTO[，]……GOTO[，]…GOTO[，]1472.

LR分析表组成移进（S），把（Si,aj）的下一个状态移入状态栈，输入符号移入文法符号栈，继续扫描下个符号。归约（r），当栈顶形成句柄时，按相应的产生式进行归约，若产生式右端长度为n，则从状态栈和文法符号栈的栈顶退n个符号，再将归约后的文法符号移入符号栈，新的状态进入状态栈。接受（acc），当输入串分析结束（只剩下“#”）时，文法符号栈中只剩下文法的开始符号时，分析成功，终止分析。报错（error），当状态栈顶为某一状态下出现不该遇到的文法符号时，说明输入串有错，报告出错信息。状态转换表中，GOTO[Si，xj]规定了当栈顶状态为Si，文法符号为Sj时,xj应转向的下一个状态(用j表示）。148231413、LR分析过程例6.3G[A]：A→B，AA→BB→aB→bG[A]的LR分析表状态ab,#AB

ACTIONGOTOS0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S426S6r1149对符号串＃a，b＃的分析过程

步骤状态栈符号栈余留符号产生式ACTION/GOTO12345678S0 # a,b# S3S0S3 #a ,b# γ32S0S2 #B ,b#B→a S5S0S2S5 #B, b# S4S0S2S5S4#B,b # γ42S0S2S5S2#B,B #B→b γ26S0S2S5S6#B,A #A→B γ11S0S1 #A #A→B,A acc1506.3.2LR(0)的分析方法

LR(k)中k=0说明无须向前查看符号.LR(0)是其它LR分析法的基础.

例6.1

在分析的第5步栈中符号为#aAc时,

用A→Ac归约而没有A→c.

实际上与栈中符号串的前缀有关.151表6.1自底向上分析法对输入串accbdd的分析过程

步骤分析栈句柄输入符号串动作1#accbdd#移进2#a

ccbdd#移进3#ac

cbdd#移进4#aAc

cbdd#归约（A→c）5#aAc

bdd#移进6#aAAc

bdd#归约（A→Ac）7#aAb

dd#移进8#aAbd

d#移进9#aAbdd#移进10#aAbdBd#归约（B→d）11#aAbBdB#归约（B→dB）12#S

aAbB#归约（S→aAbB）152分析符号串#accbdd#分析过程见表6.1,共用了12步,其中”移进7步”,归约5步。规范归约序列:accbddaAcbddaAbddaAbdBaAbBS

构造语法树过程见图

∆∆∆∆∆问题

154ØLR分析过程中，需要确定当前句型的句柄进行归约，如何在当前句型中寻找句柄？解决：直接寻找句柄有困难，可以迂回寻找含有句柄的字符串总结与思考LR方法的分析思想与分析过程LR分析方法与优先方法的区别延展学习：DonaldErvinKnuth生平以及对计算机所作出的贡献基础软件领域中编译技术发展现状1.规范前缀和可归前缀定义6.7:已知文法G[S],若有规范推导S

αβ,β∈

则称α为规范前缀,又称活前缀.(规范前缀中不含句柄之后的符号)若α是句柄的活前缀,且句柄处在α的最右端,则称α是可