5

用語が間違っている場合はご容赦ください。おそらく、私が欲しいものを説明する「正しい」言葉を手に入れるだけで、自分で答えを見つけるのに十分です.

私は ODL (オブジェクト記述言語) のパーサーに取り組んでいます。これは、NASA PDS (Planetary Data Systems; NASA がデータを公開する方法) だけが使用している難解な言語です。幸いなことに、PDS は最終的に XML に移行していますが、締め切り直前に落ちたミッションのために、まだソフトウェアを作成する必要があります。

ODL は、次のような方法でオブジェクトを定義します。

OBJECT              = TABLE
  ROWS              = 128
  ROW_BYTES         = 512 
END_OBJECT          = TABLE

私はパーサーを で書こうとしてpyparsingいますが、上記の構造にたどり着くまではうまくいっていました。

OBJECT 行の右側の値が END_OBJECT の RHV と同じであることを保証できるルールを作成する必要があります。pyparsingしかし、それをルールに入れることはできないようです。両方が構文的に有効な値であることは確認できますが、余分な手順を実行して値が同一であることを確認することはできません。

  1. これが文脈依存の文法であるという私の直感は正しいですか? これは、この問題を説明するために使用すべきフレーズですか?
  2. これが理論的な意味でどのような種類の文法であっても、pyparsingこの種の構造を処理できますか?
  3. それを処理できない場合pyparsing、それを処理できる別の Python ツールはありますか? ( /plyの Python 実装) はどうですか?lexyacc
4

2 に答える 2

6

これは実際には文脈依存言語の文法でwcwあり、w が (a|b)* にある場所として古典的に抽象化されています (反転を示す は文脈自由でwcw'あることに注意してください)。'

構文解析式文法は、セマンティック述語を使用して wcw タイプの言語を構文解析できます。PyParsing はまさにこの目的のためにヘルパー メソッドmatchPreviousExpr()とヘルパー メソッドを提供します。matchPreviousLiteral()

w = Word("ab")
s = w + "c" + matchPreviousExpr(w)

したがって、あなたの場合、おそらく次のようなことをするでしょう

table_name = Word(alphas, alphanums)
object = Literal("OBJECT") + "=" + table_name + ... +
  Literal("END_OBJECT") + "=" +matchPreviousExpr(table_name)
于 2013-02-27T04:23:25.257 に答える
3

原則として、パーサーはコンテキストフリーの解析エンジンとして構築されます。コンテキスト依存性がある場合は、解析後 (または少なくとも関連する解析手順が完了した後) に移植されます。

あなたの場合、文脈自由文法規則を書きたいとします:

  head = 'OBJECT' '=' IDENTIFIER ;
  tail = 'END_OBJECT'  '=' IDENTIFIER ;
  element = IDENTIFIER '=' value ;
  element_list = element ;
  element_list = element_list element ;
  block = head element_list tail ;

head と tail の構成要素が一致する識別子を持っているかどうかのチェックは、技術的にはパーサーによって行われません。

ただし、多くのパーサーでは、構文要素が認識されたときに、多くの場合、ツリー ノードを構築する目的で、セマンティック アクションを実行できます。あなたの場合、これを使用して追加のチェックを有効にします。elementについては、 IDENTIFIERが既にブロック内にあるものと重複していないことを確認する必要があります。これは、検出された各要素に対して、対応するIDENTIFIERを取得し、ブロック固有のリストを作成して重複チェックを有効にする必要があることを意味します。ブロックの場合、先頭の *IDENTIFIER*をキャプチャし、それが末尾の*IDENTIFIER*と一致することを確認します。

これは、解析を表すツリーを構築し、ツリーのさまざまな場所にさまざまな状況依存の値をぶら下げる場合に最も簡単です (たとえば、head節のツリー ノードに実際のIDENTIFIER値を付加します)。テールコンストラクトのツリー ノードを構築している時点で、ツリーをたどり、ヘッドツリーを見つけて、識別子を比較するのは簡単です。

これは、ツリー全体が最初に構築され、次にツリーに対する後処理パスがこのチェックに使用されると想像すると、より簡単に考えることができます。実際、怠け者はこのようにしています :-} 私たちがしているのは、後処理ステップで実行できる作業を、セマンティック アクションに関連付けられたツリー構築ステップにプッシュすることだけです。

これらの概念はいずれも Python 固有のものではなく、PyParsing の詳細は多少異なります。

于 2013-02-27T03:47:58.563 に答える