誤ってチューリング完全な解析ライブラリを作成してしまった

私は現在、C++ 解析 DSL ライブラリである lexy に取り組んでいます。入力を解析する方法を説明すると、lexy はそのコードを生成し、エラー回復、解析ツリーの生成、および解析値を処理します。このようなパーサー ジェネレーターは、以下に基づいて分類されます対応する形式言語の表現力。たとえば、厳密な正規表現は、決定論的文脈自由言語の厳密なサブセットである正規言語のみを解析できます。

lexy は、本質的に (手動で指定された!) 任意の先読みを持ち、他の状態を持たない再帰降下パーサーの構文糖衣であり、後者のカテゴリに分類されます。そのカテゴリのパーサーは、タグが一致する XML などのコンテキスト依存言語を解析できません。それらを処理するために、「コンテキスト変数」のサポートを追加しました:解析中に変更できる状態です。

しかし、コンテキスト変数の実装の最近のリファクタリングで、私は誤って大きな制限を削除してしまいました。これにより、lexy Turing-complete が作成されました。したがって、パーサーは入力の解析中に任意の計算を行うことができます。

TL;DR: 実行できる字句文法を書きました 、parse だけではありません 、単純なチューリング完全言語です。

lexy のコンテキスト変数

XML パーサーの例として、コンテキスト変数を lexy に追加しました。XML タグには開始タグと終了タグがあり、同じでなければなりません:

01

これを解析するには、開始タグを解析し、それが何であったかを思い出し、終了タグがあるときにそれを比較する必要があります。これは、従来の文脈自由文法では不可能です。同様に、「<」のようなものは解析できません。コード>09 a、次に 19 b、次に 28 カウントを覚えて 2 回「読む」方法がないためです。

lexy のコンテキスト変数がそれを可能にします。たとえば、31 本質的には 41 です 解析中に変更できます:作成して値に初期化し、入力を消費しながらインクリメント/デクリメントできます.これにより、上記の言語を解析できます:

10

このプロダクションは、55 用に 1 つずつ、計 3 つのカウンターを作成します。 、69 に 1 つ 、および 74 用に 1 つ .次に、遭遇するすべての文字のカウンターをインクリメントしながら、文字を繰り返し解析します.最後に、それらがすべて等しいことをアサートします.

私が最初にコンテキスト変数を実装したとき、それらは単一のプロダクションに対してローカルでした:プロダクション内で作成されたすべての変数は、プロダクションの外からアクセスできません.これにより、コンテキスト変数を再帰と組み合わせることができなくなりました.

しかし、コンテキスト インターフェイスの最近のリファクタリング中に、コンテキスト変数のストレージをグローバル コントロール ブロックに移動しました。これは、すべての子プロダクションで使用できるようになったことを意味します!

知らず知らずのうちに、レクシー文法をチューリング完全にしてしまいました。 プログラミング言語ですが、実行 直接!

WHILE プログラミング言語

実際のプログラミング言語に実際に似ている単純なチューリング完全言語を考えてみましょう:WHILE.それは (無限の) 符号なし整数変数 85 、定数の加算/減算、および while ループ。チューリング完全性にはこれで十分ですが、便宜上、if ステートメントも付けましょう。

EBNF 文法は次のようになります:

28

それだけです。変数から定数を代入、加算、または減算することしかできないことに注意してください。他の変数ではありません。これにより、94 などの単純なタスクが作成されます。 非常に面倒ですが、可能です:

32

すべての変数が符号なし整数であるため、上記のコードは機能します。

前述のように、WHILE はチューリング完全です。無限に多くの変数が与えられた場合、計算可能なすべての計算に使用できます。ここでは証明しませんが、説明のために、n 番目のフィボナッチ数を計算するプログラムを次に示します。 /P>

40

lexy grammar でそれを実行してみましょう。

WHILE の実行:変数

WHILE を lexy で実行するには、すべての変数の値を保存する必要があります。おそらくご想像のとおり、107 を使用しています。 このアプローチには、解決する必要がある 2 つの問題があります。

まず、コンテキスト カウンターの「名前」が型によって与えられます。必要な場合は 117 変数、120 を作成する必要があります 特に、無限またはユーザー定義の変数はサポートできませんが、文法で指定された有限セットのみをサポートします。

これにより、WHILE はチューリング完全ではなくなりますが、問題ありません。チューリング完全性には無限のメモリが必要ですが、コンピューターは有限です。制限は固定されていますが任意であるため、コンパイル中に十分な忍耐力があれば、任意に大きくすることができます。

コードでは、変数のテンプレートを使用します:

58

2 番目の問題は、134 の方法です。 変更可能:144 があります 、それを 1 ずつインクリメント/デクリメントし、156 、ルールによって消費される文字数を加算/減算します。

WHILE では、変数は 10 進数で指定されます。これは、168 の一致する数値を実行しながら、最初に (何らかの方法で) 読み取りを 10 進数に変換する必要があることを意味します。 可能ですが、非常に面倒です。

より実用的な解決策は、単項数字に切り替えることです。 183 で構成されています 196 を使用できます

61

これは明らかに、WHILE のチューリング完全性には影響しません。

数値の解析は、0 個以上の 209 を解析するのと同じくらい簡単です。 文字:

73

WHILE の実行:変数ステートメント

3 つの「変数ステートメント」 213227 、および 236 変数名に応じて異なるコンテキスト カウンターを変更する必要があります。これは、単一のプロダクションではなく、プロダクション テンプレートがあることを意味します。

89

ステートメントの実際の本文は、244 を変更する必要があります。 したがって、加算と減算は 250 に直接マップされます と 262 :

99

割り当てはよりトリッキーです:272 を使用できます 変数が現在ゼロの場合のみ。変数をリセットするには、ゼロでない限りカウンターをデクリメントするループを使用します:

107

すべてをまとめると、完全な製品ができあがります:

114

WHILE の実行:If ステートメント

変数ステートメント 282 と同様 ステートメントも変数名でテンプレート化する必要があります。292 を呼び出します。 それに応じて分岐します。変数名がゼロの場合、if をスキップし、else があれば実行します。それ以外の場合は、if を実行し、else をスキップします。

if/else の本体は、中かっこで囲まれたステートメントのリストです。それを実行するには、それらを解析する必要があります:300 で見られるように 、入力を解析すると、それに応じてカウンターが変更されます。lexy には角かっこで囲まれたもののリストのサポートが組み込まれているため、これは簡単です:

129

ステートメントを実行せずにスキップするには、カウンターに触れることなく、ステートメントを解析するだけの別のバージョンのプロダクションを追加するだけです。代わりに、私は別のアプローチを選択しました。開き括弧と閉じ括弧が同じ数になるまで、入力を破棄する必要があります。これは 318 です。 実際には以下のために設計されました:

134

変数 320 の if ステートメント 次に、変数カウンターの値に基づいて正しいバージョンを選択します:

146

WHILE の実行:While ステートメント

while ステートメントの解析は if:we branch on 335 に似ています 本文をスキップするか、実行します。ただし、ループの本文を実行した後、再度実行する必要がある場合があります!

これは、本体を実行するときに、入力を while ループの先頭に巻き戻して再試行する必要があることを意味します.lexy has 348 そのために:ルールを解析しますが、入力を消費しません。ただし、358 コンテキスト変数へのアクセスを提供しません!

これは技術的な制限ではありません。 361 の実装を簡単に変更できました コンテキスト変数を内部ルールに転送します.WHILE インタープリターをサポートする以外に理由はありません.そのため、これは、例のカスタムルールを記述する必要がある唯一のケースです.372 382 を解析します コンテキスト変数にアクセスし、入力を元の実装に巻き戻します。

そのため、while ステートメントの実行は簡単です。

159

WHILE の実行:プログラム

すべてをまとめると 391 です 405 にディスパッチするだけのプロダクション 、 418 、および 427 さまざまな変数、およびトップレベルの 434 production.後者はすべての 440 を作成する必要があります オブジェクトと解析 451 ファイルの終わりに到達するまで s.その後、465 の値を取得します。 変数にして結果として返します。

165

これで、ファイルを入力として読み取って解析し、プログラムを実行できます:

179

完全なコードはこちら:

470 を明示的にビルドする必要があります テンプレートのインスタンス化の数が多いため、しばらく時間がかかります (私のラップトップでは 15 秒)。

結論

これは役に立ちますか?

それどころか、チューリング完全言語には問題があります。たとえば、字句文法は無限ループを作成する可能性がありますが、これは現在、一般的なケースでは検出できません。WHILE のおかげで、停止問題に帰着します。

ただし、lexy にはすでに無限ループがありました:

186

これは、字句文法が実際には宣言型ではないためです。それらは、すべてがどのように解析されるか、いつ、どのようにバックトラックする必要があるか、およびどのような順序で代替を試行するかを正確に指定する必要がある、手書きのパーサーの構文糖衣です。

チューリング完全性には 481 の使用が必要です これは簡単に監査できます。一般に、より一般的な入力を解析し、後で検証することで、ルールの使用を避けることをお勧めします。これにより、より適切なエラー メッセージとエラー回復が可能になります。

私はチューリング完全なルールを計画していませんでしたが、それを導入したリファクタリングを元に戻すつもりはありません:今ではよりクリーンでシンプルな実装になっています. .

解析中に実際に複雑なことをする必要がある場合は、 494 を使用することをお勧めします このルールにより、一部のプロダクションを手動で解析できます。こちらの例をご覧ください。

付録:WHILE での素数テスト

次のコードは、単純なプライム テスターのメイン ループを WHILE で実装します。これは、lexy で実行できる単項数を含む変更された構文を使用します。

197