regex - 通常対 LALR(1): どちらが速いか

Question

同じ言語を定義する 2 つの文法があるとします: 通常の文法と LALR(1) の文法です。

通常のアルゴリズムと LALR(1) アルゴリズムはどちらも O(n) で、n は入力長です。

正規表現は通常、正規言語の解析に好まれます。なんで？それらがより高速であるという正式な証拠はありますか（またはそれは明らかです）？

Answer 1

解析と認識には大きな違いがあります。正規言語パーサーを構築することはできますが、ほとんどの有用な言語は有用で明確な正規文法では解析できないため、非常に制限されます。ただし、ほとんどの (すべてではないにしても) 正規表現ライブラリは、おそらく有限数の「キャプチャ」が追加された を認識します。

いずれにせよ、解析はもはやパフォーマンスのボトルネックではありません。IMHO、解析するように見える言語を明らかに解析するツールを使用する方がはるかに優れています。

一方、言語を認識することだけが目的であり、その言語がたまたま正規表現である場合、正規表現ははるかに簡単で、必要なインフラストラクチャ (パーサー ジェネレーター、専用の DSL、やや複雑な Makefile など) がはるかに少なくなります。など）

(通常ではない言語機能の例として、括弧を挙げます。)

Answer 2

書きやすいという理由で、人々は正規表現を好みます。あなたの言語が通常の言語である場合、わざわざ CFG 文法を作成する必要はありません。