第5章 自下而上的语法分析LR(0)

第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

本文来源：https://www.bwwdw.com/article/5rae.html