2 using System.Collections.Generic;
3 public class Pair<A, B> {
4 public A _1 { get; private set; }
5 public B _2 { get; private set; }
6 public Pair(A _1, B _2) {
10 public override string ToString() {
11 return string.Format("({0}, {1})", _1, _2);
14 public class ParseResult<A> {
15 public A Item { get; private set; }
16 public string Rest { get; private set; }
17 public ParseResult(A item, string rest) {
21 public override string ToString() {
22 return string.Format("(value = {0}, rest = {1})", Item, Rest);
25 public class Parser<A> {
26 public Func<string, ParseResult<A>> Target { get; set; }
27 public Parser(Func<string, ParseResult<A>> target) {
30 public ParseResult<A> Parse(string input) {
33 public static Parser<A> Make(Func<string, ParseResult<A>> target) {
34 return new Parser<A>(target);
36 public static implicit operator Parser<object>(Parser<A> p) {
37 return Parser<object>.Make((input) => {
38 var r = p.Parse(input);
39 return r != null ? new ParseResult<object>(r.Item, r.Rest) : null;
42 public Parser<A> Or(Parser<A> p2) {
43 return Make((input) => {
45 return r != null ? r : p2.Parse(input);
48 public Parser<Pair<A, B>> Seq<B>(Parser<B> p2) {
49 return Parser<Pair<A, B>>.Make((input) => {
50 var r1 = Parse(input);
51 if(r1 == null) return null;
52 var r2 = p2.Parse(r1.Rest);
53 if(r2 == null) return null;
54 return new ParseResult<Pair<A, B>>(
55 new Pair<A, B>(r1.Item, r2.Item), r2.Rest
59 public static Parser<object> operator!(Parser<A> p) {
62 public static Parser<Object> operator~(Parser<A> p) {
65 public Parser<object> Not() {
66 return Parser<object>.Make((input) => {
68 return r == null ? new ParseResult<object>(null, input) : null;
71 public Parser<object> And() {
72 return this.Not().Not();
74 public Parser<A> Opt() {
75 return Or(BasicOperations.Str("").Apply<A>((p) => default(A)));
77 public Parser<B> Apply<B>(Func<A, B> f) {
78 return Parser<B>.Make((input) => {
79 var r1 = Parse(input);
80 return r1 != null ? new ParseResult<B>(f(r1.Item), r1.Rest) : null;
83 public Parser<List<A>> Rep() {
84 return Parser<List<A>>.Make((input) => {
85 var rs = new List<A>();
87 while((r = Parse(input)) != null) {
91 return new ParseResult<List<A>>(rs, input);
94 public Parser<List<A>> Rep1() {
95 return this.Seq(this.Rep()).Apply((p) => {
101 public class BasicOperations {
102 public static Parser<string> Any = Parser<string>.Make((input) => {
103 return input.Length > 0 ?
104 new ParseResult<string>(input.Substring(0, 1), input.Substring(1)) : null;
106 public static Parser<string> Str(string param) {
107 return Parser<string>.Make((input) => {
108 return input.StartsWith(param) ?
109 new ParseResult<string>(param, input.Substring(param.Length)) : null;
112 public static Parser<A> Rule<A>(Func<Parser<A>> f) {
113 return Parser<A>.Make((input) => f().Parse(input));
116 public class User : BasicOperations {
117 public static Parser<object> S = Rule(() =>
118 (~A.Seq(!Str("b"))).Seq(Str("a").Rep1()).Seq(B).Seq(!Str("c"))
120 public static Parser<object> A = Rule(() =>
121 Str("a").Seq(A.Opt()).Seq(Str("b"))
123 public static Parser<object> B = Rule(() =>
124 Str("b").Seq(B.Opt()).Seq(Str("c"))
126 static void Main(string[] args) {
127 Console.WriteLine("{0}", S.Parse(args[0]));