Parsing Expression Grammar (2)

PEGはその定義通りにプログラムを書くとパースをすることができる．まぁ言語が高階関数を使えないと辛いけど．というわけで書いてみた．ただし，メモ化はしていないので激遅なはず．まぁ単に書いてみた，というだけ．何故かHaskellで書いてあるのをよく見るのでHaskellで．本当はElmで書こうかと思ったけどなんか失敗した．

isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
isPrefixOf [] _ = True
isPrefixOf _ [] = False
isPrefixOf (x:xs) (y:ys) = 
  case x == y of
    True -> isPrefixOf xs ys
    False -> False

pegstr :: String -> String -> Maybe String
pegstr s str =
  if isPrefixOf s str then Just (drop (length s) str)
  else Nothing

(//) :: (String -> Maybe String) -> (String -> Maybe String) -> String -> Maybe String
e1 // e2 = (\str -> 
  case e1 str of
    Just x -> Just x
    Nothing -> e2 str)

(##) :: (String -> Maybe String) -> (String -> Maybe String) -> String -> Maybe String
e1 ## e2 = (\str ->
  case e1 str of
    Nothing -> Nothing
    Just x -> e2 x)

pegnot :: (String -> Maybe String) -> String -> Maybe String
pegnot e str =
  case e str of
    Nothing -> Just str
    Just x -> Nothing

pegand e str =
  case e str of
    Nothing -> Nothing
    Just x -> Just str

pegrepeat :: (String -> Maybe String) -> String -> Maybe String
pegrepeat e str =
  case e str of
    Nothing -> Just str
    Just x -> pegrepeat e x


tos :: Maybe String -> String
tos s = 
  case s of
  Nothing -> "Nothing"
  Just x -> x

peghatena :: (String -> Maybe String) -> String -> Maybe String
peghatena e str = 
  case e str of
    Nothing -> Just str
    Just x -> Just x

a = pegstr "a"
b = pegstr "b"
c = pegstr "c"
empty = pegstr ""
anyc = a // b // c
na :: String -> Maybe String
na = (a ## (peghatena na) ## b)
nb :: String -> Maybe String
nb = (b ## (peghatena nb) ## c)
ns :: String -> Maybe String
ns = pegand (na ## (pegnot b)) ## (a ## (pegrepeat a)) ## nb ## (pegnot anyc)

main = putStrLn(tos (ns "aabbccc"))

C#でも書いてみた．

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.ComponentModel;

class PEG{
  Func<string,string> func;
  public PEG(){}
  public PEG(Func<string,string> f){func = f;}
  public PEG(string str){
    func = (s => {
      if(s.StartsWith(str))return s.Substring(str.Length);
      else return null;
    });}
  public static PEG operator+(PEG e1,PEG e2){
    return new PEG(s => {
      var r1 = e1.parse(s);
      if(r1 == null)return null;
      else return e2.parse(r1);
    });
  }
  public static PEG operator/(PEG e1,PEG e2){
    return new PEG(s => {
      var r1 = e1.parse(s);
      if(r1 != null)return r1;
      else return e2.parse(s);
    });
  }
  public static PEG operator!(PEG e){
    return new PEG(s => {
      if(e.parse(s) == null)return s;
      else return null;
    });
  }
  public PEG repeat(){
    Func<string,string> f= null;
    f = (s => {
      var r = parse(s);
      if(r == null)return s;
      else return f(r);
    });
    return new PEG(f);
  }
  
  public PEG hatena(){
    return new PEG(s => {
      var r = parse(s);
      if(r == null)return s;
      else return r;
    });
  }
  public string parse(string s){return func(s);}
  public void assign(PEG e){func = e.func;}
}


static class Program{
  static void print(string s){
    if(s == null)Console.WriteLine("fail");
    else Console.WriteLine(s);
  }
  [STAThread]
  static void Main() {
    var empty = new PEG("");
    var a = new PEG("a");
    var b = new PEG("b");
    var c = new PEG("c");
    var any = new PEG(s => s.Length == 0 ? null : s.Substring(1));
    var A = new PEG();
    var B = new PEG();
    var S = new PEG();
    B.assign(b + B.hatena() + c);
    A.assign(a + A.hatena() + b);
    S.assign(!!(A + !b) + (a + a.repeat()) + B + !any);
    
    
    print(S.parse("aabbccc"));
    print(S.parse("aaabbbccc"));
  }
}