注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

shally

笑看庭前花开花落

 
 
 

日志

 
 

词法分析(字符串分析) (正规式)  

2011-09-03 19:19:42|  分类: Java |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
词法分析是编译器实现的第一步。主要是分析输入的源程序(字符串),输出该字符串中出现的所有的合法的单词。例如:int a = 3 + 5;经过词法分析会输出 int,a,=,3,+,5和;这七个单词。实现词法分析器的官方做法是:
    1.写出各个单词的正规式(正则表达式);
    2.根据正规式构造NFA(不确定的有限自动机);
    3.将NFA转换DFA(确定的有限自动机);
    4.根据DFA就可以实现词法分析器,写出程序。
下面用实例来说明上面的各个步骤:
    假设我们要实现一个很简单的脚本,该脚本中只有两种类型的单词,一种就是变量,变量名的规则就是以字母开头后面紧跟0个或多个字母或数字的的字符串,如 a 和 a12d3 等;另一种就是操作符,很简单只有 &,|,~,(,),==,!= 这几个。给出几个脚本的实例:result1 & result2,rst1&(rst2|rst3),answer1 | (~answer2)。
按照上面的步骤,让我们来看一下如何实现这个词法分析器:
第一步:写出正规式
    变量的正规式是:letter(letter|digit)*
    操作符的正规式:&,|,~,(,)。由于操作符都是固定字符的,所以正规式就是它本身。
第二步:根据正规式构造NFA
    正规式构造NFA的基础是先构造正规式中每个字符的NFA,如变量的正规式中只有两个字符 letter 和 digit,他们的正规式分别是:
                 
根据构造|形式的NFA的公式可以构造 letter|digit 的NFA如下图:

(letter|digit)*的NFA为:

letter(letter|digit)*的NFA为:

第三步:将NFA转换为DFA
    先是将所有通过ε可以到达的状态合并,由上图NFA可以看出1,2,3,4,6,9都是通过ε可以直接用箭头连接的,以此类推5,8,9,3,4,6和7,8,9,3,4,6都是可以合并称一个状态的,如下图:

此图用新的DFA表示如下:

   由于生成的DFA的状态过多,需要将上面的DFA最小化,生成状态数最少的DFA,最小化DFA的过程就是将那些无论怎样转换都仍然转换到本组合内部的状态组合合并,如上图{B,C,D}这三个状态组合称状态组无论经过letter还是digit转换都仍然转换到该组合,那么就可以将这三个状态合并,如下图:
        用新状态表示为:      
脚本中变量的DFA已经构造好了。
由于操作符都是固定字符,所以DFA比较简单,下面给出几个的图示例子:


现在我们将各个单词的DFA组合在一起,大致类似下图:

实际上,由于这种很简单的例子不必套用这种正规的步骤来得到DFA,可以直接把图画出来。首先画一个开始状态(Start)和一个结束状态(Done),然后再考虑各个单词之间的关系将其分类,这种分类的过程就看你的经验了,依据各个单词挨个字符被识别的过程即可画出类似上图的DFA,然后再根据这个DFA写出词法分析的程序来就非常的简单了。
本文摘自:http://www.blogjava.net/qujinlong123/archive/2007/05/08/113773.html
  评论这张
 
阅读(252)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017