Parsing Expression Grammar(PEG)は、Bryan FordによってPOPL 2004で発表された文法の形式化です。PEGはRecognition(認識）をベースとしており、Context Free Grammar(CFG)と異なっています。 PEGは曖昧でない言語を受理するのに便利な特性を持っており、PEGをベースにした構文解析器生成系が多数登場しています。また、PEGはパーザコンビネータと呼ばれる、プログラミング言語内に構文解析用DSLを埋め込む手法とも関連があります。 この勉強会では、 PEGの基本 PEGの応用例（構文解析器生成系、パーザコンビネータなど） PEGの拡張 等について勉強します（PEGに関する予備知識はなくて済むようにするつもりです）。また、 PEG以外の構文解析手法 LL法 LR法 LL(*)法 (ANTLR) GLR法 GLL法 PEG以
Scala基礎文法最速マスターを書こうか迷っていたら、既にyuroyoroさんに書かれてしまったので、ちょっと違う方向で。BNFを既に知っている人は、これを読めばPEGの基礎をマスターしてPEGを書くことができるようになるでしょう(ほんとか？)。 基本 Parsing Expression Grammar(PEG)はBNFに似ているけど、ちょっと(かなり？)違う文法の表記法です。BNFはその文法がどのような言語を表現しているかを定めるのに対して、PEGは入力がどのように解析されるかを定めます。PEGとBNFの一番大きな違いは、PEGには曖昧さが無いことです。たとえば、プログラミング言語のif文を表現する次の擬似BNFには曖昧さがあります。 statement ::= if_statement | ...; if_statement ::= IF LPAREN expr RPAREN sta
詳しい解説はネット上に沢山存在するので割愛しますが、ご覧のようにEBNFの表現の一つに（EBNFはいくつかの表現方法があるようです。例えばこれはW3Cが定義しているものです）似ています。違いは先に述べたようにChoiceの働きが異なるのと、文法上に先読みが存在することです。 このPEGを使って四則演算を受理するシンプルなルールを書くとすると、例えばこのようになります。 # expressionからパースが始まるとする expression <- additive additive <- multitive ("+" multitive / "-" multitive)* multitive <- primary ("*" primary / "/" primary)* primary <- "(" expression ")" / number number <- digit+ digit
PEGとC++11で作る言語処理系 言語処理系の作成と聞くと、難易度が高いと感じるかもしれません。しかしパーサージェネレータなどのツールを活用することによって，その敷居はぐっと低くなります。 この分野では、BNFからパーサーを生成するYaccが有名です。最近では PEG（Parser Expression Grammar）も知られるようになってきました。PEGの特徴の一つは，構文ルールだけでなく字句ルールも同時に定義できることです。現在、主要なプログラミング言語のほとんどにPEGパーサージェネレータが存在します。中には抽象構文木（AST）まで生成してくれるものもあります。 こうしたツールの助けを活用すると，言語処理系の作成はかなり容易になります。PEGで文法を定義し，ASTを実行する評価器を実装すれば，あとはPEGライブラリの助けを借りて言語処理系を完成させることができます。 今回は拙作の
This week we make the parser generator “self-hosted”, meaning the parser generator generates its own parser. [This is part 7 of my PEG series. See the Series Overview for the rest.] So we have a parser generator, a piece of which is a parser for grammars. We could call this a meta-parser. The meta-parser works similar to the generated parsers: GrammarParser inherits from Parser, and it uses the sa
I’ve alluded to left-recursion as a stumbling block a few times, and it’s time to tackle it. The basic problem is that with a recursive descent parser, left-recursion causes instant death by stack overflow. [This is part 5 of my PEG series. See the Series Overview for the rest.] Consider this hypothetical grammar rule: expr: expr '+' term | termIf we were to naively translate this grammar fragment
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Replacing CPython’s parser - Python Language Summit 2020