4

最近、パーサーではなく文法pyparsingを書くことによってデータを解析するための素晴らしいツールであるpython モジュール を発見しました。私は文脈自由文法の考え方に慣れていないので、この質問の誤った仮定を修正してください。

Pyparsing は、BNF ( Backus–Naur Form ) 文脈自由文法を実装できます。この文法は再帰的である可能性がありますが、前方参照を持つことはできますか? この質問に出くわして以来、これに対する答えについて疑問に思っていました。具体例を挙げましょう。次の文字列を考えてみましょう。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

文法を次のようにします。

<number> :: __<digit>__
<block>  :: <number>(x) (<number> <number> <number> .... x times)

つまり、最初の数値トークンを読み取り、それを名前を付けて保存してxから、次の数値を消費してxそれらをグループ化します。解析された行は次のようになります。

 [[1, 2], [3, 4, 5, 6], [7, 8, 9, 10, 11, 12, 13, 14], [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

私はpyparsingを使用しない単純なpython MWEを書いたので、私がやろうとしていることは明らかです:

A = range(1,31)

B, sub_b = [], []
consume  = 0

for a in A:
    if consume: 
        sub_b.append(a)
        consume -= 1
    else:
        if sub_b: B.append(sub_b)
        sub_b = [a,]
        consume = a
B.append(sub_b)
print B

2 つの (関連する) 質問: これは BNF 文脈自由文法で実行できますか? はい/いいえの場合、どうすればできpyparsingますか?

4

3 に答える 3

3

文脈自由文法や通常の文法には、パラメータ化されたサイズのようなものはありません。あなたのような数値パラメータconsumeは CFG モデルの一部ではなく、別の方法で効果を得ることは不可能であることを証明できます。ただし、任意の固定長のプロダクションを作成できるため、長さ 1、長さ 2、長さ 3 などのブロックのプロダクションを作成できます。

<block3> :: <number> <number> <number>

または、同様に、プレフィックスまたはポストフィックスとして長さを一致させます。

<block3a> :: 3 <number> <number> <number>
<block3b> :: <number> <number> <number> 3

などです。したがって、やりたいことを行うには、そのような規則を含む文法が必要なだけですN。

特定の CFG には、有限数のこれらのプロダクションのみが含まれます。プレフィックスとしてもポストフィックスとしても、無制限のパラメーター化されたサイズを処理できる CFG (BNF またはその他の形式) を作成することは数学的に不可能です。実際には、必要に応じて新しいプロダクションで CFG をオンザフライで更新できる場合があります。たとえば、数字を読んで、まだ存在しない場合は文法Nのルールを作成します。blockNしかし、パラメーター化された無制限のサイズをキャプチャできる単一の CFG はありません。

文脈依存の文法についても尋ねたので、編集してください。それでもうまくいきません。問題は、文法のクラスではなく、整数演算の使用です。チョムスキー階層の形式言語は有限数の記号 (トークン) で定義され、無限に多くの整数であるため、明確な意味を割り当てることはできません (解析手順は整数演算に依存していることに注意してください)。

長さを前処理して同じ数の星 ( ) のシーケンスにする場合* * * 4 7 10、CFG パーサーは自明です。

<group> :: * <group> <number>
<group> :: * <number>

これはまさにいわゆるa^n b^n言語です。「10」などを意味する記号を使用することもできます。ただし、前処理を行わない場合、唯一の解決策 (および手順またはチューリング マシンが実際に行うこと) は、文法の数字表記を解釈することです。たとえば、"21" をテン テン ワンとして解析します。これが CFG で実行できるかどうかは疑問ですが (問題は、数百万、数十億などの個別のルールなしで任意に長い数字を処理することです)、よくわかりません。いずれにせよ、実際の整数を使用する方がはるかに簡単であるため、学術的な演習としてのみ興味深いものです。整数を使った形式言語の性質を研究した人はいると思いますが、それについては何も言えません。

于 2012-04-05T15:38:38.490 に答える
3

Pyparsing には、countedArrayあなたが求めていることを正確に実行するヘルパーが含まれています。これは引数を 1 つ取り、expr整数の後に expr の「n」個のインスタンスが続くものを解析します。入力文字列については、次のように記述できます。

from pyparsing import *
from pprint import pprint

# make a long string of integers, starting at 0
source = ' '.join(map(str, range(50)))

# define an integer as a 'word' of numeric digits
integer = Word(nums)

# add a parse action to convert the parsed strings to integers, at parse time
integer.setParseAction(lambda t:int(t[0]))

# parse the source string into counted strings of integers, and print out
# with pprint
lists = OneOrMore(countedArray(integer)).parseString(source)
pprint(lists.asList())

プリントアウト:

[[],
 [2],
 [4, 5, 6],
 [8, 9, 10, 11, 12, 13, 14],
 [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

  • 添付された解析アクションintegerは、数値文字列を整数に戻します (リスト内の数値を引用符で囲みません)。

  • ソース文字列の先頭の「0」によって作成された最初の空のリストに注意してください。

  • ソース文字列には 30 を超える数が含まれていますが、別のカウントされた配列には十分ではありません。

countedArray先頭の整数に一致する式を作成し、その後にキャプティブ未定義の Forward 式を続けることで、このトリックを実現します。先頭の整数に付加された解析アクションexpr*nは、キャプティブ Forward に式を挿入し、次に続く「n」個の expr を解析します。簡単に記述countedArray(Word(alphas))して解析"4 the quick brown fox"して を取得でき['the', 'quick', 'brown', 'fox']ます。@Aaronが彼の答えで指摘しているように、返されたリストのlenを取得することで簡単に取得できるため、先頭のカウンターを保持する必要はありません。

pyparsing は、FollowedBy および NotAny コンストラクトを使用した、より伝統的な先読みもサポートしています (NotAny は、'~' 演算子を使用して省略できます)。Word(alphas) + FollowedBy(Word('aeiou',alphas))この文字列「4 スコアと 7 年前...」では、「スコア」と「年」に一致するを使用して、母音で始まる単語が後に続く文字列を選択できます。または、 を使用してピリオドが後に続かない単語はWord(alphas) + ~Literal('.')、「ago」以外のすべての単語に一致します。この場合、一致する入力文字列を検索しようとすると、searchStringorscanStringの代わりに使用しますparseString。

于 2012-04-06T03:03:17.953 に答える
1

あまり。

文法を持つことの要点は、人間が理解できる方法でデータを定義できるようにすることです。デモ文字列は読み取り可能ですが、なぜ?1以外の何かを意味するの3ですか?

あなたの場合の正しい入力は次のようになります。

[[2], [4, 5, 6], [8, 9, 10, 11, 12, 13, 14], [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]]

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

<model> :: <term>
<list>  :: <term> | <term> <opt-whitespace> <list>
<term>  :: '[' <list> ']'

次に、リストの長さを調べることで、不足しているカウント要素を回復できます。

于 2012-04-05T15:46:26.613 に答える