powershellでパーサコンビネータ

JavaScriptでパーサコンビネータのコンセプトを理解するが、とても良記事だったので、powershellで写経した。

これを理解すると

• クロージャがある言語ならパーサが簡単に書ける
• その言語の知識内で実装できるので、パーサのための新たな構文を覚える必要がない
• パーサを拡張しやすい

っとパーサの作成がとても身近に感じられるようになる。

なお、なぜpowershellかというと、固定長文字列を分解する良い方法(Perl,Ruby,Pythonの unpack のようなこと)がないかなあと思ったときにちょうどこの記事のことを思い出したからである。
例えば、それ用のパーサを定義すれば

  $x = $target[0..(0+4-1)]
  $y = $target[4..(4+3-1)]

なんて書かずに

  & seq (setvar x (tokenN 4)) `
        (setvar y (tokenN 3)) `
        $target 0

などと書けるのである。なんかLispっぽい。setvar や tokenN の実装は示さないがここでは、イメージをつかめてもらえれば良い。ただし、実際に数十桁、数百行ある固定長文字列をパースさせたところ非常に遅かった。これは追求はしていないが、パーサコンビネータではなくpowershell v2もしくはpowershellそのものの問題だと思う。

速度面以外でも、powershell でこの手のことをやってあーこの言語には向いてないなっと思った。
でも、

  $target |
    setvar x (tokenN 4) |
    setvar y (tokenN 3)

こんな風に書けるようかっこ良くインタフェースを設計するのも面白そう。

そんな夢を見つつ、以下、元記事のソースの写経である。長いが内容に関しては元記事がすばらしくわかりやすいのでそちらを参照してほしい。

function token {
  Param($str)

  $len = $str.Length

  return {
    Param($target, $position)

    if ($target.Length -ge ($position + $len) -and $target.Substring($position, $len) -eq $str) {
      return @($true, $str, ($position + $len))
    } else {
      return @($false, "", $position)
    }
  }.GetNewClosure()
}

# & (token 'foobar') 'foobar' 0 # => (True, 'foobar', 6)
# & (token 'foobar') 'foobar' 1 # => (False, '', 1)

function many {
  Param($parser)

  return {
    Param($target, $position)
    $result = [Collections.ArrayList]@()

    for (;;) { 
      $parsed = & $parser $target $position

      if ($parsed[0]) {
        $result.Add($parsed[1]) | Out-Null
        $position = $parsed[2]
      } else {
        break
      }
    }

    return ($True, (-join $result), $position)
  }.GetNewClosure()
}

# & (many (token 'hoge')) 'hogehoge' 0 # => (True, ('hoge', 'hoge'), 8)
# & (many (token 'hoge')) '' 0   # => (True, '', 0)

function choice {
  $parsers = $args

  return {
    Param($target, $position)

    for ($i = 0; $i -lt $parsers.Length; $i++) {
      $parsed = & $parsers[$i] $target $position
      if ($parsed[0]) {
        return $parsed
      }
    }

    return ($false, '', $position)
  }.GetNewClosure()
}


# $parse = many (choice (token 'hoge') (token 'fuga'))
#
# & $parse '' 0           # => (True, '', 0)
# & $parse 'hogehoge' 0   # => (True, ('hoge', 'hoge'), 8)
# & $parse 'fugahoge' 0   # => (True, ('fuga', 'hoge'), 8)
# & $parse 'fugafoo' 0    # => (True, 'fuga', 4)

function seq {
  $parsers = $args

  return {
    Param($target, $position)

    $result = [Collections.ArrayList]@()
    for ($i = 0; $i -lt $parsers.Length; $i++) {
      $parsed = & $parsers[$i] $target $position

      if ($parsed[0]) {
        $result.Add($parsed[1]) | Out-Null
        $position = $parsed[2]
      } else {
        return @($false, '', $position)
      }
    }
    return @($true, (-join $result), $position)
  }.GetNewClosure()
}

# $parse = seq (token 'foo') (choice (token 'bar') (token 'baz'))
#
# & $parse 'foobar' 0  # => (True, ('foo', 'bar'), 6)
# & $parse 'foobaz' 0  # => (True, ('foo', 'baz'), 6)
# & $parse 'foo' 0     # => (False, '', 3)

function option {
  Param($parser)

  return {
    Param($target, $position)

    $result = & $parser $target $position

    if ($result[0]) {
      return $result;
    } else {
      return ($true, '', $position)
    }
  }.GetNewClosure()
}

# $parser = option (token 'hoge')
#
# & $parser 'hoge' 0 # => (True, 'hoge', 4)
# & $parser 'fuga' 0 # => (True, '', 0)

function regex {
  Param($regexp)

  if ($regexp -is [String]) {
    $regexp = New-Object Regex ($regexp)
  }

  if (! $regexp.ToString().StartsWith("\G")) {
    $regexp = New-Object Regex (("\G" + $regexp.ToString()), $regexp.Options)
  }

  return {
    Param($target, $position)

    $regexResult = $regexp.Match($target, $position)

    if ($regexResult.Success) {
      $position += $regexResult.Length;
      return ($true, $regexResult.Value, $position)
    } else {
      return ($false, "", $position)
    }
  }.GetNewClosure()
}

# $parser = regex "hoge"
#
# & $parser 'hoge' 0 # => [true, 'hoge', 4]を返す

# $parser = regex ([regex]"([1-9][0-9]*)")
#
# & $parser '2014' 0 # => (True, '2014', 4)
# & $parser '01' 0   # => (False, '', 0)

なお、元記事の lazy の実装で止まっているが、これはpowershellのクロージャがなんかおかしいのかバグっているのか実装できなかったからである。
これは、以下のクロージャのサンプルが"BAR"ではなく"FOO"を表示してしまうことに起因している。

& {
  $foo = "FOO"

  $bar = {
    Write-Warning $foo
  }.GetNewClosure()

  $foo = "BAR"

  & $bar
}

powershellのGetNewClosure()は今ひとつ理解できない挙動をする。(powershell v4, v5 で確認)

追記: powershellのクロージャを理解するにpowershellのクロージャが普通と異なる点について記載した