CKY チャート解析アルゴリズムを使用してプログラミング言語の構文を解析することは良い考えですか (自然言語の構文を解析するために主に使用されることを知っています)?
1 に答える
3
CKY は任意の文脈自由言語を解析できますが、時間の複雑さは他の言語に比べて大きくありません。CKY では、文法がチョムスキー標準形である必要があります。これにより、文法のサイズが大きくなり、実行時間も長くなる可能性があります。これは、迅速で汚いパーサーにとっては問題のないアプローチですが、より大きな入力や複雑な文法にスケールアップしようとすると問題が発生します。
比較的簡単に実装できるわかりやすい構文解析アルゴリズムを探している場合は、Parsing Expression Grammars (PEG) を参照してください。文脈自由言語の大部分のサブセットに加えて、文脈依存性が制限された一部の言語を認識することができます。動作する PEG パーサーがあれば、簡単にメモ化を追加できます。これにより、線形時間で実行される Packrat パーサーが得られます。PEGs、Packrat、および左再帰文法を可能にするこの拡張機能に関する学術論文はすべて非常に理解できるものです。
于 2012-04-29T17:54:29.390 に答える