プログラミング言語の構文解析用のCKY

Question

プログラミング言語の構文解析にCKYチャート解析アルゴリズムを使用することをお勧めします（自然言語の構文解析に主に使用されていることがわかっています）。

Answer 1

CKYは任意のコンテキストフリー言語を解析できますが、時間の複雑さは代替案に比べてあまり大きくありません。 CKYでは、文法のサイズを爆破させてランニングタイムを傷つける可能性があるChomsky Normal Formに文法が必要です。素早く汚れたパーサーにとっては大丈夫ですが、大きな入力や複雑な文法にスケールアップしようとすると問題に遭遇します。

比較的簡単に実装できる理解可能な構文解析アルゴリズムを探している場合は、構文解析文法（PEG）をご覧ください。彼らは、文脈自由言語の大きなサブセットと、限られた文脈感度を有するいくつかの言語を認識することができる。動作しているPEGパーサーがあれば、memoizationを追加するのは簡単です。これは、線形時間で実行されるPackrat Parserを提供します。左回帰文法を可能にするためのPEGs、Packrat、およびthis extensionの学術論文はすべて理解可能です。