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

接昨天

 

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

 

     状态机行为就是 ：

 

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

 

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

 

 

        class State{
        StateType type = StateType.BEGIN;

	public State nextState(char i){
		return null;
	}
}

 

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

 

建立一个IntState 然后重载 State：

 

 

 

  class IntState extends State{
      public State nextState(char c){
            if(c >= '0' && c <= '9'){
                  return this;
            }else{
                  return null;
            }
      }
}

 

 

 

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

 

 

  String prostr  = "192321 2312 3243";
  String buff = "";
 for(int i=0 ; i<prostr.length() ; i++){
        char c = prostr.charAt(i);
        State st = intStat.nextSate(c);
         buff += c;
        if(st == null){
             print buff;
        }
}

 

 

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

 

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

 

 

			
     floatSate：
                      public State nextState(char i){
				if(isDigit(i)){
					return floatSt;
				}else if(i == '.' || isAlpha(i)){  // 浮点数状态下 输入“.”  和字符 返回deny状态 说明词法错误，这里也可以做成抛异常
					return deny;
				}else{
					return null;  //如遇到空格 或者其他的字符 则说明词法完成 顺利通过
				}
			}
     spaceState     识别空白的字符

                      public State nextState(char i){
				if(isSpace(i)){
					return spaceSt;
				}else{
					return null;
				}
			}

 

 常用的函数 

 

	public static boolean isAlpha(char i){
		return (i>='a' &&  i<='z') || (i>='A' && i<='Z');
		}
		
	public static boolean isDigit(char i){
		return (i>='0' &&  i<='9') ;
		}
		
	public static boolean isSpace(char i){
		return (i==' ' || i=='\r' || i=='\n' || i=='\t') ;
		}

 

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

 

 

map.put("(", new State(StateType.LPARENT));

 

 

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

 

 

public State nextState(char i){
				if(isAlpha(i) || i == '_'){    //如第一个字符遇见字母 ，那么接下来就返回 identState ，它用来识别变量和关键字这类的。
					return identSt;
				}else if(isDigit(i)){           //如是数字 看开头是0打头的 有可能是0x 也可是8位的 ，如果不是0 那就是整型的。当然整型半截可能遇见“.”
					if(i == '0'){              //在整型状态下遇见"." 就返回floatState 当作float识别。 这里用了子状态 。其实可以多生成些状态不要子
						intSt.subtype = 8160;  //状态
					}else{
						intSt.subtype = 10;
					}
					return intSt;
				}else if(i == '\"'){  // 引号出现说明后边是 字符串
					return strSt;
				}else if(isSpace(i)){
					return spaceSt;
				}else {              // 如果是其他符号 看看是不是单个的 {} []: ,. 之类的
					return smap.get(String.valueOf(i));
				}
			}

 

 

 

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

 

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

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

 

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

 

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

 

字符串 ： abcd

DFA 过程：  先看和 aaa 匹配么再和bbb匹配 在和ccc匹配

NFA过程： 先看abcd的第一个字符 和 aaa bbb ccc 那个匹配 。然后在看第二个字符b ...

有点类似一个深度优先 一个是广度优先。

 

  今天到这里 待续

  大家过年好，春节快乐。

 

  给出词法分析的代码

 

 

 

 

 

 

 

 

现在的人越来越喜欢作秀了,且不说有啥气候

自定义一些脚本语言很多项目是有好处的. 比如SQL parser及审计工作, 监控的规则编写.  我们用到了很多的自定义的语言, 或者parser脚本的工具.

至少也用用正则吧...

接昨天

 

到目前为止 已经有了一个词法分析的东东。 还不完善 不过已经可以把大部分程序里出现的有意义的字符识别出来了。例如：

 

 

		test = "int a = 5.234; float b = 3;<\n"
			+ "! <= += >= !=8377243.324324 () 3244\r\n"
			+ " 432 rewrew-  \"fdsfdfds\"\n"
			+ " 09\n"
		        + "//fdafdfd 843728 fdfdfd \n"
		        + "fdfdsfd ffff";

 

 被分解后输出为：

 

int		INTEGER_TYPE
a		IDENT
=		ASSIGN
5.234		FLOAT
;		SEMI
float		FLOAT_TYPE
b		IDENT
=		ASSIGN
3		INTEGER
;		SEMI
<		LT
!		NOT
<=		LE
+=		PLUS_A
>=		GE
!=		NE
8377243.324324		FLOAT
(		LPARENT
)		RPARENT
3244		INTEGER
432		INTEGER
rewrew		IDENT
-		MINUS
fdsfdfds		STR
------------------err-----------------------   //有了一点词法分析报错的 功能。 显示什么位置出现了错误
unexpect char "9" 
at line : 4 col :3
------------------errend--------------------
0		INTEGER
//fdafdfd 843728 fdfdfd 		SKIP
fdfdsfd		IDENT
ffff		IDENT

 

 

 

尽管上边的字符串不是合法的语句 ，但是词法分析不关系语句是否合法 ，只是把相应的有意义的字符串分解出来即可。 

 

 

 

语法分析比较难点  ，我也刚看不久。 表述不清楚的地方 大家查查资料吧。

 

首先 我们看看如何解析 数学表达式。 这是最简单的 也是最复杂的一种语法了。 简单的 如  2+4     4-2   .... 等等 

 

好现在可以写一个简单的程序处理这些了。

 

 

  express(){
      
      int left ,right  , result;
  
      Token tk = getNextToken();
       
       if(tk.type == INT){
             left = tk.value;             
       }
        tk = getNextToken();

       if(tk.type == ADD){
               tk = getNextToken();
              right = tk.value;
              result = left + right;
       }else if(tk.type == MINUS){
              tk = getNextToken();
              right = tk.value;
              result = left - right;
       }

}

 

 

很简单 出来了 计算 加减的表达式。  可是这个表达式比较弱 只能计算 两个数的加法减法。 改进一下。

 

 

 express(){
      
      int left ,right  , result;
  
      Token tk = getNextToken();
       
       if(tk.type == INT){
             left = tk.value;             
       }
        while(tk = getNextToken() != null){  //这里加入个循环 ，即让后边在出现 + - 的运算都进行下去

       if(tk.type == ADD){
               tk = getNextToken();
              right = tk.value;
              result = left + right;
       }else if(tk.type == MINUS){
              tk = getNextToken();
              right = tk.value;
              result = left - right;
       }
}

}

 

 

加入了循环处理 这就让  他可以处理 4+3-32+23-0  .... 的运算。

 

下一步加入 × /  运算。 这个比较麻烦的地方就是 。如何才能是乘除先运算  加减后运算？  

 

看这个 例子:     a + c*d

 

可以把 c*d 看作是一个整体 ，原来的表达式 ====》  a + b   ；  b ====> c*d

 

上边那个express() 函数 只能计算加减 。 可以计算  a +b  这部分。 但现在b 不是一个具体的数字了  ，而是一个 需要求解的未知值。

 

我们可以把b当作一个函数 ，这样表达式就变为了  a + b()  .在计算这个表达式之前 就得先计算b这个函数值 。 这样就体现了 × / 优先于 +- 计算了。 

 

糊涂了？  还是看代码吧 ，文字还是不如代码容易理解。

 

 

express(){
      
      int left ,right  , result;
  
      Token tk = getNextToken();
       
       if(tk.type == INT){
             left = tk.value;             
       }
        while(tk = getNextToken() != null){  //这里加入个循环 ，即让后边在出现 + - 的运算都进行下去

       if(tk.type == ADD){
              right = b();       //注意这里的变化
              result = left + right;
       }else if(tk.type == MINUS){
              right = b();      //注意这里的变化
              result = left - right;
       }
}

}

 

 

原来的right的值 直接取一个token就得到了 。这里变为了 调用一个叫做b函数。  现在我们假定了 后边跟着一个 c *d 运算 。那么b 函数这么写

 

 

    

int b(){
     int left ,right  , result;
   
      Token tk = getNextToken();
       
       if(tk.type == INT){
             left = tk.value;             
       }
        while(tk = getNextToken() != null){  

       if(tk.type == MULTIPLY){
              right = getNextToken().value;       
              result = left * right;
       }else if(tk.type == DIVIDE){
              right = getNextToken().value;       
              result = left /right;
       }
}

 

这个上边算加减的函数差不多  。到这里虽然可以计算 想 a + c *d 这类的表达式  可是现在也只能计算这样的表达式 。换一种写法就不行了。写成 c*d +a 就歇菜了。

 

想来想去 发现这么着是不行的。 继续顺着上边的思路走。 a + c*d ==> a + b ; b ==> c*d   你会发现  。a 也可能是一个表达式啊。  a 可能是 a ==> e + f 。那

 

e 呢? f呢 都可能是表达式, 感觉很混乱 ，还好 有人帮你整理了这中混乱， 于是就有了BNF 这种东西   .  先看看 BNF 是如何处理这中问题的。 

 

 

BNF 的思路和上边的思考过程 很像 不过更科学 。看看bnf 怎么描述 表达式的。

 

express === >   A + express | A - express | A

 

| 代表 或者的关系 。 A 可以理解为一个返回确切数字的函数 。 汉语意思可以说 表达式 是一个数字 + 或者 - 一个表达式  或者 就一个确切数字组成的。

 

这是个递归的说法 ，似乎看不到底 但是有一点很重要 它已经表达了有加 减。

 

现在开始定义 A 了 ，这里把A改名 叫做 term  因为这是通常都这么叫

 

express === >   term + express | term - express | term

 

把这个翻译成程序就是 

 

 

  int   express () {
        int left = term();
        Token tk = getNextToken();

        //express ==> term + express | term - express
        if(tk.type == PLUS || tk.type == MINUS){
              int right = express();
              return  left + - right;
        }else { putBack (tk )} //上边测试是不是×/ 不是的话吧这个token放回去 。这里很重要。 也很难说清楚流程 开代码 或者跟代码更容易明白
         // express == > term();  因为上边已经求出 left = term(); 所以直接返回left 
         return left

}

 

 

    现在定义 term ==> factor * term | factor / term | factor

 

简直跟express 一模一样的定义 ，这次定义了 乘除的运算。 可以看到 问题变得月来越小了

 

 

 

 

 int   term () {
        int left = factor();
        Token tk = getNextToken();

        //term ==> factor * term | factor / term
        if(tk.type == MULTIPLY || tk.type == DIVIDE){
              int right = factor();
              return  left  * / right;
        }else { putBack (tk )} //上边测试是不是×/ 不是的话吧这个token放回去 。这里很重要。 也很难说清楚流程 开代码 或者跟代码更容易明白
         // express == > term();  因为上边已经求出 left = term(); 所以直接返回left 
         return left

}

 

 

这次出现了 factor  。 factor 如何定义？ 再往下分解 就是 数字了 factor ==> num | - num

 

int factor(){

    Token tk = getNextToken();
    if(tk.type == MINUS){
         return  - tk.value
    }
    return tk.value;
}

 

BNF主要是用了递归的方式 分解问题 。 

 

 

写了这么多 发现 还是看程序更容易理解  还是上程序吧 。。。 下边的程序计算一个 表达式  ，包括 括号 和 正负号 求模 功能。

 

 

 

当运算量大的时候，用正则会有效率问题吧

你是说你用java实现了一个词法分析器吧，词法分析貌似比较简单啊

楼主讨论的东西还是有一定价值的，有兴趣可以看看我做的这个东东，然后大家可以交流一下，http://linliangyi2007.iteye.com/blog/337069

大牛出现  呵呵 。 前一阵子就参看过你的程序了

我早就有自己写个动态语言的相法，语法规则像JSON那样，灵活又简洁，可编译原理学得不好，还只能写Lexer和Parser。有空的话和LZ切磋切磋，怎么样？QQ：307609641 email:g.johnsonlee@gmail.com.

下面是我写的解析JSON语法的代码：http://johnson-lee.iteye.com/blog/586686
望各位拍砖......