5

私はForward()pyparsingから要素を理解しようとしています。この単純なBNFがあるとします。

identifier  =
  "a..z,$,_"  <  "a..z,$,_,0..9"  >

package_name = 
  identifier 
  /  ( package_name  "." identifier )

そして、結果として得られるか、再帰から戻らないjava.lang.Stringかのように、単純なパッケージを解析しようとします。java私はこのようにそれを試しました:

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal

identifier=Word(alphas+"$_",alphanums+"$_")
dot=Literal(".")

package_name = Forward()
definition = package_name+dot+identifier
package_name << Group(identifier+ZeroOrMore(definition))

package_name.parseString("java.lang.String")

[['java']]を出力します

from pyparsing import alphas,alphanums, Word, Forward, ZeroOrMore, Group, Literal

identifier=Word(alphas+"$_",alphanums+"$_")
dot=Literal(".")

package_name = Forward()
definition = identifier^package_name+dot+identifier
package_name << definition

package_name.parseString("java.lang.String")

再帰制限に達します

Forwardこのプレースホルダーはどのように機能しますか?

4

1 に答える 1

14

問題はForward、文法にあるのではなく、本質的に制限が早すぎるか、Pyparsingのような素朴な再帰下降パーサーでは決定できない方法で再帰的であることにあります。

あなたはこれを持っています:

package_name = identifier | (package_name "." identifier )

左から右に一致する場合、これは常に単一の識別子に一致し、その後、次のピリオドに一致しようとせずに停止します。identifier最後に一致するように順序を切り替える場合:

package_name = (package_name "." identifier) | identifier

。。。package_name一致するかどうかを判断するために最初に行う必要があるのは、一致するかどうかを判断することであるため、無限に再帰しpackage_nameます。これは左再帰文法であり、Pyparsingのような単純な再帰下降パーサーでは処理できません。Pyparsingは、一致が後続の一致にどのように影響するかを先読みしません。左から右にマッチを試みるだけです。

Forward文法の繰り返し方を変えることで、どのように機能するかの簡単な例を得ることができます。

identifier  = pyp.Word(pyp.alphas+"$_", pyp.alphanums+"$_")
package_name = pyp.Forward()
package_name << ((identifier + '.' + package_name) | identifier)

>>> package_name.parseString("java.lang.String")
[u'java', u'.', u'lang', u'.', u'String'], {})

ここでは、再帰は左側ではなく右側で発生するため、Pyparsingはそれを段階的に一致させることができます。

(ZeroOrMoreの使用は赤いニシンです。このような再帰的な文法を使用する場合は、再帰的な定義によって部分式が複数回一致することがすでに許可されているため、ZeroOrMoreは使用しないでください。しかし、私のコメントでは、この種の文法を再帰なしで定義する方がはるかに簡単です。)

于 2013-01-20T00:17:24.103 に答える