Skip to content

Instantly share code, notes, and snippets.

@yumura
Last active August 6, 2016 01:47
Show Gist options
  • Save yumura/94ef4d72a2af011819f838f55ae1bbe4 to your computer and use it in GitHub Desktop.
Save yumura/94ef4d72a2af011819f838f55ae1bbe4 to your computer and use it in GitHub Desktop.
PowerShell で数式パーサーを書きたかった...
$here = Split-Path -Parent $MyInvocation.MyCommand.Path
$sut = (Split-Path -Leaf $MyInvocation.MyCommand.Path).Replace(".Ex.Tests.", ".")
. "$here\$sut"
function json
{
Begin {$w = @()}
Process {$w += ,$_}
End
{
ConvertTo-Json $w -Compress -Depth 20 |
%{
$_ -replace '{"value":', '' `
-replace ",`"Count`":\d+}", ''
}
}
}
filter flatten {if ($_ -is 'Array') {$_ | flatten} else {$_}}
$parser = recd @{
# Expression -> Term (('+'|'-') Term)*
Expression = {seq `
($_.Term)`
(many `
(seq `
(char +-)`
($_.Term)))}
# Term -> Factor (('*'|'/') Factor)*
Term = {seq `
($_.Factor)`
(many `
(seq `
(char */)`
($_.Factor)))}
# Factor -> '(' Expression ')' | Sign Expression | Number
Factor = {choice `
(seq `
(char '(')`
($_.Expression)`
(char ')'))`
(seq `
($_.Sign)`
($_.Expression))`
($_.Number)}
# Sing -> '+'|'-'
Sign = {map {switch ($_) {'+' {'positive'}; '-' {'negative'}}} (char '+-')}
# Number -> ('1'..'9') ('0'..'9')* | '0'
Number = {map {[int]$_} (regex "[1-9]\d*|0")}
}
Describe Sign {
$S = $parser.Sign
It positive {
parse '+' $S | json | Should be '["positive"]'
}
It negative {
parse '-' $S | json | Should be '["negative"]'
}
It none-sine {
try {parse foo $S}
catch {$_ | Should be '位置 0 の解析に失敗しました。'}
}
}
Describe Number {
$N = $parser.Number
It zero {
parse '0' $N | json | Should be '[0]'
}
It non-zero {
parse '5' $N | json | Should be '[5]'
parse '987604321' $N | json | Should be '[987604321]'
}
It non-numeric {
try {parse foo $N}
catch {$_ | Should be '位置 0 の解析に失敗しました。'}
}
}
Describe Arithmetic-Operations {
$E = $parser.Expression
It add-sub {
parse '1+2' $E | json | Should be '[[[1],[["+",[2]]]]]'
parse '3-4' $E | json | Should be '[[[3],[["-",[4]]]]]'
parse '1+2-3+4-5' $E | json | Should be '[[[1],[["+",[2]],["-",[3]],["+",[4]],["-",[5]]]]]'
}
It error-add-sub {
try {parse '1+2+' $E}
catch {$_ | Should be '位置 3 の解析に失敗しました。'}
try {parse '3-4-' $E}
catch {$_ | Should be '位置 3 の解析に失敗しました。'}
}
It mul-div {
parse '1*2' $E | json | Should be '[[[1,[["*",2]]]]]'
parse '3/4' $E | json | Should be '[[[3,[["/",4]]]]]'
parse '1*2/3*4/5' $E | json | Should be '[[[1,[["*",2],["/",3],["*",4],["/",5]]]]]'
}
It error-mul-div {
try {parse '1*2*' $E}
catch {$_ | Should be '位置 3 の解析に失敗しました。'}
try {parse '3/4/' $E}
catch {$_ | Should be '位置 3 の解析に失敗しました。'}
}
It add-sub-mul-div {
parse '1*2+3-4/5' $E | json | Should be '[[[1,[["*",2]]],[["+",[3]],["-",[4,[["/",5]]]]]]]'
parse '1+2*3/4-5' $E | json | Should be '[[[1],[["+",[2,[["*",3],["/",4]]]],["-",[5]]]]]'
}
}
Describe parenthesis {
$E = $parser.Expression
It C_3 {
parse '(1)+(2)+(3)' $E | json | Should be '[[[["(",[[1]],")"]],[["+",[["(",[[2]],")"]]],["+",[["(",[[3]],")"]]]]]]'
parse '(1)+(2+(3))' $E | json | Should be '[[[["(",[[1]],")"]],[["+",[["(",[[2],[["+",[["(",[[3]],")"]]]]],")"]]]]]]'
parse '((1)+2)+(3)' $E | json | Should be '[[[["(",[[["(",[[1]],")"]],[["+",[2]]]],")"]],[["+",[["(",[[3]],")"]]]]]]'
parse '((1)+(2)+3)' $E | json | Should be '[[[["(",[[["(",[[1]],")"]],[["+",[["(",[[2]],")"]]],["+",[3]]]],")"]]]]'
parse '(((1)+2)+3)' $E | json | Should be '[[[["(",[[["(",[[["(",[[1]],")"]],[["+",[2]]]],")"]],[["+",[3]]]],")"]]]]'
}
It error {
try {parse ')1(' $E}
catch {$_ | Should be '位置 0 の解析に失敗しました。'}
try {parse '(1' $E}
catch {$_ | Should be '位置 0 の解析に失敗しました。'}
try {parse '(1+(2' $E}
catch {$_ | Should be '位置 0 の解析に失敗しました。'}
}
}
Describe all {
$E = $parser.Expression
It all {
parse '-1/2+(+3*4)-5' $E | flatten | ConvertTo-Json -Compress | `
Should be '["negative",1,"/",2,"+","(","positive",3,"*",4,")","-",5]'
}
}
# Invoke
# ======
filter Invoke-Parse ([string]$Target, $Parser)
{
trap {break}
$len = $Target.Length
$result, $newPosition = Invoke-Parse-Partial @PSBoundParameters
if ($newPosition -eq $len) {return ,$result}
throw "全 ${len} 文字の解析に失敗しました。位置 ${newPosition} まで解析しました。"
}
filter Invoke-Parse-Partial ([string]$Target, $Parser)
{
trap {break}
$success, $result, $newPosition = Invoke-Parse-Raw @PSBoundParameters
if ($success) {return $result, $newPosition}
throw "位置 ${newPosition} の解析に失敗しました。"
}
filter Invoke-Parse-Raw
{
Param
(
[string]$Target,
[ValidateRange(0, [int]::MaxValue)]
[int]$Position = 0,
$Parser
)
$p = $Parser.Param
& $Parser.Function $Target $Position @p
}
Set-Alias parse Invoke-Parse
Set-Alias parsep Invoke-Parse-Partial
Set-Alias parser Invoke-Parse-Raw
# New
# ===
filter New-Closure($Param, $Function)
{New-Object psobject -Property $PSBoundParameters}
filter New-CharParser([string] $Char)
{
New-Closure @{Char = $Char.ToCharArray()} {
param ([string]$Target, [int]$Position, $Char)
foreach ($c in $Char)
{
if ($Target[$Position] -eq $c) {return $true, $c, ($Position + 1)}
}
$false, $null, $Position
}
}
filter New-TokenParser([string] $Token)
{
New-Closure $PSBoundParameters {
param ([string]$Target, [int]$Position, $Token)
$len = $Token.length
if ($Position + $len -gt $Target.Length)
{return $false, $null, $Position}
if ($Target.Substring($Position, $len) -ne $Token)
{return $false, $null, $Position}
$true, $Token, ($Position + $len)
}
}
filter New-RegExParser ([regex] $RegEx)
{
$str = $RegEx.ToString()
if ($str[0] -ne '^') {$RegEx = New-Object RegEx ("^(${str})", $RegEx.Options)}
New-Closure @{RegEx = $RegEx} {
param([string]$Target, [int]$Position, $RegEx)
if ($Position -gt $Target.Length) {return $false, $null, $Position}
$result = $RegEx.Match($Target, $Position, ($Target.Length - $Position))
if (-not $result.Success) {return $false, $null, $Position}
$true, $result.Value, ($Position + $result.Length)
}
}
filter New-WrapperParser($Parser)
{
New-Closure $PSBoundParameters {
param([string]$Target, [int]$Position, $Parser)
Invoke-Parse-Raw @PSBoundParameters
}
}
filter New-RecursiveParser([ScriptBlock] $NewParser)
{
$_ = New-WrapperParser
$_.Param['Parser'] = & $NewParser
$_
}
filter New-RecursiveDescentParser ([HashTable] $Parser)
{
$_ = $Parser.Clone()
foreach($name in $Parser.Keys)
{$_[$name] = New-WrapperParser}
foreach($name in $Parser.Keys)
{$_[$name].Param['Parser'] = & $Parser[$name]}
$_
}
Set-Alias char New-CharParser
Set-Alias token New-TokenParser
Set-Alias regex New-RegExParser
Set-Alias rec New-RecursiveParser
Set-Alias recd New-RecursiveDescentParser
# ConvertTo
# =========
filter ConvertTo-OptionalParser($Parser)
{
New-Closure $PSBoundParameters {
param ([string]$Target, [int]$Position, $Parser)
$success, $result, $newPosition = Invoke-Parse-Raw @PSBoundParameters
if ($success) {return $success, $result, $newPosition}
$true, $null, $Position
}
}
filter ConvertTo-ManyParser($Parser)
{
New-Closure $PSBoundParameters {
param ([string]$Target, [int]$Position, $Parser)
$success, $result, $newPosition = $true, @(), $Position
while ($true)
{
$success, $r, $newPosition = Invoke-Parse-Raw $Target $newPosition $Parser
if (-not $success) {break}
if ($null -ne $r) {$result += ,$r}
}
if ($result.length -eq 0) {$result = $null}
$true, $result, $newPosition
}
}
filter ConvertTo-NewResultParser([ScriptBlock]$ScriptBlock, $Parser)
{
New-Closure $PSBoundParameters {
param ([string]$Target, [int]$Position, $Parser, $ScriptBlock)
$success, $_, $newPosition = Invoke-Parse-Raw $Target $Position $Parser
if ($success)
{
if ($_ -is [array]) {$_ = & $ScriptBlock @_}
else {$_ = & $ScriptBlock $_}
}
$success, $_, $newPosition
}
}
Set-Alias many ConvertTo-ManyParser
Set-Alias option ConvertTo-OptionalParser
Set-Alias map ConvertTo-NewResultParser
# Join
# ====
filter Join-Parser-Choice
{
New-Closure @{Parser = $args} {
param ([string]$Target, [int]$Position, $Parser)
$success, $result, $newPosition = $false, $null, $Position
foreach ($p in $Parser)
{
$success, $result, $newPosition = Invoke-Parse-Raw $Target $Position $p
if ($success) {break}
}
$success, $result, $newPosition
}
}
filter Join-Parser-Sequence
{
New-Closure @{Parser = $args} {
param ([string]$Target, [int]$Position, $Parser)
$success, $result, $newPosition = $true, @(), $Position
foreach ($p in $Parser)
{
$success, $r, $newPosition = Invoke-Parse-Raw $Target $newPosition $p
if (-not $success) {return $false, $null, $newPosition}
if ($null -ne $r) {$result += ,$r}
}
if ($result.length -eq 0) {$result = $null}
$success, $result, $newPosition
}
}
Set-Alias choice Join-Parser-Choice
Set-Alias seq Join-Parser-Sequence
$here = Split-Path -Parent $MyInvocation.MyCommand.Path
$sut = (Split-Path -Leaf $MyInvocation.MyCommand.Path).Replace(".Tests.", ".")
. "$here\$sut"
function json
{
Begin {$w = @()}
Process {$w += ,$_}
End
{
ConvertTo-Json $w -Compress -Depth 20 |
%{
$_ -replace '{"value":', '' `
-replace ",`"Count`":\d+}", ''
}
}
}
Describe New-CharParser {
$parser = char abcde
It true_target {
parser a 0 $parser | json | Should Be '[true,"a",1]'
parser c 0 $parser | json | Should Be '[true,"c",1]'
parser e 0 $parser | json | Should Be '[true,"e",1]'
}
It false_target {
parser g 0 $parser | json | Should Be '[false,null,0]'
}
It true_position {
parser _b_ 1 $parser | json | Should Be '[true,"b",2]'
parser __d__ 2 $parser | json | Should Be '[true,"d",3]'
}
It false_position {
parser a 1 $parser | json | Should Be '[false,null,1]'
parser _a_ 0 $parser | json | Should Be '[false,null,0]'
parser _a_ 2 $parser | json | Should Be '[false,null,2]'
}
It empty {
parser '' 0 $parser | json | Should Be '[false,null,0]'
}
}
Describe New-TokenParser {
$parser = token foo
It true_target {
parser foo 0 $parser | json | Should Be '[true,"foo",3]'
}
It false_target {
parser bar 0 $parser | json | Should Be '[false,null,0]'
}
It true_position {
parser _foo_ 1 $parser | json | Should Be '[true,"foo",4]'
parser __foo__ 2 $parser | json | Should Be '[true,"foo",5]'
}
It false_position {
parser foo 4 $parser | json | Should Be '[false,null,4]'
parser _foo_ 0 $parser | json | Should Be '[false,null,0]'
parser _foo_ 4 $parser | json | Should Be '[false,null,4]'
}
It empty {
parser '' 0 $parser | json | Should Be '[false,null,0]'
}
}
Describe New-RegExParser {
$parser = regex [1-9]\d*
It true_target {
parser '42' 0 $parser | json | Should Be '[true,"42",2]'
parser '1234567890' 0 $parser | json | Should Be '[true,"1234567890",10]'
}
It false_target {
parser foo 0 $parser | json | Should Be '[false,null,0]'
parser '042' 0 $parser | json | Should Be '[false,null,0]'
}
It true_position {
parser _42_ 1 $parser | json | Should Be '[true,"42",3]'
parser __42__ 2 $parser | json | Should Be '[true,"42",4]'
}
It false_position {
parser 42 3 $parser | json | Should Be '[false,null,3]'
parser _42_ 0 $parser | json | Should Be '[false,null,0]'
parser _42_ 3 $parser | json | Should Be '[false,null,3]'
}
It empty {
parser '' 0 $parser | json | Should Be '[false,null,0]'
}
}
Describe ConvertTo-OptionalParser {
$parser = (option (token foo))
It true_target {
parser foofoo 0 $parser | json | Should Be '[true,"foo",3]'
parser bar 0 $parser | json | Should Be '[true,null,0]'
parser foo 4 $parser | json | Should Be '[true,null,4]'
}
It true_position {
parser _foo_ 1 $parser | json | Should Be '[true,"foo",4]'
parser __foo__ 2 $parser | json | Should Be '[true,"foo",5]'
}
It empty {
parser '' 0 $parser | json | Should Be '[true,null,0]'
}
}
Describe ConvertTo-ManyParser {
$parser = (many (token foo))
It true_target {
parser foofoo 0 $parser | json | Should Be '[true,["foo","foo"],6]'
parser bar 0 $parser | json | Should Be '[true,null,0]'
parser foo 4 $parser | json | Should Be '[true,null,4]'
}
It true_position {
parser _foo_ 1 $parser | json | Should Be '[true,["foo"],4]'
parser __foo__ 2 $parser | json | Should Be '[true,["foo"],5]'
}
It empty {
parser '' 0 $parser | json | Should Be '[true,null,0]'
}
}
Describe ConvertTo-NewResultParser {
$parser = (map {"map:${_}!!!"} (token foo))
It true_target {
parser foo 0 $parser | json | Should Be '[true,"map:foo!!!",3]'
}
It false_target {
parser bar 0 $parser | json | Should Be '[false,null,0]'
}
It true_position {
parser _foo_ 1 $parser | json | Should Be '[true,"map:foo!!!",4]'
parser __foo__ 2 $parser | json | Should Be '[true,"map:foo!!!",5]'
}
It false_position {
parser foo 4 $parser | json | Should Be '[false,null,4]'
parser _foo_ 0 $parser | json | Should Be '[false,null,0]'
parser _foo_ 4 $parser | json | Should Be '[false,null,4]'
}
It empty {
parser '' 0 $parser | json | Should Be '[false,null,0]'
}
}
Describe Join-Parser-Choice {
$parser = (choice (token foo) (token bar))
It true_target {
parser foo 0 $parser | json | Should Be '[true,"foo",3]'
parser bar 0 $parser | json | Should Be '[true,"bar",3]'
}
It false_target {
parser baz 0 $parser | json | Should Be '[false,null,0]'
}
It true_position {
parser _foo_ 1 $parser | json | Should Be '[true,"foo",4]'
parser __bar__ 2 $parser | json | Should Be '[true,"bar",5]'
}
It false_position {
parser foo 4 $parser | json | Should Be '[false,null,4]'
parser _bar_ 0 $parser | json | Should Be '[false,null,0]'
parser _foo_ 4 $parser | json | Should Be '[false,null,4]'
}
It empty {
parser '' 0 $parser | json | Should Be '[false,null,0]'
}
}
Describe Join-Parser-Sequence {
$parser = (seq (token foo) (token bar))
It true_target {
parser foobar 0 $parser | json | Should Be '[true,["foo","bar"],6]'
}
It false_target {
parser baz 0 $parser | json | Should Be '[false,null,0]'
}
It true_position {
parser _foobar_ 1 $parser | json | Should Be '[true,["foo","bar"],7]'
parser __foobar__ 2 $parser | json | Should Be '[true,["foo","bar"],8]'
}
It false_position {
parser foobar 6 $parser | json | Should Be '[false,null,6]'
parser _foobar_ 0 $parser | json | Should Be '[false,null,0]'
parser _foobar_ 7 $parser | json | Should Be '[false,null,7]'
}
It empty {
parser '' 0 $parser | json | Should Be '[false,null,0]'
}
}
Describe New-RecursiveParser {
$parser = (rec {option (seq (token foo) ($_))})
It true_target {
parser foo 0 $parser | json | Should Be '[true,["foo"],3]'
parser foofoo 0 $parser | json | Should Be '[true,["foo",["foo"]],6]'
parser foofoofoo 0 $parser | json | Should Be '[true,["foo",["foo",["foo"]]],9]'
}
It true_position {
parser _foo_ 1 $parser | json | Should Be '[true,["foo"],4]'
parser __foo__ 2 $parser | json | Should Be '[true,["foo"],5]'
}
It empty {
parser '' 0 $parser | json | Should Be '[true,null,0]'
}
}
Describe New-RecursiveDescentParser {
$parser = recd @{
1 = {option $_.2}
2 = {seq (token foo) $_.1}
}
It true_target {
parser foo 0 $parser.1 | json | Should Be '[true,["foo"],3]'
parser foo 0 $parser.2 | json | Should Be '[true,["foo"],3]'
parser foofoo 0 $parser.1 | json | Should Be '[true,["foo",["foo"]],6]'
parser foofoofoo 0 $parser.2 | json | Should Be '[true,["foo",["foo",["foo"]]],9]'
}
It true_position {
parser _foo_ 1 $parser.1 | json | Should Be '[true,["foo"],4]'
parser __foo__ 2 $parser.1 | json | Should Be '[true,["foo"],5]'
}
It empty {
parser '' 0 $parser.1 | json | Should Be '[true,null,0]'
parser '' 0 $parser.2 | json | Should Be '[false,null,0]'
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment