乐趣区

关于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();
    }
}
退出移动版