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

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

P>т.е. передавать параметры сюда можно только списками

... только в списках должны быть результаты работы подправила из теле цилка. Для подправил которые не имеют методов-обработчиков нужно передавать структуру Token описывающую область строки с которой было сопоставлено правило (т.е. пока что PosStart + PosEnd).
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: [Macro] PEG-парсер (разработка)
От: para  
Дата: 15.03.10 19:57
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Теперь надо подумать о более эффективной реализации.

VD>Если есть возможность хорошо бы это дело по Скайпу перетереть.
к сожалению у меня скайпа нет пока..

VD>Там где сейчас в код вставляются:

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

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


ок буду думать.

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

надо либо запретить использовать безымянные терминальные '*' и '/', либо добавлять их в АСТ выражения терминальными листьями чего пока не сделано.
в противном случае, при разборе этого правила '/' и spaces либо будут неизвестны, либо сольются в
 "/       "

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

VD>... только в списках должны быть результаты работы подправила из теле цилка. Для подправил которые не имеют методов-обработчиков нужно передавать структуру Token описывающую область строки с которой было сопоставлено правило (т.е. пока что PosStart + PosEnd).


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

P>к сожалению у меня скайпа нет пока..


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

P>единственный важный нюанс:

P>для правила вида:
P>
P>mulOrDiv        : int = simplExpr (('*' / '/') spaces simplExpr)*;
P>

P>надо либо запретить использовать безымянные терминальные '*' и '/',

Не надо! Это очень удобно!

P> либо добавлять их в АСТ выражения терминальными листьями чего пока не сделано.


Я же говорю — не надо вообще никакого АСТ строить. Вот как должен выглядеть обработчик для mulOrDiv:
mulOrDiv(simplExpr : int, mulDivs : list[Token * Token * simplExpr]) : int
{
  mutable result = simplExpr;

  foreach ((operator, _, secondExpr) in mulDivs)
    if (GetChar(operator.StartPos) == '*')
      result *= secondExpr;
    else
      result /= secondExpr;
}

то есть для каждого подправила внутри обрабатываемого правила мы добавляем по параметру. Если подправило — это цикл, то добавляем список. Если в цикле более одного [под]подправила, то описываме содержимое цикла кортежем с числом элементов равным числу подподправил.

Или, даже лучше так:
mulOrDiv(simplExpr : Token, mulDivs : list[Token * Token * Token]) : int
{
  mutable result = simplExpr.Value;

  foreach ((operator, _, secondExpr) in mulDivs)
    if (GetChar(operator.StartPos) == '*')
      result *= secondExpr.Value;
    else if (secondExpr.Value == 0)
      Error(secondExpr, "The divider must be non zero value!");
    else 
      result /= secondExpr.Value;
}

то есть пусть в обработчик всегда передаются только Token-ы. А уже Token-ы пусть содержат значение, если его возвратил обработчик подправила для этого токена. Правда, при этом значения долны иметь одинаковый тип для всех токенов грамматики. Это конечно не здорово. Ну, да у нас же макрос. Мы ведь можем сгенерировать и множество типов токен, по одному для каждого типа возвращаемого правилом значения.

P>в противном случае, при разборе этого правила '/' и spaces либо будут неизвестны, либо сольются в

P>
P> "/       "
P>


Во многих случаях это не проблема. Скажем для простотя реализации мы можем сделать Trim для строки.

P>тоже займусь этим, после того как переоформлю текущий код по формированию АСТ.

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

Тут ты не прав. АСТ не только не надо формировать, но и нельзя этого делать иначе мы получим тормоза на ровном месте. Тому же калькурятору нужно считать значения, а не строить АСТ выражения. Уж лучше просто потерять те значения которые посчитаны напрасно, чем создавать объекты. Ведь int — это синимальный тип-значение. Он скорее всего будет в регистр запихнут. А объект по любому будет создаваться в куче и при этом еще будут делаться блокировки.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 20:25
Оценка:
Здравствуйте, para, Вы писали:

P>да, терминальные символы я везде заменю со стороки на TokenInfo


Только не надо этих Info. Token и так отлично понятно.

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

Введи в макрос PegParser параметр в который можно будте передать список таких правил.

Возможно имеет смысл даже задавть те правила для которых нужно формировать токены.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: [Macro] PEG-парсер (разработка)
От: para  
Дата: 16.03.10 06:08
Оценка:
Здравствуйте, VladD2, Вы писали:

P>>тоже займусь этим, после того как переоформлю текущий код по формированию АСТ.

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

VD>Тут ты не прав. АСТ не только не надо формировать, но и нельзя этого делать иначе мы получим тормоза на ровном месте. Тому же калькурятору нужно считать значения, а не строить АСТ выражения. Уж лучше просто потерять те значения которые посчитаны напрасно, чем создавать объекты. Ведь int — это синимальный тип-значение. Он скорее всего будет в регистр запихнут. А объект по любому будет создаваться в куче и при этом еще будут делаться блокировки.


ты меня тут не понял.
парсер в любом случае извлекает из выражения АСТ. давай договоримся, что если это АСТ не сохраняется в памяти, а сразу вызываются обработчики, будем называть это виртуальным АСТ.
Но даже виртуальное АСТ надо наполнять.
в примере
P>>
P>>mulOrDiv        : int = simplExpr (('*' / '/') spaces simplExpr)*;
P>>

не получится разобрать к виду
VD>
VD>mulOrDiv(simplExpr : int, mulDivs : list[Token * Token * simplExpr]) : int
VD>{
...
VD>}
VD>

потому что когда парсер встретит '*' или '/', то он не добавит его к АСТ(в том числе виртуальному), а следовательно нечего будет передать в этот метод.
этого просто пока не реализовано.
Re[8]: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 16.03.10 10:15
Оценка:
Здравствуйте, para, Вы писали:

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


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

Тот же компилятор не нуждается в AST, так как производит вычисления сразу.

P>Но даже виртуальное АСТ надо наполнять.

P>в примере
P>>>
P>>>mulOrDiv        : int = simplExpr (('*' / '/') spaces simplExpr)*;
P>>>

P>не получится разобрать к виду
VD>>
VD>>mulOrDiv(simplExpr : int, mulDivs : list[Token * Token * simplExpr]) : int
VD>>{
P>...
VD>>}
VD>>

P>потому что когда парсер встретит '*' или '/', то он не добавит его к АСТ(в том числе виртуальному), а следовательно нечего будет передать в этот метод.

Если передавать нечего, то нужно передавать токен описывающий диапазон строки сопоставленный с подправилом. Посмотри еще раз приведенный пример. В нем подправило "('*' / '/')" сопоставляется с первым Token в кортеже, а подправило spaces со вторым Token. Это позволяет извлечь значение оператора, реально разобранного в строке, с помощью информации извлеченной из первого Token-а кортежа.

Так что парсеру нужно сохранять значения разобранных подправил, получаемые по мере разбора правил, но не в виде AST, а в виде отдельных токенов и значений. Эти значения (токены и значения полученные от обработчиков вложенных правил) должны храниться просто в стеке. Если произойдет откат, то даже не придется ничего делать.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: [Macro] PEG-парсер (разработка)
От: para  
Дата: 16.03.10 12:21
Оценка:
Здравствуйте, VladD2, Вы писали:
P>>потому что когда парсер встретит '*' или '/', то он не добавит его к АСТ(в том числе виртуальному), а следовательно нечего будет передать в этот метод.

VD>Если передавать нечего, то нужно передавать токен описывающий диапазон строки сопоставленный с подправилом. Посмотри еще раз приведенный пример. В нем подправило "('*' / '/')" сопоставляется с первым Token в кортеже, а подправило spaces со вторым Token. Это позволяет извлечь значение оператора, реально разобранного в строке, с помощью информации извлеченной из первого Token-а кортежа.


под "нечего" я подразумеваю отсутсвие этого токена и отсутствие информации от расположении токена в исходной разбираемой строке.

на вход парсеру подашь "1 / 2"
вызовется гененрирующий метод с параметрами: ("1", ["2"])

так что сейчас буду заниматься тем, чтоб "/" после парсинга добавлялось к "АСТ"
и на вход методу шло: ("1", ["/","2"])

когда будет создаватьтся корректное АСТ, буду переходить на прямые вызовы.

Кстати.
если неправильно составить грамматику, парсер может уйти в бесконечный цикл.
Есть ли планы/алгоритмы проверки корректности семантики грамматики?
Re[10]: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 16.03.10 14:00
Оценка:
Здравствуйте, para, Вы писали:

P>под "нечего" я подразумеваю отсутсвие этого токена и отсутствие информации от расположении токена в исходной разбираемой строке.


P>на вход парсеру подашь "1 / 2"

P>вызовется гененрирующий метод с параметрами: ("1", ["2"])

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

P>и на вход методу шло: ("1", ["/","2"])

Ты меня не слышишь.

Давай еще раз по порядку. Дай свое описание термина "АСТ" и объясни зачем оно тебе нужно.

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


Не нужно ни формировать АСТ, ни дожидаться того когда он стане корректным. Надо тупо вызвать методы-обработчики для всех для всех разобранных правил, а промежуточные результаты просто держать в стеке. Если результат некоторого метода в дальнейшем не понадобится, то и фиг бы с ним. Это следствие выбранного алгоритма.

Посторайся понять, промежуточное АСТ будет существенно тормозить скорость парсера, так как создание объектов — это дорогая операция.

P>Кстати.

P>если неправильно составить грамматику, парсер может уйти в бесконечный цикл.
P>Есть ли планы/алгоритмы проверки корректности семантики грамматики?

ЗЫ

Постарайся все же понять, что построение АСТ это не нужная, вредная операция. От нее нужно отказаться. Это возможно и даже не очень сложно.

Да, но сначала нужно качественно реализовать основной алгоритм и вызов методов-обработчиков.
Прямую левую рекурсию нужно переписывать, а не прямую детектить и сообщать об ошибке.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: [Macro] PEG-парсер (разработка)
От: para  
Дата: 16.03.10 14:07
Оценка:
VD>Давай еще раз по порядку. Дай свое описание термина "АСТ" и объясни зачем оно тебе нужно.
оно нужно для отладки и подтверждения факта правильного распарсивания.

VD>Постарайся все же понять, что построение АСТ это не нужная, вредная операция. От нее нужно отказаться. Это возможно и даже не очень сложно.

я это понял уже

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

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


А разве он работает не правильно?

P>я буду убирать хранение АСТ и вызывать методы-обработчики напрямую


ОК.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG-парсер
От: para  
Дата: 17.03.10 13:27
Оценка: 129 (1)
Добавил возможность обработки терминальных символов в правой части нетерминального правила.

теперь правило
mulOrDiv        : int = simplExpr (('*' / '/') spaces simplExpr)*;

преобразуется в
unnamedRule_1         = ('*' / '/');
mulOrDiv        : int = simplExpr (unnamedRule_1 spaces simplExpr)*;


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

Несколько замечаний по коду...

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

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

Если в макрос тебе понадобится уникальное имя, то лучше не изобретать велосипед с каунтерами, а использовать функцию Nemerle.Compiler.Util.tmpname(). Она генерирует уникальные имена с которыми невозможно пересечься нечаянно. Она выдает имена в формате Util.tmpname("Test") => "_N_Test_4321".

Устраняй причины предупреждений (warning-ов). И удаляй не нужный код. Все что нужно можно всегда найти в SVN или прикопать в других каталогах.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: para  
Дата: 17.03.10 16:49
Оценка:
спасибо
Re: PEG-парсер
От: para  
Дата: 18.03.10 12:31
Оценка: 126 (1)
Залил версию без хранения АСТ
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 15:55
Оценка:
Здравствуйте, para, Вы писали:

P>Залил версию без хранения АСТ


Супер! Молодец!

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

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

Далее нужно будет доводить все это дело до ума:
1. Оптимизировать производительность.
2. Добавлять проверки.
3. Добавить возможность расширения парсера.

Ну, и экспериментировать по всякому.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 15:58
Оценка:
Здравствуйте, para, Вы писали:

P>Залил версию без хранения АСТ


Да... Применение "lazy" — это баловство в данном случае.

Просто реализуй свойство Data вручную следующим образом:
public Data : string
{
  get
  {
    when (_data == null)
      _data = _text.Substring(_startPos, _endPos - _startPos));

    _data
  }
}
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 16:23
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>>>А если кто-то решит токен кудато сохранить?

VD>>По лучит по рукам коода попытается его потом использовать.
WH>Нет. Он получит мутные глюки и как следствие бросит это дело.

Подумалось...

Для написания и отладки грамматик несомненно удобнее иметь токен в виде объекта.

С точки зрения скорости лучше конечно передавать минимальную информацию. Возможно просто не передавать ничего, пользуясь знанием о внутреннем содержимом и состоянии парсера.

Ну, и раз у нас в руках такая крутая штука как макросы, то мы можем обеспечить и то, и другое!

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

При таком подходе в оптимизированной версии вообще не придется передавать параметров. Вместо этого будет генерироваться код который будет получать нужные данные позиционно (на основании пзиции подправила).
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: WolfHound  
Дата: 18.03.10 16:29
Оценка:
Здравствуйте, VladD2, Вы писали:

P>>Залил версию без хранения АСТ

VD>Супер! Молодец!
Если ты посмотришь код ты ты поймешь какую ерунду он там понаписал.
Вот например:
            def l = _capturedTokens;
            _capturedTokens = [];
            
            def newPos = { $(compile(rule)) };    
          
            if(newPos < 0)
            {      
              _capturedTokens = l;     
            }
            else
            {
              def t = $(tokenExpr);                
              
              _capturedTokens = l + [t];     
            }     
            newPos

К чему приведет выделеное в случае попадания этого безобразия внутрь * думаю объяснять не надо.

Сам код тоже весьма неряшлив особенно если включить режим View White Space
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: PEG-парсер
От: WolfHound  
Дата: 18.03.10 16:29
Оценка: +1
Здравствуйте, VladD2, Вы писали:

P>>Залил версию без хранения АСТ

VD>Да... Применение "lazy" — это баловство в данном случае.
Особенно если учесть то что оно не правильно использовано...
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.