私はC/ALプログラミング言語用のある種のlintツールを作成しようとしています。したがって、基本的には、ソースコードに対して構文と字句解析を実行する必要があります。パーサーを最初から作成することを計画しましたが、これらのパーサーを自動的に生成するのに役立つツールがたくさんあることに気付きました。
20メガバイトのコードを1つのピースでチェックするのが通常のシナリオであり、そのツールをカスタムルールで拡張できるようにする必要があるため、パフォーマンスが必要です。そこで、JavaScriptを使用することにしました。
これまでのところ、 JisonとPEG.jsを使用できる2つのジェネレーターを見つけました。
それらのどれが私にもっと解析パフォーマンスを与えますか？たぶんライブラリを比較するのではなく、アルゴリズムを比較するのでしょうか？
どちらが私のニーズに適していますか（汎用プログラミング言語の解析）？
更新： 私は同様のQ＆Aを見つけました：
一般に、Jisonが実装しているようなshift-reduceパーサーから非常に優れた解析パフォーマンスが得られます。おそらく少し古い学校ですが、非常に厳しいメモリ要件と線形時間で機能する可能性があります。
PEGは別の種類のパーサーを生成します。これはおそらくより機能的ですが、同じ結果を生成するにはより多くのメモリが必要になります。つまり、PEGは入力に比例した量のメモリを必要としますが、LALRパーサーははるかに少ないスペース（一部のテーブルと小さなスタック）でそれを実行します。
「パフォーマンスが必要です（20Mbの場合）...そこでJavascriptを決定しました」。これらは矛盾しています。
注意深くコーディングされた再帰下降パーサーはかなり高速ですが、多くのコードを作成する必要があります。一般に、LALR（1）パーサー（文法などからBisonによって生成されたもの）は非常に高速で、コーディングが非常に簡単です。（LALRパーサーをマシンコードに直接コンパイルする方法を示すテクニカルペーパーがあります。これらのパーサーは非常に高速ですが、ビルドするには多くのカスタム機械を実装する必要があります）。
最小限の汗で高性能な解析をフラットにしたい場合は、LRStarを検討する必要があります。（私は著者を知っており、非常に尊敬していますが、それ以外の場合はこれを行うことはできません）。これにより、非常に高速なLALRパーサーが生成されます。欠点：文法をLALR互換にする必要があります。他のCプログラムを拡張するのと同じ方法で、Cコードを記述することにより、「ルール」を拡張する必要があります。これはJavaScriptIMHOを作成するよりもそれほど悪くはないように見えますが、ルールははるかに高速に実行される可能性が高く、これを検討している規模ではこれが重要になります。
GLR解析は、簿記が多いため、LALRよりも必然的に遅くなります。しかし、それは一定の要因にすぎません。これは、LRStarのような高性能エンジンよりも重要な場合があります（たとえば、100倍）。文法を形にするのははるかに簡単であり、文法が複雑でないほどカスタムルールを作成しやすくなるため、問題を起こす価値があるかもしれません。本当に数百万行のコードがある場合、これらのパーサーはせいぜい中速になります。
PEGは基本的にバックトラックです。それは物事を試して、それらが機能しないときにバックトラックする必要があります。それらは、少なくともバックトラックの量だけLALRパーサーよりも遅くなければなりません。文法の整形の問題もあります。
ただし、少し洗練された何かをしたい場合は、構文解析だけでは不十分であることがわかります。その場合、構文解析を最適化する必要はありません。プログラム分析のためにインフラストラクチャを最適化する必要があります。別の方法については、構文解析後の生活に関する私のエッセイを参照してください 。
これまでのところ、JisonとPEG.jsを使用できる2つのジェネレーターを見つけました。それらのどれが私にもっと解析パフォーマンスを与えますか？
私が作成したJavaScriptパーサーライブラリのベンチマークによると、PEG.jsの方が高速であるようです（少なくともChrome / V8では）。
ここでオンラインで実行できます： http ：//sap.github.io/chevrotain/performance/
このベンチマークでは、非常に単純なJSON文法を使用して、より大きく複雑なプログラミング言語の文法ではなく、解析ライブラリのパフォーマンスを比較していることに注意してください。