Re[2]: PEG-парсер
От: para  
Дата: 12.03.10 19:06
Оценка:
может в грамматике подправить?
    opAdd    : int = expr1 '+' spaces expr0;
    opSub    : int = expr1 '-' spaces expr0;

=>
    opAdd    : int = expr0 '+' spaces expr0;
    opSub    : int = expr0 '-' spaces expr0;


жаль комп на работе остался, щас бы попробовал
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 12.03.10 19:18
Оценка:
Здравствуйте, para, Вы писали:

P>вобщем буду искать косяк


Посидел... подумал... Проблема точно в грамматике. Смотри что получается...

Разберем работу на основе простого выражения "2 + 1 — 3".

когда происходит разбор правила
opAdd    : int = expr1 '+' spaces expr0;

логика получается такая...

Сначала правило expr1 разбирает 2. Далее запись будет такая:
opAdd => (expr1 => expr2 => num => 2) ...

Длее происходит разбор правила expr0:
expr0 => opSub => (expr1 => expr2 => num => 1) + (expr0 => expr1 => expr2 => num => 3)


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

Так что я бы посоветовал поменять граматику, или плюнуть на ассоциативность.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 12.03.10 19:21
Оценка:
Здравствуйте, para, Вы писали:

P>может в грамматике подправить?

P>
P>    opAdd    : int = expr1 '+' spaces expr0;
P>    opSub    : int = expr1 '-' spaces expr0;
P>

P>=>
P>
P>    opAdd    : int = expr0 '+' spaces expr0;
P>    opSub    : int = expr0 '-' spaces expr0;
P>


P>жаль комп на работе остался, щас бы попробовал


Не, так нельзя. Это будет скрытая левая рекурсия opAdd => expr0 => opAdd => ...

Это дело лучше через циклы выраизть. Я тут рядом тебе описал правильную грамматику.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG-парсер
От: para  
Дата: 15.03.10 09:34
Оценка:
Закомитил работающую версию парсера.
Дизайн кривоватый, но более — менее понятный..со временем промежуточные поля в классе (CaptureTree) уберутся.

Там в тудушках отметил, что можно и что буду потихоньку делать.

Пока что есть один не очень хороший баг:
если идут два терминальных символа подряд, они не всегда раздельно доходят до обработки
в частности, знаки "+-*/" идут вместе с последующими пробелами.
буду думать над этим...
Re[2]: PEG-парсер
От: para  
Дата: 15.03.10 11:24
Оценка:
Здравствуйте, para, Вы писали:

P>если идут два терминальных символа подряд, они не всегда раздельно доходят до обработки

P>в частности, знаки "+-*/" идут вместе с последующими пробелами.
P>буду думать над этим...

вернее терминальные символы вообще не добавляются в АСТ, а у меня нечаянно получился грязный хак
Re[3]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 16:15
Оценка:
Здравствуйте, para, Вы писали:

P>>если идут два терминальных символа подряд, они не всегда раздельно доходят до обработки

P>>в частности, знаки "+-*/" идут вместе с последующими пробелами.
P>>буду думать над этим...

P>вернее терминальные символы вообще не добавляются в АСТ, а у меня нечаянно получился грязный хак


Что-то я не могу понять, что за проблема такая. Можно пояснить на примере?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 16:22
Оценка:
Здравствуйте, para, Вы писали:

Это... По возможности не оставляй в коде куски закоментированного кода. Если кому-то понадобится старый код, пусть смотрит историю изменений.

А то грязи много и понять, что же собственно изменилось не просто.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 16:25
Оценка:
Здравствуйте, para, Вы писали:

Да... И побольше комментариев! Они никогда и никому не помешают.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 16:28
Оценка:
Здравствуйте, para, Вы писали:

Поглядел код и понял, что пришло время позаботиться о юнит-етстировании. Наверно стоит начать использовать NUnit для этого.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG-парсер
От: para  
Дата: 15.03.10 16:42
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Что-то я не могу понять, что за проблема такая. Можно пояснить на примере?


под терминальным символом я понимаю:
//именованный: spaces
spaces                = ' '*;
//неименованные: '*' и '/'
mulOrDiv        : int = simplExpr (('*' / '/') spaces simplExpr)*;

проблема была в следующем:
в парсере не происходило добавления терминальных символов к АСТ, а я брал за терминальные символы участки исходного текста, разделённые НЕтерминальными символами, в результате в списке терминальных символов, находилось:
"10 " вместо "10" и " "
и "+ " вместо "+" и " "

проблема была в следующем:
при парсинге или даже при формировании грамматики терминальные символы не обрабатывались как Rule.Capture
более того у них не сохранялись имена (spaces, digit..) и вообще при оптимизации грамматики именнованые "инлайнились" и становились неименованными.

В новой ревизии я добавил сохранение имени для (spaces, digit..), а также добавление именованных терминальным символов в АСТ.

Мне кажется получился уже довольно функциональный код. Наверное можно строить и сложные грамматики. пока только одно ограничение: не использовать неименнованные терминальные символы:
 grammar
  {  
    any                    = ['\u0000'..'\uFFFF'];
    digit                  = ['0'..'9']+;
    spaces                 = ' '*;
    
    mulOp                  = '*';
    divOp                  = '/';
    sumOp                  = '+';
    subOp                  = '-';    
    leftBrace              = '(';  
    rightBrace             = ')';    
    
    num             : int = digit + spaces;
    unaryMinus      : int = subOp spaces simplExpr;
    parenthesesExpr : int = leftBrace spaces sumOrSub rightBrace spaces;
    simplExpr       : int = num / parenthesesExpr / unaryMinus;
    mulOrDiv        : int = simplExpr ((mulOp / divOp) spaces simplExpr)*;
    sumOrSub        : int = mulOrDiv  ((sumOp / subOp) spaces mulOrDiv )*;
    start           : int = spaces sumOrSub !any;
  }

в ближайшее время займусь рефакторингном того сумбура, который я внёс))
Re: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 17:57
Оценка:
Поглядел что получается и возникли следующие вопросы.

1. Вместо использования описанных мной методов-обработчиков в коде используются два мало понятных метода DoOperation и DoGenerateResult. Это временное явление (для того чтобы разобраться с происходящим) или — это такое изменение дизайна?

2. В DoGenerateResult передается имя разбираемого правила в виде строки. Это совершенно не эффективно. Планируется это как-то оптимизировать?

3. Это скорее замечание нежели вопрос. В сгенерированном коде появилось очень много замыканий. Это плохо скажется производительности конечного парсера. Надо подумать над тем как от этого избавиться. Вообще, вопрос эффективности получаемого кода очень важен. Причем она будет зависеть от выбранных проектных решений. Так что это как раз тот случай когда о производительности нужно думать с самого начала.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 17:58
Оценка:
Здравствуйте, para, Вы писали:
P>под терминальным символом я понимаю:
P>
P>//именованный: spaces
P>spaces                = ' '*;
P>//неименованные: '*' и '/'
P>mulOrDiv        : int = simplExpr (('*' / '/') spaces simplExpr)*;
P>

P>проблема была в следующем:
P>в парсере не происходило добавления терминальных символов к АСТ, а я брал за терминальные символы участки исходного текста, разделённые НЕтерминальными символами, в результате в списке терминальных символов, находилось:
P>"10 " вместо "10" и " "
P>и "+ " вместо "+" и " "

Так и должно быть. У тебя же такая грамматика.

Если бы ты реализовал все как я описывал бы, то для каждого подправила ты бы вставил отдельный Caoture и все стало бы выделяться.

P>проблема была в следующем:

P>при парсинге или даже при формировании грамматики терминальные символы не обрабатывались как Rule.Capture
P>более того у них не сохранялись имена (spaces, digit..) и вообще при оптимизации грамматики именнованые "инлайнились" и становились неименованными.

Все правильно. Марос должен вставлять Rule.Capture для каждого подправила правила для которого имеется обработчик.

P>В новой ревизии я добавил сохранение имени для (spaces, digit..), а также добавление именованных терминальным символов в АСТ.


P>Мне кажется получился уже довольно функциональный код. Наверное можно строить и сложные грамматики. пока только одно ограничение: не использовать неименнованные терминальные символы:...


Ты видимо не очень хорошо понял то что я излагал. Прочти мое описание еще раз.

P>в ближайшее время займусь рефакторингном того сумбура, который я внёс))


Меня вот это как раз интересует. Но об этом давай в отдельной подветке теме поговорим, чтобы не искать часами нужных сообщений. Вот здесь
Автор: VladD2
Дата: 15.03.10
.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 18:45
Оценка:
Здравствуйте, VladD2, Вы писали:

Посмотрел по внимательнее на генерируемый макросом код. Понял что в нем мне не нравится.

Ты, в момент разбора грамматики, строишь некое виртуальное AST. А в момент когда вызываются DoOperation и oGenerateResult в них передаются значения из этого AST.

Это плохой подход с точки зрения производительности конечного парсера.

Макрос должен генерировать вызовы методов-обработчиков в моменты когда парсер заканчивает разбор того или иного правила.
При этом нужно формировать минимум промежуточных структур. Фактически до окончания разбора подправила ты должен хранить только позиции на начало и на конец правила.
Если правило возвращает значение, то ты так же должен запомнить результат в стеке. Если все подправила спарсятся, ты должен передать эти значения в метод-обработчик, иначе про них просто нужно забыть. Таким образом при откатах отпаренные значения просто будут теряться.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: [Macro] PEG-парсер (разработка)
От: para  
Дата: 15.03.10 19:13
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Поглядел что получается и возникли следующие вопросы.


VD>1. Вместо использования описанных мной методов-обработчиков в коде используются два мало понятных метода DoOperation и DoGenerateResult. Это временное явление (для того чтобы разобраться с происходящим) или — это такое изменение дизайна?

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

твой пример:
VD>    // этот обработчик вызывается после окончания разбора правила "num"
VD>    num(digitsTok : TokenInfo, _spacesTok : TokenInfo) : int
VD>    {
VD>      int.Parse(digitsTok.GetString())
VD>    }

безусловно хорош, но до крайнего коммита я не мог отделить digitsTok от spacesTok и "num" в АСТ не учавствовало
по этому я делал как мог.
в конечном итоге сделаю так как у тебя.
хотя сейчас я подумал что в макросе будет параметр, который будет позволять делать и так и эдак.

VD>2. В DoGenerateResult передается имя разбираемого правила в виде строки. Это совершенно не эффективно. Планируется это как-то оптимизировать?

следствие первого ответа: для идентификации правила, вместо строки будет использоваться имя вызываемого метода
для варианта с одним методом возможно стоит передавать ссылку на правило из грамматики — но его надо ещё перенести из макроса в парсер...

VD>3. Это скорее замечание нежели вопрос. В сгенерированном коде появилось очень много замыканий. Это плохо скажется производительности конечного парсера. Надо подумать над тем как от этого избавиться. Вообще, вопрос эффективности получаемого кода очень важен. Причем она будет зависеть от выбранных проектных решений. Так что это как раз тот случай когда о производительности нужно думать с самого начала.

я не очень хорошо знаком с ФП. приведи пожалуйста пример замыканий В сгенерированном коде
компилятор правил парсера я почти не менял...
Re[3]: [Macro] PEG-парсер (разработка)
От: para  
Дата: 15.03.10 19:21
Оценка:
Здравствуйте, VladD2, Вы писали:

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


VD>Посмотрел по внимательнее на генерируемый макросом код. Понял что в нем мне не нравится.


VD>Ты, в момент разбора грамматики, строишь некое виртуальное AST. А в момент когда вызываются DoOperation и oGenerateResult в них передаются значения из этого AST.

Таково наследство.
По правде говоря, изначально это АСТ было в виде списка. в предыдущем комите я сделал его деревом, а в последнем, добавил (digit, spaces и подобные) терминальные листья.
Я в комментах к коду написал, что буду думать как избавиться от хранения АСТ.
всё же сначала хотелось чтоб парсер заработал хоть как-нибудь.
Re[3]: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 19:23
Оценка:
Здравствуйте, para, Вы писали:

P>хотя сейчас я подумал что в макросе будет параметр, который будет позволять делать и так и эдак.


Задача и так сложная. Не надо ее усложнять введением разных вариантов. Нужно реализовать один — самый эффективный.

VD>>2. В DoGenerateResult передается имя разбираемого правила в виде строки. Это совершенно не эффективно. Планируется это как-то оптимизировать?

P>следствие первого ответа: для идентификации правила, вместо строки будет использоваться имя вызываемого метода
P>для варианта с одним методом возможно стоит передавать ссылку на правило из грамматики — но его надо ещё перенести из макроса в парсер...

Что значит "имя вызываемого метода". Имелось в виду, что сам вызываемый метод и будет идентифицировать правило?

VD>>3. Это скорее замечание нежели вопрос. В сгенерированном коде появилось очень много замыканий. Это плохо скажется производительности конечного парсера. Надо подумать над тем как от этого избавиться. Вообще, вопрос эффективности получаемого кода очень важен. Причем она будет зависеть от выбранных проектных решений. Так что это как раз тот случай когда о производительности нужно думать с самого начала.

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

Данный вопрос был вызван моим не пониманием реализации. Вопрос в данной формулировке снимается. Вместо этого ответь, плиз, на этот вопрос:
http://rsdn.ru/forum/nemerle/3736654.1.aspx
Автор: VladD2
Дата: 15.03.10
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: [Macro] PEG-парсер (разработка)
От: para  
Дата: 15.03.10 19:30
Оценка:
Здравствуйте, para, Вы писали:
P>
VD>>    // этот обработчик вызывается после окончания разбора правила "num"
VD>>    num(digitsTok : TokenInfo, _spacesTok : TokenInfo) : int
VD>>    {
VD>>      int.Parse(digitsTok.GetString())
VD>>    }
P>

ещё осталась одна штука которая мешает так сделать.
если залезть дебагером сюда, то увидишь что в операцию mulOrDiv передаётся неопределённое число аргументов — не a/b, а a/b*c*d.....
т.е. передавать параметры сюда можно только списками
Re[4]: [Macro] PEG-парсер (разработка)
От: para  
Дата: 15.03.10 19:33
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Что значит "имя вызываемого метода". Имелось в виду, что сам вызываемый метод и будет идентифицировать правило?

да именно
Re[4]: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 19:35
Оценка:
Здравствуйте, para, Вы писали:

P>Таково наследство.


Ясно.

P>По правде говоря, изначально это АСТ было в виде списка. в предыдущем комите я сделал его деревом, а в последнем, добавил (digit, spaces и подобные) терминальные листья.

P>Я в комментах к коду написал, что буду думать как избавиться от хранения АСТ.
P>всё же сначала хотелось чтоб парсер заработал хоть как-нибудь.

Как нибудь он таки заработал. Кстати, поздравляю!

Теперь надо подумать о более эффективной реализации.
Если есть возможность хорошо бы это дело по Скайпу перетереть.

Там где сейчас в код вставляются:
currentCaptureNode.ChildCaptures.Add(cn)
нужно вставлять вызовы методов-обработчиков. Точнее не совсем там, а скорее "в том же духе", но это уже детали.

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

ЗЫ

Я в ближайшее время постараюсь улучшить качество кода и отладочной информации генерируемых для макросов. Это должно упростить работу.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 19:47
Оценка:
Здравствуйте, para, Вы писали:

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

P>>
VD>>>    // этот обработчик вызывается после окончания разбора правила "num"
VD>>>    num(digitsTok : TokenInfo, _spacesTok : TokenInfo) : int
VD>>>    {
VD>>>      int.Parse(digitsTok.GetString())
VD>>>    }
P>>

P>ещё осталась одна штука которая мешает так сделать.
P>если залезть дебагером сюда, то увидишь что в операцию mulOrDiv передаётся неопределённое число аргументов — не a/b, а a/b*c*d.....
P>т.е. передавать параметры сюда можно только списками

Ну, да. Так и надо делать. Цикл и должен разворачиваться в последовательность (список).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.