PEGがおもしろいのでネットをさまよっていたらPEG Example Generatorとかいうのがみつかったので，自分でも書いてみた．書いてあるとおり，CFGとして生成してみることにしたのだが，書いてあるとおり無限ループがやっかい．とりあえずA / BについてはBから展開することにしてみたけど，駄目な時は駄目．言語はC#

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


class PEG{
  Func<string,string> func;
  Func<IEnumerable<string>> cfl;
  static IEnumerable<string> sum(Func<IEnumerable<string>> s1,Func<IEnumerable<string>> s2){
    var e2 = s2().GetEnumerator();
    if(e2.MoveNext())yield return e2.Current;
    var e1 = s1().GetEnumerator();
    if(e1.MoveNext())yield return e1.Current;
    while(true){
      var b2 = e2.MoveNext();
      if(b2)yield return e2.Current;
      var b1 = e1.MoveNext();
      if(b1)yield return e1.Current;
      if(!b1 && !b2)break;
    }
    yield break;
  }
  static IEnumerable<Tuple<string,string>> product(Func<IEnumerable<string>> s1,Func<IEnumerable<string>> s2){
    var e1 = s1().GetEnumerator();
    var e2 = s2().GetEnumerator();
    var l1 = new List<string>();
    var l2 = new List<string>();
    for(int N = 0 ; ; ++N){
      if(e1.MoveNext())l1.Add(e1.Current);
      if(e2.MoveNext())l2.Add(e2.Current);
      if(l1.Count + l2.Count <= N)yield break;
      for(int i = 0 ; i <= N ; ++i){
        if(i < l1.Count && N - i < l2.Count)yield return new Tuple<string,string>(l1[i],l2[N - i]);
      }
    }
  }
  static IEnumerable<string> add_empty(Func<IEnumerable<string>> s){
    yield return "";
    foreach(var x in s())yield return x;
  }
  
  public PEG(){}
  public PEG(Func<string,string> f){func = f;cfl = ()=>new string[]{};}
  public PEG(string str){
    func = (s => {
      if(s.StartsWith(str))return s.Substring(str.Length);
      else return null;
    });
    cfl = ()=>new string[]{str};
  }
  public static PEG operator+(PEG e1,PEG e2){
    var peg = new PEG(s => {
      var r1 = e1.parse(s);
      if(r1 == null)return null;
      else return e2.parse(r1);
    });  
    peg.cfl = ()=>product(e1.cfl,e2.cfl).Select(x => x.Item1 + x.Item2).Distinct();
    return peg;
  }
  public static PEG operator/(PEG e1,PEG e2){
    var peg = new PEG(s => {
      var r1 = e1.parse(s);
      if(r1 != null)return r1;
      else return e2.parse(s);
    });
    peg.cfl = ()=>sum(e1.cfl,e2.cfl).Distinct();
    return peg;
  }
  public static PEG operator!(PEG e){
    var peg = new PEG(s => {
      if(e.parse(s) == null)return s;
      else return null;
    });
    peg.cfl = ()=>new string[]{""};
    return peg;
  }
  public PEG repeat(){
    Func<string,string> f= null;
    f = (s => {
      var r = parse(s);
      if(r == null)return s;
      else return f(r);
    });
    var peg = new PEG(f);
    peg.cfl = (() => {
      return Enumerable.Concat(new string[]{""},product(cfl,peg.cfl).Select(x => x.Item1 + x.Item2)).Distinct();
    });
    return peg;
  }
  public PEG hatena(){
    var peg = new PEG(s => {
      var r = parse(s);
      if(r == null)return s;
      else return r;
    });
    peg.cfl = ()=>add_empty(cfl).Distinct();
    return peg;
  }
  public string parse(string s){return func(s);}
  public void assign(PEG e){func = e.func;cfl = e.cfl;}
  public IEnumerable<string> take_cfl(int n){
    int i = 0;
    foreach(var s in cfl()){
      if(i == n)break;
      yield return s;
      ++i;
    }
  }    
  public IEnumerable<string> take(int n){
    int i = 0;
    foreach(var s in cfl()){
      if(i == n)break;
      if(parse(s) == ""){
        ++i;
        yield return s;
      }
    }
  }
}
static class Program{
  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();
    var Z = any.repeat();
    B.assign(b + B.hatena() + c);
    A.assign(a + A.hatena() + b);
    S.assign(!!(A + !b) + (a + a.repeat()) + B + !any);
    foreach(var s in S.take(10)){
      Console.WriteLine(s);
    }
  }
}