参考《编译原理及实践》
有如下文法:A→(A)|a
先给出该文法的DFA:
根据规定,将A'→A作为开始。
得到文法:
A'→A
A→(A)|a
-----------------
根据从左到右扫描,虚拟一个游标。当前游标在-1处,即:
A'→A
↑(在A前面)
让游标向右移动(第一次移动)。得到
A'→A
↑(在A后面)
但由于A是一个可分解的文法(A→(A)|a)。所以,要向右移一位,则必须考虑分解式的情况,即得到:
1、由于A→(A),所以如果输入时'('时,则有:
A→(A)
↑(在'('后面)
同时,由于A得到文法(A)和a
则在这里需要加入另外两个文法:
A→(A)
↑(在'('前)
A→a
↑(在'a''前)
即:状态0 到 状态3的转换
2、由于A→a,所以如果输入时'a',则有:
A→a
↑(在'a'后面)
即:状态0到状态2的转换
3、若输入为整个A则得到:
A→A
↑(在A后面)
即:状态0到状态1的转换
此时已得到4个状态。且状态1和2均已移动完成(到达规约状态)
则现在只考虑状态3。
状态3能接受3个输入。
1、输入'(':则图中状态3的第二条文法得到第一条文法。第三条文法不响应'('
2、输入'a':由第三条文法响应,得到状态2(这是一个规约状态)
3、输入A:则第一条文法响应输入。得到状态4
状态4只接受一种输入即')'到达状态5(规约状态)
移动-规约过程分析:
创建一个堆栈,栈顶为$
设输入为:((a)),在该输入后添加$
从左到右扫描
1、'('。状态转到3,不是规约状态,将3加入堆栈
当前堆栈:$ ( 3
2、'('。仍回到状态3
当前堆栈 $ ( 3 ( 3
3、'a'。压入栈顶,到达状态2,其文法为A→a,从堆栈弹出a(栈顶元素),将A压入栈顶
当前堆栈$ ( 3 ( A
4、压入栈顶后到达状态4,将')'压入堆栈
当前堆栈:$ ( 3 ( A )
5、压入堆栈后到达状态5,是一个规约状态,则使用A→(A)规约,弹出状态3,将A压入栈顶到达状态4
当前堆栈:$ ( A 4
6、')'。压入栈顶到达状态5,是一个规约状态,使用A→(A)规约
最终表达式被接受。
- 大小: 28.2 KB
分享到:
相关推荐
试析贫困地区农村社会保障问题-----杨杰.doc
试析城市弱势群体的权益保护-论文.zip
试析北伐战争胜利进军的原因-4页.pdf
试析移动互联网时代高校课堂管理方式的改革.pdf
试析神经网络系统的机器学习过程.pdf
试析伊斯兰仪式的制度功能-试析伊斯兰仪式与社会制序.doc
试析淮河流域洪涝灾害原因及治理对策,朱建龙,谷俊杰,淮河流域是洪涝灾害十分严重的地区,淮河也是七大江河中洪涝灾害最频繁、灾情最严重的河流之一。其原因有三个:(1)特殊的不利�
试析洛克财产权的起源、意义及评判-7页.pdf
试析汕头市中心城区城市卫生管理存在的问题及对策-论文.zip
试析APP视角下的移动电子商务发展潜力研究.pdf
试析计算机网络技术在企业信息化过程中的实践应用分析.pdf
试析电力配网运维管理的现状及措施.pdf试析电力配网运维管理的现状及措施.pdf试析电力配网运维管理的现状及措施.pdf试析电力配网运维管理的现状及措施.pdf试析电力配网运维管理的现状及措施.pdf试析电力配网运维管理...
试析电力配网运维管理的现状及措施.docx试析电力配网运维管理的现状及措施.docx试析电力配网运维管理的现状及措施.docx试析电力配网运维管理的现状及措施.docx试析电力配网运维管理的现状及措施.docx试析电力配网...
试析4G移动通信技术及其面临的问题.pdf
试析电脑随机分案过程中存在的问题及对策.pdf
移动通信技术在物联网中的应用试析.pdf
试析昌黎地秧歌的现状及传承保护
试析从文学发展看女性自觉意识的觉醒
试析移动互联网金融背景下的证券行业发展策略.pdf
试析路桥施工中加固技术及设计.docx