[PEG] Добавил в сниппеты еще один пример. - Nemerle

Интересу ради решил попробовать в деле генератор парсеров.
Задачу выбрал синтетическую — разбор некоего подмножества JavaScript.

Парсер, доступный в ревизии 8980 умеет разбирать псевдопрограммы вроде этой:

var x1 = "asfasdasdf"; // comment
x2.bla = 'dfasdf"asdfsd" asds';

x = y.z = t ? a : 0x23 * 7 + 1;
; //empty statement !
function Foo(
    a1 /* a1 arg*/ ,
    b,
    c) {
  var s = t ? true : false ? h ? 7 : 8++ : g ? 3 + bar(1, 2).f : 4;
  var tmp = this.xxx(/* no args! */)(a1, /* passing b*/ b, c /*and c*/).result;
  return function(k, t) { return ++0x45ff+++1; };
}

На выходе он в презентабельном виде отображает AST:


var x1 = "asfasdasdf";
x2.bla = 'dfasdf"asdfsd" asds';
x = y.z = (t ? a : (0x23 * (7 + 1)));;
function Foo(a1, b, c)
{
    var s = (t ? true : (false ? (h ? 7 : (8++)) : (g ? (3 + bar(1, 2).f) : 4)));
    var tmp = this.xxx()(a1, b, c).result;
    return function (k, t)
    {
        return ((++(0x45ff++)) + 1);
    };
}

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

Возникли два вопроса:

1) Как обрабатывать ошибки?
2) Что делать если в языке ключевые слова регистронезависимые (Pascal, SQL)?

Здравствуйте, hardcase, Вы писали:

H>Возникли два вопроса:

H>1) Как обрабатывать ошибки?

Пока что путем ведения дополнительных правил которые отлавливают ошибку. Пример можно поглядеть в коде строчного калькулятора:
http://nemerle.googlecode.com/svn/nemerle/trunk/snippets/peg-parser/Calculator/CalcParser.n

    any                   = ['\u0000'..'\uFFFF'];
    digit                 = ['0'..'9']+;
    spaces                = ' '*;
    
    num                   : int = digit spaces;
    unaryMinus            : int = '-' spaces simplExpr;
    parenthesesExpr       : int = '(' spaces sumOrSub ')' spaces;
    parenthesesExprError  : int = '(' spaces sumOrSub (any / !any);
    simplExpr             : int = num / parenthesesExpr / unaryMinus / parenthesesExprError / simplExprError;
    simplExprError        : int = any;
    inputError            : int = any;
    mulOrDiv              : int = simplExpr (('*' / '/') spaces simplExpr)*;
    sumOrSub              : int = mulOrDiv  (('+' / '-') spaces mulOrDiv )*;
    mainRule              : int = sumOrSub inputError?;
    start                 : int = spaces mainRule !any;

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

По уму нужно дорабатывать парсер следующим образом:
1. Добавить конструкцию Error (или Fail), которая будет принимать сообщение об ошибке. Такую констуркцию можно будет использовать вместо правил отлавливающих ошибки. Таким образом вместо:

    parenthesesExpr       : int = '(' spaces sumOrSub ')' spaces;
    parenthesesExprError  : int = '(' spaces sumOrSub (any / !any);
    simplExpr             : int = num / parenthesesExpr / unaryMinus / parenthesesExprError / simplExprError;
    simplExprError        : int = any;
...
    private parenthesesExprError(first : NToken, _ : NToken, _ : VToken[int], _ : NToken) : int
    {
      throw ParserFatalError("Не закрытая скобка", first.EndPos);
    }
    
    private simplExprError(tok : NToken) : int
    {
      throw ParserFatalError("Ожидается число или выражение в скобках", tok.StartPos);
    }

Позволили бы писать:

    parenthesesExpr       : int = '(' spaces sumOrSub ')' spaces;
    simplExpr             : int = num / parenthesesExpr / unaryMinus / '(' Error("Не закрытая скобка") / Error("Ожидается число или выражение в скобках");

Или так:

    parenthesesExpr       : int = '(' spaces sumOrSub ')' spaces;
    simplExpr             : int = num / parenthesesExpr / unaryMinus / parenthesesExprError / simplExprError;
    parenthesesExprError  : int = '(' Error("Не закрытая скобка");
    simplExprError        : int = Error("Ожидается число или выражение в скобках");

Кроме того нужна некая сокращенная форма для Error которую можно ставить перед некоторым литеральным правилом и которое само будет формировать сообщение типа "Ожидается то-то и то-то". При этом, естественно, откатов (бэктрекинга) быть не должно.

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

Я думал этим заняться. Мне это тоже нужно для тех же ХМЛ-литералов и вообще. Но если кто-то хочет помочь в расширении функционала ПЕГ-парсера, то я буду только "за"!

H>2) Что делать если в языке ключевые слова регистронезависимые (Pascal, SQL)?

Пока что можно использовать только такое извращение:

selectKwd = ('S' / 's') ('E' / 'e') ('L' / 'l') ('E' / 'e') ('C' / 'c') ('T' / 't');

Это конечно же маразм, так что нужно придумывать что-то более удобное. Что конкретно? Над этим надо думать.

В голову приходит следующее:
1. Давать префиксы или суффиксы для строковых литералов означающие, что нужно использовать ингорирование регистра при сравнении:

i"select"

2. Для ключевых слов, возможно, имеет смысл реализовать специализированное решение (если не ошибаюсь в Rats! сделано именно так).
3. Возможно имеет смысл ввести рукописные расширения. Тогда можно было бы реализовать функцию парсинга ключевых слов наиболее эффективным для конкретного языка образом (вручную).

Здравствуйте, hardcase, Вы писали:
H>

H>x = y.z = t ? a : 0x23 * 7 + 1;
H>

H>На выходе он в презентабельном виде отображает AST:
H>

H>x = y.z = (t ? a : (0x23 * (7 + 1)));;
H>

Кстати — это ошибка. У умножения приоритет должен быть выше. Так что скобки не верно выведены или распознавание не верное.

H>Основная проблема с которой пришлось бороться — это ликвидация в правилах левой рекурсии без продвижения по строке.

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

Здравствуйте, hardcase, Вы писали:

А почему JSParser.GUI на Шарпе? За одно WinForms постестировал бы.

Здравствуйте, VladD2, Вы писали:

VD>Кстати — это ошибка. У умножения приоритет должен быть выше. Так что скобки не верно выведены или распознавание не верное.

А задавать декларативно приоритет операторов как в Irony у вас нельзя? Некоторым это жизнь сильно упростило бы.

Здравствуйте, VladD2, Вы писали:

VD>В голову приходит следующее:
VD>1. Давать префиксы или суффиксы для строковых литералов означающие, что нужно использовать ингорирование регистра при сравнении:
VD>

VD>i"select"
VD>

VD>2. Для ключевых слов, возможно, имеет смысл реализовать специализированное решение (если не ошибаюсь в Rats! сделано именно так).
VD>3. Возможно имеет смысл ввести рукописные расширения. Тогда можно было бы реализовать функцию парсинга ключевых слов наиболее эффективным для конкретного языка образом (вручную).

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

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, hardcase, Вы писали:
H>>

H>>x = y.z = t ? a : 0x23 * 7 + 1;
H>>

H>>На выходе он в презентабельном виде отображает AST:
H>>

H>>x = y.z = (t ? a : (0x23 * (7 + 1)));;
H>>

VD>Кстати — это ошибка. У умножения приоритет должен быть выше. Так что скобки не верно выведены или распознавание не верное.

Это правило неверное:

infixOperator           : string    = ('+' / '-' / '*' / '/') spaces;

Тут надо поступать так же как в примере "Calculator":

    mulOrDiv              : int = simplExpr (('*' / '/') spaces simplExpr)*;
    sumOrSub              : int = mulOrDiv  (('+' / '-') spaces mulOrDiv )*;

Тут суть в том, что выражение типа "X * Y — Z" рассматривается как "(X * Y) — Z", а выражение "X — Y * Z" как "X — (Y * Z)". Так вот чтобы эти приоритеты отразить в грамматике нужно рассматривать любое сложение или вычитание как сложение или вычитание потенциального умножения или деления, а умножение или деление как потенциальное простое выражение или умножение или деление.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Необходимость писать рукописное расширение для регистронезависимых ключевых слов людей не обрадует. Все же довольно распространенный юз-кейс. В идеале бы — специальную настройку как в кокоре.

Я уже не помню как там в КокоР-е было все сделано, но там точно есть отдельно описываемый лексер. В ПЕГ-е он не нужен и у нас его нет. Стало быть указывать нужно как-то по месту.

В общем, предложения приветствуются.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>А задавать декларативно приоритет операторов как в Irony у вас нельзя? Некоторым это жизнь сильно упростило бы.

Это пока что почти чистая реализация ПЕГ-а на базе рекурсивного спуска с откатами. В ней нет даже таких понятий как "операторы", не то что их приоритетов. К тому же приоритеты могут быть не только для операторов. Так что не уверен, что это вообще нужно в для данного продукта.

Здравствуйте, VladD2, Вы писали:

ВВ>>Необходимость писать рукописное расширение для регистронезависимых ключевых слов людей не обрадует. Все же довольно распространенный юз-кейс. В идеале бы — специальную настройку как в кокоре.
VD>Я уже не помню как там в КокоР-е было все сделано, но там точно есть отдельно описываемый лексер. В ПЕГ-е он не нужен и у нас его нет. Стало быть указывать нужно как-то по месту.

В кокор лексер, конечно, отдельный, и там есть специальная инструкция типа IGNORE CASE, которая управляет генерацией лексера. Я бы, наверное, добавил такое специальное вхождение options, которое нужно указывать, скажем, вначале. Внутри — набор инструкций. Например, у инструкции ignore могут быть параметры. Типа такого:

options =
(
  ignore case,
  ignore '\t' '\r' '\n',
  что-то еще
)

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Воронков Василий, Вы писали:
ВВ>>А задавать декларативно приоритет операторов как в Irony у вас нельзя? Некоторым это жизнь сильно упростило бы.
VD>Это пока что почти чистая реализация ПЕГ-а на базе рекурсивного спуска с откатами. В ней нет даже таких понятий как "операторы", не то что их приоритетов. К тому же приоритеты могут быть не только для операторов. Так что не уверен, что это вообще нужно в для данного продукта.

Ну добавление приоритетов операторов просто-напросто упростит написание грамматики. В идеале бы, конечно, иметь некоторый механизм, который позволил бы вмешиваться в процесс парсинга и создавать специальные хелперы. И в числе таких хелперов был бы такой, который позволял бы указать приоритет. Но эта, сам понимаешь, идея из области "самолеты летят и падают"

Просто сейчас для того, чтобы сделать разбор выражений корректным, хардкейсу придется весьма сильно переделывать грамматику. Были бы явные приоритеты — добавил бы одну строчку. ИМХО в такую лужу сядут многие — это если рассчитывать на широкое применение ПЕГа.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>В кокор лексер, конечно, отдельный, и там есть специальная инструкция типа IGNORE CASE, которая управляет генерацией лексера. Я бы, наверное, добавил такое специальное вхождение options, которое нужно указывать, скажем, вначале. Внутри — набор инструкций. Например, у инструкции ignore могут быть параметры. Типа такого:

"IGNORE CASE" потенциально может потребоваться не везде. Если он нужен во всем парсере, то проблема решается просто добавлением еще одного параметра в макрос PegGrammar. Выглядеть будет примерно так:

[PegGrammar(start, IgnoreCase = true,
  grammar
  {

Здравствуйте, VladD2, Вы писали:

VD>"IGNORE CASE" потенциально может потребоваться не везде. Если он нужен во всем парсере, то проблема решается просто добавлением еще одного параметра в макрос PegGrammar. Выглядеть будет примерно так:
VD>

VD>[PegGrammar(start, IgnoreCase = true,
VD>  grammar
VD>  {  
VD>

Ну можно и так. ИМХО важнее как раз возможность полного игнора регистров. А вот фишку с избирательным игнором я бы вообще делал только по факту фич-реквеста. Многие генераторы это не умеют и ничего. Да и сам я не припомню случаев, когда реально требовался бы избирательный игнор. Для таких сценариев уже не грех и свой хелпер для ключевых слов написать.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Ну добавление приоритетов операторов просто-напросто упростит написание грамматики. В идеале бы, конечно, иметь некоторый механизм, который позволил бы вмешиваться в процесс парсинга и создавать специальные хелперы. И в числе таких хелперов был бы такой, который позволял бы указать приоритет. Но эта, сам понимаешь, идея из области "самолеты летят и падают"

В принципе операторы можно тупо распозновать так как это делает seregaa, а потом отдельным проходом выявлять приоритеты по некоторому заданному образцу. Почти так же делается в современном парсере немерле.

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

Что там сильного то? Вставить одно правило и переделать другое.

ВВ>Были бы явные приоритеты — добавил бы одну строчку. ИМХО в такую лужу сядут многие — это если рассчитывать на широкое применение ПЕГа.

Ну, если люди не знают базовых основ, то да. Вопрос в том стоит ли на них ориентироваться. Без основ все равно ничего путного не выйдет.

Сейчас есть более приоритетные задачи:
1. Обработка ошибок.
2. То же игнорирование регистра.
3. Оптимизации.

Плюс еще есть ощущение, что идеологию придуманную для синтаксических макросов в следующей версии немерла имеет смысл применить и для PEG-макроса в текущей версии.

Я тут повозился с этим макросом и пришел к выводу, что парсеры делаются итеративно, а при этом не очень удобно, что правила и их обработчики находятся на большом расстоянии. Тут нужна или навигация (чтобы от описания правила можно было бы перейти к его обработчику и обратно), или компоновка в стиле макросов. Ну, что-то вроде методов вида:

  tagOpen(lt, identifier, attrs, gt) : XmlAst.TagOpen
    subrules:
      attrs = attr*;
      lt    = '<';
      gt    = '>';
  {
    код обработчика
  }

Думаю — это легко можно реализовать в рамках текущей макросистемы.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>Ну можно и так. ИМХО важнее как раз возможность полного игнора регистров. А вот фишку с избирательным игнором я бы вообще делал только по факту фич-реквеста. Многие генераторы это не умеют и ничего. Да и сам я не припомню случаев, когда реально требовался бы избирательный игнор. Для таких сценариев уже не грех и свой хелпер для ключевых слов написать.

Тогда остается только понять как срендерить эффективный код сравнения символов с игнорированием регистра.

ЗЫ

Может проще перед реднеренгом для строки ToLower() вызвать? Ну, а значения для токенов добывать из оригинальной строки.

Здравствуйте, VladD2, Вы писали:

VD>Это правило неверное:
VD>

VD>infixOperator           : string    = ('+' / '-' / '*' / '/') spaces;
VD>

VD>Тут надо поступать так же как в примере "Calculator":
VD>

VD>    mulOrDiv              : int = simplExpr (('*' / '/') spaces simplExpr)*;
VD>    sumOrSub              : int = mulOrDiv  (('+' / '-') spaces mulOrDiv )*;
VD>

VD>Тут суть в том, что выражение типа "X * Y — Z" рассматривается как "(X * Y) — Z", а выражение "X — Y * Z" как "X — (Y * Z)". Так вот чтобы эти приоритеты отразить в грамматике нужно рассматривать любое сложение или вычитание как сложение или вычитание потенциального умножения или деления, а умножение или деление как потенциальное простое выражение или умножение или деление.

ЗЫ. Кстати, хорошо бы вместо spaces тоже писать ignore в опциях. Так продукции выглядят более "чисто". Типа:
Ignore = "\r\n\t"
это если через атрибут указывать.

Здравствуйте, Воронков Василий, Вы писали:

ВВ>ЗЫ. Кстати, хорошо бы вместо spaces тоже писать ignore в опциях. Так продукции выглядят более "чисто". Типа:
ВВ>Ignore = "\r\n\t"
ВВ>это если через атрибут указывать.

Это в принципе невозможно.

Тут поступило другое предложение. Можно идти от обратного и вместо spaces ввести специализированное правило (предопределенное) "nospaces". Тогда по умолчанию можно будет вставлять spaces между любыми правилами кроме тех случаев когда между ними уже присутствует nospaces.

Здравствуйте, VladD2, Вы писали:

VD>Тогда остается только понять как срендерить эффективный код сравнения символов с игнорированием регистра.
VD>ЗЫ
VD>Может проще перед реднеренгом для строки ToLower() вызвать? Ну, а значения для токенов добывать из оригинальной строки.

А для ключевых слов тоже ToLower() делать? Потому что я могу написать типа:

Sub = "SUB";

И хочется, чтобы оно тоже работало.
Вообще идея неплохая, не считая того, что придется держать две копии строки. Учитывая, что ведь парсер-то, наверное, юникодный? Т.е. я могу без всякого шаманства написать:

Sub = "Процедура";

В противном случае регистронезависимое сравнение весьма тривиально.
Кстати, Кокор тоже шаманит каким-то таким образом — т.е. видимо ToLower/ToUpper делает для всей строки, ибо сама логика распознавания никак не меняется при включении этой опции.

Здравствуйте, VladD2, Вы писали:

ВВ>>ЗЫ. Кстати, хорошо бы вместо spaces тоже писать ignore в опциях. Так продукции выглядят более "чисто". Типа:
ВВ>>Ignore = "\r\n\t"
ВВ>>это если через атрибут указывать.
VD>Это в принципе невозможно.

А почему?
Под ignore имеется в виду, что они учитываются как раздилители между токенами, но при этом предполагается любое их количество в любых местах и явно указывать их уже не нужно.
Говоря другим словами, эта настройка не влияет на выделение токенов, она просто означает, что везде по умолчанию стоит spaces. ИМХО вполне возможно должно быть.

VD>Тут поступило другое предложение. Можно идти от обратного и вместо spaces ввести специализированное правило (предопределенное) "nospaces". Тогда по умолчанию можно будет вставлять spaces между любыми правилами кроме тех случаев когда между ними уже присутствует nospaces.

Не до конца ясно, как это должно работать. Т.е. spaces все равно надо описывать явно? Потому что его определение не всегда же одинаково.

Здравствуйте, VladD2, Вы писали:

ВВ>>Были бы явные приоритеты — добавил бы одну строчку. ИМХО в такую лужу сядут многие — это если рассчитывать на широкое применение ПЕГа.
VD>Ну, если люди не знают базовых основ, то да. Вопрос в том стоит ли на них ориентироваться. Без основ все равно ничего путного не выйдет.

ИМХО стоит. Те, кто знают, обычно уже что-то используют. И для того, чтобы перейти от одной хорошо отлаженной и интегрированной в производство тулзы нужны уже очень хорошие причины. В количестве больше одной. (Кстати, декларативные приоритеты — одна из таких причин в принципе). Опять же все равно вряд ли все побегуть менять [подставить свой любимый генератор] на ПЕГ. А тех, кто вообще не использует это дело, привлечь проще.

VD>Сейчас есть более приоритетные задачи:
VD>1. Обработка ошибок.

Мне в целом нравится подход того же Кокора. Т.е. к примеру, если я такую продукцию:

Expr = "keyword" ( Foo | Bar ).

Распишу так:

Expr = "keyword" FooBar.
FooBar = Foo | Bar.

И у меня Foo или Bar пропущены или же в них ошибка, то будет сгенерирована ошибка типа Invalid FooBar или Missing FooBar. Которую уже легко превратить в дружелюбное сообщение. Т.е. не надо, как ты предлагаешь, делать:

Expr = "keyword" ( Foo | Bar | Error ).

Грамматика распухнет конкретно от таких вещей.

VD>2. То же игнорирование регистра.
VD>3. Оптимизации.

А тут мы, боюсь, опять приходим к CIL Switch.

От:	hardcase	http://nemerle.org
Дата:	08.07.10 08:28
Оценка:	112 (2)

От:	VladD2	www.nemerle.org
Дата:	08.07.10 16:01
Оценка:

От:	VladD2	www.nemerle.org
Дата:	08.07.10 16:08
Оценка:

От:	VladD2	www.nemerle.org
Дата:	08.07.10 16:25
Оценка:

	От:	Воронков Василий
	Дата:	08.07.10 17:10
	Оценка: