[PEG] Дизайн и эволюция
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 19:17
Оценка:
Надо обдумать следующие вещи:

1. Оптимизации. Из наиболее очевидных мне видятся:
1) упрощенные ДКА (позволяющие не входить в заведомо не разбираемые для текущего символа подправила);
2) точках отсечения (позволяющие не откатываться до нуля, а выдавать сообщения об ошибках и обнулять хэш-таблицу мемоизации, если таковая будет использоваться).
2. Генерацию осмысленных сообщений об ошибках при этом не понижая (существенно) производительности парсера.
3. Мемоизацию. Можно ли создать алгоритм который статически вычислит правила требующие мемоизации? Конечно можно мемоизировать все нетермиальные правила не удовлетворяющие LL(1), но боюсь, что это будет не очень эффективно.
4. Динамическое расширение. Точнее о том, как реализовать остальные пункты при этом не потеряв возможности реализовать динамическое расширение парсера?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: [PEG] Дизайн и эволюция
От: para  
Дата: 28.03.10 08:08
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>2. Генерацию осмысленных сообщений об ошибках при этом не понижая (существенно) производительности парсера.
как я понимаю:

ошибки у нас двух типов: семантические и синтаксические
1 — выявляются при формировании нетерминальных символов, например деление на ноль при раскрытии правила деления
2 — (синтаксические и лексические одновремменно) — неправильные терминальные символы определяются самим парсером и выглядят как return -1
за исключением случая для правила выбора из нескольких терминальных символов

как можно наверное сделать (пока теретически, на оптимальность не претендую):

если токен ошибочный, то возвращать вместо или внутри него факт ошибки. как парсером, так и программистом.
если подправило вернуло токен с ошибкой, то распарсить другие подправила и вернуть ошибку, обработчик правила не вызывать.(нейтрализация ошибки)

По осмысленности сообщений:
знаем токен и его локейшн, знаем конкретную позицию ошибочного символа , знаем правило которое не может разобрать
на основе этого можем вывести: error in "..." got ".." expected "..." or...
плюс можем дать возможность программисту переопределить выходящие сообщения

Про валидаю самой грамматики:
Если Составить грамматику для нотации PEG, и сгенерить для неё парсер, то ошибки в грамматике будут определятся природой парсера
хотя наверное слишком заумно?

По оптимизации:
у нас выполняется немного холостой работы при откатах при разборе правила выбора, как я понимаю.
было бы неплохо ранжировать последовательность попыток парсинга подправил, в зависимости от сложности подправила, а ещё лучше в зависимости от статистической частоты встречи этого подправила на реальных текстах.
не берусь оценить сложность и полезность такого выкрутаса.

Влад где-то писал про проход парсером второй раз для вывода ошибок
на самом деле надо второй раз проходить не по всем правилам и не по всему тексту, а только если разбор всех подправил Choice завершился ошибкой
Re[2]: [PEG] Выявление ошибок и сигнализация об ошибках
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.03.10 10:54
Оценка:
Здравствуйте, para, Вы писали:

P>ошибки у нас двух типов: семантические и синтаксические

P>1 — выявляются при формировании нетерминальных символов, например деление на ноль при раскрытии правила деления
P>2 — (синтаксические и лексические одновремменно) — неправильные терминальные символы определяются самим парсером и выглядят как return -1
P>за исключением случая для правила выбора из нескольких терминальных символов

С семантическими ошибками все ясно. Нужно только продумать механизм через который методы-обработчики смогут сообщить об ошибках. Кроме того, PEG-парсер может очень сильно откатиться и ошибка выданная из обработчика может оказаться просто ложным срабатыванием. По тому ошибки как и результат парсинга нужно накапливать в возвращаемом значении.

P>как можно наверное сделать (пока теоретически, на оптимальность не претендую):


P>если токен ошибочный, то возвращать вместо или внутри него факт ошибки. как парсером, так и программистом.

P>если подправило вернуло токен с ошибкой, то распарсить другие подправила и вернуть ошибку, обработчик правила не вызывать.(нейтрализация ошибки)

Основная сложность парсера с откатами состоит в том, что до окончания всего процесса парсинга мы не можем сказать был ли откат вызван ошибкой во входных данных (разбираемой строке, далее "ошибкой") или природой грамматики.

Скажем разбираем мы число. У нас могут быть варианты:
1. Число с плавающей точкой начинающееся с цифр с точкой идущей после цифр.
2. Число с плавающей точкой начинающееся с точки.
3. Число с плавающей точкой начинающееся с цифр но не имеющее точки, а содержащее мантису или суффикс описывающий тип числа.
4. Целое число.
5. Шестнадцатеричное целое число.

Вот как это примерно выглядит:
decimalDigits             = digit+;
hexDigit                  = ['0'..'9', 'A'..'F', 'a' .. 'f'];
integerTypeSuffix         = 'U' / 'u' / 'L' / 'l' / "UL" / "Ul" / "uL" / "ul" / "LU" / "Lu" / "lU" / "lu";
decimalIntegerLiteral     = decimalDigits !(realTypeSuffix / E / '.') integerTypeSuffix? spaces;
hexadecimalIntegerLiteral = '0' ('x' / 'X') hexDigit+  integerTypeSuffix? spaces;
integerLiteral            = decimalIntegerLiteral / hexadecimalIntegerLiteral;
exponentPart              = E  ('+' / '-' / Empry)   decimalDigits;
E                         = 'e' / 'E';
realTypeSuffix            = 'F' / 'f' / 'D' / 'd' / 'M' / 'm';

// decimalIntegerLiteral пересекается с realLiteral, так что нужно использовать предикаты или ставить 
// realLiteral раньше decimalIntegerLiteral в преорететном выборе!
realLiteral1              = decimalDigits  '.'   decimalDigits   exponentPart?   realTypeSuffix?;
realLiteral2              =                '.'   decimalDigits   exponentPart?   realTypeSuffix?;
realLiteral3              =                      decimalDigits   exponentPart    realTypeSuffix?;
realLiteral4              =                      decimalDigits                   realTypeSuffix;
realLiteral               = realLiteral1 / realLiteral2 / realLiteral3 / realLiteral4;


Все числа, кроме пункта два, могут начинаться с цифры. При этом, большее число правил разбора цифр начинается с подправила decimalDigits (т.е. нескольких идущих последовательно цифр).

Таким образом откаты возникают неизбежно даже при разборе совершенно корректных правил.
По этому невозможно достоверна сказать является ли возврат правилом -1 признаком наличия ошибки (ошибки во входных данных) или это часть более общего правила которое будет успешно распарсено после некоторого отката и перехода к другому подправилу.

Очевидно, что ошибкой является откат из правила в которое парсер вошел с наибольшим значением позиции. Скажем если мы разбираем строку:
/* Ля-ля-ля */ 1234(321

То ошибкой будет символ "(", но правило разбора числа отработает совершенно корректно и распознает целое число!
Возьмем другой пример:
1234.23

Здесь при разборе целого числа спарсится подправило decimalDigits, но после, когда будет достигнут символ '.' будет произведен откат, так как этот символ не удовлетворяет предикату "!(realTypeSuffix / E / '.')". Далее будет произведена попытка разбора других правил разбора чисел и одно из них таки распознает число с плавающей точкой.

О том, что произошла ошибка мы можем узнать только когда произойдет откат из самого первого правила (например, start).

Так вот, нашей задачей является выявление списка правил предшествующих получению отката из при максимально возможной позиции.

Мы должны выдать сообщение типа: "В позиции Х ожидается: $(список правил которые потерпели неудачу в этой позиции)".

Кроме того в реальном парсере нельзя завершать парсинг при обнаружении первой ошибки. Парсер, может работать в режиме IDE и программист даже в программе содержащей ошибки хочет видеть фолдинг (сворачивание частей коде), подсветку синтакчиса, навигацию по списку типов и их членов (комбы в редакторе IDE).

Для этого нужно уметь восстанавливаться после сбоя. В принципе восстановление может быть возложено на саму грамматику.

Скажем в список правил разбирающих подвыражения внутри блока (фигурных скобок содержащих подвыражения разделенные точкой с запятой):
block = '{' (expr ';')* '}';

можно расширить правило:
block     = '{' (expr ';' / errorExpr)* '}';
errorExpr = (!(';' / '}') any)+ ';'?;

Правило errorExpr будет принимать любой ввод до ";" (включительно) или до "}". При этом обработчик этого правила должен возвращать специальный элемент AST описывающий ошибку.

Если запихивать такие обработчики всюду, то возможно будет даже обойтись без автоматического выявления ошибок. Но парсеры пишут люди и мы не можем полагаться, что они учтут все нюансы. К тому же это много лишней работы.

Таким образом парсер должен уметь сам выявить ошибку — набор правил не распознавших самый вложенный ввод (с самой большой позицией).

Кроме того нужно ввести точки отсечения — это некий синтаксис указывающий макросу, что если парсер дошел до этого места в правиле, то откатываться за это место бессмысленно и если это происходит нужно вместо этого начинать процедуру выявления ошибки и генерацию сообщения об ошибки.

Возможно что к точкам отсечения удастся прикрутить и средства автоматического восстановления.

Скажем пример с разбором блока, приведенный выше, можно переписать следующим образом, с использованием точек отсечения:
block     = '{' (expr # ';')* # '}';

Знак "#" здесь означает точку отсечения. Парсер не должен откатываться за эту точку вместо этого он должен автоматически сгенерировать код сообщающих об ошибке и производящий восстановление состояния парсера (пропускать все символы пока не встретится следующий обязательный символ или один из необязательных (идущих за #).

В приведенном примере точек отсечения две, так как ошибка может быть как внутри отдельного выражения, тогда имеет смысл попытаться восстановиться до следующей точки с запятой. Кроме того после ошибки может и не следовать точки с запятой, но следовать закрывающая фигурная скобка. Тогда откатываться нужно до нее. Таким образом код отката должен генерироваться весьма хитрой логикой учитывающей внешние коды отката. Иначе может получиться так, что в выражении:
{ 1 + } - 2;

откат произойдет не до закрывающей фигурной скобки, а до точки с запятой идущей после двойки, а это нарушит парность скобок, что приведет к появлению тучи наложенных ошибок в дальнейшем.


Подытоживая, хочу еще раз акцентировать внимание задачах. Их две:
1. Выявления самой дальней позиции которая не сопоставилась ни с одним правилом и выявления списка правил которые в этот момент парсер пытался применить.
2. Реализация точек отсечения позволяющих с одной стороны остановить бессмысленные откаты, а с другой сгенерировать код восстановления после ошибок.

С первым пунктом самая большая проблема — это производительность! Ведь для того чтобы получить эту самую максимальную позицию и список правил их нужно запоминать при каждом откате (или наоборот, при увеличении позиции). При этом позицию нужно сравнивать с предыдущей (чтобы не запомнить меньшую позицию). А это такты процессора, то есть тормоза!

Вот и приходит на ум идея, раз уж особенностями PEG-а являются массовые откаты не позволяющие осуществлять никакие побочные эффекты (хранить данные в полях или глобальных переменных), то может быть для выявления ошибок проще прогнать парсер два раза?
Первый проход — скоростной. В нем не производится запоминание информации о максимальной позиции и правил которые парсер пытается распознать в этом месте.
Второй проход — "педантичный". В нем производятся все проверки и запоминается максимальная позиция.

При наличии точек отсечения может статься так, что до второго прохода дело не дойдет даже при наличии ошибок. Это делает двухпроводную схему в двойне оправданной!

При втором проходе нужно использовать другой парсер. Это должна быть копия исходного парсера но с кодом учета максимальной позиции и списка применяемых правил. Он будет работать чуть медленнее, но зато выдаст требуемое сообщение об ошибке.

Альтернативный вариант — добавлять код учета максимальной позиции и списка применяемых правил в основной парсер. Но боюсь, что это может несколько замедлить основной парсер. В прочем, если это замедление будет несущественным (скажем, до 10%), то этим можно пренебречь.

Таким образом разумно было бы попытаться реализовать оба варианта (с отдельной копией парсера и с парсером в котором всегда встроен код обработки ошибок) и сравнить быстродействие.

Вот этим исследованием и нужно заняться.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.