LR(0)文法项目集规范族、DFA和分析表的构建实例_weixin_30525825的博客-程序员ITS301

技术标签: c/c++  



最近在复习编译原理,考试之前以为自己懂了,眼高手低就没去实践。结果一考试出问题了。。。。

学习就要脚踏实地,容不得半点模糊。凭着侥幸心理很危险的。以后要引以为戒啊。
特别写出这篇文章 :一来总结一下这几天的收获。二来与君共勉。


一、概念

1.概念解释

1、活前缀:不包含句柄右侧任一符号的规范句型的前缀称为该句型的活前缀。
                例如:Bab是下面那个文法的一个句型,其中b是句柄。
                那么针对这个句型的活前缀有:ε、B、Ba 和Bab
                (其实,LR分析器的工作过程实际上就是逐步产生规范句型的活前缀。
                 如果能构造出一个识别文法所有规范句型活前缀的确定有穷自动机即DFA,就能很方便的构造出LR分析表)
2、LR(0)项目:右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目
                 注意:A --> ε 只对应一个项目 A -->  .
(LR(0)项目描述了活前缀和句柄的不同识别状态)
3、ε-可达:从 S' --> .S 出发,不必再识别任何符号就可以到达 S --> .BB,就称 S --> .BB是从
                S' --> .S 出发 ε-可达的。
4、项目集闭包:用Item0表示DFA的初始状态,对应分析的开始,并期待着逐步将输入符号串
                归约为开始符号S‘。因此将S' --> .S 放到 Item0 中,意即等待归约出S,且目前尚未
                得到S的任何符号。
                Item0 = CLOSURE({S' --> .S}) = {S' --> .S,S --> .BB,B --> .aB,B --> .b}
                该项目集合中所有的项目都是从S' --> .S 出发 ε-可达的,称为{S' --> .S}的项目集闭包
              (每个项目集闭包对应着分析器的一个状态)
5、后继项目:项目 A --> αX.β   称为 A --> α.Xβ  的后继项目
6、后继项目集:假定Item0是文法G的一个LR(0)项目集,
               则称 GO(Item0,X) = CLOSURE({A --> αX.β})  为 Item0 关于X的后继项目集。
               GO为项目集的转移函数。
7、项目集规范族:项目集的全体

2.例子

文法:
S --> BB
B --> aB
B --> b

二、实现步骤

1.扩展文法

S' --> S
S --> BB
B --> aB
B --> b

2.求出项目集规范族

Item0 = CLOSURE({S' --> .S}) = {S' --> .S,S --> .BB,B --> .aB,B --> .b}
Item1 =GO(Item0,S) = CLOSURE({S' --> S.}) = {S' --> S.}
Item2 = GO(Item0,B) = CLOSURE({S --> B.B}) = {S --> B.B,B --> .aB,B --> .b}
Item3 = GO(Item0,a) = CLOSURE({B --> a.B}) = {B --> a.B,B --> .aB,B --> .b}
Item4 = GO(Item0,b) = CLOSURE({B --> b.}) = {B --> b.}
至此Item0已经遍历完,开始遍历下一个,由于Item1圆点已经到达末尾,所以跳过Item1。
Item5 = GO({Item2,B) = CLOSURE({S --> BB.}) = {S --> BB.}
由于 GO(Item2,a) 和 GO(Item2,b) 重复,所以去掉。
Item6 = GO(Item3,B) = CLOSURE({ B --> aB.}) = {B --> aB.}
由于 GO(Item3,a) 和 GO(Item3,b) 重复,所以去掉。
至此,项目集闭包不再增加,所以项目集规范族构造完毕!

3.构造DFA

方法很简单,看一下结果就懂了,在这里就不赘述了。
需要注意的是:要找到每个集合和其他集合所有的转移路径,容易遗漏!
 
 
 

4.构造LR(0)分析表(根据自己画出的DFA图,将分析表填充)

 
输入:文法G的扩展文法G'
输出:G'的LR(0)分析表(即 Action表和Goto表)
步骤:
1、本例中Item2  --B-->  Item5,则在  状态号为2的行,列名为B的格中填入状态5
(转移条件为非终结符,填充Goto表,填入状态号, 转移条件为终结符,填充Action表,
填入Sn,Sn表示移进,移进符号并且移进状态号n)
Item2  --a-->  Item3 ,则在状态号为2的行,列名为a的格填入S3。
2、对于圆点在右部最右边:
if  A --> α. ∈ Itemk (0<k<n)  & A --> α 为G的第 j 个产生式,
then for  任意 a ∈ T U {#}  do
Action[k,a]  =  Rj
(Rn表示归约,不移进符号,用第n个产生式的右部替换符号栈的X)
3、if  S' --> S.  ∈Itemk (0<k<n)    then Action[k,#] = acc.
 

转载于:https://www.cnblogs.com/standby/p/6792837.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30525825/article/details/95301556

智能推荐

使用js写一个2048_写做四月一日的四月一日的博客-程序员ITS301_2048js代码

为什么标题叫使用js写一个2048呢?因为我不会页面美化(在这里给div加外边距和内边距已经是我做页面美化的极限了)!!!!本来打算导入SemanticUI来美化页面的,结果发现SemanticUI的弹出层需要jqeruy支持。那我用原生js写不是显得很呆?那就不对页面做美化了,能看就行,消息提示也使用尊贵的alert()来完成吧。首先我们创建一个html文件,在body标签体内写我们需要的东西&lt;!DOCTYPE html&gt;&lt;html&gt; &lt;...

np.min()和np.argmin()函数用法_小菜的成长之路的博客-程序员ITS301_min和argmin

np.min()函数用于返回列表中的最小值np.argmin()函数用于返回一维列表最小值索引或多维列表展平之后的最小值索引import numpy as nplst1=[1,100,56,78,0]lst2=[[100,4,5],[3,5,7],[5,0,6]]print("lst列表中的最小值是:")print(np.min(lst1))print("lst1列表中最小值的索引是:")print(np.argmin(lst1))print("lst2列表中最小值的索引是:")prin

知识图谱的neo4j使用版本的问题_技术修行的博客-程序员ITS301

neo4j使用的版本有社区版,企业版,区别的介绍。从功能的角度这两者在功能上没有本质区别。主要区别是如下几点:1、容量:社区版最多支持 320 亿个节点、320 亿个关系和 640 亿个属性,而企业版没有这个限制;2、并发:社区版只能部署成单实例,不能做集群。而企业版可以部署成高可用集群或因果集群,从而可以解决高并发量的问题;3、容灾:由于企业版支持集群,部分实例出故障不会影响整...

python判断字符串,str函数isdigit、isdecimal、isnumeric的区别_weixin_30496431的博客-程序员ITS301

s为字符串s.isalnum() 所有字符都是数字或者字母s.isalpha() 所有字符都是字母s.isdigit() 所有字符都是数字s.islower() 所有字符都是小写s.isupper() 所有字符都是大写s.istitle() 所有单词都是首字母大写,像标题s.isspace() 所有字符都是空白字符、\t、\n、\r判断是整数还是浮点数a=123b=123.123&gt;&gt;&...

tensorflow的详细安装(包含jupyter notebook)_独宠。的博客-程序员ITS301_jupyter notebook安装tensorflow

WARNING: A newer version of conda exists. <== current version: 4.8.2 latest version: 4.12.0首先要添加国内的镜像源通道,一般都是默认的国外镜像连接,下载会很慢;之前用了清华的镜像源,现在被设置权限了可能安装之后有问题,所以可以下列命令使用解除权限

Spark Standalone和Yarn工作模式_myllxy的博客-程序员ITS301_spark standlone yarn

一.常用的参数其中- -deploy-mode默认为client。二.Standalone模式1.Standalone-client模式提交任务./spark-submit --master spark://node1:7077 --deploy-mode client --class org.apache.spark.examples.SparkPi …/examples/jars/...

随便推点

基于pytorch的GRUCell的简单文本分类_jianshanzhange的博客-程序员ITS301_grucell pytorch

import torchimport torchtextimport numpy as npimport torch.nn as nnimport torch.nn.functional as Ffrom torchtext.vocab import GloVeimport timestart=time.time()#每篇提取200个单词TEXT = torchtext.data.Field(lower=True, fix_length=200, batch_first=False)L

php,apache开启curl扩展_陈文文子的博客-程序员ITS301_apache curl

1.开启curl扩展的前提是已配置好PHP与apache,能正常运行2.首先打开php.ini文件,找到extention=php_curl.dll ,去掉前面的分号3.确定php扩展目录ext文件夹下有php_curl.dll文件4.在Apache的配置文件http.conf中添加以下内容:LoadFile D:/qizhuyun/php5.4/php5ts.dllLoadFi

我对active object的一点理解_程序员丹尼尔的博客-程序员ITS301

 作者:huwell     发表日期:2003年10月18日    阅读次数:428 --------------------------------------------------------------------------------Active object是EPOC中最具特色的东西,它提供了非抢占式多任务(和传统的Unix系统一样)。从而使得多线程编程对大多数程序和服

python做物联网控制_GitHub - ATM006/iot-platform: python实现智能家居物联网服务平台_weixin_39648492的博客-程序员ITS301

iotDesign of IoT Service platform for smart home systemAbstractWith the maturity of technologies such as Internet of Things, big data, cloud computing, the development of Internet of Things applicatio...

java面试题_xiaomin_____的博客-程序员ITS301

java 面试题 一、Java基础知识1.Java有那些基本数据类型,String是不是基本数据类型,他们有何区别。2.字符串的操作:  写一个方法,实现字符串的反转,如:输入abc,输出cba  写一个方法,实现字符串的替换,如:输入bbbwlirbbb,输出bbbhhtccc。3.数据类型之间的转换  如何将数值型字符转换为数字(Integer,Double)  如何将数字转换为字符 

Ubuntu下安装 编译项目_weixin_34273479的博客-程序员ITS301

在Ubuntu下安装GCC和其他一些Linux系统有点不一样。方法一:sudo apt-get build-depgcc方法二:sudo apt-get installbuild-essential安装完了可以执行gcc--version 命令来查看版本。编译则使用gcc命令。要往下学习首先就得熟悉gcc命令的...

推荐文章

热门文章

相关标签