3458人阅读
编译原理（3）
一、正则表达式转换成正则文法
例1.(a|b)*a(a|b)(a|b)
转换成左线性正则文法：
(1).S-&Aa|Ab
(2).A-&Ba|Bb
(4).C-&Ca|Cb|ε
由观察发现，一个正则表达式转换成左线性正则文法，需要从右边开始分解。
(1).Aa型最简单，为一个连接运算，可化为S-&Aa。
(2).A(a|b)型为一个选择运算，根据连接在选择上的分配律，可化为S-&Aa|Ab。
(3).Aa*型，根据*运算的定义，可化为S-&Sa，S继续作为下一级的非终结符号，若已经分析到最左边，则B-&Ba|ε。
(4).递归上述步骤。
转换成右线性正则文法：
(1).S-&aS|bS
(3).A-&aB|bB
(4).B-&a|b
由观察发现，一个正则表达式转换成右线性正则文法，需要从左边开始分解。
(1).aA型，可化为S-&aA
(2).(a|b)A型，可化为S-&aA|bA
(3).a*A型，可化为S-&aS,S继续作为下一级的非终结符号，若已经分析到最右边，则B-&aB|ε。
& (1).由上得知，分解的步骤的书目和操作数有关，N个操作数(单个字符或括号组成的字符），需要分解N步。
& (2).由转换为左线性正则文法和右线性正则文法的过程中得知，连接和选择都较容易，主要在重复运算当中，需要用上一级到非终结符号来继续产生下一级，当处于最后一级时，需要另作处理。
例2.a*aba*a
(5).D-&Da|ε
二、正则文法转换成正则表达式
两个转换互为逆操作，逆向分析而已。
(1).首先观察得知，该文法为右线性正则文法。
(2).按照转换规则进行串接。
& S-&aS =& S-&a*aA =& S-&a*abB =& S-&a*aba*B =& S-&a*aba*a
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：176163次
积分：2302
积分：2302
排名：第13873名
原创：49篇
转载：104篇
(1)(1)(3)(2)(4)(18)(32)(34)(58) 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
《编译原理》习题参考答案（一）
下载积分：1200
内容提示：《编译原理》习题参考答案（一）
文档格式：PDF|
浏览次数：258|
上传日期： 09:58:18|
文档星级：
该用户还上传了这些文档
《编译原理》习题参考答案（一）
官方公共微信编译原理2010级(A)试卷以及参考答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
编译原理2010级(A)试卷以及参考答案
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩5页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢编译原理试题B及答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
编译原理试题B及答案
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩3页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢}