首页 文章 Go语言基础 编译原理 LR语法
0
0
0
33

编译原理 LR语法

基础语法 语法 原理

复习

我们想要通过自底向上文法来进行语法分析,就要使用移入-归约法不断将右串归约成左侧的非终结符最后回到开始字符。在这个过程中,遇到的问题有:何时移入?何时归约?归约时哪部分归约?归约成哪部分?

LR(k)语法

  • L表示从左往右扫描,R表示反向构造出一个最右推导,k表示向前看k个字符,缺省为1。

  • 一个输入:字符串w;一个输出:分析完成的树;一个栈;一个驱动程序;一个语法分析表。分析表包括Action部分和Goto部分。

  • 每次实现,先将初始状态S0压入栈,将串w$作为输入缓冲区内容。接着调用驱动程序。

LR表结构

两部分构成,一个语法分析动作函数Action,一个转换函数Goto。

1.Action函数

ACTION[i, a],其中i为状态,a为输入符号 (或者结束符$),有以下操作:
(1) sj:移入状态j进状态栈,将符号a移入符号栈;
(2) rj:使用第j个产生式A -> β进行归约,将状态栈的 |β| 个状态出栈,并且将新的状态移入栈 (Goto函数求新状态);将符号栈的 |β| 个符号出栈,将A移入符号栈;
(3) 接受 (acc);
(4) 报错 (error);

2.Goto函数
如果GOTO[Ii, A] = Ij, 那么GOTO把状态I和一个非终结符号A映射到状态j。

基于LR分析表的自底向下分析

分析程序如下:

对于下面的文法:
(1)E -> E + T (2) E -> T
(3) T -> T * F (4) T ->F
(5) F -> ( E ) (6) F -> id
给出了LR语法分析表:

执行id * id + id的分析。

流程:

1.将初始状态0入栈,输入串加$如缓冲区。
2.每次比较栈顶元素和输入缓冲区第一个字符,查表,sj表示移入,并且将状态j入栈。rj表示归约,按照表达式j进行归约。然后弹出表达式长度个字符,得到新的栈顶元素t,再查表,将Goto[t,A]的状态入栈。
3.重复以上操作,如果出现查表为空,则转错误处理。如果查表得acc,则成功完成。

构造SLR分析表(SLR:简单LR技术)

1、从文法构造识别可行前缀的DFA
2、从以上DFA构造分析表
在构造表分析表前,先让我们了解一些基本概念。

可行前缀

定义:一个可行前缀是一个最右句型的前缀,并且它没有越过该最右句型的最右句柄的右端。
举例:S=>*rm γAw =>*rm γBw ,这里句柄是B,因此可行前缀包括γB的所有前缀(包括空串e和γB本身),但不能是γBw。

定义:文法的一个产生式G加上其右部某一位置的一个点,这个点表示了分析过程中的状态。
举例:产生式A->XYZ 产生的四个项:
A->·XYZ
A->X·YZ
A->XY·Z
A->XYZ·
以第二个项为例,其表示已经接收了一个可以由X推导的串,如果希望能归约,那么接下来要识别一个能够由YZ推导的串。
(A->空串e 只产生一个项A->·)

增广文法(拓广文法)

定义:如果G是一个以S为开始符号的文法, 那么G的拓广文法G’就是在G中加上新开始符号S’和产生式S’ -> S而得到的文法。
简言之,就是给文法添加一条文法:S’->S,其中S是原文法的开始符号。

项集闭包的求法

如果I是文法G的一个项集,那么CLOSURE(I)就是根据下面的两个规则从I构造得到的项集::

  1. 一开始,将I中的各个项加入到CLOSURE(I)中。
  2. 如果A -> α•Bβ在CLOSURE(I)中,B->γ是一个产生式,并且B->•γ不在CLOSURE(I)中,就将这个项加入其中。不断应用这个规则,直至没有新项添加。(大概意思就是如果闭包里如果没有希望识别γ的状态,就添加这个状态)

OK,准备工作完成,接下来开始实例构造。

给定文法
• E -> E + T | T
• T -> T * F | F
• F -> ( E ) | id

构造识别可行前缀的DFA。

1)先改写成增广文法:

• E ’ -> E
• E -> E + T | T
• T -> T * F | F
• F -> ( E ) | id

2)下面求项集的闭包。

I0=CLOSURE({E ’ -> •E})={E ’ -> •E, E -> •E + T, E -> •T, T -> •T * F, T -> •F, F -> •( E ), F -> •id}
//第一条是固定的,都是求增广出的文法的闭包,而文法E ’ -> •E又可以根据项集闭包的求法,推出之后的几条。

I1 = GO(I0, E) = CLOSURE({E’ ->E•, E -> E• + T}) = {E’ ->E•, E -> E• + T}
//第二步,对I0中的项,先加入自己,再识别E后产生的新项的闭包。

I2 = GO(I0, T) = CLOSURE({E -> T•, T ->T•*F}) = {E -> T•, T ->T•*F}

I3 = GO(I0, F) = CLOSURE({T -> F•}) = {T -> F•}

I4 = GO(I0, ( ) = CLOSURE({F -> ( •E )}) = {F -> ( •E ), E -> •E + T, E -> •T, T -> •T * F, T -> •F, F -> •( E ), F -> •id}
//这一步,除了加入自己,又根据闭包的规则加入了很多别的项

I5 = GO(I0, id) = CLOSURE({F -> id•}) = {F -> id•}

GO(I1, $) = accept
//接收,不另外设状态。

I6 = GO(I1, +) = CLOSURE({E -> E + •T}) = {E -> E + •T, T -> •T * F, T -> •F, F -> •( E ), F -> •id}
//I1的下一个状态求完了

I7 = GO(I2, *) = CLOSURE({T ->T*•F}) = {T ->T*•F, F -> •( E ), F -> •id}

I8 = GO(I4, E) = CLOSURE({F -> ( E•), E -> E •+ T} = {F -> ( E•), E -> E •+ T}

I9 = GO(I4, T) = CLOSURE({E -> T•, T -> T •* F}与I2一致,故不用新设状态。I9继续为下面的状态所用。)

I9 = GO(I6, T) = CLOSURE({E -> E + T•, T -> T •* F}) = {E -> E + T•, T -> T •* F}

I10 = GO(I7, F) = CLOSURE({T ->T*F•}) = {T ->T*F•}

I11 = GO(I8, )) = CLOSURE({F -> ( E)•}) = {F -> ( E)•}
//至此,没有更多新状态生成,并且所有状态都编号了。
//GO函数相当于DFA的边,理论上每构造一个新状态Ii,只要某终结符x存在于它的FOLLOW集中,即下一步有可能会出现,那么必然存在GO(Ii, x),这里没有全部列出来只是因为去掉了重复的状态。
//所有高亮显示的为核心项,包括初始项E ’ -> •E以及所有•不在最左端的项;除了E’ -> •E之外所有的点在最左端的所有项为非核心项。

3)画NFA图:

因为是手工构建,所以可以跳过写闭包的部分直接画图。

4)构建分析表

• 使用下面规则构造状态i的goto函数:对所有的非终结符A,如果goto(Ii, A) = Ij, 那么goto[i, A] = j。
理解:简要来说,就是根据DFA进行归约。

• 使用下面的规则构造状态i的action函数:
(1)如果A -> α •aβ在Ii中,并且goto(Ii, a) = Ij,那么置action[i, a]为sj
(2)如果A -> α•在Ii中,那么对FOLLOW(A)中的所有a,置action[i, a]为rj,j是产生式 A -> a的编号。
(3)如果S’ -> S•在Ii中,那么置action[ i, $ ]为接受acc。
(4)不能由上面两步定义的条目都置为error。
理解:先画好表格框架,再对于状态Ii的许多的项,寻找•右侧带终结符的项,再查图,DFA接收该终结符后转移到的状态Ij,对应表格就填sj。仍然对于这些项,寻找已经接收到了最后一个了(即•在最右端)的项,把这些项的左侧非终结符的FOLLOW集求出来,将里面的元素全标记成要归约的。accept比较简单。FOLLOW集最好一开始就先求一下,具体求法见《编译原理 LL(1)文法》。

小结

一些值得思考的问题:
1)为什么要对文法G进行拓广?不拓广会怎么样?
拓广后,归约成开始符号一定是接受状态。不拓广,归约成开始符号也不一定是接受状态,有可能是某些文法中间就包括了开始符号。不拓广,可能会在多处出现acc。

2)为什么称为LR(0)自动机?
0指构造自动机的时候,没有假设下一个输入符号是什么。

3)为什么称LR(0)自动机为识别文法活前缀 (可行前缀)的DFA?
功能: 从开始状态到接受状态中间的那些符号, 构成一个活前缀。

4)SLR指什么?
简单的LR语法分析。

5)SLR(1)文法指什么?
根据分析表,自底向上构造语法分析的时候,只需要看一个lookahead符号 。SLR(1) 简称为SLR。

6)LR(0)文法和SLR(1)文法的关系?
LR(0)文法是SLR(1)文法的子集。LR(0)文法不能解决移进-归约冲突和归约-归约冲突。所以如果存在以上两种冲突,LR(0)文法不能处理。SLR(1)文法能解决归约-归约冲突但不能解决移进-归约冲突,所以预测分析表的一个窗口可能会出现两个入口(移进或归约)。但他们构造预测分析表的流程是一样的。

到此这篇关于“编译原理 LR语法”的文章就介绍到这了,更多文章或继续浏览下面的相关文章,希望大家以后多多支持Go语言编程网!

相关文章

创建博客

开始创作
写作能提升自己能力,也能为他人分享知识。

在线教程

查看更多
  • Go入门指南

    Go入门指南

  • Go语言高级编程

    Go语言高级编程

  • Go Web 编程

    Go Web 编程

  • GO专家编程

    GO专家编程

  • Go语言四十二章经

    Go语言四十二章经

  • 数据结构和算法(Golang实现)

    数据结构和算法(Golang实现)

Go语言编程网

微信扫码关注订阅号


博客 资讯 教程 我的