Pull to refresh

Monadic Parser Combinator в Nemerle

Reading time 7 min
Views 2.3K
Недавно обнаружил замечательную статью Monadic Parser Combinator про создание парсеров. Основная идея заключена в том, что бы описать парсер как объект первого класса, что бы можно было произвести декомпозицию исходной задачи и представить искомый парсер в виде синтеза более простых парсеров. Что бы облегчить комбинацию парсеров используется подход replace error with list of success. В языке haskell очень удобно работать с созданием парсеров, так как эта задача естественно ложится на концепцию монад, к сожалению в nemerle монады не поддерживаются, но все же язык достаточно мощный, что бы справиться с данной задачей.

    Более подробно представить парсер можно как отображение из строки в список кортежей, где первый элемент кортежа — разобранная часть строки, а второй элемент — оставшаяся часть строки. В случае неудачного разбора возвращается пустой список. В разных случаях то, что я назвал разобранной частью строки, может иметь разный тип, поэтому естественно считать тип парсера полиморфным, например, string -> list['a * string]. Ниже такую конструкцию буду обозначать как парсер['a].

    Дальше нужно рассмотреть комбинацию парсеров. Допустим нужно разобрать и вычислить «sin42», и мы уже имеем парсер, который умеет разбирать математические функции — math : парсер[double->double], и парсер, умеющий разбирать числа — number : парсер[double] (через : описан тип парсеров).
Искомый парсер можно записать в следующем виде:
def eval = text=>math(text).Map((f,rest)=>number(rest).Map((a,b)=>(f(a),b))).Fold([], (e,acc)=>e+acc)

Получилось достаточно емко, но только красноглазый фанат ФП может согласиться, что это красивый код. Ниже я определю оператор на парсерах и этот код можно будет переписать в следующем виде:
def eval = math * (f => number * (x => result(f(x))))

Простым языком действие оператора '*' можно описать как создание нового парсера, который действует следующим образом: применяет первый парсер, затем второй парсер параметризирует разобранным результатом первого и продолжает разбор. На вход оператор '*' имеет парсер['a] и функцию, которая производит параметризацию, типа 'a->парсер['b].

    Ниже, для примера простоты и мощности такого подхода, я написал парсер, который проверяет корректность арифметических выражений, состоящих из положительных чисел, скобок и операции "+". Код написан на nemerle, но я постараюсь комментировать синтаксис, семантику постарайтесь понять сами, но осторожно — не сломайте мозг! И не пугайтесь размера кода, так как половина в нем может быть вынесена в отдельную библиотеку для создания парсеров, в случае с haskell библиотека, основанная на таком подходе — parsec. Поехали!
using System;
using System.Console;
    Подключаю необходимые пространства имен и раскрываю класс System.Console — от ныне все его статические методы становятся глобальными функциями/процедурами. Про модуль, функциональные типы вместо делегатов, отсутствие new перед вызовом конструктора и описание конструктора через слово this, я, наверное, писал раньше. Замечу сейчас только, что generic-параметры в nemerle задаются через квадратные скобки, а не через угловые, что имя типа может содержать апострофов и что в немерле считается правилом хорошего тона давать имена generic параметрам, начинающиеся с апострофа.
module Program
{
 class Parser['a]
 {
  public this(core : string -> list['a*string]) { this.core = core }
  core : string -> list['a*string];

    Тип кортежа, в котором первый элемент имеет тип int, а второй string, в nemerle записывается как int*string, сам кортеж, если еще не писал об этом, записывается, например так: def tuple = (45,«qwerty»). Теперь, надеюсь, понятна запись list['a*string].
  public Parse(text : string) : list['a*string] { core(text) }

  public static @*['b](self : Parser['a], parser : 'a->Parser['b]) : Parser['b]
  {
   Parser(fun(text : string) : list['b*string]
   {
    def data = self.Parse(text);
    data.Map((ast,rest) => parser(ast).Parse(rest)).FoldRight([], (e,acc) => e+acc)
   })
  }

    @* не мат, как подумал мой друг, а синоним operator* в языке C#. Другая синтаксическая особенность, которую вы еще не встречали в этом блоге — fun. Это не что иное как лямбда выражение, другой возможный синтаксис для лямбды совпадает с синтаксисом из C#, например следующие примеры кода эквивалентны: fun(x) { x+1 } и x=>x+1; опционально можно указывать тип, например, fun(x : int) : int { x+1 } или x : int => x + 1. В случае, когда лямбду можно записать а одну строчку я использую второй вариант, иначе первый.
  public static @+(a : Parser['a], b : Parser['a]) : Parser['a]
  {
   Parser(text => a.Parse(text) + b.Parse(text) )
  }
 }

    В немерле определена операция + для списков, в коде выше она использовалась внутри тела лямбды.
 class zero['a] : Parser['a] { public this() { base(x=>[]) } }
 
 class result['a] : Parser['a]
 {
  public this(value : 'a) { base(text => [(value,text)]) }
 }

    В немерле, как и в языке Java вызов конструктора базового класса происходит внутри конструктора подкласса. Два класса, которые я определил, являются фундаментальными парсерами, и многие другие парсеры и генераторы парсеров созданы их основе. Класс result можно сравнить с конструктором монады в haskell. Генератором парсера я назвал функцию, которая возвращает парсер, например ниже определен генератор symbol(x : char) : Parser[char], который создает парсер, ожидающий указанный символ в начале строки разбора.

    Ниже я определяю три комбинатора парсеров. Так как весь это код пишется внутри модуля, который является статическим классом, то я могу запросто объявлить статические методы этого класса (ключевое слово static не нужно в данном случае, так как это модуль) и пользоваться ими как глобальными функциями. Комбинатором парсеров я назвал функцию, которая принимает на вход парсер или парсеры, а на выходе возращает парсер. Тривиальным комбинатором является тождественная функция, но она не интересна, поэтому я определил комбинаторы many, many1 и oneOf. Первый повторяет парсер, который имеет на входе, пока строка, которую он разбирает это позволяет (аналог * в регулярных выражениях), второй является аналогом + в регулярном выражении, а третий пытается применить последовательно, переданные ему парсеры до тех пор, пока один из них не разберет часть строки успешно.
 many['a] (parser : Parser['a]) : Parser[list['a]]
 {
  parser * (x => many(parser) * (xs => result(x::xs))) + result([])
 }
 
 many1['a] (parser : Parser['a]) : Parser[list['a]]
 {
  parser * (x => many(parser) * (xs => result(x::xs)))
 }
 
 oneOf['a] (params parsers : array[Parser['a]]) : Parser['a]
 {
  Parser(fun(text){
   parsers.FoldLeft([], fun(e,acc)
   {
    | (_, []) => e.Parse(text)
    | (_, _) => acc
   })
  })
 }

    В последнем генераторе, в теле лямбда выражении используется сокращенный синтаксис для pattern matching. Его можно использовать в том случае, когда аргументы функции участвуют в pattern matching и тело функции состоит из одного выражения сопоставления с образцом. Приведу эквивалентные примеры кода: def foo(x) { match(x) { | [] => «empty» | _ => "!empty" } } и def foo(x) { | [] => «empty» | _ => "!empty" }.

Внимание!

    Ниже идет уже существенный код, который создает проверяющий парсер. Весь код до этого можно вынести в библиотеку, так как он наиболее обобщен и не привязан к конкретному парсеру.
 Main() : void
 {
  def item = Parser(x => if (x.Length==0) [] else [(x[0],x.Substring(1))] );
  def sat(predicate) { item * (x => if (predicate(x)) result(x) else zero()) }
  def symbol(x : char) { sat(y => x==y) }
  def digit = sat(x => '0' <= x && x <= '9');
  def number = many1(digit);
  
  def expr()
  {
   def parentheses =
    symbol('(') * (_ =>
     expr() * ( _=>
      symbol(')') * (_ => result([]))
     )
    );
   
   def trivial = oneOf(number, parentheses);
   
   def mul =
    trivial * ( _ =>
     many1(symbol('*') * ( _ => trivial)) * (_ => result([]))
    );
   
   def sarg = oneOf(mul, trivial);
   
   def sum =
    sarg * ( _ =>
     many1(symbol('+') * ( _ => sarg)) * (_ => result([]))
    );
   
   oneOf(sum,mul,trivial)
  }
  
  WriteLine(expr().Parse("5+42*(8+1)"));
  _ = ReadLine();
 }
}

    Этот уже код должен быть понятен (синтаксически), единственное, что я упустил, это не объяснил, что делает слово def. Это слово произошло от английского define, что значить объявить. Именно этим оно и занимается: позволяет давать имя значению и объявлять локальные функции (относительно метода класса и других локальных функций). Первое похоже на поведение слова var в языке C#, только в немерле изменить значение имени уже нельзя, проще это понять на примере:
def x = 1; // правильно
x = x + 1; // ошибка компиляции
def x = x + 1; // компиляция прошла успешно
mutable y = 1; // mutable — полный аналог var в языке C#
y = y +1; // все хорошо.

Еще одно замечание к коду парсера: expr объявлен как локальная функция, так как его описание ссылается на самого себя.

P.S. Надеюсь я смог адекватно пересказать идеи статьи и поближе познакомить читателей с языком nemerle.

cc-by-nc-sa
Tags:
Hubs:
+17
Comments 9
Comments Comments 9

Articles