写一个自己的动态语言吧。 初学乍练的。

动态语言大行其道 ，不过还有不少公司在用着java 。 很大部分人也会java 。

 

所以用java 来开发自己的一个动态语言 不错 。反正总是要东西打发内心的无聊， 治疗枯燥的工作对人心理的创伤。

 

搞这么大个题目 ，招来不少人 。高手也会来吧？ 本人编译原理原来上学就没学好 ，这也算是初学乍练 ，您看得高兴捧个人场 ，看得不高兴 多多指教 ，以免我误导了群众。

 

 

首先 我必须承认我这话说大了。 我目前只是写到了 词法分析器 和 一个表达式计算。距离动态语言 还差的远。 我也很怀疑我有时间真的写完这些 。今天有空就写点 。 本文的宗旨 就是简单。主要是复杂的东东 我也说不出来 。

 

编译原理 上过这课的都知道 很无聊。 工作两年基本忘掉 残留下来的概念看到了热泪盈眶的 想不起来。 咱就再回忆一遍吧。

 

 

 

第一个 DFA 确定状态机。

 

 

先不说这是啥。 看一个例子， 为了说明状态机的作用和能力 得绕点路先撇开编译原理 抛开概念看看怎么一步步发现这个DFA。 如很解析xml html？

 

这是我在做一个手机浏览器的时候遇到的问题，虽然有很多库，但是手机上没有或者有不适合，于是自己搞一个 。这里就不争论 “轮子” 的问题了。

 

<p> xxxxx </p>

这是典型的一段xml 。 注意看， 主要分两部分 ‘<’ 和 ‘>’ 括住的部分,和之外的东西 也就是 ‘>’ 和 ‘<’ 括住的部分。 其实就是把tag 和 内容 区分开。分出如下：

 

p xxxxx /p   3块

 

 

于是写代码如下

 

     state = 初始状态
     for char in htmlstr{
         if 初始状态{
            if(char == '<'){
               state = tag状态
            }
         }else if tag状态{
            if(char == '>'){
               state = 内容状态
            }else{
              tagstr += char;
            }
         }else if 内容状态{
            if(char == '<'){
               state = tag状态
            }else{
               contentstr += char;
            }
         }
 

 

呵呵 第一步 把tag 和 内容分开了  。 有同学问 < > 不会乱出现么？ 规则上规定xml 中< >必须是tag 的 遇到和要转义 就是用 &lt 这种东东代表一下。 但是也会遇到不转义的写错的 这个只要加上写判断 容错即可 这里不做详述。

 

 

tag 里边还有东东啊 

 

<img src="url" alt="xxxx">

 

 

同理可以分状态 处理之。 找到tag名字img之前叫做状态1 ,然后遇到空格 变为状态2， 然后遇到=号变为状态3 ..... 当然这里的逻辑比上边复杂一些 ，其实也就是又臭又长些 。

 

上边说的就是一个 原始的用 if else 构成的状态机。 状态机 就是根据输入 改变到不同的状态 然后做不同的处理 。简单的通俗的说 状态机 == 装逼的switch 

 

这里

 

http://code.google.com/p/tagparser/

 

有源码 python  和 java 的 。写的都比较乱 凑合着看吧  ，不大 也就是200行左右解析html xml 之流。

 

python 版本的还有一个抓取tianya 论坛的一个例子 不知道现在还能用吗 很长时间了

 

今天就到这吧 。

 

明天继续....

 

接昨天

 

     if else  或者 switch 构成的 状态机 非常简陋。  状态越来越多的时候变得乱七八糟 。 所以要分解包装一下。

 

     状态机行为就是 ：

 

                  ----输入---->switch----改变状态--->

 

      在游戏编程  Ai设计中经常用到 ，不过我们这里只主要是谈编译 ，所以输入就变成了 一个字符  输出为一个状态。 一直说“状态” 这个东西 那就把它搞成一个类吧

 

 

 

nextState 就是主要部分了 输入为一个字符串 输出也就是返回值 为一个State。 看看如何用这个State来识别一个 整型数字 例如 1000 100 99 .....

 

建立一个IntState 然后重载 State：

 

 

 

 

 

 

这个比较简单 可以生成一个 IntSate  intState =  new IntState()  看看它如何工作

 

 

 

 

其结果就是把字符串中的整型数字给 挑出来了。 这看起来很容易不是么？ 等等如果它没有split 强大费这种力气干么？ 实际上程序文件包含的字符串比这复杂的多，有int  float string 变量 关键字 各种符号.... ....................木有关系 统统没有关系 每一个建立一个state即可

 

如 floatState stringState  看看如何编写 ，这里只写出nextState 函数 它们都是继承自State类

 

 

 

 常用的函数 

 

 

 识别 单个的符号 更简单了 直接用State 生成一个不用继承，然后把它放入到一个字典里 在扫描程序字符串的时候可以快速查到。如下

 

 

 

 

这里还需要一个开始的状态 ，编译开始时 从一个字符开始扫描 。第一个字符有可能是 整型数字 也可能是字母 也可能 变量。 可以如下编写

 

 

 

 

    一旦一个状态识别完 就会返回null 说明一个词义被确认 而且这个词是整型 还是浮点型 还是字符串 ... 都是最后的那个状态类型。 这时候可以根据类型 把字符串转化为java 的类型了。 

 

   其中遇到的一些 小问题 。如  第一个字符是 0 ,就有几种可能  十六进制0x7873  浮点数0.423  八进制0632，如何确定 用intSate  还是用floatState ？

这里我程序里是假定是整型先 如遇到“.” 状态机返回floatSate这样就跳到了浮点型识别， 在区分 八进制还是十六进制的时候 用了子状态 。其实这么做不好。最好引入中间状态 如叫做 zeroState   .在这个状态里就可以区分到底是用那个状态机去识别。  因为再往后一个字符就可以确定是什么类型 如果是‘x’就是十六位整型。 

 

   这种情况很常见，就是一个字符出现不能确定状态该怎么走 ，方法就是引入中间状态。  最后实现了 每个状态输入一个字符 就可以确定下一个状态，这也是为什么叫做有限确定状态机 DFA 。一个输入可能对应多个状态的叫做非确定状态机 NFA 。很恶心的书上把简单的概念都写得抽象的吓人，真不知道为啥？为了严谨？ 写书给人看的 搞的跟给机器写书一样 。 隐隐约约记得书上像些咒语一样 写着如何把NFA 转为DFA .....  压根我看不明白。

 

   状态机的应用还很多 。其实正则就是状态机实现的 。有的是用NFA 有的是用DFA规则。 表现的区别 如匹配 （aaa|bbb|cdd）  。

 

 

 

  今天到这里 待续

  大家过年好，春节快乐。

 

  给出词法分析的代码

 

 

 

太少了，不过瘾

...
这也算?!

無語。。。

我认为DFA实质上是一个有向拓扑图，状态改变其实可以用图遍历来实现
不过DFA在有递归的文法上貌似没什么好的办法处理，LZ能帮忙解答下吗

不想打击你,如果只是写了lexer和parser的话,我建议你啊看俺antlr或者javacc 吧,只需要写自己的文法规则就行了,没必要大费周折,但是如果你要挑战一下自己,写lexer和parser的话,只能为你加油

写这个的目的是为了 手动构造这些东东 。学习的。 如果使用antlr 之类的就没必要看这个了。 喜欢使用工具 就去使用吧。可以不care这些 呵呵

DFA 用来做词法分析还不错 。文法的话 还是递归的处理比较好 ，这方面我也正在学习 以后会写 。

无语啊。。。 看来真是太无聊了！

PS: JAVAEYE越来越无趣了，这样的贴也放首页。。。

我用java写过一个，很简单，用正则表达式把源码分割，然后就是根据语法规则和运算符的优先级进行运算就好了。