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

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

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

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

第一，我的工作是一个 Java 程序员；
第二，文本解析或者语法解析的在日常中需要比拟多；
第三，大部分的解析工作对性能的要求不会太高，好用且易读的 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 行就是一个按逗号分隔的字符串。

同样是下面两个例子

// 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 由四个局部组成：

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

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

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

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

根底解析器

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

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);
    
    ...
}

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

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 形容语法

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

语法形容：

应用 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，详见源码

正则表达式是另一种解析的技术，它和确定性无限自动机 (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)

对于回溯

对于分组与援用的实现

Just My Socks（注册教程内含优惠码）

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

引言

什么是 Parser Combinator

Parser Combinator 的劣势与劣势

为什么要用 Java 来实现

函数式语言中的 Parser Combinator

应用 Java 实现之后的成果

设计

Parser

Result

IBuffer

实现

Parser

Result

IBuffer

根底解析器

应用 Parser Combinator

json 解析器

正则表达式(Regex)

对于回溯

对于分组与援用的实现

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）