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)?
Пока что можно использовать только такое извращение:
Это конечно же маразм, так что нужно придумывать что-то более удобное. Что конкретно? Над этим надо думать.
В голову приходит следующее:
1. Давать префиксы или суффиксы для строковых литералов означающие, что нужно использовать ингорирование регистра при сравнении:
i"select"
2. Для ключевых слов, возможно, имеет смысл реализовать специализированное решение (если не ошибаюсь в Rats! сделано именно так).
3. Возможно имеет смысл ввести рукописные расширения. Тогда можно было бы реализовать функцию парсинга ключевых слов наиболее эффективным для конкретного языка образом (вручную).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
H>На выходе он в презентабельном виде отображает AST: H>
H>x = y.z = (t ? a : (0x23 * (7 + 1)));;
H>
Кстати — это ошибка. У умножения приоритет должен быть выше. Так что скобки не верно выведены или распознавание не верное.
H>Основная проблема с которой пришлось бороться — это ликвидация в правилах левой рекурсии без продвижения по строке.
Кстати, левую рекурсию нужно выявлять еще при компиляции и сообщать об этом. Думаю сделать это не сложно будет. Надо всего лишь пройтись по всем правилам (до оптимизации) и попробовать спуститься в левое правило (производя при этом подсчет количества входов и выходов в правило).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Кстати — это ошибка. У умножения приоритет должен быть выше. Так что скобки не верно выведены или распознавание не верное.
А задавать декларативно приоритет операторов как в Irony у вас нельзя? Некоторым это жизнь сильно упростило бы.
Здравствуйте, VladD2, Вы писали:
VD>В голову приходит следующее: VD>1. Давать префиксы или суффиксы для строковых литералов означающие, что нужно использовать ингорирование регистра при сравнении: VD>
VD>i"select"
VD>
VD>2. Для ключевых слов, возможно, имеет смысл реализовать специализированное решение (если не ошибаюсь в Rats! сделано именно так). VD>3. Возможно имеет смысл ввести рукописные расширения. Тогда можно было бы реализовать функцию парсинга ключевых слов наиболее эффективным для конкретного языка образом (вручную).
Необходимость писать рукописное расширение для регистронезависимых ключевых слов людей не обрадует. Все же довольно распространенный юз-кейс. В идеале бы — специальную настройку как в кокоре.
Тут суть в том, что выражение типа "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>
Ну можно и так. ИМХО важнее как раз возможность полного игнора регистров. А вот фишку с избирательным игнором я бы вообще делал только по факту фич-реквеста. Многие генераторы это не умеют и ничего. Да и сам я не припомню случаев, когда реально требовался бы избирательный игнор. Для таких сценариев уже не грех и свой хелпер для ключевых слов написать.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Ну добавление приоритетов операторов просто-напросто упростит написание грамматики. В идеале бы, конечно, иметь некоторый механизм, который позволил бы вмешиваться в процесс парсинга и создавать специальные хелперы. И в числе таких хелперов был бы такой, который позволял бы указать приоритет. Но эта, сам понимаешь, идея из области "самолеты летят и падают"
В принципе операторы можно тупо распозновать так как это делает seregaa, а потом отдельным проходом выявлять приоритеты по некоторому заданному образцу. Почти так же делается в современном парсере немерле.
ВВ>Просто сейчас для того, чтобы сделать разбор выражений корректным, хардкейсу придется весьма сильно переделывать грамматику.
Что там сильного то? Вставить одно правило и переделать другое.
ВВ>Были бы явные приоритеты — добавил бы одну строчку. ИМХО в такую лужу сядут многие — это если рассчитывать на широкое применение ПЕГа.
Ну, если люди не знают базовых основ, то да. Вопрос в том стоит ли на них ориентироваться. Без основ все равно ничего путного не выйдет.
Сейчас есть более приоритетные задачи:
1. Обработка ошибок.
2. То же игнорирование регистра.
3. Оптимизации.
придуманную для синтаксических макросов в следующей версии немерла имеет смысл применить и для PEG-макроса в текущей версии.
Я тут повозился с этим макросом и пришел к выводу, что парсеры делаются итеративно, а при этом не очень удобно, что правила и их обработчики находятся на большом расстоянии. Тут нужна или навигация (чтобы от описания правила можно было бы перейти к его обработчику и обратно), или компоновка в стиле макросов. Ну, что-то вроде методов вида:
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Ну можно и так. ИМХО важнее как раз возможность полного игнора регистров. А вот фишку с избирательным игнором я бы вообще делал только по факту фич-реквеста. Многие генераторы это не умеют и ничего. Да и сам я не припомню случаев, когда реально требовался бы избирательный игнор. Для таких сценариев уже не грех и свой хелпер для ключевых слов написать.
Тогда остается только понять как срендерить эффективный код сравнения символов с игнорированием регистра.
ЗЫ
Может проще перед реднеренгом для строки ToLower() вызвать? Ну, а значения для токенов добывать из оригинальной строки.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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. Оптимизации.
Здравствуйте, Воронков Василий, Вы писали:
ВВ>А для ключевых слов тоже ToLower() делать?
В грамматике?
ВВ>Потому что я могу написать типа:
ВВ>
ВВ>Sub = "SUB";
ВВ>
Можно просто выдавать ошибки по этому поводу. Точнее по поводу использования любых букв в верхнем регистре.
ВВ>Вообще идея неплохая, не считая того, что придется держать две копии строки.
Мне кажется в наше время это не проблема. Вторая строка нужна на маленький промежуток времени, так что будет реюзаться одна и та же область LOH-а в GC.
ВВ>Учитывая, что ведь парсер-то, наверное, юникодный?
Да. Точнее он дотнетный и не делающий никаких предположении о типе контента (нет никаких таблиц или еще чего-то что могло бы зависит от размера символов).
ВВ>Т.е. я могу без всякого шаманства написать:
ВВ>
ВВ>Sub = "Процедура";
ВВ>
Можешь конечно. Но ты же хочешь не чувствительный к регистру парсинг? Тогда можно смириться, что в случае не чувствительного к регистру парсера надо писать все слова в нижнем регистре.
ВВ>В противном случае регистронезависимое сравнение весьма тривиально. ВВ>Кстати, Кокор тоже шаманит каким-то таким образом — т.е. видимо ToLower/ToUpper делает для всей строки, ибо сама логика распознавания никак не меняется при включении этой опции.
Возможно. Думаю, что тут все очень просто. Стоимость регистро-независимого сравнения весьма высока по сравнению с примитивными операциями типа x == 'c'. Потом химии много, а толку мало.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
ВВ>Под ignore имеется в виду, что они учитываются как раздилители между токенами, но при этом предполагается любое их количество в любых местах и явно указывать их уже не нужно.
Ага. Только нет самого понятия "токен". Мы описываем парсер строки! Лексера нет как ложку в Матрице.
ВВ>Говоря другим словами, эта настройка не влияет на выделение токенов, она просто означает, что везде по умолчанию стоит spaces. ИМХО вполне возможно должно быть.
Только при условии, что можно указать, что где-то не надо ставить эти самые spaces. Это нужно или задавать для каждого отдельного правила, или нужно вводить nospaces.
А вообще, на практике добавление spaces не взывает никаких проблем. Просто это не привычно для тех кто использовал лексерные парсеры (классно звучит).
VD>>Тут поступило другое предложение. Можно идти от обратного и вместо spaces ввести специализированное правило (предопределенное) "nospaces". Тогда по умолчанию можно будет вставлять spaces между любыми правилами кроме тех случаев когда между ними уже присутствует nospaces.
ВВ>Не до конца ясно, как это должно работать. Т.е. spaces все равно надо описывать явно? Потому что его определение не всегда же одинаково.
Нет. Алгоритм следующий. Все подправила (кроме содержимого литералов) дополняем spaces-ами. Если по логике пробелы не нужны, то мы пишем так:
Здравствуйте, Воронков Василий, Вы писали:
VD>>Сейчас есть более приоритетные задачи: VD>>1. Обработка ошибок.
ВВ>Мне в целом нравится подход того же Кокора. Т.е. к примеру, если я такую продукцию:
Он тут пролетает, так как является LL(1)-автоматом. Ему не сложно самостоятельно определить, что есть ошибка во входной строке. У ПЕГ-а же ошибок в коде просто не бывает. У ПЕГ-а бывают откаты. После того как будет откачено стартовое правило, можно будет сказать, что во входной строке что-то не так, так как она не парсится данным парсером. Но где ошибка понять будет невозможно.
Один из способов понять где же ошибка — это запоминать максимальную позицию в которой был произведен откат и правило которое было откачено. Но это а) не эффективно, б) не всегда дает хороший результат (например, так нельзя указать на то, что некоторая открывающая скобка незакрыта).
ВВ>Т.е. не надо, как ты предлагаешь, делать:
ВВ>Expr = "keyword" ( Foo | Bar | Error ).
ВВ>Грамматика распухнет конкретно от таких вещей.
LL(1)-грамматики в сотни раз проще чем PEG-овские. И вся эта мощь определяется операторами приоритетного выбора которые предоставляют ограниченный откат. Мы просто не можем вставлять Error в конец всех операторах приоритетного выбора. Это не позволит откатиться правилу которое вызвало данное.
VD>>2. То же игнорирование регистра. VD>>3. Оптимизации.
ВВ>А тут мы, боюсь, опять приходим к CIL Switch.
Ну, это отдельный вопрос.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>>>2. То же игнорирование регистра. VD>>>3. Оптимизации.
ВВ>>А тут мы, боюсь, опять приходим к CIL Switch.
VD>Ну, это отдельный вопрос.
Я это все перечислял чтобы объяснить, что "есть у нас и другие дела" (с). И это только с ПЕГ-ом. А еще есть компилятор, интеграция и т.п.
Лучше бы присоединился и помог бы.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Нет. Алгоритм следующий. Все подправила (кроме содержимого литералов) дополняем spaces-ами. Если по логике пробелы не нужны, то мы пишем так: VD>
nopace это таки кривь.
Ибо в подавляющем большенстве случаев у нас для всего правила либо нужно игнорировать пробелы либо нет.
Так что лучше raw syntax.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Ну можно и так. ИМХО важнее как раз возможность полного игнора регистров. А вот фишку с избирательным игнором я бы вообще делал только по факту фич-реквеста. Многие генераторы это не умеют и ничего. Да и сам я не припомню случаев, когда реально требовался бы избирательный игнор. Для таких сценариев уже не грех и свой хелпер для ключевых слов написать.
Как раз в случае с отсутствием лексера, частичный игнор очень важен. Допустим, для языка, у которого регистр кейвордов не важен, но строковые литералы зависят от регистра (а большинство языков "нечуствительных к регистру" именно такие).
Здравствуйте, catbert, Вы писали:
C>Как раз в случае с отсутствием лексера, частичный игнор очень важен. Допустим, для языка, у которого регистр кейвордов не важен, но строковые литералы зависят от регистра (а большинство языков "нечуствительных к регистру" именно такие).
Честно говоря, не понимаю, как это связано со строками. Парсеру вообще нет дело до того, что содержится внутри "".
Здравствуйте, hardcase, Вы писали:
H>Теперь компиляция проекта длится несколько долгих-долгих минут. Там полиномиальная сложность что ли с какой-то дикой степенью?
Исправил еще ошибки в 8985.
Компиляция проекта занимает порядка 10 минут.
Здравствуйте, hardcase, Вы писали:
H>Я знаю. Мне просто было лень писать правила. Сейчас добавил операторы в соответствии с вот этой древней докой.
H>Теперь компиляция проекта длится несколько долгих-долгих минут. Там полиномиальная сложность что ли с какой-то дикой степенью?
Если бы ты добавил правила из этой доки, то парсинг вообще никогда не завершился бы (если конечно переполнения стека не случилось бы). Там описана лево-рекурсивная грамматика. Он с помощью нисходящего спуска вообще не парсится.
Скорее всего ты добавил нечто другое, но тоже не очень хорошее (экспонентное).
Грамматика для бинарных операторов должна быть примерно такая:
Здравствуйте, catbert, Вы писали:
C>Как раз в случае с отсутствием лексера, частичный игнор очень важен. Допустим, для языка, у которого регистр кейвордов не важен, но строковые литералы зависят от регистра (а большинство языков "нечуствительных к регистру" именно такие).
Я же сказал "Ну, а значения для токенов добывать из оригинальной строки.". То есть парсер работает с копией строки в приведенной к нижнему или верхнему регистру, а функция GetText() работает с оригиналом и добывает исходные значения.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>Я знаю. Мне просто было лень писать правила. Сейчас добавил операторы в соответствии с вот этой древней докой.
H>>Теперь компиляция проекта длится несколько долгих-долгих минут. Там полиномиальная сложность что ли с какой-то дикой степенью?
VD>Если бы ты добавил правила из этой доки, то парсинг вообще никогда не завершился бы (если конечно переполнения стека не случилось бы). Там описана лево-рекурсивная грамматика. Он с помощью нисходящего спуска вообще не парсится.
Я в курсе. Меня интересовал набор и приоритет операций.
VD>Скорее всего ты добавил нечто другое, но тоже не очень хорошее (экспонентное).
VD>Грамматика для бинарных операторов должна быть примерно такая: VD>
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>Исправил еще ошибки в 8985. H>>Компиляция проекта занимает порядка 10 минут.
VD>Погоди. "Компиляция проекта" в смысле немерлового проекта содержащего грамматику? Или речь о работе самого парсера получаемого по этой грамматике?
VD>Если первое, то нужно искать баг. Такого точно не должно быть.
Да. Компиляция парсера этой грамматики в которую я добавил весь этот красивый спектр операторов теперь занимает чуть больше 10 минут (дома машинка пошустрее и считает за 7 минут).
Здравствуйте, hardcase, Вы писали:
H>Да. Компиляция парсера этой грамматики в которую я добавил весь этот красивый спектр операторов теперь занимает чуть больше 10 минут (дома машинка пошустрее и считает за 7 минут).
А не смотрел профайлером что занимает основное время?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Кстати еще смущает размер кода. Теперь сборка с парсером стремится к 400КБ. Это нормально?
К сожалению — да. Без специальных оптимизаций там генерирутся слишком много млекого кода. Плюс Вольфхаунд наладил там инлайнинг который приводит к дублированию массы мелких правил. С одной стороны это повышает скорость (теоретически), с другой приводит к разбуханию кода. Тут тоже надо еще покумекать как лучше поступать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>Да. Компиляция парсера этой грамматики в которую я добавил весь этот красивый спектр операторов теперь занимает чуть больше 10 минут (дома машинка пошустрее и считает за 7 минут).
VD>А не смотрел профайлером что занимает основное время?
Судя по тому, что я увидел в профайлере, все время времени компилятор проводит в OptimizeRule, а имеенно в CanInline, которая похоже имеет жуткую полиномиальную сложность.
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, VladD2, Вы писали:
VD>>Здравствуйте, hardcase, Вы писали:
H>>>Да. Компиляция парсера этой грамматики в которую я добавил весь этот красивый спектр операторов теперь занимает чуть больше 10 минут (дома машинка пошустрее и считает за 7 минут).
VD>>А не смотрел профайлером что занимает основное время?
H>Судя по тому, что я увидел в профайлере, все время времени компилятор проводит в OptimizeRule, а имеенно в CanInline, которая похоже имеет жуткую полиномиальную сложность.
Исправил в r8986. Теперь оно так долго не занимается прогревом процессора.
Здравствуйте, hardcase, Вы писали:
H>Судя по тому, что я увидел в профайлере, все время времени компилятор проводит в OptimizeRule, а имеенно в CanInline, которая похоже имеет жуткую полиномиальную сложность.
А попробуй как ее просто отключить.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>>Исправил в r8986. Теперь оно так долго не занимается прогревом процессора.
H>От этой жары уже и соображаю плохо... Сделал лучше: r8987.
А после исправления что занимает основное время (с точки зрения профайлера)?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>>Исправил в r8986. Теперь оно так долго не занимается прогревом процессора.
H>От этой жары уже и соображаю плохо... Сделал лучше: r8987.
Кстати, проект ты в ШарпДевелопе создавал?
С ним явно что-то не так. В студии какие-то странные проблемы.
Я его (от греха) пересоздал с помощью VS.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Кстати еще смущает размер кода. Теперь сборка с парсером стремится к 400КБ. Это нормально?
Удалил строки используемые для отладки, стало ~300Кб.
Для радикального уменьшения надо менять генерацию кода для терминальных правил (тех что разбирают отдельные символы и не содержат рекурсии). Их можно превратить в ДКА или даже специализированный код. Например, для распознавания "строк" (последовательного набора символов) можно применять сравнение строк или хотя бы более оптимальный код генерировать (без откатов и доп.проверок длинны строки.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Интересу ради решил попробовать в деле генератор парсеров. H>Задачу выбрал синтетическую — разбор некоего подмножества JavaScript.
Это! Может лучше займешься созданием грамматики для C#? Нам это дело намного больше нужно. Тогда и конвертер на его базе организовали бы, и даже возможность включать в немерловый проект C#-исходников.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>Интересу ради решил попробовать в деле генератор парсеров. H>>Задачу выбрал синтетическую — разбор некоего подмножества JavaScript.
VD>Это! Может лучше займешься созданием грамматики для C#? Нам это дело намного больше нужно. Тогда и конвертер на его базе организовали бы, и даже возможность включать в немерловый проект C#-исходников.
Можно попробовать в принципе попробовать. Не думаю, что сильно сложно будет, просто рутинного кода мноооого.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>>Исправил в r8986. Теперь оно так долго не занимается прогревом процессора.
H>>От этой жары уже и соображаю плохо... Сделал лучше: r8987.
VD>А после исправления что занимает основное время (с точки зрения профайлера)?
Нормально стало вроде. Других задержек пока не замечено.
Здравствуйте, hardcase, Вы писали:
VD>>Это! Может лучше займешься созданием грамматики для C#? Нам это дело намного больше нужно. Тогда и конвертер на его базе организовали бы, и даже возможность включать в немерловый проект C#-исходников.
H>Можно попробовать в принципе попробовать.
Давай! Это будет очень полезно. А я постараюсь сосредоточиться на развитии генератора парсеров.
H>Не думаю, что сильно сложно будет, просто рутинного кода мноооого.
+1
ЗЫ
Ко всему прочему это будет первым шагом к новой версии Немерла, так как это будет пример реально достаточно большого размера, чтобы проверить все что нужно проверить (производительность, сложность, проблемы, ...).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>Возникли два вопроса:
H>1) Как обрабатывать ошибки?
В ревизии 9007 я залил небольшое расширение парсера. Теперь в парсер добавляется свойство MaxRollbackPos. В этом свойстве запоминается максимальная позиция в которой был произведен откат. Фактически — это позиция в которой отбламался парсер. Эту позицию можно использовать для выдачи "общего" сообщения об ошибке, например, "Недопустимый токен".
В будущем, я думаю, нужно в этих же позициях запоминать так же некий идентификатор правила на котором произошел облом. Тогда можно будет формировать более осмысленные сообщения об ошибок.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>В ревизии 9007 я залил небольшое расширение парсера. Теперь в парсер добавляется свойство MaxRollbackPos. В этом свойстве запоминается максимальная позиция в которой был произведен откат. Фактически — это позиция в которой отбламался парсер. Эту позицию можно использовать для выдачи "общего" сообщения об ошибке, например, "Недопустимый токен".
Кстати, как в текущем парсере дела с "точками отсечения"? Ну, теми, после отката до которых парсер вываливается с ошибками.
Здравствуйте, catbert, Вы писали:
C>Кстати, как в текущем парсере дела с "точками отсечения"? Ну, теми, после отката до которых парсер вываливается с ошибками.
Никак, но можно создать правило перехватывающее любой ввод и выдать в нем ошибку.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
VD>>Это! Может лучше займешься созданием грамматики для C#? Нам это дело намного больше нужно. Тогда и конвертер на его базе организовали бы, и даже возможность включать в немерловый проект C#-исходников.
H>Можно попробовать в принципе попробовать. Не думаю, что сильно сложно будет, просто рутинного кода мноооого.
Ну, так как?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, hardcase, Вы писали:
H>К сожалению прошедшую неделю был крайне далек от какого-либо компьютера H>Буду фигачить на этой.
Давай. Причем не стесняйся дергать меня (можно по Скайпу, в нем у меня логин VladD2), если что-то не так будет с PegGrammar. Это важно для будущей версии компилятора.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>К сожалению прошедшую неделю был крайне далек от какого-либо компьютера H>>Буду фигачить на этой.
VD>Давай. Причем не стесняйся дергать меня (можно по Скайпу, в нем у меня логин VladD2), если что-то не так будет с PegGrammar. Это важно для будущей версии компилятора.
Сделал начальный коммит грамматики и простую систему тестирования правил.
Здравствуйте, hardcase, Вы писали:
H>Сделал начальный коммит грамматики и простую систему тестирования правил.
Парсер теперь распознает объявления (покачто без генерирования AST) всевозможных типов (в грамматике около 200 правил).
Сборка с парсером имеет размер в полтора мегабайта.
Здравствуйте, hardcase, Вы писали:
H>Сделал начальный коммит грамматики и простую систему тестирования правил.
По поводу модификаторов (public, new, static, ...).
Не стоит описывать свой список для каждого типа деклараций. Людям свойственно ошибаться. Они часто лепят идентификаторы не по месту. И при этом им нужны внятные сообщения об ошибках. Если же забить их в грамматику, то сообщение будет типа "не ожидаемый идентификатор".
Лучше сделать единый список идентификаторов и проверять их в семантическом действии (обработчике). Или после правильного списка модификаторов давать полный список и при его сопоставлении выдавать ошибку (это будет чуть медленнее).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>По поводу модификаторов (public, new, static, ...).
VD>Не стоит описывать свой список для каждого типа деклараций. Людям свойственно ошибаться. Они часто лепят идентификаторы не по месту. И при этом им нужны внятные сообщения об ошибках. Если же забить их в грамматику, то сообщение будет типа "не ожидаемый идентификатор".
VD>Лучше сделать единый список идентификаторов и проверять их в семантическом действии (обработчике). Или после правильного списка модификаторов давать полный список и при его сопоставлении выдавать ошибку (это будет чуть медленнее).
Так оно и будет. Когда грамматику допишу до конца, буду ее слегка сжимать, так как она сейчас содержит достаточно много семантических правил, проверку которых можно вынести в обработчики.
Здравствуйте, hardcase, Вы писали:
H>Так оно и будет. Когда грамматику допишу до конца, буду ее слегка сжимать, так как она сейчас содержит достаточно много семантических правил, проверку которых можно вынести в обработчики.
За месяц успеешь это дело добить? Хорошо бы конечно это дело в релиз впихнуть.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, hardcase, Вы писали:
H>>Так оно и будет. Когда грамматику допишу до конца, буду ее слегка сжимать, так как она сейчас содержит достаточно много семантических правил, проверку которых можно вынести в обработчики.
VD>За месяц успеешь это дело добить? Хорошо бы конечно это дело в релиз впихнуть.
Я постараюсь, но сам понимаешь, у меня гарантии как в китайской бане.
Здравствуйте, hardcase, Вы писали:
H>И их тоже (да, у меня сегодня свободный денек подвернулся). Пожалуй с грамматикой закончил, можно приступать к AST.
Здравствуйте, hardcase, Вы писали:
H>И их тоже (да, у меня сегодня свободный денек подвернулся). Пожалуй с грамматикой закончил, можно приступать к AST.
Вот это не верно.
Эти правила должны заканчиваться на !identifierPartCharacters s
С keyword и много чем другим та же фигня.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[13]: [PEG] Добавил в сниппеты еще один пример.
От:
Аноним
Дата:
13.08.10 21:43
Оценка:
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, hardcase, Вы писали:
H>>И их тоже (да, у меня сегодня свободный денек подвернулся). Пожалуй с грамматикой закончил, можно приступать к AST. WH>
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, hardcase, Вы писали:
H>>И их тоже (да, у меня сегодня свободный денек подвернулся). Пожалуй с грамматикой закончил, можно приступать к AST. WH>
Здравствуйте, <Аноним>, Вы писали:
А>Случайно попал. А потом было лень удалять.
Нужно удалить. Нечего автогенереннам файлам делать в репозитории.
Тем более если это всеголишь отладочная печать.
А>Ок. Пересмотрю грамматику, если честно, то я так и не понял логики работы !xxx — захватывает ли он символы или нет.
Нет.
! и & это синтаксические предикаты которые заглядывают на неопределенное колличество символов вперед никогда не съдая символы.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, hardcase, Вы писали:
H>>И их тоже (да, у меня сегодня свободный денек подвернулся). Пожалуй с грамматикой закончил, можно приступать к AST. WH>
Из build 9212
Компильнул пример с калькулятором.
Почему-то у парсера только один раз срабатывает _calc.TryParse(text);
При последующих вызовах парсится предыдущая строка, которая была при первом вызове. Где-то кешируется, а дальше хоть пустую строку передавай, парсится то что было при первом вызове. Это так и задумано или у меня что-то сломалось?
Здравствуйте, Silver_s, Вы писали:
S_>Здравствуйте, hardcase, Вы писали:
S_>Из build 9212 S_>Компильнул пример с калькулятором. S_>Почему-то у парсера только один раз срабатывает _calc.TryParse(text); S_>При последующих вызовах парсится предыдущая строка, которая была при первом вызове. Где-то кешируется, а дальше хоть пустую строку передавай, парсится то что было при первом вызове. Это так и задумано или у меня что-то сломалось?
Хмм сейчас (в транке) пример с калькулятором не собирается, поправим в ближайшее время.
TryParse в конечном счете разворачивается вот в это:
Здравствуйте, hardcase, Вы писали:
H>Мне кажется там что-то с мемоизацией, так как код этот совершенно безобиден H>А пока просто создавайте каждый раз новый парсер для разбора текста.
Много с чем. И количество состояния в парсере будет только рости.
Может потом сделаем код который будет состояние парсера востанавливать но пока его нужно просто пересоздавать.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Silver_s, Вы писали:
S_>Из build 9212 S_>Компильнул пример с калькулятором. S_>Почему-то у парсера только один раз срабатывает _calc.TryParse(text); S_>При последующих вызовах парсится предыдущая строка, которая была при первом вызове. Где-то кешируется, а дальше хоть пустую строку передавай, парсится то что было при первом вызове. Это так и задумано или у меня что-то сломалось?
Баг. Исправим в ближайшее время.
Сейчас над PegGrammar ведется постоянная работа (спасибо WolfHound-у). Сделано много оптимизаций. В том числе сделана очень оригинальная оптимизация — мемоизация последних вызовов правил.
В отличии от алгоритма Packrat — это не тотальная мемоизация для всех позиций, а мемоизация только полседнего вызова правила. Наш вариант не требует наличия хэш-таблицы. К сожалению, в отличии от оригинального Packrat-а эта оптимизация не обеспечивает линейного времени парсинга для любой грамматики, но зато она обеспечивает хорошее время доступа в большинстве случаев. Избавляет от необходимости левой факторизации грамматик, и при том не не влияет так драматично на общую скорость парсинга... в отличии от Packrat котрый показывает неприемлемую скорость за счет постоянного использования мемоизации.
По сути Packrat требует линейного роста объема памяти за счет постоянной и тотальной мемоизации результатов.
Наш подход (идея WolfHound) требует константного места для мемоизации (по одной int-переменной на каждое правило имеющие обработчик). Это позволяет иметь близкой к линейной скорости, не требовать левой факторизации грамматики, и при этом оставаться очень быстрым.
Так вот, к сожалению мы не учли того, что парсер может быть запущен несколько раз подряд. При повторном запуске просто не обнуляются переменные в которых хранится мемоизированный результат, и парсер возврщает старые значения.
Мы исправим эту ошибку в ближайшее время. Все что нужно сделать — это перенести инициализацию в метды начинающие парсинг.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.