Pull to refresh

Monadic Parser Combinator в Nemerle

Programming
Недавно обнаружил замечательную статью 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:nemerlehaskell
Hubs: Programming
Total votes 17: ↑17 and ↓0+17
Views1.9K

Popular right now

Top of the last 24 hours