В предыдущей статье я описал векторные языки и их ключевые отличия от обычных языков. На коротких примерах я постарался показать, как эти особенности позволяют реализовывать алгоритмы необычным образом, кратко и с высоким уровнем абстракции. В силу своей векторной природы такие языки идеально присоблены для обработки больших данных, и в качестве доказательства в этой статье я полностью реализую на векторном языке простой SQL интерпретатор. А чтобы продемонстрировать, что векторный подход можно использовать на любом языке, я реализую тот же самый интерпретатор на Rust. Преимущества векторного подхода столь велики, что даже интерпретатор в интерпретаторе сможет обработать select с группировкой из таблицы в 100 миллионов строк за 20 с небольшим секунд.
Общий план.
Конечная цель - реализовать интепретатор, способный выполнять выражения типа:
select * from (select sym,size,count(*),avg(price) into r from bt where price>10.0 and sym='fb' group by sym,size) as t1 join ref on t1.sym=ref.sym, t1.size = ref.size
Т.е. он должен поддерживать основные функции типа сложения и сравнения, позволять where и group by выражения, а также - inner join по нескольким колонкам.
В качестве векторного языка я возьму Q, так как его специализация - базы данных.
Интерпретатор будет состоять из лексера, парсера и собственно интерпретатора. Для экономии места я буду приводить только ключевые места, а весь код можно найти здесь. Так же для краткости я реализую лишь часть функциональности, но так, чтобы все важное было на месте: join, where, group by, 3 типа данных, агрегирующие функции и т.п.
На примере лексера вы сможете познакомиться, пожалуй, с одним из самых красивых приемов программирования, который встречается в векторных языках, - использование данных как функций.
Парсеры оперируют деревьями и векторность тут не дает никаких преимуществ. Поэтому в этой части я сделаю упор на Rust и на то, как на нем можно реализовать генератор функциональных рекурсивно-нисходящих парсеров. Несмотря на свою второстепенность, эта часть занимает большое количество места, поэтому я перенес ее в конец, чтобы не утомлять читателей.
Наконец, сам интерпретатор. На Q он имеет весьма скромные размеры - строк 25. На Rust, конечно, гораздо больше, но написать его проще, чем может показаться. Нужно просто по шагам повторять все операции Q, адаптируя их к специфике Rust.
Это моя первая программа на Rust и сразу хочу сказать, что слухи о его сложности сильно преувеличены. Если писать в функциональном стиле (read only), то проблем нет никаких. После того, как Rust несколько раз забраковал мои идеи, я понял, чего он хочет и уже не сталкивался с необходимостью все переделывать из-за контроллера ссылок, а явные времена жизни понадобились только один раз и по делу. Зато взамен мы получаем программу, которую можно распараллелить по щелчку пальцев. Что мы и сделаем, чтобы добиться просто феноменальной производительности для столь примитивной программы.
В завершение о производительности. Векторный подход настолько крут, что без разницы - пишите вы на интерпретируемом языке или на Rust, все равно всю работу делают векторные операции. Поэтому интерпретатор на Q работает всего в полтора раза медленнее самого Q на аналогичных данных.
Лексер
Векторные языки идеальны для написания лексеров. Пусть у нас есть функция fsa, которая принимает на вход текущее состояние лексера и входной символ и возвращает новое состояние:
fsa[state;char] -> state
Если мы применим эту функцию последовательно ко всей входной строке, то получим на выходе последовательность состояний лексера, т.е. каждому символу будет поставлено в соответствие состояние лексера. Все, что нам остается, это найти индексы особых граничных состояний и разрезать по ним входную строку на части. Схему работы лексера можно изобразить наглядно:
Т.е. есть следующие этапы:
-
Кодирование. Входные символы отображаются в группы (my.var -> aa.aaa, 12.01 -> 00.00, "str 1" -> "sss 1" и т.д.).
-
Трансформация. Закодированные символы пропускаются через fsa (aa.aaa -> aAAAAA, 00.00 -> 0IFFF, "sss 1" -> "SSSSSR).
-
Разбиваем начальную строку на части по начальным состояниям (a, 0, " и т.д.). Для удобства все не начальные состояния обозначены большими буквами.
Все три этапа - это векторные операции, поэтому на Q эта идея реализуется одной строкой (все состояния закодированы так, что начальные меньше limit):
(where fsa\[start;input]<limit)cut input
Это в сущности весь лексер. Правда еще необходимо определить fsa. В подавляющем большинстве случаев в качестве fsa можно взять матрицу - таблицу переходов конечного автомата. Простой автомат можно задать и руками, но можно реализовать небольшой DSL. Отображение в группы можно организовать через небольшой массив (ограничимся ASCII символами для простоты):
cgrp: ("\t \r\n";"0..9";"a..zA..Z"),"\\\"=<>.'";c2grp: 128#0; // массив [0;128]// Q позволяет присваивать значения по индексу любой формы.// В данном случае массиву массивов. В Rust необходимы два явных цикла:// cgrp.iter().enumerate().for_each(|(i,&s)| s.iter()// .for_each(|&s| c2grp[s as usize] = i + 1));c2grp[`int$cgrp]: 1+til count cgrp;
Для краткости я не привожу все цифры и буквы. Нас интересуют пробельные символы, цифры, буквы, а также несколько специальных символов. Мы закодируем эти группы числами 1, 2 и т.д., все остальные символы поместим в группу 0. Чтобы закодировать входную строку, достаточно взять индекс в массиве c2grp:
c2grp `int$string
Автомат задается правилами (текущее состояние(я);группа(ы) символов) -> новое состояние. Для обозначения групп и начальных состояний токенов удобно использовать первые символы соответствующих групп (для группы 0..9 - 0, например). Для обозначения промежуточных состояний - большие буквы. Например, правило для имен можно записать так:
aA А a0.
т.е. если автомат находится в состояниях "a" (начало имени) или "A" (внутри имени), и на вход поступают символы из групп [a,0,.], то автомат остается в состоянии "A". В начальное состояние "a" автомат попадет автоматически, когда встретит букву (это правило действует по умолчанию). После этого, если дальше он встретит букву, цифру или точку, то перейдет во внутреннее состояние "A" и будет там оставаться до тех пор, пока не встретит какой-то другой символ. Я запишу все правила без лишних комментариев (Rust):
let rules: [&[u8];21] = [b"aA A a0.", // имена b"0I I 0",b"0I F .",b"F F 0", // int/float b"= E =",b"> E =",b"< E =",b"< E >", // <>, >= и т.п. b"\" S *",b"S S *",b"\"S R \"", // "str" b"' U *",b"U U *",b"'U V '", // 'str' b"\tW W \t"]; // пробельные символы
Числа и строки заданы в упрощенном формате. "*" в качестве входного символа имеет специальное значение - все возможные символы. Большие буквы - это состояния внутри токенов. Такая договоренность дает нам возможность легко определить начало токена - это все состояния, которые не большие буквы.
Матрица fsa из этих правил генерируется элементарно. Схематично это выглядит так:
fsa[*;y] = y (по умолчанию для всех состояний)"aA A a0." -> "aA","A","a0."; fsa[enc["aA"];enc["a0."]] = enc["A"]...
Необходимо закодировать символы с помощью вектора states:
states: distinct " ",(first each cgrp),raze fsa[;1];limit: 2+count cgrp;enc:states?; // в Q encode - это поиск индекса элемента в векторе
Вперед поместим все начальные состояния (пробел для учета группы 0), чтобы можно было легко определить limit.
Код генерации fsa я опускаю - он следует схеме выше.
Матрица переходов у нас есть, осталось определить саму функцию lex. В парсере нам понадобится знать тип токена, поэтому вычислим и его тоже. На Rust лексер выглядит так:
let s2n = move |v| ["ID","NUM","STR","STR","WS","OTHER"][find1(&stn,&v)];move |s| { if s.len()==0 {return Vec::<Token>::new()}; let mut sti = 0usize; let st: Vec<usize> = s.as_bytes().iter().map(|b| { // st:fsa\[0;c2grp x] sti = fsa[sti][c2grp[std::cmp::min(*b as usize,127)]]; sti}).collect(); let mut ix: Vec<usize> = st.iter().enumerate() // ix:where st<sta .filter_map(|(i,v)| if *v<sta {Some(i)} else {None}).collect(); ix.push(st.len()); (0..ix.len()-1).into_iter() .filter_map(|i| match s2n(st[ix[i]]) { "WS" => None, kind => Some(Token{ str:&s[ix[i]..ix[i+1]], kind}) }).collect()
На Q получится значительно более кратко:
s2n:(states?"a0\"'\t")!("ID";"NUM";"STR";"STR";"WS");lex:{ i:where (st:fsa\[0;c2grp x])<limit; {x[;where not "WS"~/: x 0]} (s2n st i;i cut x)};
Если мы запустим лексер, то получим:
lex "10 + a0" -> (("NUM";"";"ID");("10";"+";"a0"))
Интерпретатор
Интерпретатор можно разделить на две части - выполнение выражений и выполнение select. Первая часть тривиальна на Q, но требует большого количества кода на Rust. Я приведу основные структуры данных, чтобы было понятно, как в целом работает интерпретатор. В основе лежит enum Val:
type RVal=Arc<Val>;enum Val { I(i64), D(f64), II(Vec<i64>), DD(Vec<f64>), S(Arc<String>), SS(Vec<Arc<String>>), TBL(Dict<RVal>), ERR(String),}
Есть три типа данных - строки, целые и нецелые, две формы их представления - атомарная и вектор. Также есть таблицы и ошибки. Dict - это пара Vec<String> и Vec<T> одинаковой длины. В случае таблицы T = Vec<RVal>, где каждый Val - это II, DD или SS. Rust позволяет в легкую распаралелливать программу, но нужно, чтобы типы данных позволяли передавать свои значения между потоками. Для этого я обернул все разделяемые значения в асинхронный счетчик ссылок Arc. Считается, что атомарные операции более медленные, однако в программе, которая работает с большими данными, это не имеет большого значения.
Интерпретатор работает с выражениями:
enum Expr { Empty, F1(fn (RVal) -> RRVal, Box<Expr>), // f(x) F2(fn (RVal,RVal) -> RRVal, Box<Expr>, Box<Expr>), // f(x,y) ELst(Vec<Expr>), ID(String), // variable/column Val(Val), // simple value - 10, "str" Set(String,Box<Expr>), // 'set var expr' - assignment Sel(Sel), // select Tbl(Vec<String>,Vec<Expr>), // [c1 expr1, c2 expr2] - create table }
ELst и Empty используются только парсером. Expr (ссылки на себя) необходимо хранить в куче (Box). Выполняются выражения функцией eval в некотором контексте, где заданы переменные (Set), а также могут быть определены колонки таблицы:
struct ECtx { ctx: HashMap<String,Arc<Val>>, // variables}struct SCtx { tbl: Arc<Table>, // within select idx: Option<Vec<usize>>, // idx into tbl grp: Arc<Vec<String>>, // group by cols}
eval сравнительно проста (self = ECtx):
type RRVal=Result<Arc<Val>,String>;fn top_eval(&mut self, e: Expr) -> RRVal { match e { Expr::Set(id,e) => { let v = self.eval(*e, None)?; self.ctx.insert(id,v.clone()); Ok(v)}, Expr::Sel(s) => self.do_sel(s), _ => self.eval(e, None) }}fn eval(&self, e: Expr, sctx:Option<&SCtx>) -> RRVal { match e { Expr::ID(id) => self.resolve_name(sctx,&id), Expr::Val(v) => Ok(v.into()), Expr::F1(f,e) => Ok(f(self.eval(*e,sctx)?)?), Expr::F2(f,e1,e2) => Ok(f(self.eval(*e1,sctx)?,self.eval(*e2,sctx)?)?), Expr::Tbl(n,e) => { self.eval_table(None,n,e) } e => Err(format!("unexpected expr {:?}",e)) }}
Set и Sel нужен модифицируемый контекст, а его нельзя будет передать просто так в другой поток. Поэтому eval разбит на две части. Задача resolve_name - найти переменную или колонку и при необходимости применить where индекс. eval_table - собрать таблицу из частей и проверить, что с ней все в порядке (колонки одной длины и т.п.). Функции F1 (max, count ...) и F2 (+, >=, ...) сводятся к огромным match блокам, где для каждого типа прописывается нужная операция. Макросы позволяют уменьшить количество кода. Например, для арифметических операций часть match выглядит так:
(Val::D(i1),Val::I(i2)) => Ok(Val::D($op(*i1,*i2 as f64)).into()),(Val::D(i1),Val::D(i2)) => Ok(Val::D($op(*i1,*i2)).into()),(Val::I(i1),Val::II(i2)) => Ok(Val::II(i2.par_iter() .map(|v| $op(*i1,*v)).collect()).into()),
Это может показаться неоптимальным, но когда вы обрабатываете таблицу на 100 миллионов строк, это не имеет ни малейшего значения. Видите слово par_iter выше? Это все, что нужно сделать в Rust, чтобы операция стала параллельной.
Выполнение select гораздо интереснее и сложнее. Разберем его на Q, потому что код на Rust многословно повторяет код на Q, который и сам по себе непростой.
Select состоит из подвыражений (join, where, group, select, distinct, into), каждое из которых выполняется отдельно. Самое сложное из них - join. В его основе лежит функция rename, задача которой присвоить колонкам уникальные имена, чтобы не возникло конфликта при join:
// если x это name -> найти, select -> выполнитьsget:{[x] $[10=type x;get x;sel1 x]};// в грамматике таблица определяется как '(ID|sel) ("as" ID)?'// так что x это список из 2 элементов: (ID из as или имя таблицы;ID/select)// y - уникальный префиксrename:{[x;y] t:sget x 1; // получить таблицу: names!vals k:(k!v),(n,/:k)!v:(y,n:x[0],"."),/:k:key t; // k - оригинальные имена, // v - уникальные, n - с префиксом (table.name) (k;v!value t)};
Все эти манипуляции сводятся к построению двух словарей - отображения из настоящих имен колонок и расширенных (table.name) в уникальные и из уникальных имен в сами колонки таблицы. Уникальные имена позволяют иметь в одной join таблице колонки с одинаковыми именами из разных таблиц и обращаться к ним в выражениях через нотацию с точкой.
В основе join следующая функция:
// x - текущая таблица в формате rename// y - следующая таблица в этом формате// z - join выражение, список (колонка в x;и в y)// условие join: x[z[i;0]]==y[z[i;1]] для всех ijoin_core:{[x;y;z] // m - отображение имен в уникальные для новой таблицы x+y // имена из x имеют приоритет // c - переименовываем join колонки в уникальные имена c:(m:y[0],x 0)z; // после join z[;0] и z[;1] колонки будут одинаковыми // поэтому колонки из y перенаправим на x m[z[;1]]:c[;0]; // x[1]c[;0] - просто join колонки из таблицы x (подтаблица) // y[1]c[;1] - симметрично из y // sij[xval;yval] -> (idx1;idx2) найти индексы join в обеих таблицах // sidx[(i1;i2);x;y без join колонок] - // собрать новую таблицу из x и y и индексов (m;sidx[sij[x[1]c[;0];y[1]c[;1]];x 1;c[;1]_ y 1])}// sidx просто применяет индексы ко всем колонкам и объединяет y и z// y z - это словари, но поскольку традиционно векторные функции имеют// максимально широкую область определения, не нужно обращаться явно к value sidx:{(y@\:x 0),z@\:x 1};
Вся работа выполняется в функции sij, все остальное - это манипуляции именами, колонками и индексами. Если бы мы захотели добавить другой тип индекса, достаточно было бы написать еще одну sij. Конечно, функция выглядит непросто, но учитывая, что она покрывает 80% select, ей можно это простить.
Функция sij сводится к поиску строк таблицы x в таблице y. В Rust для этих целей можно использовать HashMap с быстрой hash функцией FNV - поместить в Map одну таблицу и потом искать в ней строки второй. В Q, судя по времени выполнения, скорее всего используется что-то подобное. В целом в Q у нас есть два варианта - использовать векторные примитивы или воспользоваться встроенными возможностями связанными с таблицами. В первом варианте все по-честному:
// x и y - списки колонокsij:{j:where count[y 0]>i:$[1=count x;y[0]?x 0;flip[y]?flip x]; (j;i j)};// или на псевдокоде// i=find_idx[tblY;tblX]; j=i where not null i; return (j,i[j])
используем функцию поиска значения в векторе (?) и транспозиции матрицы (flip). Этот вариант не такой медленный как может показаться - всего в 2.5 раза медленнее, чем оптимизированный поиск сразу по таблице (который выглядит ровно также - x?y, только x и y - таблицы, а не списки векторов). Это показывает в очередной раз силу векторных примитивов.
Наконец сам join - это просто цикл свертки по всем таблицам (fold):
// "/" это fold, rename' это map(rename)sjoin:{[v] join_core/[rename[v 0;"@"];rename'[v 1;string til count v 1];v 2]};
Остальные части select гораздо проще. where:
swhere:{[t;w] i:til count value[t 1]0; // все строки по умолчанию $[count w;where 0<>seval[t;i;();w];i]}; // выбрать те, которые не 0// seval такой же как eval в Rust, т.е. его сигнатура:// seval[table,index;group by cols;expr], ECtx - это сам Q
Основная функция select:
sel2:{[p] // p ~ словарь с элементами select (`j, `s, `g и т.п.) i:swhere[tbl:sjoin p`j;p`w]; // сходу делаем join и where if[0=count p`s; // в случае select * надо найти подходящие имена колонкам rmap:v[vi]!key[tbl 0] vi:v?distinct v:value tbl 0; p[`s]:{nfix[x]!x} rmap key tbl 1]; if[count p`g; // group by // из group колонок нужен только первый элемент, нужно знать их имена gn:nfix {$[10=type x;x;""]} each p`g; // sgrp вернет список индексов (idx1;idx2;..) для каждой группы // затем нужно выполнить seval[tbl;idxN;gn;exprM] для всех idx+expr // т.е. двойной цикл, который в Q скрыт за двумя "each" g:sgrp[tbl;i;p`g]]; :key[p`s]!flip {x[z] each y}[seval[tbl;;gn];value p`s] each g; // если group нет, то все элементарно - просто seval для всех select выражений (),/:seval[tbl;i;()] each p`s };
Функция sgrp в основе group by - это просто векторный примитив group, возвращающий словарь, где ключи - уникальные значения, а значения - их индексы во входном значении:
sgrp:{[t;i;g] i value group flip seval[t;i;()] each g};
Я опускаю distinct и into части, поскольку они малоинтересны. В целом - это весь select на Q. В краткой записи он занимает всего 25 строк. Можно ли ждать хоть какой-то производительности от столь скромной программы? Да, потому что она написана на векторном языке!
Производительность
Напомню, что этот игрушечный интерпретатор может выполнять выражения типа
select * from (select sym,size,count(*),avg(price) into r from bt where price>10.0 and sym='fb' group by sym,size) as t1 join ref on t1.sym=ref.sym, t1.size = ref.size
и при этом справляться с таблицами в сотни миллионов строк. В частности таблица bt в выражении выше сгенерирована выражением:
// в интерпретаторе на Rust// s = ("apple";"msft";"ibm";"bp";"gazp";"google";"fb";"abc")// i/f - i64/f64 интервалы [0-100)set bt [sym rand('s',100000000), size rand('i', 100000000), price rand('f', 100000000)]
Т.е. содержит 100 миллионов строк. Поначалу базовый select с group by (получается 800 групп по ~125000 элементов)
select sym,size,count(*),avg(price) into r from bt group by sym,size
работал 44 секунды в программе на Rust, что совсем неплохо и само по себе. Однако после некоторых оптимизаций, а главное распаралелливания ключевых операций, мне удалось добиться скорости порядка 6 секунд. На мой взгляд весьма хороший результат для подобной таблицы.
Самое главное, программа на Rust, несмотря на свой внушительный вид, - это почти 1 в 1 программа на Q. Поэтому больших интеллектуальных усилий и даже отладки она не потребовала. Также благодаря векторности изначального языка ее ускорение путем распараллеливания не потребовало почти никаких усилий - если все операции изначально над массивами, то все что нужно - это вставить там и тут par_iter вместо iter.
Интерпретатор на Q не столь быстр, но вышеуказанный select всего на 50% медленнее аналогичного запроса на самом Q. Это значит, что по сути Q работает на больших данных почти также быстро, как и программа на компилируемом языке.
Хочу также отметить то, насколько великолепным языком проявил себя Rust. За все время разработки и отладки я не получил ни одного segfault и даже panic увидел всего несколько раз, и почти все это были простые ошибки выхода за пределы массива. Также поражает, насколько легко и безопасно в нем можно распараллелить задачу.
Парсер
Я отложил парсер на конец, поскольку он довольно объемен и не имеет прямого отношения к теме статьи. Тем не менее, может вам будет интересно ознакомиться с тем, как легко можно написать весьма серьезный парсер в функциональном стиле на Rust.
Это рекурсивный нисходящий парсер без заглядывания вперед. Из-за этого он не может предсказать следующий шаг и вынужден обходить все варианты. Такой парсер, конечно, медленный и не годится для серьезных задач, но для SQL выражений больше и не надо. Какая разница, парсится выражение 1 микросекунду или 10, если сам запрос займет минимум сотни микросекунд.
Такие парсеры часто пишут руками, и выглядят они примерно так:
parse_expr1(..) { if(success(parse_expr2(..)) { if (success(parse_str("+") || success(parse_str("-")) { if(success(parse_expr1(..)) { return <expr operation expr> } return Fail } return <expr> } return Fail;}
Главная идея предлагаемого парсера в том, что нет смысла писать это все руками, можно написать генератор подобных парсеров из BNF-подобной формы. Для всех сущностей BNF пишем по функции, затем генерируем из описания грамматики в виде строк набор парсящих функций, и все готово. В Rust, как строго типизированном языке, есть нюансы. В первую очередь определим типы для парсящих и post process функций:
type ParseFn = Box<dyn Fn(&PCtx,&[Token],usize) -> Option<(Expr,usize)>>;type PPFn = fn(Vec<Expr>) -> Expr;
ParseFn будет захватывать правила грамматики, поэтому она должна быть замыканием (closure) и лежать в куче. PCtx содержит другие ParseFn для рекурсивных вызовов и PPFn для постобработки дерева. Если парсинг не удался, она возвращает None, иначе Some с выражением и новым индексом в массив токенов. PPFn обрабатывает узел дерева, поэтому принимает безликий список выражений и превращает его в нужное выражение.
Для понимания процесса приведу часть грамматики, касающуюся выражений:
("expr", "expr1 ('or' expr {lst})? {f2}"),("expr1","'not' expr1 {f1} | expr2 ('and' expr1 {lst})? {f2}"),("expr2","expr3 (('='|'<>'|'<='|'>='|'>'|'<') expr2 {lst})? {f2}"),("expr3","expr4 (('+'|'-') expr3 {lst})? {f2}"),("expr4","vexpr (('*'|'/') expr4 {lst})? {f2}"),("vexpr","'(' expr ')' {2} | '-' expr {f1} | call | ID | STR | NUM | '[' (telst (',' telst)* {conc}) ']' {tblv}"),("call", "('sum'|'avg'|'count'|'min'|'max') '(' expr ')' {call} | 'count' '(' '*' ')' {cnt} | 'rand' '(' STR ',' NUM ')' {rand}"),
Тут видны ключевые части - имя правила, само правило и PP функции в фигурных скобках. Каждая продукция правила должна заканчиваться на PP функцию, поскольку правило возвращает Expr, а не Vec<Expr>. PP функция по умолчанию возвращает последний элемент вектора, поэтому кое-где PP функций нет. ID, NUM и т.п. должны обрабатываться ParseFn функцией с соответствующим именем.
Генерируется наш парсер с помощью следующей функции:
let parse = |str| { let t = l(str); // add ({}) depth map let mut lvl = 0; pp_or(&t.into_iter().map(|v| { match v.str.as_bytes()[0] { b'(' | b'{' => lvl+=1, b')' | b'}' => lvl-=1, _ => ()}; (v,std::cmp::max(0,lvl))}).collect::<Vec<(Token,i32)>>() , 0)};
l - это лексер, я переиспользую для этого лексер SQL. Нужно добавить карту глубины вложенности скобок, чтобы было удобно выделять BNF подвыражения. Поскольку это парсер для внутренних потребностей, то нет необходимости проверять правильность скобок, беспокоиться о глубине рекурсии и т.п.
Далее наше правило поступает в парсер BNF. Нужно реализовать следующие компоненты:
-
or правило - A | B
-
and правило - A B C
-
const правило - "(", "select".
-
token правило - NUM, STR.
-
subrule правило - expr1, call.
-
optional правило - A?
-
0+ правило - A*
-
1+ правило - A+
-
PP правило - {ppfn}
Это работа, требующая тщательности, но проделать ее нужно один раз. Например, or правило:
fn pp_or(t: &[(Token,i32)], lvl:i32) -> ParseFn { if t.len() == 0 {return Box::new(|_,_,i| Some((Expr::Empty,i)))}; let mut r: Vec<ParseFn> = t .split(|(v,i)| *i == lvl && v.str.as_bytes()[0] == b'|' ) .map(|v| pp_and(v,lvl)).collect(); if 1 == r.len() { r.pop().unwrap() } else { Box::new(move |ctx,toks,idx| r.iter().find_map(|f| f(ctx,toks,idx))) }}
Функция должна вернуть ParseFn замыкание. В общем случае, когда pp_and вернула несколько ParseFn, нужно организовать цикл и выполнять подфункции, пока одна из них не вернет Some.
pp_and работает аналогично, только все ее подфункции должны вернуть Some. Также в случае успеха она должна вызвать нужную PPFn для обработки результата.
fn pp_and(t: &[(Token,i32)], lvl:i32) -> ParseFn { if t.len() == 0 {return Box::new(|_,_,i| Some((Expr::Empty,i)))}; let (rules,usr) = pp_val(Vec::<ParseFn>::new(),t,lvl); Box::new(move |ctx,toks,i| { let mut j = i; let mut v = Vec::<Expr>::with_capacity(rules.len()); for r0 in &rules { if let Some((v0,j0)) = r0(ctx,toks,j) { j = j0; v.push(v0) } else {return None} }; Some((ctx.ppfns[&usr](v),j)) })}
pp_val рекурсивно обрабатывает круглые скобки и все базовые выражения. Вот некоторые примеры из нее:
// Token - if ok call rules[Token]move |ctx,tok,i| if i<tok.len() && tok[i].kind == s {ctx.rules[&s](ctx,tok,i)} else {None}// Subrulemove |ctx,tok,i| ctx.rules[&s](ctx,tok,i))}// rule?move |ctx,tok,i| Some(rule(ctx,tok,i).unwrap_or((Expr::Empty,i)))// rule+move |ctx,tok,i| { let (e,i) = plst(&rule,ctx,tok,i); if 0<e.len() {Some((Expr::ELst(e),i))} else {None}}// где plstlet mut j = i; let mut v:Vec<Expr> = Vec::new();while let Some((e,i)) = rule(ctx,tok,j) {j=i; v.push(e)};(v,j)
Это весь код, необходимый для создания парсера. Чтобы его сгенерировать, нужно вызвать parse и положить правило в map:
let mut map = HashMap::new();map.insert("expr".to_string(), parse("expr1 ('or' expr {lst})? {f2}"));...
Также необходимо определить PP функции. В большинстве случаев они сравнительно просты:
let mut pfn: HashMap<String,PPFn> = HashMap::new();// default rulepfn.insert("default".to_string(),|mut e| e.pop().unwrap());// set name expr выражениеpfn.insert("set".to_string(),|mut e| Expr::Set(e.swap_remove(1).as_id(), e.pop().unwrap().into()) );
В Rust нельзя просто взять элемент из массива, поэтому необходимы функции типа swap_remove, которые делают это безопасно.
Наконец, положим правила в специальную структуру и определим для нее функцию parse:
PCtx { rules:map, ppfns:pfn}...impl PCtx { fn parse(&self, t:&[Token]) -> Expr { if let Some((e,i)) = self.rules["top"](&self,t,0) { if i == t.len() {e} else {Val::ERR("parse error".into()).into()} } else {Val::ERR("parse error".into()).into()} }}
Все, парсер готов. Он не быстр, но зато очень прост. Плюс он полностью динамический - можно менять правила во время выполнения программы, например, отключить какие-то возможности.
