3

質問

関数の引数を非厳密 ( by-name で渡す) として宣言する方法はありますか?

これが直接不可能な場合:同様のことを達成するのに役立つヘルパー関数またはデコレータはありますか?

具体例

これは、実験するための少しおもちゃの例です。

1括弧付きの算術式 (簡単にするために、数値を単一のリテラル値に置き換えたもの) の次の古典的な文法に対処できる、小さなパーサー コンビネーター ライブラリを構築したいとします。

num    = "1"

factor = num 
       | "(" + expr + ")"

term   = factor + "*" + term 
       | factor

expr   = term + "+" + expr
       | term

パーサー コンビparseネーターを、トークンのリストと現在の位置を取得し、解析エラーをスローするか、結果と新しい位置を返すことができるメソッドを持つオブジェクトとして定義するとします。(連結) と(代替)ParserCombinatorを提供する基本クラスを適切に定義できます。次に、定数文字列を受け入れるパーサー コンビネーターを定義し、 and を実装します。+|+|

# Two kinds of errors that can be thrown by a parser combinator
class UnexpectedEndOfInput(Exception): pass
class ParseError(Exception): pass

# Base class that provides methods for `+` and `|` syntax
class ParserCombinator:
  def __add__(self, next):
    return AddCombinator(self, next)
  def __or__(self, other):
    return OrCombinator(self, other)

# Literally taken string constants
class Lit(ParserCombinator):
  def __init__(self, string):
    self.string = string

  def parse(self, tokens, pos):
    if pos < len(tokens):
      t = tokens[pos]
      if t == self.string:
        return t, (pos + 1)
      else:
        raise ParseError
    else:
      raise UnexpectedEndOfInput

def lit(str): 
  return Lit(str)

# Concatenation
class AddCombinator(ParserCombinator):
  def __init__(self, first, second):
    self.first = first
    self.second = second
  def parse(self, tokens, pos):
    x, p1 = self.first.parse(tokens, pos)
    y, p2 = self.second.parse(tokens, p1)
    return (x, y), p2

# Alternative
class OrCombinator(ParserCombinator):
  def __init__(self, first, second):
    self.first = first
    self.second = second
  def parse(self, tokens, pos):
    try:
      return self.first.parse(tokens, pos)
    except:
      return self.second.parse(tokens, pos)

これまでのところ、すべて問題ありません。ただし、文法の非終端記号は相互に再帰的に定義されており、考えられるすべてのパーサーの組み合わせのツリーを熱心に展開することはできないため、パーサー コンビネーターのファクトリを使用して、次のようなものにラップする必要があります。

# Wrapper that prevents immediate stack overflow
class LazyParserCombinator(ParserCombinator):
  def __init__(self, parserFactory):
    self.parserFactory = parserFactory
  def parse(self, tokens, pos):
    return self.parserFactory().parse(tokens, pos)

def p(parserFactory):
  return LazyParserCombinator(parserFactory)

これにより、EBNF に非常に近い方法で文法を書き留めることができます。

num    = p(lambda: lit("1"))
factor = p(lambda: num | (lit("(") + expr + lit(")")))
term   = p(lambda: (factor + lit("*") + term) | factor)
expr   = p(lambda: (term + lit("+") + expr) | term)

そして実際に動作します： 

tokens = [str(x) for x in "1+(1+1)*(1+1+1)+1*(1+1)"]
print(expr.parse(tokens, 0))

ただし、p(lambda: ...)すべての行で少し面倒です。それを取り除く慣用的な方法はありますか？無限相互再帰の熱心な評価をトリガーせずに、何らかの方法でルールの RHS 全体を「名前で」渡すことができれば素晴らしいでしょう。

私が試したこと

コア言語で利用できるものを確認しました。「短絡」できるのは と のみの​​ようです。間違っている場合は修正してくださいif。andor

私は、他の非おもちゃの例のライブラリがこれをどのように行うかを調べてみました。

  • たとえば、 funcparserlib は明示的な前方宣言を使用して、相互再帰を回避します ( github README.md サンプル コードのforward_declandの部分を見てください)。value.define

  • いくつかのparsec.py特別な@generateデコレータを使用し、コルーチンを使用したモナド解析のようなことをしているようです。それはすべて非常に素晴らしいことですが、私の目標は、Python で利用可能な基本的な評価戦略に関してどのようなオプションがあるかを理解することです。

のようなものも見つけましたがlazy_object_proxy.Proxy、そのようなオブジェクトをより簡潔な方法でインスタンス化するのに役立たないようです。

では、引数を名前で渡し、相互に再帰的に定義された値の爆発を回避するより良い方法はありますか?

4

2 に答える 2

1

厳密に1 つの名前付き引数を受け入れる必要がある関数の特別なソリューション

f名前で1つの引数を取る必要がある関数を定義したい場合は、 にすることを検討fして@decoratorください。で散らばった引数の代わりにlambdas、デコレーターは関数定義を直接受け取ることができます。

問題のlambdasが表示されるのは、右側の実行を遅延させる方法が必要だからです。ただし、非終端記号の定義をdefローカル変数ではなく s に変更すると、RHS もすぐには実行されません。def次に、これらの s をParserCombinator何らかの方法で sに変換する必要があります。このために、デコレータを使用できます。

LazyParserCombinator次のように、関数を a にラップするデコレータを定義できます。

def rule(f):
  return LazyParserCombinator(f)

次に、各文法規則の定義を保持する関数に適用します。

@rule 
def num():    return lit("1")

@rule 
def factor(): return num | (lit("(") + expr + lit(")"))

@rule 
def term():   return factor + lit("*") + term | factor

@rule 
def expr():   return (term + lit("+") + expr) | term

ルールの右側の構文上のオーバーヘッドは最小限であり (他のルールを参照するためのオーバーヘッドはなく、p(...)-wrappers やruleName()-括弧は必要ありません)、ラムダを使用した直感に反するボイラープレートはありません。

説明：

高階関数 が与えられた場合h、それを使用して他の関数を次のように装飾できます。f

@h
def f():
  <body>

これが行うことは本質的に次のとおりです。

def f():
  <body>

f = h(f)

関数をh返すことに制約されず、ParserCombinator上記の s のような他のオブジェクトを返すこともできます。

于 2018-04-05T20:50:40.067 に答える