從零開始Java實現(xiàn)Parser?Combinator
引言
什么是Parser Combinator
Parser Combinator是函數(shù)式語言中的概念，它是一種通過組合小型解析器來構(gòu)建復(fù)雜解析器的技術(shù)。其中Parser是把輸入數(shù)據(jù)(通常是文本)轉(zhuǎn)換成特定數(shù)據(jù)結(jié)構(gòu)的函數(shù)或者對象。Parser接收一個字符串(或者字節(jié)流)作為輸入，嘗試根據(jù)預(yù)定義的規(guī)則對其進行解析，最終返回成功或者失敗的結(jié)果。Combinator是組合器，它是一些用于組合各種Parser的函數(shù)。
Parser Combinator的優(yōu)勢與劣勢
Parser Combinator的優(yōu)勢是它具有非常高的可讀性和靈活性，可讀性體現(xiàn)在它對解析對象的語法描述非常的直觀，靈活性體現(xiàn)它可以隨心所欲的組合。
Parser Combinator的劣勢在于它的性能會比專門的解析器(例如使用Flex/Bison生成的解析器)差，易用性和性能難以兼得。
為什么要用Java來實現(xiàn)
第一，我的工作是一個Java程序員；
第二，文本解析或者語法解析的在日常中需求比較多；
第三，大部分的解析工作對性能的要求不會太高，好用且易讀的Parser Combinator非常有使用價值；
第四，目前沒有找到好用的Parser Combinator的實現(xiàn)。
函數(shù)式語言中的Parser Combinator
以haskell中的parsec為例。假設(shè)有一個解析格式化之后的時間字符串的需求，格式化之后的時間是這樣的：2023-05-01 12:30:30，使用parsec來解析這個時間字符串的代碼可以這樣寫:
-- 定義解析的目標(biāo)數(shù)據(jù)結(jié)構(gòu)
data Time = Time
{ year :: Int
, month :: Int
, day :: Int
, hour :: Int
, minute :: Int
, second :: int
}
-- 解析整數(shù)的解析器
anyInt :: Parser Int
anyInt = read <$> many1 (satisfy isDigit)
-- 目標(biāo)解析器，通過組合anyInt 和 char函數(shù)實現(xiàn)
timeParser :: Parser Time
timeParser = Time <$> anyInt << char '-'
<*> anyInt << char '-'
<*> anyInt << char ' '
<*> anyInt << char ':'
<*> anyInt << char ':'
<*> anyInt即使沒學(xué)過haskell的人也可以體會到使用Parser Combinator帶來的那種直觀感。再舉個解析解析一行csv數(shù)據(jù)的例子：
csvLineParser :: Parser [String] csvLineParser = many (satisfy (/= ',')) `sepBy` (symbol ',')
我們簡單的認為csv行就是一個按逗號分隔的字符串。
使用Java實現(xiàn)之后的效果
同樣是上面兩個例子
// 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方法用于將解析的結(jié)果收集目標(biāo)結(jié)構(gòu)
- some方法是一個組合函數(shù)，意思是重復(fù)當(dāng)前Parser 1次或無限次，類似于正則表達式中的+
- sepBy方法是一個組合函數(shù)，意思是使用其參數(shù)中的Parser作為分隔符
設(shè)計
Parser
Parser由四個部分組成：
- runParser函數(shù)：Parser的核心函數(shù)，它解析輸入并返回解析結(jié)果
- isIgnore：標(biāo)識此Parser的結(jié)果是否需要忽略，例如解析時間字符串時的橫杠(-)和冒號(:)是不需要出現(xiàn)在結(jié)果里面的。
- map：將Parser的結(jié)果轉(zhuǎn)換成目標(biāo)數(shù)據(jù)結(jié)構(gòu)
- Combinators：各種用于組合的函數(shù),例如(chain, some, many,sepBy, repeat...)
Result
Result用于表示Parser解析的結(jié)果，其中包含兩個主要組成部分：
- 一個表示解析成功的List：由于解析器是可以組合的，所以Result是各個小解析器的結(jié)果的組合，需要用List來存儲
- 一個表示失敗的錯誤信息：用一個字符串就可以了
IBuffer
用于表示輸入的數(shù)據(jù)，其內(nèi)部維護的是一個byte[]和表示解析位置的下標(biāo)，另外還有一些用于操作下標(biāo)的方法。
基礎(chǔ)解析器
- TextParsers：用于解析文本數(shù)據(jù)
- NumberParsers：用于解析數(shù)字
- ByteParsers：用于解析字節(jié)流
實現(xiàn)
Parser
public abstract class Parser {
//是否需要忽略解析結(jié)果
protected boolean ignore = false;
//判斷此解析器的結(jié)果是否需要忽略
public boolean isIgnore() {
return this.ignore;
}
//設(shè)置此解析器的結(jié)果需要忽略
public Parser ignore() {
this.ignore = true;
return this;
}
//解析器的執(zhí)行函數(shù)，內(nèi)部執(zhí)行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 {
//結(jié)果列表
private List result;
//錯誤信息
String errorMsg;
//解析消耗的輸入的長度
int length;
//解析的位置，相對于整個輸入來說
int pos;
}IBuffer
public interface IBuffer {
//回溯
void backward(int n);
//前進，消耗輸入
void forward(int n);
//讀取輸入，但不設(shè)置position
byte[] headN(int n);
... //其他的輔助方法
}基礎(chǔ)解析器
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();
}
};
}
//解析指定的字節(jié)數(shù)組
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();
}
};
}
//解析一個指定字節(jié)
public static Parser one(byte b) {
return satisfy(a -> a == b);
}
//讀取n個字節(jié)
public static Parser take(int n) {
...
}
//路過n個字節(jié)
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) {
...
}
... //其他的各種基礎(chǔ)解析器
}NumberParser
public class NumberParsers {
//解析一個字符串表示的指定整數(shù)
public static Parser intStr(int a) {
}
//解析一個字符表示的任意整數(shù)
public static Parser anyIntStr() {
}
//解析一個小端序編碼的整數(shù)
public static Parser intLE(int a) {
}
//解析一個大端序編碼的整數(shù)
public static Parser intBE(int a) {
}
... //其他的解析器
}Combinators
public abstract class Parser{
...
//重復(fù)0到無限次
public Parser many() {
....
}
//連接另一個Parser，先執(zhí)行當(dāng)前解析器，再執(zhí)行被連接的解析器
//如果當(dāng)前解析器失敗則直接失敗，被連接的解析器不一定會用到
//所以使用Supplier來模擬惰性求值
public Parser chain(Supplier<Parser> parser) {
...
}
//如果當(dāng)前解析器失敗，則嘗試使用另一個解析器
public Parser or(Supplier<Parser> parser) {
...
}
//使用一個函數(shù)將解析結(jié)果轉(zhuǎn)換成任意數(shù)據(jù)結(jié)構(gòu)
public Parser map(Function<List, ?> mapper) {
...
}
//重復(fù)當(dāng)前解析器n次
public Parser repeat(int n) {
...
}
//添加了停止條件的many
//當(dāng)遇到參數(shù)中指定的Parser可以解析的內(nèi)容時就停止重復(fù)操作
public Parser manyTill(Parser parser) {
...
}
//去掉前后的空格
public Parser trim(boolean includeNewline) {
...
}
... //其他的組合函數(shù)
}使用Parser Combinator
通常使用Parser Combinator需要完成幾個步驟:
- 定義目標(biāo)數(shù)據(jù)結(jié)構(gòu)
- 分析語法
- 使用Parser Combinator描述語法
下面我們來用它分別實現(xiàn)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
數(shù)據(jù)結(jié)構(gòu)
根據(jù)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)
正則表達式是另一種解析的技術(shù)，它和確定性有限自動機(DFA)是等價的。理論上正則可以做的事情，Parser Combinator也能做，而且Parser Combinator更靈活與強大一些。我們這里要實現(xiàn)的實際上是一個轉(zhuǎn)換器，將一個正則表達式轉(zhuǎn)換成由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> ;數(shù)據(jù)結(jié)構(gòu)
定義RParser類，用于描述Regex表示中每一個部分對應(yīng)的解析器
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)。同時對應(yīng)不同的ParserType還有一些額外的數(shù)據(jù)：分組編號，引用編號，對應(yīng)的Parser，一個表示正則中重復(fù)的函數(shù)(Function<Parser, Parser>)
使用Parser Combinator描述Regex
public Parser parser() {
return Parser.choose(
() -> many(), // *號重復(fù)
() -> some(), // +號重復(fù)
() -> range(), //{m,n}重復(fù)
() -> repeat(),//{n}重復(fù)
() -> optional(), //?可有可無
() -> validToken() //普通合法的token
).many().map(s -> {
return RParser.builder().parser(chainParsers(s))
.type(RParser.ParserType.PARSER)
.build();
});
}其中的第一個子解析器的結(jié)果都是的RParser的對象，再使用chainParsers方法來將它們連接起來。
關(guān)于回溯
之前實現(xiàn)的Combinator組合都是非回溯的，但正則表達式是需要回溯的，例如
使用".*abc"來匹配"xxxabc"是可以成功的
*但是，TextParser.any().many().chain(() -> TextParsers.string("abc"))來解析"xxxabc"卻會失敗。原因是TextParser.any().many()會消耗掉所有的輸入，后面的 TextParsers.string("abc")就沒有輸入了。 因此，我們要限制第一個Parser讓它不要消耗所有的輸入。
我使用循環(huán)切分Buffer的方式來限制第一個解析器，具體來說，我會將當(dāng)前的Buffer從位置i(i >= 0 && i <= length)把它切成兩個(left, right)，將left給到第一個解析器，將right給到第二個解析器，同時添加一個參數(shù)(greedy)來表示是否需要找到最優(yōu)(最長)匹配結(jié)果或者直接在第一個匹配結(jié)果的時候退出循環(huán)并返回成功。具體的回溯實現(xiàn)參見BacktraceParser中
關(guān)于分組與引用的實現(xiàn)
分組：使用一個AopParser類來給Parser的parser函數(shù)添加裝飾，在解析前使用全局自增id生成分組編號。在解析后緩存解析結(jié)果(以便后續(xù)引用的時候使用)
引用：使用編號查詢對應(yīng)分組所緩存的解析結(jié)果，動態(tài)生成解析器
性能測試
目前的性能與經(jīng)過優(yōu)化的專業(yè)的解析器相關(guān)非常大，使用Parser Combinator實現(xiàn)的json解析器比fastjson要慢100倍的樣子。對于性能要求高的場景，還是建議使用專門的解析器，或者使用Flex/Bison來生成解析器
完整的項目地址：https://github.com/janlely/jparser
---性能測試更新----
用Haskell的Z.Data.Parser也寫了一個json parser，和fastjson對比了一下，比fastjson稍快一些?？磥磉€是java不適合函數(shù)式編程，并不是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日更新----
最近在研究如何進行性能優(yōu)化時發(fā)現(xiàn)，性能不好的主要原因是當(dāng)目標(biāo)對象的語法中含有遞歸時，由于不得不使用Supplier來防止暴棧，導(dǎo)致了每次調(diào)用Supplier::get方法的額外性能開銷。例如json和語法中，json包含array，同時array也包含json，因此JsonParser中不得不使用Supplier。由于haskell中不存在這個問題，因此使用haskell實現(xiàn)在的json parser的性能就很好。
關(guān)于如何選擇解析器的一點建議：
1、當(dāng)需目標(biāo)語法中有遞歸，同時對性能要求比較高的場景，建議使用ANTLR
2、對性能要求不高場景，可以使用jparser，因為它使用起來比ANTLR要簡單的多。
一個使用jparser實現(xiàn)計算器的例子:
語法: 注意要避免左遞歸
<expr> ::= <term> | <term> "+" <expr> | <term> "-" <expr>
<term> ::= <factor> | <factor> "*" <term> | <factor> "/" <term>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= <digit> | <digit> <number>
<digit> ::= "0" | "1" | "2" | ... | "9"實現(xiàn)：
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實現(xiàn)Parser Combinator的詳細內(nèi)容，更多關(guān)于Java實現(xiàn)Parser Combinator的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
SpringSecurity實現(xiàn)動態(tài)url攔截(基于rbac模型)
本文主要介紹了SpringSecurity動態(tài)url攔截，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
Java使用pulsar-flink-connector讀取pulsar catalog元數(shù)據(jù)代碼剖析
這篇文章主要介紹了Java使用pulsar-flink-connector讀取pulsar catalog元數(shù)據(jù)代碼剖析,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-08-08
冒泡排序的原理：假設(shè)要求的數(shù)組是正序，兩兩進行比較，如果前一個書比后一個數(shù)小，位置不變。如果前一個數(shù)比后一個數(shù)大，位置互換，再跟后一個數(shù)進行比較，直到最后。就是逐步把大數(shù)送到最后，下面來個實例給大家看看2013-11-11
本篇文章主要介紹了詳解SpringBoot定時任務(wù)說明，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-03-03
Java實現(xiàn)經(jīng)典角色扮演偵探游戲游戲的示例代碼
這篇文章主要介紹了如何利用Java語言自制一個偵探文字游戲—《角色扮演偵探》，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編學(xué)習(xí)一下2022-02-02
springboot 啟動如何修改application.properties的參數(shù)
這篇文章主要介紹了springboot 啟動如何修改application.properties的參數(shù)方法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
Java Web實現(xiàn)添加定時任務(wù)的方法示例
這篇文章主要介紹了Java Web實現(xiàn)添加定時任務(wù)的方法,涉及java web定時任務(wù)控制類定義、調(diào)用及監(jiān)聽器定義、添加等相關(guān)操作技巧,需要的朋友可以參考下2018-01-01
Retrofit+Rxjava實現(xiàn)文件上傳和下載功能
這篇文章主要介紹了Retrofit+Rxjava實現(xiàn)文件上傳和下載功能，文中提到了單文件上傳和多文件上傳及相關(guān)參數(shù)的請求，需要的朋友參考下吧2017-11-11
這篇文章主要介紹了Java 鎖的知識總結(jié)及實例代碼,需要的朋友可以參考下2016-09-09
這篇文章主要介紹了JAVA對稱加密算法PBE定義與用法,結(jié)合實例形式分析了JAVA對稱加密算法PBE的概念、原理、定義及使用方法,需要的朋友可以參考下2019-09-09