LINQ: интересный подход к написанию парсеров

В рамках одного небольшого проекта появилась задача обработки достаточно простого языка. Курс трансляции в университете я успешно прошёл, но к сожалению писать так как нас учили не очень хотелось, всё таки Ахо и компания написали свой монументальный труд около двух десятков лет назад, поэтому хотелось чего-нибудь интересного. В результате гугле нарвался на замечательную статью, которая продемонстрировала, как можно использовать LINQ выражения для парсинга: Monadic Parser Combinators using C# 3.0.


Как насчёт маленького примерчика. Например небольшой калькулятор :)
И начнём пожалуй с конца, а именно конструктор класса нашего парсера

copy to clipboardподсветка кода

1. Whitespace = Rep(Char(' ').Or(Char('\t').Or(Char('\n')).Or(Char('\r'))));  
2. WsChr = chr => Whitespace.And(Char(chr));  
3. Id = from w in Whitespace  
4.      from c in Char(char.IsLetter)  
5.      from cs in Rep(Char(char.IsLetterOrDigit))  
6.      select cs.Aggregate(c.ToString(), (acc, ch) => acc + ch);  
7. Number = from w in Whitespace  
8.      from cs in Rep(Char(char.IsDigit))  
9.      select cs.Aggregate(cs.ToString(), (acc, ch) => acc + ch);  
10. Ident = (from n in Number  
11.          select n)  
12.      .Or(from i in Id  
13.          select i);  
14. Sub = (from id in Ident  
15.        from u in WsChr('+')  
16.        from s in Sub  
17.        select (Term)((AgreggateTerm)s).Add(id, u.ToString()))  
18.    .Or(from id in Ident  
19.        from u in WsChr('-')  
20.        from s in Sub  
21.        select (Term)((AgreggateTerm)s).Add(id, u.ToString()))  
22.    .Or(from id in Ident  
23.        select (Term)new AgreggateTerm(id));  
24. Mult = (from s in Sub  
25.         from u in WsChr('*')  
26.         from m in Mult  
27.         select (Term)((AgreggateTerm)m).Add((AgreggateTerm)s, u.ToString()))  
28.     .Or(from s in Sub  
29.         from u in WsChr('/')  
30.         from m in Mult  
31.         select (Term)((AgreggateTerm)m).Add((AgreggateTerm)s, u.ToString()))  
32.     .Or(from s in Sub  
33.         select (Term)new AgreggateTerm((AgreggateTerm)s));  
34. All = from m in Mult select m;  

Ничего не напоминает? Лично для меня, когда привык к небольшой избыточности, это напоминает вид расширенной формы Бэкуса-Наура.

По сути всё просто мы переопределяем всякие select, where, or и прочие вещи, чтобы с помощью LINQ пробежать по всем char'ом в строке. Только в отличии от стандартного способа в виде while - switch это подход выглядит очень красиво. Главное достоинство в расширяемости. По приведенной выше ссылке можно найти полный код, в котором всего лишь надо заменить конструктор парсера, например на тот что я привёл, в результате получим парсер нашего языка, вот так всё просто :)