1

この質問が一部の人にとって明らかである場合はご容赦ください。しかし、私はインタープリターの書き方を独学しようとしています。私はPythonでこれをやっています.Lexerはすでにプログラムされています.

作成されたトークンのリストを取得しましたが、解析ツリーの構築で行き詰まっています。ここからどこへ行くべきかについてはある程度の考えがありますが、正しく考えているかどうかはわかりません。

これは、正規表現を使用した単純な算術式の文法で定義した構文です。

<a_expression> = <identifier | number> <operator> <identifier | number>

しかし、パーサーがレクサーからこのパターンに一致するトークンのストリームを受け取った場合:

<identifier | number> <operator> <identifier | number> <operator> <identifier | number>

2 つのオペランドではなく、2 つの演算子と 3 つのオペランドがあるため、これを解析するにはどうすればよいですか?

さらに、n 個のオペランドと n-1 個の演算子をどのように処理すればよいですか? これは再帰的に行うべきだと思いますが、さまざまなタイプの式に対してさらにパーサーを定義する必要があるかどうか、またはここからどこへ行くべきかはわかりません。n 個のオペランドと n-1 個の演算子のパターンを正規表現と一致させることはできますか?

4

3 に答える 3

3

今日の「正規」表現は正規言語の土地に厳密に追いやられているわけではありませんが、やろうとしていることを行うには、より強力なツールが必要であることがわかります。

Context-Free Grammars は必要なものであり、Python で CFG を作成するためのツールがいくつかあります。最も注目すべきはpyparsingですが、調べることができる Pysec と呼ばれる Haskell の Parsec ライブラリのポートもあります。

于 2013-09-12T20:47:23.210 に答える
2

正規表現が構文を解析するのに適しているかどうかは、構文 (つまり、文法) も規則的か、別のチョムスキー クラスかによって異なります。

タイプ 0 (制限のない) 文法の場合、チューリング マシンが必要になります。

タイプ 1 (状況依存型) の場合、線形境界付きオートマトン (または上記のいずれか) が必要になります。

タイプ 2 (コンテキストフリー) の場合、プッシュダウン オートマトン (または上記のいずれか) が必要になります。

また、正規表現 (または上記のいずれか) で読み取ることができるのは、タイプ 3 (正規) のみです。

ウィキペディアなどでさらに読み物を見つけることができます。

于 2013-09-12T20:47:12.407 に答える
2

優先順位のある中置演算は通常の言語ではありません。正規表現は、正規言語の解析にのみ適しています。(現代の正規表現の実装は実際には単なる正規表現ではなく、実際にはほとんどの文脈自由言語を解析できます…しかし、それらのいくつかは指数関数的に時間がかかり、どの言語かを予測するのは自明ではありません。)

しかし、それは文脈自由言語です。簡単な説明については、文脈自由文法に関するウィキペディアの記事を参照してください。文脈自由文法は、通常の言語と文脈自由言語の両方の構文解析に適しています。

ただし、正規ではない多くの言語は、CFG の全機能を必要としません。

2 つの重要なクラスは、(線形時間で) LLまたはLR解析可能なクラスです。(これらのバリアント、特に LALR と SLR も重要です。) たとえば、Python は LL(1) パーサーによって解析できます (少なくともリファレンス実装では解析されます)。

あなたの言語は、LR(1) のさらに制限的なサブセットであるOPに適合します。実際、その名前が示すように (「OP」は「Operator Precedence」の略です)、これはパラダイム ケースです。また、OP パーサーは、より一般的なパーサーよりもはるかに簡単に手動で記述できます。したがって、カスタム パーサーをゼロから作成する場合は、おそらくここで使用したいと思うでしょう。

于 2013-09-12T20:54:49.953 に答える