パーサー・コンビネータ

ABAの日誌さんで、C#でパーサーコンビネータという記事を見つけた。しかし、僕のUbuntu + Monoな環境では*1、Extension Methodsができないようで(?)と勘違いしていたので、Extension Methodsを使わない形で、書いてみた。

[追記]MonoでExtension Methods使えました。っていうか、「System.Coreアセンブリへの参照を加えよ」という親切なエラーメッセージが出ているのに、読まずに「あ、だめだ」と思ってしまっていたみたい。ごめん。[/追記]

using System;
using System.Text;
using System.Collections.Generic;

namespace Parsers
{
	
	public class ParseError : Exception
	{
	}
	
	public class Unit
	{
		static public readonly Unit Instance = new Unit();
		private Unit()
		{
		}
	}
	
	public abstract class Maybe<T>
	{
		public abstract bool IsJust();
		public abstract T FromMaybe();
	}
	
	public sealed class Just<T> : Maybe<T>
	{
		private readonly T Value;
		public Just(T val)
		{
			Value = val;
		}
		public override bool IsJust ()
		{
			return true;
		}
		public override T FromMaybe()
		{
			return Value;
		}
	}
	
	public sealed class Nothing<T> : Maybe<T>
	{
		static public readonly Nothing<T> Instance = new Nothing<T>();
		private Nothing()
		{
		}
		public override bool IsJust ()
		{
			return false;
		}
		public override T FromMaybe()
		{
			throw new ParseError();
		}
	}
	
	public abstract class Parser
	{
		protected delegate T Parsing<T>();
		
		/* Option
		 *   失敗したときに入力を消費しない。
		 *   Parsecの(optionMaybe . try)に相当
		 */
		protected abstract Parsing<Maybe<T>> Option<T>(Parsing<T> parsing);
		protected Parsing<T> Return<T>(T val)
		{
			return delegate(){
				return val;
			};
		}
		protected Parsing<List<T>> Many<T>(Parsing<T> parsing)
		{
			return delegate(){
				List<T> list = new List<T>();
				Maybe<T> a;
				while((a = Option(parsing)()).IsJust()){
					list.Add(a.FromMaybe());
				}
				return list;
			};
		}
		protected Parsing<List<T>> Many1<T>(Parsing<T> parsing)
		{
			return delegate(){
				T a = parsing();
				List<T> list = Many(parsing)();
				
				list.Insert(0, a);
				return list;
			};
		}
		protected Parsing<T> Any<T>(params Parsing<T>[] parsings)
		{
			return delegate(){
				Maybe<T> a;
				int i;
				for(i = 0; i < parsings.Length - 1; i++){
					if((a = Option(parsings[i])()).IsJust()){
						return a.FromMaybe();
					}
				}
				return parsings[i]();
			};
		}
		protected Parsing<List<T>> SepBy<T,S>(Parsing<T> parsing, Parsing<S> separator)
		{
			return delegate(){
				Parsing<T> remaining = delegate(){
					separator();
					return parsing();
				};
				
				T a = parsing();
				List<T> list = Many(remaining)();
				
				list.Insert(0,a);
				return list;
			};
		}
		protected Parsing<List<T>> EndBy<T,S>(Parsing<T> parsing, Parsing<S> separator)
		{
			return delegate(){
				List<T> list = SepBy(parsing,separator)();
				separator();
				return list;
			};
		}
	}
	
	public class ArrayParser<T> : Parser
	{
		private int Index;
		private readonly T[] Content;
		public ArrayParser(T[] content)
		{
			Index = 0;
			Content = content;
		}
		protected Parsing<T> Pop(Predicate<T> predicate)
		{
			return delegate(){
				if(Index >= Content.Length){
					throw new ParseError();
				}else if(predicate(Content[Index])){
					return Content[Index++];
				}else{
					throw new ParseError();
				}
			};
		}
		protected override Parsing<Maybe<S>> Option<S>(Parsing<S> parsing)
		{
			return delegate(){
				int index = Index;
				try{
					S a = parsing();
					return new Just<S>(a);
				}catch(ParseError){
					Index = index;
					return Nothing<S>.Instance;
				}
			};
		}
		protected Unit End()
		{
			if(Index >= Content.Length){
				return Unit.Instance;
			}else{
				throw new ParseError();
			}
		}
	}
	
	public class CharParser : ArrayParser<char>
	{
		public CharParser(string content) : base(content.ToCharArray())
		{
		}
		protected Parsing<char> Char(Predicate<char> predicate)
		{
			return Pop(predicate);
		}
		protected Unit Eof()
		{
			return End();
		}
	}
	
	public class CsvParser : CharParser
	{
		public CsvParser(string content) : base(content)
		{
		}
		public static string[][] Parse(string content)
		{
			CsvParser parser = new CsvParser(content);
			return parser.CSV();
		}
		public string[][] CSV()
		{
			List<string[]> list = EndBy<string[],Unit>(Line, Eol)();
			Eof();
			return list.ToArray();
		}
		public string[] Line()
		{
			List<string> list = SepBy<string,char>(Cell,Char(x => x == ','))();
			return list.ToArray();
		}
		public string Cell()
		{
			List<char> list = Many1(Char(x => x != ',' && x != '\n'))();
			
			StringBuilder sb = new StringBuilder();
			foreach(char c in list){
				sb.Append(c);
			}
			return sb.ToString();
		}
		public Unit Eol()
		{
			Char(x => x == '\n')();
			return Unit.Instance;
		}
	}
	
	class Test
	{
		public static void Main (string[] args)
		{
			string csv =
				"東京都,2187.65,3044818\n" +
				"愛知県,5164.58,7417378\n" +
				"大阪府,1897.86,8839168\n";
			string[][] data = CsvParser.Parse(csv);
			foreach(string[] line in data){
				Console.Write("Line: ");
				foreach(string cell in line){
					Console.Write("(" + cell + ")");
				}
				Console.WriteLine();
			}
		}
	}
}

Unitクラスとか、MaybeクラスとかはHaskellの作法から輸入。こういうちょっとした型があるといろいろ便利。

Parser抽象クラスがパーサー・コンビネータの集合で、これを継承して使うことになる。パーサー・コンビネータの「パーサー」はネーミングが衝突してしまうので、Parsingというdelegate型で表すことにした。

CsvParserクラスが利用例。完全ではないがCSVを解析できる。解析文法はReal World Haskellを参考にした。

Parsecを参考にしているけど、速度よりも使い勝手を優先して、先読みに制限はなく、どのコンビネータも、失敗すれば常に完全にロールバックされる。

*1:べつにマイクロソフトが嫌いとかそういうわけではない。たんに経済的事情。