之前强行看过一段时间编译原理，看了三章就看不下去了，特别痛苦。而且看完就跟失忆了一样，看了什么也记不起来。最近在看Scala的东西，看到Scala的一个库，又对parser有一点兴趣，这里是一些思考和记录。
刚看到这个东西的时候觉得特别炫酷，比如你需要匹配一个字符加数字并把它组装起来，只需要这么写。
case class WordFreq(word: String, count: Int) {
override def toString = "Word <" + word + "> " +
"occurs with frequency " + count
}
class SimpleParser extends RegexParsers {
def word: Parser[String] = """[a-z]+""".r ^^ { _.toString }
def number: Parser[Int] = """(0|[1-9]\d*)""".r ^^ { _.toInt }
def freq: Parser[WordFreq] = word ~ number ^^ { case wd ~ fr => WordFreq(wd,fr) }
}
object TestSimpleParser extends SimpleParser {
def main(args: Array[String]) = {
parse(freq, "johnny 121") match {
case Success(matched,_) => println(matched)
case Failure(msg,_) => println("FAILURE: " + msg)
case Error(msg,_) => println("ERROR: " + msg)
}
}
}
它和语法翻译器几乎是一模一样，^^左边是文法，右边是动作。
我尝试去理解/实现它，先从简单的开始：
-
匹配上面的结果又三种状态，Success，Fail，Error。我估计Fail是匹配失败，Error是异常，在这里异常就先不去管它了。用Result接口来表示匹配结果：
public interface Result<E> { E get(); default boolean isSuccess() { return this instanceof Success; } static <E> Result<E> success(E e) { return new Success<E>(e); } static <E> Result<E> fail(String errorMessage) { return new Fail<>(); } class Success<E> implements Result<E> { E val; Success(E val) { this.val = val; } @Override public E get() { return val; } } class Fail<E> implements Result<E> { @Override public E get() { return null; } } }Fail类后续可以添加一些匹配出错的信息，现在也先不去管它
-
定义Paser接口：
public interface Parser { Result<String> parser(ByteBuffer buffer); }*为了方便回溯，直接用
ByteBuffer，这样在匹配开始时调用mark()，回溯就只需要调用reset()。 -
开工！
匹配字母：
Parser alpha = b -> { b.mark(); StringBuilder builder = new StringBuilder(20); while (b.hasRemaining()) { byte c = b.get(); if (Character.isAlphabetic(c)) builder.append(c); else break; } if (builder.length() > 0) { return Result.success(builder.toString()); } else { b.reset(); return Result.fail(); } };匹配数字：
Parser num = b -> { b.mark(); StringBuilder builder = new StringBuilder(20); while (b.hasRemaining()) { byte c = b.get(); if (Character.isDigit(c)) builder.append(c); else break; } if (builder.length() > 0) { return Result.success(builder.toString()); } else { b.reset(); return Result.fail(); } };几乎是一模一样，那么把重复的部分提取出来，谓词作为一个参数传进去。
static Parser product(Predicate<Character> pred) { return b -> { b.mark(); StringBuilder builder = new StringBuilder(20); while (b.hasRemaining()) { byte c = b.get(); if (pred.test((char) c)) { builder.append(c); } else { break; } } if (builder.length() > 0) { return Result.success(builder.toString()); } else { b.reset(); return Result.fail(); } }; }那上面的代码就可以改成:
Parser alpha = product(Character::isAlphabetic); Parser num = product(Character::isDigit);简洁!
思考：这个东西就是处理重复的类似字符，比如都是数字或者都是字母，他们的判断可以用同一个逻辑，也就是传进去的Predicate参数。如果把参数拓展成Paser，parse返回的Success 和 Fail 就相当于true 和 false，
那么这个东西就可以处理正闭包了！按着这个思路下去正则表达式里的?,*,+就全出来了，感觉一个正则表达式引擎正在向你徐徐挥手有没有~
static Parser questionMark(Parser parser) { return b -> { Result<String> result = parser.parse(b); return result.isSuccess() ? result : Result.success(""); }; } static Parser kleenStar(Parser parser) { return b -> { Result<String> r = kleenPlus(parser).parse(b); return r.isSuccess() ? r : Result.success(""); }; } static Parser kleenPlus(Parser parser) { return b -> { StringBuilder builder = new StringBuilder(100); Result<String> r; while ((r = parser.parse(b)).isSuccess()) { builder.append(r.get()); } return builder.length() > 0 ? Result.success(builder.toString()) : Result.fail(); }; }代码有一点难看，Resuslt类似Java8里的Optional，那么再加一点东西。
default Result<E> onfail(E val){ return isSuccess() ? this : success(val); } static Result<String> concat(Result<String> r1, Result<String> r2) { return r1.isSuccess() && r2.isSuccess() ? success(r1.get() + r2.get()) : fail(); }最终版本：
static Parser questionMark(Parser p) { return b -> p.parse(b).onfail(""); } static Parser kleenStart(Parser p){ return b -> kleenPlus(p).parse(b).onfail(""); }接下来是连接，可选操作：
static Parser link(Parser p1, Parser p2) { return b -> Result.concat(p1.parse(b), p2.parse(b)); } static Parser option(Parser p) { return b -> p.parse(b).onfail(""); }简单测试一下：
public static void main(String[] args){ ByteBuffer buffer = ByteBuffer.wrap("heihei12323**&$3".getBytes()); System.out.println(Parser.link(Parser.alpha, Parser.num).parse(buffer).get()); }按照这个思路正则表达式引擎就可以搞下去了，虽然目前分组还不是很清楚该怎么弄。
我们已经成功跑偏了
本来是准备写Parser，怎么搞成正则表达式引擎了？那就先放着，回过头来，现在缺一个东西，那就是语义动作，不然搞来搞去都是字符串，没什么意思。
语义动作就是把匹配的字符串转换为值，那么Result再加两个方法：
default <T> Result<T> map(Function<E, T> f){ return isSuccess() ? success(f.apply(get())) : fail(); } default <T> Result<T> flatmap(Function<E, Result<T>> f) { return f.apply(get()); }Parser添加方法：
default <E> Result<E> parse(ByteBuffer buffer, Function<String, E> function){ return parse(buffer).map(function); }我们注意到，如果前面的匹配失败，这里会出问题。function要处理输入参数的情况，而且Parser可以改成Parser<E>，E就是最后解析出来的值，他可以是int、String、数据结构、语法树节点等等任何东西。
待续
网友评论