文脈自由文法のためのパーサーの作成

数年前、私はDelphiでPrologインタープリターを書くつもりでした。 パーサーを作成することから始めることにしました。 Prolog専用のアナライザーを書くことは私にとって非常に複雑に思えたので、ユニバーサルアナライザーとそのためのProlog構文を書く方が簡単でした。 まあ、それはすべて非常に複雑で長いため、私はこの考えを捨てました。 しかし、パーサーは残りました。 ここでは、スペルについて説明します。



目的 ： 文脈自由文法をサポートするパーサーを作成します 。 また、パーサーは、分析プロセスでいくつかのアクション（たとえば、解釈に関連付けられている）を実行できます-いわゆる。 パーサーの「ユーザー部分」。



この方法で構文をメモリに保存します。構文解析の開始元となる非構文の初期構文があります。 また、各記号*に、この記号の後に分析を続行するための記号のリストを持たせます。 リストが空の場合、分析は正常に完了したと見なすことができます。

*構文文字には、端末と非端末の2種類があります

図 1

再帰アルゴリズムでは、各反復は1つの用語では機能しませんが、現在の用語のリストでは機能します 。



:



, :

.. , ;

;

;

:

.. , :

.... ;

.... ;

.... // " "

.... ,

...... , ;

.... ;

.. ;

:

.. ;

.. :

.... ;

.... // " "

.... ,

...... , ;

.... ;

.. ;

;

// ,

;

, , .







（直感的な人間の言語を使用しています...またはその主題に関する即興演奏）



分析が失敗した場合、テキストの最後までの最初の構文エラーの一部のみがソーステキストから残ります。 いくつかのエラーの検索を実装するには、1つの簡単なことを行うだけで十分です：ユーザーパーツからシステムコマンドの実行を削除し、エラーメッセージを表示し、解析結果をインターセプトし、「失敗」から「成功」に変更することを確認します。



ユーザー部分の詳細：

1. そのような文字を作成する必要があるので、英語の文字または数字の文字列です。 これは、30の異なる用語でエンコードする必要があります（難しい/長い）。 これを回避するには、パーサーの「ユーザー部分」で単純な文字列チェックを行い、予備の解析結果をチェック結果に変更するだけで十分です。
2. また、ユーザー部分では、システム言語コマンドの実行（解釈時）を提供することができます。たとえば、Brainfuck言語構文がモデル化され、テキストに「+」文字が見つかった場合、ユーザー部分は現在のセルの値を1つ増やします。

それはすべて書くことです。このアルゴリズムを実装して試してみてください。



これについては、Wikipediaの記事Syntactic Analysisで読むこともできます。



PS ここには、ソースコード（Delphi上の）とパーサーDLLを含むアーカイブがあり、Delphiのプロジェクトとしてのインポートがあり、ここにテストプログラムがあります。 構文をテキスト形式で記述し（その方法はreadme.txtに記述されています）、その入力行を解析できます。 表示される入力ウィンドウは、パーサーのユーザー部分を模倣します。フィールド内のテキストは、分析されたテキストの残りの部分（ユーザー部分で変更可能）、テキストの上のリテラル（ある場合）、見出し-TrueまたはFalse-架空（つまり、ユーザー部分）現在の用語の分析結果はそれぞれ成功または失敗であり、ボタンOKとキャンセルはユーザー部分によって返された用語の分析の将来の結果です。 最後に、エラーの音または構文解析の結果を示す情報ウィンドウの音が再生されます。 入力フィールドの入力行も変更されます。



編集 ：現実に応じて記事を編集しました。