Skip to content

Instantly share code, notes, and snippets.

@ulve

ulve/Combinator.cs

Last active April 4, 2018 13:17
Show Gist options
  • Save ulve/c160e9fbe9418e7ac20e4182ad7b5f8f to your computer and use it in GitHub Desktop.
Save ulve/c160e9fbe9418e7ac20e4182ad7b5f8f to your computer and use it in GitHub Desktop.
Download ZIP
Simple parser combinator
Raw
Combinator.cs
using System;
using System.Collections.Generic;
using System.Linq;
namespace ParserCombinator
{
public class Result<T, U>
{
public U Value { get; private set; }
public T Rest { get; private set; }
public Result(U value, T rest)
{
Value = value;
Rest = rest;
}
}
public delegate Result<T, U> Parser<T, U>(T input);
public static class ParserCombinatorExtensions
{
public static Parser<T, U> Or<T, U>(this Parser<T, U> parser1, Parser<T, U> parser2)
{
return input => parser1(input) ?? parser2(input);
}
public static Parser<T, U> And<T, V, U>(this Parser<T, U> parser1, Parser<T, U> parser2)
{
return input => parser2(parser1(input).Rest);
}
}
public static class ParserCombinatorsMonad
{
public static Parser<T, U> Filter<T, U>(this Parser<T, U> parser, Func<U, bool> pred)
{
return input => {
var res = parser(input);
if (res == null || !pred(res.Value))
return null;
return res;
};
}
public static Parser<T, V> Map<T, U, V>(this Parser<T, U> parser, Func<U, V> selector)
{
return input => {
var res = parser(input);
if (res == null) return null;
return new Result<T, V>(selector(res.Value), res.Rest);
};
}
public static Parser<T, U> FlatMap<T, V, X, U>(this Parser<T, V> parser, Func<V, Parser<T, X>> selector, Func<V, X, U> projector)
{
return input => {
var res = parser(input);
if (res == null)
return null;
var val = res.Value;
var res2 = selector(val)(res.Rest);
if (res2 == null)
return null;
return new Result<T, U>(projector(val, res2.Value), res2.Rest);
};
}
}
public abstract class Parsers<T>
{
public Parser<T, U> Succeed<U>(U value)
{
return input => new Result<T, U>(value, input);
}
public Parser<T, U[]> Repeat<U>(Parser<T, U> parser)
{
return RepeatOnePlus(parser).Or(Succeed(new U[0]));
}
public Parser<T, U[]> RepeatOnePlus<U>(Parser<T, U> parser)
{
return parser.FlatMap(x => Repeat(parser), (x, xs) => (new[] { x }).Concat(xs).ToArray());
}
}
public abstract class CharParsers<T> : Parsers<T>
{
public abstract Parser<T, char> AnyChar { get; }
public Parser<T, char> Char(char ch)
{
return AnyChar.Filter(c => c == ch);
}
public Parser<T, char> Char(Predicate<char> pred)
{
return AnyChar.Filter(c => pred(c));
}
}
public class Mål
{
public string Målnummer { get; private set; }
public List<string> Sökande { get; private set; }
public Mål(string målnummer, string sökande)
{
Målnummer = målnummer;
Sökande = new List<string> { sökande };
}
public override string ToString()
{
return $"Målnummer: {Målnummer}\nSökande: {Sökande.First()}";
}
}
public abstract class MålParser<T> : CharParsers<T>
{
public MålParser()
{
Whitespace = Repeat(Char(' ').Or(Char('\t').Or(Char('\n'))));
Målnummer = Char(char.IsDigit)
.FlatMap(x => Char(char.IsDigit), (a, b) => new List<char> { a, b })
.FlatMap(y => Char('-'), (a, b) => { a.Add(b); return a; })
.FlatMap(z => Char(char.IsDigit), (a, b) => { a.Add(b); return a; })
.FlatMap(w => Char(char.IsDigit), (a, b) => { a.Add(b); return a; })
.Map(x => new string(x.ToArray()));
Sökande = Whitespace.FlatMap(x => Repeat(Char(char.IsLetter)), (a, b) => new string( b));
Allt = Whitespace.FlatMap(målnummer => Målnummer, (space, målnummer) => målnummer)
.FlatMap(sökande => Sökande, (målnummer, sökande) => new Mål(målnummer, sökande));
}
public Parser<T, char[]> Whitespace;
public Parser<T, string> Målnummer;
public Parser<T, string> Sökande;
public Parser<T, Mål> Allt;
}
public class MålParserFromString : MålParser<string>
{
public override Parser<string, char> AnyChar
{
get
{
return input => input.Length > 0 ? new Result<string, char>(input[0], input.Substring(1)) : null;
}
}
}
class Program
{
static void Main(string[] args)
{
var parser = new MålParserFromString();
Result<string, Mål> result = parser.Allt(" 12-34 Olov Det borde bara bli Olov här resten skall bryta ");
Console.WriteLine(result.Value);
}
}
}
Raw
Syntax.cs
using System;
using System.Collections.Generic;
using System.Linq;
namespace ParserCombinator
{
public class Result<T, U>
{
public U Value { get; private set; }
public T Rest { get; private set; }
public Result(U value, T rest)
{
Value = value;
Rest = rest;
}
}
public delegate Result<T, U> Parser<T, U>(T input);
public static class ParserCombinatorExtensions
{
public static Parser<T, U> Or<T, U>(this Parser<T, U> parser1, Parser<T, U> parser2)
{
return input => parser1(input) ?? parser2(input);
}
public static Parser<T, U> And<T, V, U>(this Parser<T, U> parser1, Parser<T, U> parser2)
{
return input => parser2(parser1(input).Rest);
}
}
public static class ParserCombinatorsMonad
{
public static Parser<T, U> Where<T, U>(this Parser<T, U> parser, Func<U, bool> pred)
{
return input => {
var res = parser(input);
if (res == null || !pred(res.Value))
return null;
return res;
};
}
public static Parser<T, V> Select<T, U, V>(this Parser<T, U> parser, Func<U, V> selector)
{
return input => {
var res = parser(input);
if (res == null) return null;
return new Result<T, V>(selector(res.Value), res.Rest);
};
}
public static Parser<T, U> SelectMany<T, V, X, U>(this Parser<T, V> parser, Func<V, Parser<T, X>> selector, Func<V, X, U> projector)
{
return input => {
var res = parser(input);
if (res == null)
return null;
var val = res.Value;
var res2 = selector(val)(res.Rest);
if (res2 == null)
return null;
return new Result<T, U>(projector(val, res2.Value), res2.Rest);
};
}
}
public abstract class Parsers<T>
{
public Parser<T, U> Succeed<U>(U value)
{
return input => new Result<T, U>(value, input);
}
public Parser<T, U[]> Repeat<U>(Parser<T, U> parser)
{
return RepeatOnePlus(parser).Or(Succeed(new U[0]));
}
public Parser<T, U[]> RepeatOnePlus<U>(Parser<T, U> parser)
{
return parser.SelectMany(x => Repeat(parser), (x, xs) => (new[] { x }).Concat(xs).ToArray());
}
}
public abstract class CharParsers<T> : Parsers<T>
{
public abstract Parser<T, char> AnyChar { get; }
public Parser<T, char> Char(char ch)
{
return AnyChar.Where(c => c == ch);
}
public Parser<T, char> Char(Predicate<char> pred)
{
return AnyChar.Where(c => pred(c));
}
}
public class Mål
{
public string Målnummer { get; private set; }
public List<string> Sökande { get; private set; }
public Mål(string målnummer, string sökande)
{
Målnummer = målnummer;
Sökande = new List<string> { sökande };
}
public override string ToString()
{
return $"Målnummer: {Målnummer}\nSökande: {Sökande.First()}";
}
}
public abstract class MålParser<T> : CharParsers<T>
{
public MålParser()
{
Whitespace = Repeat(Char(' ').Or(Char('\t').Or(Char('\n'))));
Målnummer = from c in Whitespace
from x1 in Char(char.IsDigit)
from x2 in Char(char.IsDigit)
from x3 in Char('-')
from x4 in Char(char.IsDigit)
from x5 in Char(char.IsDigit)
select new string(new[] { x1, x2, x3, x4, x5});
Sökande = from c in Whitespace
from sökande in Repeat(Char(char.IsLetter))
select new string(sökande);
Allt = from c in Whitespace
from målnummer in Målnummer
from sökande in Sökande
select new Mål(målnummer, sökande);
}
public Parser<T, char[]> Whitespace;
public Parser<T, string> Målnummer;
public Parser<T, string> Sökande;
public Parser<T, Mål> Allt;
}
public class MålParserFromString : MålParser<string>
{
public override Parser<string, char> AnyChar
{
get
{
return input => input.Length > 0 ? new Result<string, char>(input[0], input.Substring(1)) : null;
}
}
}
class Program
{
static void Main(string[] args)
{
var parser = new MålParserFromString();
Result<string, Mål> result = parser.Allt(" 12-34 Olov Det borde bara bli Olov här resten skall bryta ");
Console.WriteLine(result.Value);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment