第5章

语法分析(2)——LR(k)分 析方法

5.1 LR分析方法概述

LR分析法是一类分析方法的简称，通常记为LR(k) 分析法。 L是指从左至右方式扫描输入串；

R是指最右推导(规范推导)的逆过程； K是指每次根据当前输入符号最多向前查看K个符号就可

以确定下一步动作；

本章重点介绍LR(0) 分析表的构造算法及相关知识。

5.1 LR分析方法概述5.1.1 LR分析器1.一个LR(k)分析器主要由三部分组成： 分析栈(含状态栈和符号栈) 控制程序(也称为驱动程序) 分析表(分析动作表和状态转换表)

2.分析表： LR分析器的核心“分析表”由分析动作表(ACTION 表)和goto函数表(GOTO表)两部分组成，它们 都是用二维 数组表示的。 ACTION表指明了分析程序采取的动作：

移进：句柄尚未形成，将符号移进栈。 归约：句柄已经形成，用对应的产生式进行归约。 接收：表示整个分析工作完毕，输入串合法。 报错：出错处理。 GOTO[s,A]=后继状态(决定当前状态的下一状态)

3.LR分析过程1)LR分析方法的主要思想：

严格地进行最左归约(识别句柄并归约它)。 将识别句柄的过程划分为由若干状态控制，每个状 态控制识别出句柄的一个符号。 符号栈：存放已识别的部分。

状态栈：存放状态。由一个总控程序来控制整个识别过程。

2)LR分析步骤

3)具体分析过程实例

5.2 LR(0)分析法5.2.1 LR(0)项目集规范族和LR(0)分析表的构造 相关概念1:活前缀与可规前缀 自下而上的移进——规约分析，是对句柄进行规范规

约，它是规范推导的逆过程，规范推导出来的句型是规范句型。一个符号串的前缀是指该串的任意首部，包括 。 定义：规范句型的一个前缀，如果不含句柄右边的任

何符号，则称它是规范句型的一个活前缀，包含句柄的活前缀称为可规前缀。

1. 文法G的拓广文法

给定文法G,S是其开始符号，G的拓广文法是G ,其开始符号为S ,区别在于后者仅增加一个产

生式S S,把它作为第0个产生式添加到文法G中。例如：文法G[A]: A (A) , A a 则该文法的拓广文法G [A ]: A A, A (A),A a

2.文法G的LR(0)项目定义：在文法G的每一个产生式右部的某个位置添加一个 “·”,点号左边表示该产生式的右部在符号栈的栈顶已经出现的 部分，点号右边表示如果要用该产生式进行规约，还应该出现 的部分。 一般产生式A β对应的项目个数为| β |+1,特别地，产生式 A ε的项目个数为1,即A .

A · 希望看到从输入串中与AB对应的符号串。 AB A A· 已识别出由A对应的输入符号，并希望看到与B对 B 应的输入串

。 A AB·与AB对应的输入串已经识别出来，可以进行规约。

相关概念2:项目的分类显然不同的项目反映了分析过程中栈顶的不同情况，因 此我们可以根据它们的不同作用，将一个文法的全部L(0)项 目进行分类： 1)对于形如A α· 项目，因为它表示右部符号串α(可为ε)已 经出现在栈顶，此时相应的动作应该是按此产生式进行归约， 故将此项目称为归约项目。 2)项目S S·仅用于分析过程中最后一次归约，所以称为接 受项目。 3)对于形如A α· Xβ的项目，其中α可以为空符号串： 当X为终结符号时，相应的分析动作应该将当前的输入符 号移入栈中，我们称它为移进项目； 当X为非终结符号时，由于我们期待着从余留的输入串中 进行归约而得到X,因此此类项目为待约项目； 注： 有的书上还把S · S称为开始项目，也可称为待约项目。

例:文法G [A ]: ① A A ② A (A) ③ A a 则该文法的项目为： A . A 待约项目(也可称为开始项目) A A . 接受项目 A .(A) 移进项目 A (. A) 待约项目 A (A .) 移进项目 A (A) . 归约项目 A .a 移进项目 A a . 归约项目

3.LR(0)项目集规范族的构造 相关函数：(1)设I为项目集(即由项目组成的集合),构造I的闭包函 数CLOSURE(I)的算法如下： I中的每一基本项目都属于它； 若A · B 属于CLOSURE(I),且B 是文法中的一个产生

式，则关于非终结符B的任何形如B · 的项目也属于它； 重复上述步骤，直到它不再增大为止

。

例如： I ={A . A} 则I0=CLOSURE(I)={A . A,

A .(A), A .a }

(2) 设Ii是文法的G[S]的一个LR(0)项目集，非空符号X VT∪VN,定义Ii及X间的函数为：go(Ii, X)=CLOSURE (J) =IJ

其中J={A X· A · Ii} X 先找出Ii中所有形如A · X 的项目； 然后将它们变成A X· 放入集合J中；

再求CLOSURE

(J);

例如：设I0={A . A,A .(A), A .a },求go(I0, A)=? 分析：首先找出I0中形如“ .A ”的项目： A . A 然后变成：A A .放入J中，即J={A A . } 最后CLOSURE (J)= CLOSURE ({A A . })

={A A . }

4.LR(0)项目集规范族的构造方法要构造识别所有规范句型全部活前缀的DFA,首先要确 定DFA的状态，而每一个状态都是由若干个LR(0)项目组成 的集合(也称为项目集)。对于构成识别一个文法活前缀的 DFA的项目集( 即DFA的状态)的全体，称为这个文法的 LR(0)项目集规范族( 即DFA的所有状态) 。

对于LR(0)项目集规范族——在CLOSURE(I)和go(Ii, X) 作用下，可获得的项目集的全体C:① 令C={I0} ,其中I0=CLOSURE({开始项目，如S · S})

② 对每个Ii C和Ii中形如

“· X”的项目，若go(Ii, X)非空 且不属于C,则将go(Ii, X)之值加入C;③ 重复②直至C不再增大；

例:求文法G [A ]的LR(0)项目集规范族C : ① A A ② A (A) ③ A a 分析：初始化C={I0} I0=CLOSURE({开始项目})= CLOSURE({A . A}) ={A . A,A .(A), A .a } go(I0, A)=CLOSURE (J)= CLOSURE ({A A . }) ={A A . }= I1 go(I0, ()=CLOSURE (J)= CLOSURE ({A (. A)}) ={A (. A), A .(A), A .a }= I2 go(I0, a)=CLOSURE (J)= CLOSURE ({A a .}) ={A a .}= I3 go(I2, A)=CLOSURE (J)= CLOSURE ({A (A .)}) ={A (A .)}= I4 go(I2, ( )=CLOSURE (J)= CLOSURE ({A (.A)}) ={A (. A), A .(A), A .a }= I2 go(I2, a)=CLOSURE (J)= CLOSURE ({A a .}) ={A a .}= I3 go(I4, ))=CLOSURE (J)= CLOSURE ({A (A) .}) ={A (A) .}= I5

5.构造识别所有规范句型全部活前缀的DFA方法： 1.把文法的LR(0)项目集规范族中的每一个项目集作为DFA 的一个状态； 2.把含有开始项目的项目集作为DFA的初态； 3.每一个项目集都是DFA的终态； 4.把文法的终结符和非终结符作为DFA的字母表； 5. go(Ii, X)作为单值转换函数；

例:求文法G [A ]的LR(0)项目集规范族C : ① A A ② A (A) ③ A a 分析：I0=CLOSURE({开始项目})={A . A,A .(A), A .a } go(I0, A)= {A A . }= I1 go(I0, ()={A (. A), A .(A), A .a }= I2 go(I0, a)= {A a .}= I3 go(I2, A)={A (A .)}= I4 go(I2, ( )={A (. A), A .(A), A .a }= I2 go(I2, a)={A a .}= I3 go(I4, ))={A (A) .}= I5A . A A .(A) A .a I0 A a A a . a A I3 A A . I1

(A (. A) A .(A) A .a } I2 (

A (A .) I4

)

A (A) . I5

6.构造LR(0)分析表的算法 ①若项目A

· Ii ,且go(Ii, x)=Ij x

若x VT ,则置ACTION[i , x]= Sj

若x VN ,则置GOTO[i, x]=j。 ③若项目S S· Ik ,则置ACTION[

k , # ]=acc。

②若项目A · i,对于任何输入符号a (VT∪{#}), I

则置ACTION[i,a]=rj,即“用第j条产生式A 进行归约” (这里假定A 是G 中的第j条产生式)。④分析表中凡不能用规则①~③填入信息的元素均置上ERRO R(用空白表示)。

可以通过识别活前缀的DFA来构造LR(0)分析表

A . A A .(A) A .a I0( A (. A) A .(A) A .a } I3 (

A a

A A .

I1

A a .

I2

aA A (A .) I4 ) A (A) . I5