PEG
https://engineering.linecorp.com/ja/blog/peg-parser-generator-packrat-parser/
Parsing Expression Grammar
字句解析付きのコンパイラコンパイラ
形式文法の一種
PEGに曖昧さは存在しない
|(又は)とかがない
正しい構文木は常に1つ
逆に
自然言語の多義性を、そのまま複数の構文木が可能である、という形で形式化するのには向かない。ref
字句ルールと構文ルールを同時に定義できる
論文
http://bford.info/pub/lang/peg.pdf
BNF記法と異なる点
BNFの|と似ているものに\がある
「又は」ではなく、「左辺の解析が成功すれば、右辺を解析」を表す
Parsecとの対応 ref
並び: e1 e2
do e1; e2
選択: e1 / e2
e1 <|> e2
ゼロ個以上: e*
many e
1個以上: e+
many1 e
省略可能: e?
AND述語: &e
try e
NOT述語: !e
notFollowedBy e
字句解析と構文解析を同時に行う
実装
Go
https://github.com/pointlander/peg
PEG.js
https://qiita.com/mizchi/items/d948eb667a0ef67b97bc
参考
Parsing Expression Grammar - Wikipedia
https://kmizu.hatenablog.com/entry/2021/02/20/014408
https://qnighy.hatenablog.com/entry/2015/11/12/162424
https://engineering.linecorp.com/ja/blog/peg-parser-generator-packrat-parser/
https://mizunashi-mana.github.io/blog/posts/2021/11/peg-parser-generating-by-ptera/
https://blog.logrocket.com/building-rust-parser-pest-peg/
rustで作る