关于java:从零开始用Java-实现Parser-Combinator

引言

什么是Parser Combinator

Parser Combinator是函数式语言中的概念，它是一种通过组合小型解析器来构建简单解析器的技术。其中Parser是把输出数据(通常是文本)转换成特定数据结构的函数或者对象。Parser接管一个字符串(或者字节流)作为输出，尝试依据预约义的规定对其进行解析，最终返回胜利或者失败的后果。Combinator是组合器，它是一些用于组合各种Parser的函数。

Parser Combinator的劣势与劣势

Parser Combinator的劣势是它具备十分高的可读性和灵活性，可读性体现在它对解析对象的语法形容十分的直观，灵活性体现它能够得心应手的组合。

Parser Combinator的劣势在于它的性能会比专门的解析器(例如应用Flex/Bison生成的解析器)差，易用性和性能难以兼得。

为什么要用Java来实现

第一，我的工作是一个Java程序员；
第二，文本解析或者语法解析的在日常中需要比拟多；
第三，大部分的解析工作对性能的要求不会太高，好用且易读的Parser Combinator十分有应用价值；
第四，目前没有找到好用的Parser Combinator的实现。

函数式语言中的Parser Combinator

以haskell中的parsec为例。假如有一个解析格式化之后的工夫字符串的需要，格式化之后的工夫是这样的：2023-05-01 12:30:30，应用parsec来解析这个工夫字符串的代码能够这样写:

-- 定义解析的指标数据结构
data Time = Time
  { year :: Int
  , month :: Int
  , day :: Int
  , hour :: Int
  , minute :: Int
  , second :: int
  }

-- 解析整数的解析器
anyInt :: Parser Int
anyInt = read <$> many1 (satisfy isDigit)

-- 指标解析器，通过组合anyInt 和 char函数实现
timeParser :: Parser Time
timeParser = Time <$> anyInt << char '-'
                  <*> anyInt << char '-'
                  <*> anyInt << char ' '
                  <*> anyInt << char ':'
                  <*> anyInt << char ':'    
                  <*> anyInt

即便没学过haskell的人也能够领会到应用Parser Combinator带来的那种直观感。再举个解析解析一行csv数据的例子：

csvLineParser :: Parser [String]
csvLineParser = many (satisfy (/= ',')) `sepBy` (symbol ',')

咱们简略的认为csv行就是一个按逗号分隔的字符串。

应用Java实现之后的成果

同样是下面两个例子

// timeParser
Parser intParser = NumberParser.anyIntStr();
Parser timeParser = intParser.chain(() -> TextParsers.one('-').ignore()) //year 
                             .chain(() -> intParser).chain(() -> TextParsers.one('-').ignore()) //month
                             .chain(() -> intParser).chain(() -> TextParsers.one(' ').ignore()) //day
                             .chain(() -> intParser).chain(() -> TextParsers.one(':').ignore()) //hour
                             .chain(() -> intParser).chain(() -> TextParsers.one(':').ignore()) //minute
                             .chain(() -> intParser); //second
Result result = timeParser.runParser(new Buffer("2023-05-01 12:30:30".getBytes()));
assert result.<Integer>get(0) = 2023
assert result.<Integer>get(1) = 5
assert result.<Integer>get(2) = 1
assert result.<Integer>get(3) = 12
assert result.<Integer>get(4) = 30
assert result.<Integer>get(5) = 30

//csvLineParser
Parser csvLineParser = TextParser.satisfy(Character::isLetterOrDigit).some()
                    .map(Mapper.toStr())
                    .sepBy(TextParsers.one(',');

其中

chain办法用于连贯另一个Parser
map办法用于将解析的后果收集指标构造
some办法是一个组合函数，意思是反复以后Parser 1次或有限次，相似于正则表达式中的+
sepBy办法是一个组合函数，意思是应用其参数中的Parser作为分隔符

设计

Parser

Parser由四个局部组成：

runParser函数：Parser的外围函数，它解析输出并返回解析后果
isIgnore：标识此Parser的后果是否须要疏忽，例如解析工夫字符串时的横杠(-)和冒号(:)是不须要呈现在后果外面的。
map：将Parser的后果转换成指标数据结构
Combinators：各种用于组合的函数,例如(chain, some, many,sepBy, repeat…)

Result

Result用于示意Parser解析的后果，其中蕴含两个次要组成部分：

一个示意解析胜利的List：因为解析器是能够组合的，所以Result是各个小解析器的后果的组合，须要用List来存储
一个示意失败的错误信息：用一个字符串就能够了

IBuffer

用于示意输出的数据，其外部保护的是一个byte[]和示意解析地位的下标，另外还有一些用于操作下标的办法。

根底解析器

TextParsers：用于解析文本数据
NumberParsers：用于解析数字
ByteParsers：用于解析字节流

实现

Parser

public abstract class Parser {
    //是否须要疏忽解析后果
    protected boolean ignore = false;
    //判断此解析器的后果是否须要疏忽
    public boolean isIgnore() {
        return this.ignore;
    }
    //设置此解析器的后果须要疏忽
    public Parser ignore() {
        this.ignore = true;
        return this;
    }
    //解析器的执行函数，外部执行parser
    public Result runParser(IBuffer buffer) {
        Result result = parse(buffer);
        if (result.isError()) {
            return result;
        }
        if (isIgnore()) {
            result.clear();
            return result;
        }
        return result;
    }

    //形象办法，具体的解析逻辑
    public abstract Result parse(IBuffer buffer);
    
    ...
}

Result

public class Result {
    //后果列表
    private List result;
    //错误信息
    String errorMsg;
    //解析耗费的输出的长度
    int length;
    //解析的地位，绝对于整个输出来说
    int pos;
}

IBuffer

public interface IBuffer {
    //回溯
    void backward(int n);
    //后退，耗费输出
    void forward(int n);
    //读取输出，但不设置position
    byte[] headN(int n);

    ... //其余的辅助办法
}

根底解析器

ByteParsers

public class ByteParsers {
    //解析一个满足条件的字符
    public static Parser satisfy(Predicate<Byte> predicate) {
        return new Parser() {
            @Override
            public Result parse(IBuffer buffer) {
                Optional<Byte> b = buffer.head();
                if (b.isEmpty() || !predicate.test(b.get())) {
                    return Result.builder()
                            .pos(buffer.getPos())
                            .errorMsg(ErrorUtil.error(buffer))
                            .build();
                }
                buffer.forward(1);
                return Result.builder()
                        .result(List.of(b))
                        .length(1)
                        .build();
            }
        };
    }
    //解析指定的字节数组
    public static Parser bytes(byte[] data, String desc) {
        return new Parser() {
            @Override
            public Result parse(IBuffer buffer) {
                byte[] bs = buffer.headN(data.length);
                if (!Arrays.equals(data, bs)) {
                    return Result.builder()
                            .pos(buffer.getPos())
                            .errorMsg(ErrorUtil.error(buffer))
                            .build();
                }
                buffer.forward(bs.length);
                return Result.builder()
                        .length(data.length)
                        .result(List.of(data))
                        .build();
            }
        };
    }
    //解析一个指定字节
    public static Parser one(byte b) {
        return satisfy(a -> a == b);
    }
    //读取n个字节
    public static Parser take(int n) {
        ...
    }
    //路过n个字节
    public static Parser skip(int n) {
        ...
    }
    ...
}

TextParsers

public class TextParsers {
    //解析一个满足条件的，特地编码的字符
    public static Parser satisfy(Predicate<Character> predicate, Charset charset) {
        return new Parser() {
            @Override
            public Result parse(IBuffer buffer) {
                byte[] bytes = buffer.headN(4);
                Optional<Character> ch = CharUtil.read(bytes, charset);
                if (ch.isPresent() && predicate.test(ch.get())) {
                    int len = String.valueOf(ch.get()).getBytes(charset).length;
                    buffer.forward(len);
                    return Result.builder()
                            .result(List.of(ch.get()))
                            .length(len)
                            .build();
                }
                return Result.builder()
                        .pos(buffer.getPos())
                        .errorMsg(ErrorUtil.error(buffer))
                        .build();
            }
        };
    }
    //应用默认编码UTF-8
    public static Parser satisfy(Predicate<Character> predicate) {
        return satisfy(predicate, StandardCharsets.UTF_8);
    }
   
    //解析一个特定编码的特定字符
    public static Parser one(char ch, Charset charset) {
        ...
    }

    ... //其余的各种根底解析器
}

NumberParser

public class NumberParsers {
    //解析一个字符串示意的指定整数
    public static Parser intStr(int a) {
    }
    
    //解析一个字符示意的任意整数
    public static Parser anyIntStr() {
    }

    //解析一个小端序编码的整数
    public static Parser intLE(int a) {
    }
    //解析一个大端序编码的整数
    public static Parser intBE(int a) {
    }

    ... //其余的解析器
}

Combinators

public abstract class Parser{
    ...  
    //反复0到有限次
    public Parser many() {
        ....
    }
    //连贯另一个Parser，先执行以后解析器，再执行被连贯的解析器
    //如果以后解析器失败则间接失败，被连贯的解析器不肯定会用到
    //所以应用Supplier来模仿惰性求值
    public Parser chain(Supplier<Parser> parser) {
       ...
    }
    //如果以后解析器失败，则尝试应用另一个解析器
    public Parser or(Supplier<Parser> parser) {
        ...
    }
    //应用一个函数将解析后果转换成任意数据结构
    public Parser map(Function<List, ?> mapper) {
        ...
    }
    //反复以后解析器n次
    public Parser repeat(int n) {
        ...
    }
    //增加了进行条件的many
    //当遇到参数中指定的Parser能够解析的内容时就进行反复操作
    public Parser manyTill(Parser parser) {
        ...
    }
    //去掉前后的空格
    public Parser trim(boolean includeNewline) {
        ...
    }
    
    ... //其余的组合函数
}

应用Parser Combinator

通常应用Parser Combinator须要实现几个步骤:

定义指标数据结构
剖析语法
应用Parser Combinator形容语法

上面咱们来用它别离实现csv,json,xml和正则表达式(Regex)

json解析器

语法形容：

应用EBNF形容JSON的语法如下:

J = E
E = O | A | S | N | B | Null
O = '{' [ (S ':' E) { ',' (S ':' E) } ] '}'
A = '[' [ E { ',' E } ] ']'
S = "string"
N = "number"
B = "true" | "false"
Null = "null"

json由六种类型组成，别离是Object, Array, String, Number, null, bule

数据结构

依据json的语法能够定义以下几个class用于示意json：JsonValue, JsonObject, JsonMember, JsonArray, JsonType。其中JsonValue：

public class JsonValue {
    /**
     * type of json value
     */
    JsonType type;
    /**
     * value
     */
    Object value;
}

应用Parser Combinator形容Json

...
   public static Parser jsonParser() {
       return stringParser()
               .or(() -> objectParser().trim(true))
               .or(() -> arrayParser().trim(true))
               .or(() -> nullParser().trim(true))
               .or(() -> boolParser().trim(true))
               .or(() -> numberParser().trim(true))
               .trim(true);
   }
   //stringParser
   ...
   //objectParser
   ...
   //nullParser
   ...
   //boolParser
   ...
   //numberParser
   ...

CSV解析器、XML解析器
相似于json，详见源码

正则表达式(Regex)

正则表达式是另一种解析的技术，它和确定性无限自动机(DFA)是等价的。实践上正则能够做的事件，Parser Combinator也能做，而且Parser Combinator更灵便与弱小一些。咱们这里要实现的实际上是一个转换器，将一个正则表达式转换成由Parser Combinator示意的解析器。

语法示意

R = E ;
E = T { "|" T } ;
T = F { F } ;
F = A [ Q ] ;
A = C | "." | "(" E ")" | "[" [ "^" ] CC "]" ;
C = <non-meta character> | "\\" <any character> ;
Q = "*" | "+" | "?" | "{" N [ "," [ N ] ] "}" ;
CC = { CR } ;
CR = <non-hyphen character> | <non-hyphen character> "-" <non-hyphen character> ;
N = <non-zero sequence of digits> ;

数据结构

定义RParser类，用于形容Regex示意中每一个局部对应的解析器

public class RParser {

    private ParserType type;
    private int quoteId;
    private int groupId;
    private Parser parser;
    private Function<Parser, Parser> func;
    public RParser apply(Function<Parser, Parser> func) {
        if (this.parser != null) {
            this.parser = func.apply(this.parser);
        }
        this.func = func;
        return this;
    }
    public enum ParserType {
        PARSER,
        QUOTE,
        GROUP;
    }
}

RParser中有一个ParserType类型用于示意它是一人一般的Parser、一个分组(Group)或者是一个援用(Quote)。同时对应不同的ParserType还有一些额定的数据：分组编号，援用编号，对应的Parser，一个示意正则中反复的函数(Function<Parser, Parser>)

应用Parser Combinator形容Regex


    public Parser parser() {
        return Parser.choose(
                () -> many(),  // *号反复
                () -> some(),  // +号反复
                () -> range(), //{m,n}反复
                () -> repeat(),//{n}反复
                () -> optional(), //?可有可无
                () -> validToken() //一般非法的token
        ).many().map(s -> {
            return RParser.builder().parser(chainParsers(s))
                    .type(RParser.ParserType.PARSER)
                    .build();
        });
    }

其中的第一个子解析器的后果都是的RParser的对象，再应用chainParsers办法来将它们连接起来。

对于回溯

之前实现的Combinator组合都是非回溯的，但正则表达式是须要回溯的，例如

应用”.*abc”来匹配”xxxabc”是能够胜利的
*然而，TextParser.any().many().chain(() -> TextParsers.string("abc"))来解析”xxxabc”却会失败。起因是TextParser.any().many()会消耗掉所有的输出，前面的 TextParsers.string("abc")就没有输出了。因而，咱们要限度第一个Parser让它不要耗费所有的输出。
我应用循环切分Buffer的形式来限度第一个解析器，具体来说，我会将以后的Buffer从地位i(i >= 0 && i <= length)把它切成两个(left, right)，将left给到第一个解析器，将right给到第二个解析器，同时增加一个参数(greedy)来示意是否须要找到最优(最长)匹配后果或者间接在第一个匹配后果的时候退出循环并返回胜利。具体的回溯实现参见BacktraceParser中

对于分组与援用的实现

分组：应用一个AopParser类来给Parser的parser函数增加装璜，在解析前应用全局自增id生成分组编号。在解析后缓存解析后果(以便后续援用的时候应用)
援用：应用编号查问对应分组所缓存的解析后果，动静生成解析器
性能测试
目前的性能与通过优化的业余的解析器相干十分大，应用Parser Combinator实现的json解析器比fastjson要慢100倍的样子。对于性能要求高的场景，还是倡议应用专门的解析器，或者应用Flex/Bison来生成解析器

残缺的我的项目地址：https://github.com/janlely/jparser

—性能测试更新—-

用Haskell的Z.Data.Parser也写了一个json parser，和fastjson比照了一下，比fastjson稍快一些。看来还是java不适宜函数式编程，并不是Parser Combinator这个模式的问题。

import Z.Data.Parser
    ( anyCharUTF8, char8, parse', satisfy, text, Parser )
import Text.Printf (printf)
import Control.Applicative.Combinators ( some, (<|>), many, sepBy )
import Data.Functor (($>))
import Z.Data.CBytes (unpack)
import Z.Data.ASCII (w2c)
import Z.Data.Vector.Base (packASCII, elem)
import Prelude hiding (elem)
import Control.Monad (replicateM_)

data JsonMember = JsonMember String JsonValue deriving (Show)

data JsonValue = JsonString String
               | JsonNull
               | JsonNumber Double
               | JsonObject [JsonMember]
               | JsonArray [JsonValue] deriving (Show)
jsonParser :: Parser JsonValue
jsonParser = JsonString <$> stringParser <|> nullParser <|> numberParser <|> objectParser <|> arrayParser

nullParser :: Parser JsonValue
nullParser = text "null" $> JsonNull

stringParser :: Parser String
stringParser = char8 '"' *> contentParser <* char8 '"'
  where charParser = do
          ch <- anyCharUTF8
          if ch == '\\' || ch == '"'
             then fail $ printf "unexpect char %c" ch
             else pure ch
        escapeParser = char8 '\\' *> char8' '"' <|> char8 '\\' *> char8' '\\'
        contentParser = some (charParser <|> escapeParser)
        char8' c = char8 c $> c


memberParser :: Parser JsonMember
memberParser = JsonMember <$> stringParser <* char8 ':'
                          <*> jsonParser 

arrayParser :: Parser JsonValue
arrayParser = JsonArray <$> (char8 '[' *> jsonParser `sepBy` char8 ',' <* char8 ']')

objectParser ::Parser JsonValue 
objectParser = JsonObject <$> (char8 '{' *> memberParser `sepBy` char8 ',' <* char8 '}')

numberParser :: Parser JsonValue 
numberParser = JsonNumber . read <$> some validChar
  where validChar = w2c <$> satisfy (`elem` packASCII ".-0123456789e")

—5月22日更新—-

最近在钻研如何进行性能优化时发现，性能不好的次要起因是当指标对象的语法中含有递归时，因为不得不应用Supplier来避免暴栈，导致了每次调用Supplier::get办法的额定性能开销。例如json和语法中，json蕴含array，同时array也蕴含json，因而JsonParser中不得不应用Supplier。因为haskell中不存在这个问题，因而应用haskell实现在的json parser的性能就很好。

对于如何抉择解析器的一点倡议：

1、当需指标语法中有递归，同时对性能要求比拟高的场景，倡议应用ANTLR

2、对性能要求不高场景，能够应用jparser，因为它应用起来比ANTLR要简略的多。

一个应用jparser实现计算器的例子:

语法: 留神要防止左递归

<expr> ::= <term> | <term> "+" <expr> | <term> "-" <expr>
<term> ::= <factor> | <factor> "*" <term> | <factor> "/" <term>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= <digit> | <digit> <number>
<digit> ::= "0" | "1" | "2" | ... | "9"

实现：

public class Calculator {

    @Test
    public void testCalc() {
        Result result = expr().parse(Buffer.builder().data("(1+2)*3-(4*2)".getBytes()).build());
        assert result.<Double>get(0).compareTo(1.0) == 0;
        result = expr().parse(Buffer.builder().data("1+2*3-(4*2)".getBytes()).build());
        assert result.<Double>get(0).compareTo(-1.0) == 0;
    }

    public Parser expr() {
        return Parser.choose(
                () -> term().chain(TextParsers.one('+').ignore())
                        .chain(() -> expr()).map(s -> (double)s.get(0) + (double)s.get(1)),
                () -> term().chain(TextParsers.one('-').ignore())
                        .chain(() -> expr()).map(s -> (double)s.get(0) - (double)s.get(1)),
                () -> term()
        );
    }

    public Parser term() {
        return Parser.choose(
                () -> factor().chain(TextParsers.one('*').trim(false).ignore())
                        .chain(() -> term()).map(s -> (double)s.get(0) * (double)s.get(1)),
                () -> factor().chain(TextParsers.one('/').trim(false).ignore())
                        .chain(() -> term()).map(s -> (double)s.get(0) / (double)s.get(1)),
                () -> factor()
        );
    }

    public Parser factor() {
        return Parser.choose(
                TextParsers.one('(').ignore()
                        .chain(() -> expr())
                        .chain(TextParsers.one(')').ignore()),
                number()
        );
    }

    public Parser number() {
        return NumberParsers.anyDoubleStr();
    }
}

关于java:从零开始用Java-实现Parser-Combinator

引言

什么是Parser Combinator

Parser Combinator的劣势与劣势

为什么要用Java来实现

函数式语言中的Parser Combinator

应用Java实现之后的成果

设计

Parser

Result

IBuffer

实现

Parser

Result

IBuffer

根底解析器

应用Parser Combinator

json解析器

正则表达式(Regex)

对于回溯

对于分组与援用的实现

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于java:从零开始用Java-实现Parser-Combinator

引言

什么是Parser Combinator

Parser Combinator的劣势与劣势

为什么要用Java来实现

函数式语言中的Parser Combinator

应用Java实现之后的成果

设计

Parser

Result

IBuffer

实现

Parser

Result

IBuffer

根底解析器

应用Parser Combinator

json解析器

正则表达式(Regex)

对于回溯

对于分组与援用的实现

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复