PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.03.10 20:09
Оценка:
Хочу привлечь желающих к проекту "макроса построителя парсеров на основе PEG-нотации", сокращенно "PEG-парсер", или еще более сокращенно nPEG.

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

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

Вот требования которые предъявляемые к этому проекту:
1. Скорость работы. Парсер полученный с помощью nPEG должен максимально быстро парсить LL(1)-грамматики и приемлемо быстро грамматики LL(*) (т.е. с неограниченным заглядыванием вперед).
2. Должна поддерживаться нотация PEG (в том числе предикаты).
3. Парсер должен поддерживать модульность. Пока что предполагается, что от класса в котором реализуется парсер можно будет унаследовать другие классы в которых можно будет изменять (дополнять, изменять или упрощать) исходную грамматику, но возможно, что стоит внести и более мощные методы расширения (подключение нескольких грамматик).
4. Реакции (т.е. код который должен выполняться в те моменты когда парсер распознает ту или иную конструкцию описанную в грамматике) должны оформляться отдельными методами и находиться внутри классов, а не внутри описания грамматики (как это происходит в большинстве современных построителях парсеров).

Заготовка проекта находится здесь, т.е. в репозитории Nemerle.

Чтобы получить доступ на запись в репозиторий Nemerle нужно прислать мне гуглеый экаунт (это может быть адрес на gmail или экаунт заведенный на code.google.com).

Вот пример простого калькулятора описанного с помощью данного макроса:
  [PegGrammar(start,
  grammar
  {
    any            = ['\u0000'..'\uFFFF'];
    digit          = ['0'..'9'];
    spaces         = ' '*;
    num      : int = digit+ spaces;

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

    expr1          = opDiv / opMul / expr2;
    opDiv    : int = expr2 '/' spaces expr1;
    opMul    : int = expr2 '*' spaces expr1;

    expr2    : int = num / brackets;

    brackets : int = ('(' spaces expr0 ')' spaces)

    start          = spaces expr0 spaces !any;
  })]
  class CalcGrammar
  {
    // этот обработчик вызывается после окончания разбора правила "num"
    num(digitsTok : TokenInfo, _spacesTok : TokenInfo) : int
    {
      int.Parse(digitsTok.GetString())
    }

    // этот обработчик вызывается после окончания разбора правила "brackets"
    brackets(_leftBracket : TokenInfo, _spaces1 : TokenInfo, expr0 : int, _rightBracket : TokenInfo, _spaces2 : TokenInfo) : int
    {
      expr0
    }

    // этот обработчик вызывается после окончания разбора правила "opAdd"
    opAdd(expr1 : int, _pluseTok : TokenInfo, _spaces : TokenInfo, expr0 : int) : int
    {
      expr1 + expr0
    }
  
    // Остальные правила опущены ...
  }


На сегодня реализовано:
1. Разбор PEG-грамматики приведенной выше.
2. Генерация простого сопоставления.

На сегодня не реализовано:
1. Распознавание обработчиков и подстановка их вызовов в код парсера (генерируемый в процессе работы макроса).
2. Обработка ошибок (распознавание ошибочных ситуаций и вывод информации о них для пользователя конечного парсера).
3. Разного рода оптимизации и то что пока даже представить себе сложно .

Основной код парсера написан WolfHound. Код распознавания грамматики — мной.

Описание файлов:
1. Тесты.
2. Macro.n — описание макросов grammar и PegGrammar, а так же GrammarImpl в котором сведена низкоуровневая логика генерации парсера (т.е. логика работы макроса PegGrammar). Макрос grammar — это небольшой трюк заставляющий немерловый компилятор не парсить код грамматики по правилам немерле, а хранить ее в виде токена. Данный токен извлекается и обрабатывается макросом PegGrammar (а точнее функций Parsing.ParseRules).
3. Parsing.n — код производящий парсинг токена из макроса grammar и преобразующий его в AST-парсера описываемое вариантным типом Rule. Это обычный нисходящий рекурсивный парсер написанный врукопашную. Единственная его особенность он разбирает токены немерле, а не входную строку.
4. Rule.n — variant Rule — можно сказать AST парсера (внутреннее представление правил). Вот как он выглядит:
  internal variant Rule
  {
    | Choice         { rules : list[Rule]; }
    | Sequence       { rules : list[Rule]; }
    | Call           { name : string; }
    | RepeatMin      { minCount : int; rule : Rule; }
    | RepeatMinMax   { minCount : int; maxCount : int; rule : Rule; }
    | Chars          { chars : list[RangeSet]; }
    | Not            { rule : Rule; }
    | And            { rule : Rule; }
    | Capture        { name : string; argType : RuleType; retType : RuleType; rule : Rule; }
    | ExtensionPoint { name : string; }
...

5. RangeSet.n — описание класса RangeSet хранящего (и управляющего) диапазонами символов.
6. Grammar.n — класс в котором формируется грамматике (не уверен, лучше спросить WolfHound-а).
7. Optimizer.OptimizeGrammar.n — оптимизация грамматики (сокращение путем обледенения с другими правилами и выбрасывания лишнего). Фактически просто формирует новую грамматику помещая в нее оптимизированные правила (см. пункт 8).
8. Optimizer.OptimizeRule.n — оптимизация правил.
9. RuleCompiler.CompileRule.n — преобразование грамматики (в виде AST на базе вариантного типа Rule) в код парсера, т.е. генерация кода парсера. Собственно самый недописанный кусок.

Задача простая — довести все это до кондиции (т.е. до того момента когда генератор парсеров можно будет использовать в реальных проектах).

ЗЫ

Клятвенно обещаю, что как только макрос заработает как надо, я напишу, с его помощью, грамматику для C# 3.0 (точнее его подтипа не использующего небезопасный код) и сделаю так, чтобы немерле мог компилировать большую часть C#-код!
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG-парсер
От: Мишень-сан  
Дата: 02.03.10 08:46
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>4. Rule.n — variant Rule — можно сказать AST парсера (внутреннее представление правил). Вот как он выглядит:

VD>
VD>  internal variant Rule
VD>  {
VD>    | Choice         { rules : list[Rule]; }
VD>    | Sequence       { rules : list[Rule]; }
VD>    | Call           { name : string; }
VD>    | RepeatMin      { minCount : int; rule : Rule; }
VD>    | RepeatMinMax   { minCount : int; maxCount : int; rule : Rule; }
VD>    | Chars          { chars : list[RangeSet]; }
VD>    | Not            { rule : Rule; }
VD>    | And            { rule : Rule; }
VD>    | Capture        { name : string; argType : RuleType; retType : RuleType; rule : Rule; }
VD>    | ExtensionPoint { name : string; }
VD>  }
VD>


А не подскажете, для чего ноды типа Call и Capture? Первый, похоже, есть ссылка на правило. Второй —

P.S. Не могу ни разу обещать, что займусь, т.к. грамматическим разбором начал интересоваться совсем недавно, а потому туп в этом деле как пробка. Но чем чёрт не шутит...
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 02.03.10 12:35
Оценка:
Здравствуйте, Мишень-сан, Вы писали:

Вообще-то конечно на такие вопросы лучше бы отвечать Вольфхаунду, ну, да попробую...

МС>А не подскажете, для чего ноды типа Call и Capture? Первый, похоже, есть ссылка на правило. Второй —


Верно, Call — это обращение к другому правилу.

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

Такие заглушки генерируются для правил которые имеют имена и описание типа. В моем примре это num, brackets, opAdd и т.п.

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

Более точно может сказать только Вольфхаунд.

МС>P.S. Не могу ни разу обещать, что займусь, т.к. грамматическим разбором начал интересоваться совсем недавно, а потому туп в этом деле как пробка. Но чем чёрт не шутит...


Ну, все мы когда-то ничего в парсинге не понимали. Даже те кто проходил их в универе, так как там их обычно проходят мимо .

В общем, пока более опытные товарищи борются с ленью и старыми проблемами можно внести свое имя в аналы истории и очень существенно помочь проекту. Макрос и правда очень интересный и вызовет, на мой взгляд, серьезный интерес.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG-парсер
От: WolfHound  
Дата: 09.03.10 16:51
Оценка:
Здравствуйте, VladD2, Вы писали:

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

Не "возможно", а необходимо.
Причем должна быть возможность подключать и отключать расширения во время разбора текста.
Иначе синтаксические макросы работать не будут.

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

VD>Вот пример простого калькулятора описанного с помощью данного макроса:

Тут тоже не все так просто особенно с учетом расширяемости.

Короче пока мало понятно как это должно выглядить и во что компилироваться.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 09.03.10 17:58
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Не "возможно", а необходимо.


OK.

WH>Причем должна быть возможность подключать и отключать расширения во время разбора текста.


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

WH>Иначе синтаксические макросы работать не будут.


Это понятно. Но этот макрос все же нужен в первую очередь для пользователей Nemerle 1.0.

WH>Также для модульности совершенно необходима поддержка левой рекурсии иначе операторы охрнеешь добавлять.


Я бы пережил. Или обошелся бы переписыванием прямой левой рекурсии.
Что касается операторов, то для них нужно будет создавать более специализированное решение которое позволит объявлять их совсем декларативно (с указанием приоритетов и ассоциативности). Лично я вижу себе это примерно так:
macro operator @+ (expr1, expr2)
  associativity: left
  precedence:    less then: * great then: <<
{
  ...
}

Но это опять таки относится к макросам в Nemerle 2.0.

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

WH>Короче пока мало понятно как это должно выглядить и во что компилироваться.


Как я уже сказал, для макроса не нужно излишних изысков. Он должен быть просто построителем парсеров по PEG-грамматике. Это даст нам возможность опробовать нужные идеи и в дальнейшем или расширить его до нужных кондиций, или написать новую версию учитывающую полученный опыт.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG-парсер
От: para  
Дата: 11.03.10 13:56
Оценка:
Начал разбираться.
не легко.

Есть несколько вопросов:
В классе CalcGrammar есть метод Start, который, вероятно и производит парсинг.
1. Что должно получиться на выходе парсера?
2. для калькулятора — В какой момент должно производится вычисление выражения1 &mdash; 2* 3 -4+5/(6- 7) ;?

Пока есть такое предложение:
Те члены парсера, которые не зависят от грамматики вынести в базовый класс:

public abstract class ParserBase
  {
    protected _text : string;
    protected _cache : System.Collections.Generic.Dictionary[int, int] = System.Collections.Generic.Dictionary();
    protected _captures : System.Collections.Generic.List[LRPEGCC.Capture] = System.Collections.Generic.List();        

    public Captures : System.Collections.Generic.List[LRPEGCC.Capture] 
    { 
      get { _captures } 
    }        

    public this(text : string)
    {
      _text = text;
    }    

    protected GetChar(pos : int) : char
    {
      _text[pos];
    }    

    protected CheckTextLength(pos : int) : bool
    {
      pos < _text.Length;
    }       

    public abstract Start() : int; 
  }

В результате немного упростится код макроса
и самого парсера
[PegGrammar(start,
  grammar
  {
    any       = ['\u0000'..'\uFFFF'];
    digit     = ['0'..'9'];
    spaces    = ' '*;
    num       = digit+ spaces;
    expr0     = opAdd / opSub / expr1;
    opAdd     = expr1 '+' spaces expr0;
    opSub     = expr1 '-' spaces expr0;
    expr1     = opDiv / opMul / expr2;
    opDiv     = expr2 '/' spaces expr1;
    opMul     = expr2 '*' spaces expr1;
    expr2     = num / ('(' spaces expr0 ')' spaces);
    start     = spaces (expr0 ";" spaces)+ !any;
  })]
  public class CalcParser : ParserBase
  {  
    public this(text : string)
    {
        base(text);
    }

    //обработчики...
  }


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

P>Есть несколько вопросов:

P>В классе CalcGrammar есть метод Start, который, вероятно и производит парсинг.
P>1. Что должно получиться на выходе парсера?
P>2. для калькулятора — В какой момент должно производится вычисление выражения1 &mdash; 2* 3 -4+5/(6- 7) ;?

Сразу оговорюсь, что так как код этого проекта в основном писал не я (я писал только код разбора PEG-грамматики — Parsing.n), то я могу в основном высказывать только свои догадки.

Как я понимаю на сегодня сам парсинг, т.е. вызов пользовательских методов при разборе правил грамматики не реализован вовсе. Там есть что-то очень зачаточное.

Как я понимаю метод Start — это метод входа в парсер. Он генерируется макросом (см. Macro.n строка 70) и на сегодня возвращает количество опарсеных символов (что ни для чего кроме тестов не годится).

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

Поясню мысль...

Парсер может просто интерпретировать выражение. Тогда на выходе мы должны получить просто целое число (int или long). Но парсер может генерировать некое AST или даже эмитить код в MSIL.
В случае генерации AST выходом парсера должна быть некая структура данных описывающая это AST (например, вариантный тип данных).

Так вот, то что возвращает парсер должно зависеть от двух вещей:
1. От аннотаций типов указанных у правил в грамматике. Посмотри на строку 37 файла Main.n. Там приведена грамматика с такими аннотациями. В данном случае Expr — это вариантный тип описанный в строке 10 этого же файла.

2. От типов возвращаемых значений методов-обработчиков. Их поддержка (как я понимаю) пока что вообще не реализована. Но в них то как раз вся суть и заключается. Семантические действия производимые парсером должны определяться именно методами-обработчиками.

Я не даром описал (здесь
Автор: VladD2
Дата: 01.03.10
) эти самые гипотетические обработчики.

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

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

Теперь немного о правилах по которым должна работать генерация методов-обработчиков.

Имя обработчика должно соответствовать имени правила.
Параметры методов-обработчиков (далее МО) должны соответствовать содержимому правил по следующему принципу:
1. Если в правиле перечислена последовательность других правил, например:
opAdd    : int = expr1 '+' spaces expr0;

то для каждого подправила (обращения к правилу) МО должен содержать по одному параметру.

2. Параметр может иметь тип Token, тип описанный в правиле на который ссылается данный параметр или список, если в грамматике имеется цикл (применены операторы "+" или "*"). Если после правила соответствующего данному параметру идет оператор "?" (что означает, что правило не обязательное), то параметр может содержать null. Соответственно, если тип параметра — это value-тип, в таком случае требуется использование nullable-типа (например, если правило помечено как возвращающее тип int, то параметр должен быть типа int?).

3. Если в теле правила имеется цикл, то параметр должен быть типа list[T] где T — это тип выражения выводимый для тела цикла. Циклы, в грамматике, описываются с помощью суффиксов "*" или "+". Пример правила с циклом:
mulOrDiv          = simplExpr (('*' / '/') simplExpr)*

Здесь цикл выделен жирным.

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

Например, для примера:
any                    = ['\u0000'..'\uFFFF'];
digit                  = ['0'..'9'];
spaces                 = ' '*;
num             : Expr = digit+ spaces;
unaryMinus      : Expr = '-' simplExpr;
parenthesesExpr : Expr = '(' sumOrSub ')'
simplExpr       : Expr = num / parenthesesExpr / unaryMinus
mulOrDiv        : Expr = simplExpr (('*' / '/') simplExpr)*
sumOrSub        : Expr = mulOrDiv  (('+' / '-') mulOrDiv )*

обработчики должны иметь следующие сигнатуры:
num(digits : Token, _spaces : Token) : Expr
{
  Expr.Number(int.Parce(digits.GetString()))
}

unaryMinus(_minus : Token, simplExpr : Expr) : Expr
{
  Expr.UnaryMunus(simplExpr)
}

parenthesesExpr (_openBracket : Token, simplExpr : Expr, _closeBracket : Token) : Expr
{
  simplExpr
}

// !!! Для правила simplExpr нам не нужно писать обработчик, так как он может быть 
//     автоматически сформирован макросом (так как он просто возвращает результат
//     одного из своих подправил, которые обязаны иметь одинаковый тип возвращаемого значения)

mulOrDiv(simplExpr : Expr, addLoop : list[Token * Expr]) : Expr
{
  mutable expr = simplExpr;

  foreach ((token, secondExpr) in addLoop)
    if (token.GetChar() == '*') 
      expr = Expr.Mul(expr, secondExpr);
    else
      expr = Expr.Div(expr, secondExpr);
}

sumOrSub(simplExpr : Expr, addLoop : list[Token * Expr]) : Expr
{
  mutable expr = simplExpr;

  foreach ((token, secondExpr) in addLoop)
    if (token.GetChar() == '+') 
      expr = Expr.Add(expr, secondExpr);
    else
      expr = Expr.Sub(expr, secondExpr);
}


P>Пока есть такое предложение:

P>Те члены парсера, которые не зависят от грамматики вынести в базовый класс:...

Да, наверно это разумно.
Не уверен, что так надо поступать с _cache и _captures, так как они вроде как должны генерироваться макросом. Но, конечно методы доступа к символам строки могут распологаться и в базовом классе. Причем для этого даже не надо менять макрос. Он, скорее всего, будет работать даже если эти методы перенести в базовый класс. Он веть просто генерирует код к ним обращающийся, а то где они определены ему по фигу.

P>Естественно, не буду заливать пока, чтоб кому-нибудь не сбить мысль...


Ну, учитывая что пока что статус у проекта "никто толком не взялся", то можешь и заливать. Особых проблем возникнуть не должно.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.03.10 19:31
Оценка:
Здравствуйте, VladD2, Вы писали:

Описанный мной Token — это гипотетический класс (или структура, тут нужно покумекать) описывающий распознанную сущность. В нем должны быть члены:
StartPos             : int      // смещение начала фрагмента от начала в символах
EndPos               : int      // смещение конца фрагмента от начала в символах
Location             : Location // местоположение в тексте в терминах строка/символ в строке (аналог Location из компилятора)
GetText()            : string   // возвращает текст распознанной области
GetChar()            : char     // возвращает первый символ распознанной области (или исключение)
GetChar(index : int) : char     // возвращает n-ый символ распознанной области (или исключение)
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG-парсер
От: WolfHound  
Дата: 11.03.10 20:37
Оценка: +1
Здравствуйте, VladD2, Вы писали:

VD>Описанный мной Token — это гипотетический класс (или структура, тут нужно покумекать) описывающий распознанную сущность. В нем должны быть члены:

Токен у тебя получился очень толстым.

VD>StartPos : int // смещение начала фрагмента от начала в символах

VD>EndPos : int // смещение конца фрагмента от начала в символах
Вот этих двух полей достаточно.
Причем EndPos должен указывать не на последний символ фрагмента, а не следующий. Так намного проще.
Кстати Pos тут тоже лишний.

VD>Location : Location // местоположение в тексте в терминах строка/символ в строке (аналог Location из компилятора)

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

VD>GetText() : string // возвращает текст распознанной области

VD>GetChar() : char // возвращает первый символ распознанной области (или исключение)
VD>GetChar(index : int) : char // возвращает n-ый символ распознанной области (или исключение)
Это токену совсем не нужно. Ты не забывай что управление передается объекту Parser внутри которого есть все что нужно чтобы это получить.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[5]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.03.10 21:01
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Токен у тебя получился очень толстым.


Если передавать по ссылке, ничего страшного.
Можно сделать пул таких объектов и повторно их использовать.

VD>>StartPos : int // смещение начала фрагмента от начала в символах

VD>>EndPos : int // смещение конца фрагмента от начала в символах
WH>Вот этих двух полей достаточно.

Ну, никто же не говорит, что все должно быть полями? Другие элементы можно сделать свойствами. В прочем все равно нужна позиция в терминах строка/колонка. Именно они будут в реальном парсере использоваться.

WH>Причем EndPos должен указывать не на последний символ фрагмента, а не следующий.


Может быть. Как я уже сказал, в реальных парсерах скорее потребуется Line и Col.

WH>Так намного проще.


Кому? Макросу?

WH>Кстати Pos тут тоже лишний.


Я предпочитаю внятные имена. В прочем, меня интересует дело. А названия можно и потом отрефакторить.

VD>>Location : Location // местоположение в тексте в терминах строка/символ в строке (аналог Location из компилятора)

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

Быстрее — возможно. Проще и удобнее — однозначно, нет. Человек оперирует терминами строка/символ. Их конечно можно каждый раз вычислять, но это а) не продуктивно и б) требует таскать за локешоном строку с исходником.

WH>А при выводе сообщений пользователю уже переводить в строка/символ в строке.


О они не только в сообщениях нужны. Они в отладчике нужны. И их иногда нужно просто отдельно хранить и передавать куда-то. Без наличия исходной строки документа перевести позицию в Location не получится. А хранить стрки — это как-то расточительно.

WH>Благо для этого нужен только массив в котором лежат смещения всех строк в файле.


Массив тоже нужно создавать будте и хранить где-то. Он от строки мало чем отличаться будет. В добавок еге еще формировать придется. Когда и кто его будет формировать?

VD>>GetText() : string // возвращает текст распознанной области

VD>>GetChar() : char // возвращает первый символ распознанной области (или исключение)
VD>>GetChar(index : int) : char // возвращает n-ый символ распознанной области (или исключение)
WH>Это токену совсем не нужно. Ты не забывай что управление передается объекту Parser внутри которого есть все что нужно чтобы это получить.

Ты с какой-то не верной позиции смотришь. Кроме эффективной реализации людям еще нужен красивый итерфейс.

Писать token.GetText() все же приятнее нежели GetText(token).

Если использовать токены из пула, то заложить ссылку на строку в них можно будет еще при инициализации.

В прочем, все это опять же детали. Важно само наличие возможности получения информации о токене.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: PEG-парсер
От: WolfHound  
Дата: 11.03.10 21:29
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Если передавать по ссылке, ничего страшного.

VD>Можно сделать пул таких объектов и повторно их использовать.
Ааааааааа!!!!!!!!!!!!!! Жжжжжжжжжжжжжжжеееесть.
А если кто-то решит токен кудато сохранить?
Этож такие грабли на ровном месте...

WH>>Причем EndPos должен указывать не на последний символ фрагмента, а не следующий.

WH>>Так намного проще.
VD>Кому? Макросу?
Пользователю. С полуинтервалами работать всегда удобней.
Посмотри хотябы на STL думаешь там итераторы просто так устроены так как они устроены?

VD>О они не только в сообщениях нужны. Они в отладчике нужны.

В каком еще отладчике?
Если ты про генерацию отладочной информации то это ни разу не проблема.

VD>И их иногда нужно просто отдельно хранить и передавать куда-то.

Куда и зачем?

VD>Писать token.GetText() все же приятнее нежели GetText(token).

Как по мне так без разници. А учитывая что для первого варианта придется не слабо извращаться то второй вариант остается без вариантов.

VD>В прочем, все это опять же детали. Важно само наличие возможности получения информации о токене.

Все что для этого нужно два инта.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[7]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.03.10 21:41
Оценка:
Здравствуйте, WolfHound, Вы писали:

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


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

WH>Этож такие грабли на ровном месте...


Ну, можнос и по мордамс, а можно и впердолитьсъ (с) поручит Ржевский.

WH>>>Причем EndPos должен указывать не на последний символ фрагмента, а не следующий.

WH>>>Так намного проще.
VD>>Кому? Макросу?
WH>Пользователю. С полуинтервалами работать всегда удобней.

А зах ему вообще с позициями работать?

WH>Посмотри хотябы на STL думаешь там итераторы просто так устроены так как они устроены?


Гы. Плохой пример.

VD>>О они не только в сообщениях нужны. Они в отладчике нужны.

WH>В каком еще отладчике?

В любом. Я когда в компиляторе вожусь без Location-ов никуда.

WH>Если ты про генерацию отладочной информации то это ни разу не проблема.


Я про постоянное наличие Location. В любом месте нужно знать из чего был получен АСТ.

VD>>И их иногда нужно просто отдельно хранить и передавать куда-то.

WH>Куда и зачем?

Для хранения и обарботки. Location он нужен для всего и везде.

VD>>Писать token.GetText() все же приятнее нежели GetText(token).

WH>Как по мне так без разници. А учитывая что для первого варианта придется не слабо извращаться то второй вариант остается без вариантов.

Ну, в общем-то это не принципиально. А вот Location все же нужен.

VD>>В прочем, все это опять же детали. Важно само наличие возможности получения информации о токене.

WH>Все что для этого нужно два инта.

По два параметра на один токен? Нафиг такую оптимизацию.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.03.10 21:54
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Например, для примера:

VD>
VD>any                    = ['\u0000'..'\uFFFF'];
VD>digit                  = ['0'..'9'];
VD>spaces                 = ' '*;
VD>num             : Expr = digit+ spaces;
VD>unaryMinus      : Expr = '-' simplExpr;
VD>parenthesesExpr : Expr = '(' sumOrSub ')'
VD>simplExpr       : Expr = num / parenthesesExpr / unaryMinus
VD>mulOrDiv        : Expr = simplExpr (('*' / '/') simplExpr)*
VD>sumOrSub        : Expr = mulOrDiv  (('+' / '-') mulOrDiv )*
VD>


Да... здесь я в грамматике забыл понаставить "spaces"-ов. Реально грамматика должна быть такая:
digit                  = ['0'..'9'];
spaces                 = ' '*;
num             : Expr = digit+ spaces;
unaryMinus      : Expr = '-' spaces simplExpr;
parenthesesExpr : Expr = '(' spaces sumOrSub ')' spaces
simplExpr       : Expr = num / parenthesesExpr / unaryMinus
mulOrDiv        : Expr = simplExpr (('*' / '/') spaces simplExpr)*
sumOrSub        : Expr = mulOrDiv  (('+' / '-') spaces mulOrDiv )*


Собственно глядя на эту грамматику сразу понимаешь, что хорошо бы иметь возможность игнорировать правила вроде spaces (в смысле, не требовать их передачи в качестве параметров). Это надо как-то декларировать. Например, так:
PegGramar(..., Ignore=spaces, ...)
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: PEG-парсер
От: WolfHound  
Дата: 12.03.10 10:20
Оценка:
Здравствуйте, VladD2, Вы писали:

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

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

VD>Плюс документировать такое решение нужно конечно.

А кто ее читает?
Я в свое время написал инструкцию по установке одной своей программы.
Там инструкции было всего строк 15 так ее никто и не читал. Все долбились ко мне в аську с вопросами ответы на которые были в той инструкции.

WH>>Посмотри хотябы на STL думаешь там итераторы просто так устроены так как они устроены?

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

VD>В любом. Я когда в компиляторе вожусь без Location-ов никуда.

То есть оно только для отладки нужно?

VD>Я про постоянное наличие Location. В любом месте нужно знать из чего был получен АСТ.

Пользователю оно нужно только для отладочной информации и собщений об ошибках.

VD>Для хранения и обарботки. Location он нужен для всего и везде.

А конкретно?

VD>Ну, в общем-то это не принципиально. А вот Location все же нужен.

Так он и будет. Только там будут не строка/позиция, а смещения.

VD>>>В прочем, все это опять же детали. Важно само наличие возможности получения информации о токене.

WH>>Все что для этого нужно два инта.
VD>По два параметра на один токен? Нафиг такую оптимизацию.
Зачем по два? В чем проблема упаковать их в структуру?
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[9]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 12.03.10 15:01
Оценка:
Здравствуйте, WolfHound, Вы писали:

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


Если в дебаге добавить проверки проблем не будет.
Бесплатных бенефитов не бывает. Мы все равно в чем-то теряем, чтобы получат что-то взамен.

VD>>Для хранения и обарботки. Location он нужен для всего и везде.

WH>А конкретно?

Тебе говорят, что Location очено важная и часто используемая конструкция. Погляди по коду немерлового компилятора в каких местах Location используется.

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

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

Зачем еще что-то придумывать?

VD>>Ну, в общем-то это не принципиально. А вот Location все же нужен.

WH>Так он и будет. Только там будут не строка/позиция, а смещения.

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

VD>>По два параметра на один токен? Нафиг такую оптимизацию.

WH>Зачем по два? В чем проблема упаковать их в структуру?

Структура конечно лучше, но при этом она будет забивать стек.

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

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

Вот это дело:
    public Result : 'T
    {
      get
      {
        unless(_isParsed)
        {
            _parsedSymbolsCount = DoParse();
            _isParsed = true;
        }   
        _result
      }
      protected set
      {
        _result = value;
      }
    }

мне совсем не нравится.

Парсер должен позволять парсить несколько строк (последовательно).

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

Далее... В коде есть TODO:
// TODO: Check is subclass of ParserBase

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

Эту функцию:
P>
P>    protected CheckTextLength(pos : int) : bool
P>

лучше назвать IsPositionCorrect() или IsNotEof(), а то и IsEof(), а в коде вызвать ее !IsEof().


P>В результате немного упростится.../sourceP>
P>    public this(text : string)
P>    {
P>        base(text);
P>    }
P>

это лишнее. В базовом классе должны быть методы Parse() (с разным набором параметров: строка, строка и виртуальная начальная позиция и т.п.).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: para  
Дата: 12.03.10 18:22
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Несколько замечаний.


Ок. учту.

я сейчас сделал так, потому, что мне надо хоть в каком-то виде получить результат парсинга.
это я в частности про Result : 'T

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

мне такое положение дел пока тоже кажется не самым лучшим, но я хотел бы отложить решение проблемы вида интерфейса на потом, когда я там получше разбирусь...
Re[4]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 12.03.10 18:36
Оценка:
Здравствуйте, para, Вы писали:

P>это я в частности про Result : 'T


Кстати, лучше придерживаться правил по именовнию дотента. Апострофы в некоторых редакторах (например Сцинтиле) распознаются некорректно. Это усложняет чтение кода вне студии.

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


ОК
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG-парсер
От: para  
Дата: 12.03.10 18:43
Оценка:
с парсером, понемногу получается.
внешний вид пока отладочный
[PegGrammar(start,
  grammar
  {    
    any            = ['\u0000'..'\uFFFF'];
    digit          = ['0'..'9'];
    spaces         = ' '*;
    num      : int = digit+ spaces;
    expr0          = opAdd / opSub / expr1;
    opAdd    : int = expr1 '+' spaces expr0;
    opSub    : int = expr1 '-' spaces expr0;
    expr1          = opDiv / opMul / expr2;
    opDiv    : int = expr2 '/' spaces expr1;
    opMul    : int = expr2 '*' spaces expr1;
    expr2    : int = num / brackets;
    brackets : int = ('(' spaces expr0 ')' spaces);
    start          = spaces expr0 spaces !any;
  })]
  public class CalcParser : ParserBase[int]
  {  
    public this(text : string)
    {
        base(text);
    }  
    protected override DoGenerateResult(symbols : list[int], ruleName : string) : int
    {
    | (_, "expr2") =>
         symbols.Nth(0)
    | (_, "brackets") =>
         symbols.Nth(0)
    | (_, "opMul") =>
         symbols.Nth(0) * symbols.Nth(1);
    | (_, "opDiv") =>
         symbols.Nth(0) / symbols.Nth(1);
    | (_, "opSub") =>
         symbols.Nth(0) - symbols.Nth(1);
    | (_, "opAdd") =>
         symbols.Nth(0) + symbols.Nth(1);
    |  _ =>
         throw Exception("sds");
    }  
    protected override DoGenerateResult(symbol : string, ruleName : string) : int
    {
      int.Parse(symbol)
    }
  }

тут все инты можно заменить на PExpr и в месте с тем заменить переопределённые методы, чтобы получить более продвинуты парсер. этот просто считает)
на выходе parser.Result : int

но пока дебажу баг:
выражение
mutable text = "1 - 2* 3 -4+5/(6- 7) ; ";

решается с неверно.
порядок вызова обработчиков таков:
1. отпарсить все числа
2. 2*3 = 6
3. 6-7 = -1
5. 5/-1 = -5
6. 4-5 = -1 !!!!!!!!! вычитание и сложение у меня идёт справа налево а надо на оборот.

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

P>
P>    protected override DoGenerateResult(symbols : list[int], ruleName : string) : int
P>    {
P>    | (_, "expr2") =>
P>         symbols.Nth(0)
P>...


Здорово, что что-то работает, но выглядит это не так как хотелось бы. Этот DoGenerateResult какой-то не внятный.
Все же хотелось бы видеть вызовы именованных правил и не видеть обработки строк и этих symbols.

P>решается с неверно.

P>порядок вызова обработчиков таков:
P>...
P>5. 5/-1 = -5
P>6. 4-5 = -1 !!!!!!!!! вычитание и сложение у меня идёт справа налево а надо на оборот.

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

Возможно для начала лучше взять грамматику с циклами. В ней ассоциативность будет зависить от того как работают семантические правила. Так что лучше отлаживайся вот на такой грамматике:
any                    = ['\u0000'..'\uFFFF'];
digit                  = ['0'..'9'];
spaces                 = ' '*;
num             : Expr = digit+ spaces;
unaryMinus      : Expr = '-' spaces simplExpr;
parenthesesExpr : Expr = '(' spaces sumOrSub ')' spaces;
simplExpr       : Expr = num / parenthesesExpr / unaryMinus;
mulOrDiv        : Expr = simplExpr (('*' / '/') spaces simplExpr)*;
sumOrSub        : Expr = mulOrDiv  (('+' / '-') spaces mulOrDiv )*;
start           : Expr = spaces sumOrSub !any;


В ней ассоциативность будет зависеть только от реализации обработчиков для правил mulOrDiv и sumOrSub.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>т.е. передавать параметры сюда можно только списками

Ну, да. Так и надо делать. Цикл и должен разворачиваться в последовательность (список).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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 — это синимальный тип-значение. Он скорее всего будет в регистр запихнут. А объект по любому будет создаваться в куче и при этом еще будут делаться блокировки.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: [Macro] PEG-парсер (разработка)
От: VladD2 Российская Империя www.nemerle.org
Дата: 15.03.10 20:25
Оценка:
Здравствуйте, para, Вы писали:

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


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

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

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

Возможно имеет смысл даже задавть те правила для которых нужно формировать токены.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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, а в виде отдельных токенов и значений. Эти значения (токены и значения полученные от обработчиков вложенных правил) должны храниться просто в стеке. Если произойдет откат, то даже не придется ничего делать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>Есть ли планы/алгоритмы проверки корректности семантики грамматики?

ЗЫ

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

Да, но сначала нужно качественно реализовать основной алгоритм и вызов методов-обработчиков.
Прямую левую рекурсию нужно переписывать, а не прямую детектить и сообщать об ошибке.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>я буду убирать хранение АСТ и вызывать методы-обработчики напрямую


ОК.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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 или прикопать в других каталогах.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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. Добавить возможность расширения парсера.

Ну, и экспериментировать по всякому.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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
  }
}
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 16:23
Оценка:
Здравствуйте, WolfHound, Вы писали:

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

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

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

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

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

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

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

При таком подходе в оптимизированной версии вообще не придется передавать параметров. Вместо этого будет генерироваться код который будет получать нужные данные позиционно (на основании пзиции подправила).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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) А. Эйнштейн
Re[4]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 16:54
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Если ты посмотришь код ты ты поймешь какую ерунду он там понаписал.

WH>Вот например:
WH>
WH>            def l = _capturedTokens;
WH>            _capturedTokens = [];
            
WH>            def newPos = { $(compile(rule)) };    
          
WH>            if(newPos < 0)
WH>            {      
WH>              _capturedTokens = l;     
WH>            }
WH>            else
WH>            {
WH>              def t = $(tokenExpr);                
              
WH>              _capturedTokens = l + [t];     
WH>            }     
WH>            newPos
WH>


Ты о том, что он забыл о случаях отката или о низкой производительности?

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


Думаю, что надо объяснять. Как минимум для того чтобы исправить ошибку.
За одно для общего развития окружающих. Эту тему ведь не один человек читает...

WH>Сам код тоже весьма неряшлив особенно если включить режим View White Space


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

Лучше бы помог ему. Твои знания сейчас очень нужны.
Ну, и критику тоже лучше высказывать более конструктивно, чтобы человек мог исправиться.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG-парсер
От: WolfHound  
Дата: 18.03.10 17:20
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Ты о том, что он забыл о случаях отката или о низкой производительности?

Я об алгоритмической сложности...

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

VD>Думаю, что надо объяснять.
Там получается квадратичная сложность ибо добавление элемента в конец списка приводит к полному перестроению списка.
Я уже молчу про то что сам подход со списком концептуально не верен ибо не позволяет в одной грамматике держать правила возвращающие разные типы.

VD>Как минимум для того чтобы исправить ошибку.

Чтобы ее исправить нужно переделать все что сделал товарищь чуть менее чем полностью.

VD>Ну, это конечно проблема, но легко решаемая. Лучше проблемы с форматированием и качеством кода нежели отсутствие любых продвижений вперед на протяжении двух с половиной месяцев.

Это не подвижки. Это трата времени.

VD>Лучше бы помог ему. Твои знания сейчас очень нужны.

Помогать делать этот парсер я не буду. Ибо задавать грамматику в виде:
    any                    = ['\u0000'..'\uFFFF'];
    digit                  = ['0'..'9']+;
    spaces                 = ' '*;
    
    num             : int = digit + spaces;
    unaryMinus      : int = '-' spaces simplExpr;
    parenthesesExpr : int = '(' spaces sumOrSub ')' spaces;
    simplExpr       : int = num / parenthesesExpr / unaryMinus;
    mulOrDiv        : int = simplExpr (('*' / '/') spaces simplExpr)*;
    sumOrSub        : int = mulOrDiv  (('+' / '-') spaces mulOrDiv )*;
    start           : int = spaces sumOrSub !any;

тот еще геморой.
Более того парсер без поддержки левой рекурсии и расширения грамматики для разбора самого немерла бесполезен чуть менее полностью.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: PEG-парсер
От: para  
Дата: 18.03.10 18:38
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Если ты посмотришь код ты ты поймешь какую ерунду он там понаписал.

WH>Вот например:
WH>
WH>            def l = _capturedTokens;
WH>            _capturedTokens = [];
            
WH>            def newPos = { $(compile(rule)) };    
          
WH>            if(newPos < 0)
WH>            {      
WH>              _capturedTokens = l;     
WH>            }
WH>            else
WH>            {
WH>              def t = $(tokenExpr);                
              
WH>              _capturedTokens = l + [t];     
WH>            }     
WH>            newPos
WH>

неужели было на много лучше?
if (pos < 0)
  $(CapturesName : dyn).RemoveRange(captureId, $(CapturesName : dyn).Count - captureId); //SCG.List[]

если Вы так крут, то расскажите пожалуйста как сделать это правильно?
добавлять в начало списка?
Re[3]: PEG-парсер
От: para  
Дата: 18.03.10 18:44
Оценка:
Здравствуйте, VladD2, Вы писали:

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


есть ли смысл для каждого простого правила создавать отдельный метод
 
    | ("simplExpr", [Token.NonTerminalToken as se])  => 
          se.ComputedValue

автоматически их генерить не получится потому что может быть такой же вариант, внешне похожий
    | ("unaryMinus", [_, _, Token.NonTerminalToken as se])      =>
         se.ComputedValue * -1

или это продиктовано тоже производительностью?
Re[4]: PEG-парсер
От: para  
Дата: 18.03.10 18:45
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Сам код тоже весьма неряшлив особенно если включить режим View White Space


поправлю
Re[4]: PEG-парсер
От: para  
Дата: 18.03.10 18:49
Оценка:
Здравствуйте, WolfHound, Вы писали:
WH>
WH>            def l = _capturedTokens;
WH>            _capturedTokens = [];
            
WH>            def newPos = { $(compile(rule)) };    
          
WH>            if(newPos < 0)
WH>            {      
WH>              _capturedTokens = l;     
WH>            }
WH>            else
WH>            {
WH>              def t = $(tokenExpr);                
              
WH>              _capturedTokens = l + [t];     
WH>            }     
WH>            newPos
WH>

со временем, дойдут руки — сделаю _capturedTokens — возвращаемым значением, а не полем
Re[3]: PEG-парсер
От: para  
Дата: 18.03.10 18:59
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>Супер! Молодец!
спасибо)

VD>3. Добавить возможность расширения парсера.


как видится технология расширения парсеров?
и или комбинирования, (где-то говорилось)?

возможно ли этим макросом создать парсер описания грамматики этой нотации?
либо какой либо другой нотации, если WolfHound предложит?
Re[6]: PEG-парсер
От: para  
Дата: 18.03.10 19:22
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Я уже молчу про то что сам подход со списком концептуально не верен ибо не позволяет в одной грамматике держать правила возвращающие разные типы.


да, такой недостаток есть. я его не рассматривал как use-case. поправлю)
ксатати, где поспотреть пример грамматики с разными типами возвращаемых значений правил?

WH>Это не подвижки. Это трата времени.


поясню: для меня это в том числе обучение, (или может даже во-первых)

VD>>Лучше бы помог ему. Твои знания сейчас очень нужны.

WH>Помогать делать этот парсер я не буду. Ибо задавать грамматику в виде:
WH>
WH>    any                    = ['\u0000'..'\uFFFF'];
WH>    digit                  = ['0'..'9']+;
WH>    spaces                 = ' '*;
    
WH>    num             : int = digit + spaces;
WH>    unaryMinus      : int = '-' spaces simplExpr;
WH>    parenthesesExpr : int = '(' spaces sumOrSub ')' spaces;
WH>    simplExpr       : int = num / parenthesesExpr / unaryMinus;
WH>    mulOrDiv        : int = simplExpr (('*' / '/') spaces simplExpr)*;
WH>    sumOrSub        : int = mulOrDiv  (('+' / '-') spaces mulOrDiv )*;
WH>    start           : int = spaces sumOrSub !any;
WH>

WH>тот еще геморой.

какую бы Вы рекомендовали нотацию? тип парсера?
Re[5]: PEG-парсер
От: WolfHound  
Дата: 18.03.10 19:24
Оценка:
Здравствуйте, para, Вы писали:

P>неужели было на много лучше?

P>
P>if (pos < 0)
P>  $(CapturesName : dyn).RemoveRange(captureId, $(CapturesName : dyn).Count - captureId); //SCG.List[]
P>

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

Если не веришь в то что твой код имеет квадратичную сложность запусти вот этот тест и убедись сам:
      mutable suffix = "+1";
      for (mutable n = 1; n < 8; ++n)
      {
        suffix += suffix;
      }
      mutable text = "0";
      for (mutable n = 1; n < 20; ++n)
      {
        text += suffix;
        WriteLine($"text length is:$(text.Length)");
        def timer = Diagnostics.Stopwatch.StartNew();
        def calc = CalcParser(text);
        def pos = calc.ParsedSymbolsCount;
        def res = calc.Result;
        timer.Stop();
        WriteLine($"$pos Parse took $(timer.Elapsed)    $(Math.Sqrt(timer.Elapsed.TotalMilliseconds) / text.Length)");
        WriteLine($"result is: $res");
        WriteLine();
       }


P>если Вы так крут,

Ой какие мы обидчивые.

P>то расскажите пожалуйста как сделать это правильно?

P>добавлять в начало списка?
Выкинуть список. Совсем.
Единственно верный вариант это завести локальные переменные прямо в генерируемом коде для заинлайненых правил, а для тех правил что нельзя инлайнить нужно возвращать данные через ref параметер функции(кортежи они конечно красивее но тормозят).
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[6]: PEG-парсер
От: para  
Дата: 18.03.10 19:38
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Этот вариант не страдает квадратичной сложностью и в отличии от твоего создает почти нулевую нагрузку на сборщик мусора.

WH>Но и этот вариант соверенно не пригоден для реальной работы.
ок. спасибо.

WH>Ой какие мы обидчивые.

Мы, Николай II, не обижаемся))

WH>Выкинуть список. Совсем.

WH>Единственно верный вариант это завести локальные переменные прямо в генерируемом коде для заинлайненых правил, а для тех правил что нельзя инлайнить нужно возвращать данные через ref параметер функции(кортежи они конечно красивее но тормозят).

на выходе цикла(*) может быть произвольное количество токенов. именно по-этому я накапливаю токены в список, а затем вызываю обработчик.
как тут избавиться от списка?
Re[6]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 21:40
Оценка:
Здравствуйте, WolfHound, Вы писали:

VD>>Ты о том, что он забыл о случаях отката или о низкой производительности?

WH>Я об алгоритмической сложности...

Это меньшая из имеющихся проблем. Человек скорее всего просто не понимает к чему приводит подобный код.
Проблема решается за пять минут простой заменой list[T] на SCG.List[T].

На мой взгляд тут большей проблемой является то, что вообще есть список. Лучше бы хранить нужные данные в стековых переменных. Это позволило бы избавиться сразу от двух проблем: 1) невозможности иметь разные типы возвращаемых значений правил, 2) необходимость добавлять и удалять значения из списка (а значит перевыделять память).

Думаю, что в конечном итоге мы избавимся от списка вообще. Просто всему свое время.

WH>Там получается квадратичная сложность ибо добавление элемента в конец списка приводит к полному перестроению списка.


Согласен. Но объяснять все стоит, так как не все знают все детали.

WH>Я уже молчу про то что сам подход со списком концептуально не верен ибо не позволяет в одной грамматике держать правила возвращающие разные типы.


Дык это твой подход, как я понимаю. В любом случая — исправим. Главное чтобы было что править.

VD>>Как минимум для того чтобы исправить ошибку.

WH>Чтобы ее исправить нужно переделать все что сделал товарищь чуть менее чем полностью.

Ну, это ты со зла говоришь.

VD>>Ну, это конечно проблема, но легко решаемая. Лучше проблемы с форматированием и качеством кода нежели отсутствие любых продвижений вперед на протяжении двух с половиной месяцев.

WH>Это не подвижки. Это трата времени.

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

WH>Более того парсер без поддержки левой рекурсии и расширения грамматики для разбора самого немерла бесполезен чуть менее полностью.


Не, ну вперед. Создавай брэнч и далай в нем все что твоей душе угодно. Через месяц другой сравним результаты.

Уверен, что просто ничего не будет.

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

Прямую левую рекурсию нужно просто переписывать. Косвенную — запрещать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 21:45
Оценка:
Здравствуйте, para, Вы писали:

P>да, такой недостаток есть. я его не рассматривал как use-case. поправлю)

P>ксатати, где поспотреть пример грамматики с разными типами возвращаемых значений правил?

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

P>поясню: для меня это в том числе обучение, (или может даже во-первых)


Не бери в голову. Все в порядке.

P>какую бы Вы рекомендовали нотацию? тип парсера?


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

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

P>есть ли смысл для каждого простого правила создавать отдельный метод

P>
 
P>    | ("simplExpr", [Token.NonTerminalToken as se])  => 
P>          se.ComputedValue
P>


Для каждого — нет. Если правило только возвращает значение (транзитное), то такой метод можно подразумевать.

P>автоматически их генерить не получится потому что может быть такой же вариант, внешне похожий

P>
P>    | ("unaryMinus", [_, _, Token.NonTerminalToken as se])      =>
P>         se.ComputedValue * -1
P>


Начнем с того что достаточно "- se.ComputedValue".

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

P>как видится технология расширения парсеров?

P>и или комбинирования, (где-то говорилось)?

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

Общая идея такая. Правила состоящие из приоритетного выбора, т.е. вида "a / b / c" можно расширять путем добавления правил в начало, в конец или вместо одного из подправил.
Это сделать относительно просто. Но для полноценного расширения еще требуется управлять приоритетами (аналогично примеру грамматики выражений где "*" и "/" имели более высокий приоритет нежели "+" и "-".

P>возможно ли этим макросом создать парсер описания грамматики этой нотации?


Не понял вопроса.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: PEG-парсер
От: WolfHound  
Дата: 18.03.10 22:50
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Дык это твой подход, как я понимаю. В любом случая — исправим. Главное чтобы было что править.

Это не мой подход. То что сделал я было чисто посмотреть какие там индексы получаются.

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

VD>Прямую левую рекурсию нужно просто переписывать. Косвенную — запрещать.
Ага, конечно.
Без этого не будет работать расширяемость парсера. Вообще не будет. Тут есть только один вариант: Катахдин сделаный правильно.
Более того если делать совсем без мемоизации то есть далеко не нулевые шансы на некоторых грамматиках свалиться в экспоненту.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[7]: PEG-парсер
От: WolfHound  
Дата: 18.03.10 22:50
Оценка: +1
Здравствуйте, para, Вы писали:

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

P>как тут избавиться от списка?
Тут никак. Но во-первых ты загоняешь в этот список все, во-вторых даже для * немерловый список не вариант ибо дает большую нагрузку на GC и как я уже показал в твоем случае квадратичную сложность.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[7]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 23:05
Оценка:
Здравствуйте, para, Вы писали:

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

P>как тут избавиться от списка?

Смотри, все очень просто. Токенов нет (с) Матрица. Наш токен — это не более чем информация о начале и конце диапазона разбираемой строки.

Далее у нас есть правила (для которых мы должны вызвать метод-обработчик) и подправила — то из чего состоят правила. Подправила так же могут состоять из подправил.

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

У нас есть несколько стратегий:
1. Если подправило является ссылкой на другое правило и это другое правило возвращает значение (тип которого описан после двоеточия за именем правила), то нужно использовать возвращаемое значение другого правила как значение параметра метода-обработчика для соответствующего подправила.
2. Если мы можем протащить значение возвращаемые под-под-правилами, то нужно использовать в качестве параметров их.
3. Если нам не удается получить значение подправил, то мы используем для описания параметра тип Token который всего лишь позволяет получить подстроку сопоставленную с подправилами.

Все промежуточные значений (как полученные от правил, так и токены) можно хранить на стеке. Это так же полезно тем, что в случае откатов нам не придется беспокоиться их удалении. Для циклов (* и +) нужно использовать список. Но не обязательно list[T]. Это может быть SCG.List[T].
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 23:07
Оценка:
Здравствуйте, para, Вы писали:

P>со временем, дойдут руки — сделаю _capturedTokens — возвращаемым значением, а не полем


Имеет смысл не откладывать этот процесс долгий ящик. Для ускорения работы можно сделать его не возвращаемым значением, а ref-параметром. Но это уже оптимизация, так что ее можно отложить на потом.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 23:28
Оценка:
Здравствуйте, WolfHound, Вы писали:

VD>>Дык это твой подход, как я понимаю. В любом случая — исправим. Главное чтобы было что править.

WH>Это не мой подход. То что сделал я было чисто посмотреть какие там индексы получаются.

Дык. В комментариях ты ведь этого не написал?
Человек видел то, что видел. Он уже заменил АСТ на что-то более подходящее. Это, можно так сказать, процесс эволюции и познания. Со временем разберется и сделает все как надо.

Для накапливания результатов цикла по любому нужно использовать тот или иной вид списка. Возможно в итоге это даже будет IEnumerable[T]. Но что-то будет по любому.

VD>>Прямую левую рекурсию нужно просто переписывать. Косвенную — запрещать.

WH>Без этого не будет работать расширяемость парсера. Вообще не будет.

Будет, еще как будет.
И вообще, как-то это не конструктивно необоснованными заявлениями бросаться. Утверждаешь — обосновывай. Чем помешает расширяемости парсера отсутствие левой рекурсии?

WH>Тут есть только один вариант: Катахдин сделаный правильно.


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

WH>Более того если делать совсем без мемоизации то есть далеко не нулевые шансы на некоторых грамматиках свалиться в экспоненту.


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

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

В общем, я бы спокойно пережил без тотальных решений всех проблем. Сначала нужно получить хоть, что-то. Опробывать это что-то на практике и потом, если нужно, дорабатывать/перерабатывать, но уже с учетом полученных знаний. Это научный подход. А максимализм "или все или ничего" приведет только к одному — ничему.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 19.03.10 15:14
Оценка:
Здравствуйте, para, Вы писали:

Я немного причешу код. Не забудь обновиться и не делай пока изменений.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG-парсер
От: para  
Дата: 19.03.10 18:15
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Я немного причешу код. Не забудь обновиться и не делай пока изменений.


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

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

на следующей неделе сделаю))

меня только одно смущает:
private unaryMinus(_ : Token[int].TerminalToken, _ : Token[int].TerminalToken, se : Token[int].NonTerminalToken) : int
{
  -se.ComputedValue
}

какие-то названия типов слишком длинные получились. Хотя в них важен и параметр дженирика, потому-что как говорилось, правила могут возвращать разные значения важно различие терминальный-нетерминальный
наверное надо сократить названия типов?
private unaryMinus(_ : Token[int].Terminal, _ : Token[int].Terminal, se : Token[int].NonTerminal) : int
{
  -se.ComputedValue
}

ещё можно предложить макросу параметры отсечения ненужных параметров правил, это заодно положительно должно сказаться на производительности парсера:
[CapturesOnly(simplExpr)]
private unaryMinus(se : Token[int].NonTerminal) : int
{
  -se.ComputedValue
}

как-то так?

что-то мне часто приходится делать списки с заполнением, путём добавления элементов в конец.
я неправильно проектирую алгоритм?, или тут надо использовать какой-то другой тип контейнера?
scg.List мне что-то не очень нравися. может какой-нибудь двусвязный список?
Re[6]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 19.03.10 19:50
Оценка:
Здравствуйте, para, Вы писали:

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


VD>>Я немного причешу код. Не забудь обновиться и не делай пока изменений.


P>я днём добавил изменения которые позволяют вызывать отдельные методы-обработчики напрямую.

P>основной код на эту тему в здесь

Понял.

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


ОК.

P>меня только одно смущает:...какие-то названия типов слишком длинные получились.


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

P>ещё можно предложить макросу параметры отсечения ненужных параметров правил, это заодно положительно должно сказаться на производительности парсера


+1

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

P>я неправильно проектирую алгоритм?, или тут надо использовать какой-то другой тип контейнера?

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

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

P>scg.List мне что-то не очень нравися. может какой-нибудь двусвязный список?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 19.03.10 19:50
Оценка:
Здравствуйте, para, Вы писали:

Да... Пока не правь код, чтобы не пересечся с моими правками.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: PEG-парсер
От: para  
Дата: 19.03.10 20:38
Оценка: 39 (1)
VD>Пока что я не очень понимаю логику в соответствии с которой ты формируешь список токенов для вызова метода-обработчика. Было бы замечательно, если бы ты описал алгоритм словами. (в форуме)

тогда рассажу свои изменения с начала.
1. добавил тип правила Rule.CaptureNamedTerminalSymbolтут — оно отвечает за обнаружение терминальных токенов (те, которые не возвращают значения, имеют только строки)
2. добавил соответствующую логику их создания здесь
3. добавил преобразование скрытых терминальных правил (не имеют имени, но стоят в правой части терминального правила и имеют смысловую нагрузку только в виде строки) — максимальное сочетание правил выбора, последовательности и т.д., которое не включает вызов нетерминальных правил, но обобщает правила Rule.Char.
4. доработал оптимизатор грамматики для поддержки нового правила

5. Компилятор правил
:
Добавил поддержку нового правила и обобщил с Rule.Capture
поскольку компиляция правил происходит рекурсивно, то на каждом уровне происходит следующее:
в глобальной переменной _captures, содержится список токенов, которые обработчики этого уровня должны вернуть
но чтобы рассчитать значение на текущем уровне, надо знать список токенов, полученных с предыдущего уровня
поэтому сохраняем список, который надо вернуть, глобальную переменную обнуляем и запускаем компиляцию всех элементов нижнего уровня.
каждый из этих элементов добавляет в глобальный список по токену.
используем полученный список, чтобы рассчитать значение в текущем правиле на текущем уровне.
восстанавливаем список, в котором находятся результаты других правил на этом же уровне.
добавляем в этот список полученный результат.
возвращаем управление правилу верхнего уровня.
Разница правил Capture и CaptureNamedTerminalSymbol, состоит в том что первое добавляет в список нетерминальные символы, а второе — терминальные

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

определение метода происходит на основе анализа грамматики
имя метода-имя правила список необходимых параметров-токенов и их тип раскручивется по вложенным правилам
и подставляются из списка _captures
...
этот кусок допишу, если надо.
ЗЫ: гугл отрубился, поэтому ссылки проставить не смог.
Re[8]: PEG-парсер
От: para  
Дата: 20.03.10 12:08
Оценка:
Здравствуйте, para, Вы писали:
немного неправильно сформулировал
P> поскольку компиляция правил происходит рекурсивно, то на каждом уровне происходит следующее:

я имел в виду "разбор правил парсером происходит рекурсивно"
Re[8]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 00:53
Оценка:
Здравствуйте, para, Вы писали:

Я прошелся по проекту парсера, сделал рефакторинг и заменил список на генерацию локальных переменных (хранящих токены). Погляди изменения (diff-ом).

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

Первое что нужно понимать — список (list[T]) обладает как преимуществами, так и недостатками.
Его преимущества:
1. Линейная скорость добавления элементов в начало.
2. Неизменяемость (любое изменение списка порождает копию).
3. Инкрементальность изменений (если элементы добавляются в начало, новый список включает в себя все элементы строго).
4. Возможность анализа с помощью паттен-матчинга.
5. Позволяет эффективно перебирать элементы с начала к концу.

Именно списки используются для представления последовательностей выражений в квази-цитатах.

Недостатки списка:
1. Добавление каждого элемента создает новый объект (размещаемый в куче).
2. Склеивание списков приводит к тому что первый список полностью копируется.
3. Не эффективен перебор элементов в обратном порядке (от конца к началу).
4. Не эффективен индексный доступ.

Теперь о конкатенации списков.
Такая необходимость может возникнуть оправданно и не оправдано. У тебя в коде в большинстве случаев она возникает неоправданно. В прочем, оправданность этого весьма условна. Ведь почти всегда можно обойтись без конкатинации (если правильно составить алгоритм).
Так вот в твоем случае основной проблемой является то, что ты пытаешься работать со списком не верными (императивными, можно сказать) методами.
Запомни на будущее – цикл для обработки списков приемлем только для перебора элементов. Для формирования или изменения списков циклы лучше не применять. Это почти всегда указывает на ошибку в выборе алгоритмов.
Лучшим способом обработки списков является применение функций высшего порядка (таких как Map, Filter, Find, Fold и функций Linq).
Если требуется индексный доступ, то лучше выбрать массив или List[T]. При этом надо понимать, что конвертация чего-то в массив приемлема не всегда. Надо стараться делать это реже. Возможно лучше просто выбрать другую структуру данных для хранения информации.
Ну, и если уж список формируется императивно, то нужно учитывать то, что элементы добавляются в начало. Зачастую лучше сформировать список задом наперед и потом развернуть его.

Другие ошибки

1. Не надо оставлять мертвый код. Не стоит скрывать код комментариями или забивать на предупреждения. Код который не используется в системе нужно удалять. Если есть подозрение, что он может понадобиться позднее, то нужно или взять его позднее из SVN, или (если его не было в SVN-е) поместить код в некий катлог на своей машине (как вариант послать себе же по почте).
2. Полные пути внутри кода. Это плохо, так как с одной стороны приводит к распуханию кода, а с другой по списку юсингов нельзя понять, какие зависимости есть у данного файла.
3. Форматирование и отступы. Погляди как я его изменил и придерживайся тех же принципов.
4. Лишние скобки (как фигурные, так и круглые). Принцип должен быть одним. Если без скобок можно, то нужно обойтись без них. Опять же см. изменения в коде. Например, не стоит брать в скобки сплайс в квази-цитате, если в нем есть только одна переменная и за ней не идет символ или подчеркивание. Так же не нужно оборачивать в скобки тела циклов и тела вхождений оператора match.
5. Мало внимания уделяемого отладке. Первое что программист должен делать – это прощать свой труд. Отладка в процессе разработки занимает очень большую (если не бОльшую) часть времени. Стало быть нужно делать так, чтобы во время отладки было как можно больше информации. В первую очередь нужно переопределять метод ToString у объектов (особенно тех, что создаются в больших объемах и являются значениями для алгоритма). В нашем случае нам нужно определить ToString для токенов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 01:30
Оценка:
Здравствуйте, para, Вы писали:

Текущие задачи у нас такие:
1. Токен нужно оформить двумя структурами. Одной для терминального токена, другой токена не терминального (хранящего значение). При этом первая структура должна быть обычной (не дженерик), а вторая дженерик. Кроме этого мы должны допускать использования в одном парсере не терминальные токены с разными параметрами типов (хранящие значения разных типов).
2. Структуры описывающие токены нужно вынести в отдельную библиотеку (не макросную). В эту же библиотеку нужно вынести все остальные типы и функции требуемые парсеру в рантайме. Макро-библиотеку нужно подключить к проекту через макро-референс (чтобы предотвратить дальнейшее "засасывание" типов из макро-проекта в проекты прасера.
3. Реализовать обработку ошибок. Это нужно сделать максимально эффективно! Надо подумать как это можно сделать. Возможно надо генерировать два парсера. Один скоростной, а второй запускаемый повторно, специально для выявления ошибок. А может быть получится обойтись незначительными проверками, и соответственно, выявлять их при первом проходе.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 01:51
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Текущие задачи у нас такие:...


4. Еще надо автоматом формировать код для транзитных обработчиков вроде parenthesesExpr и simplExpr.

5. Надо сделать возможным парсить разные строки (и подстроки) одним экземпляром парсера:
* Долой свойства!
* Создаем публичные методы позволяющие вызвать любое правило в любой позиции.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: PEG-парсер
От: Аноним  
Дата: 22.03.10 17:21
Оценка:
Здравствуйте, VladD2, Вы писали:

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


VD>Текущие задачи у нас такие:

VD>1. Токен нужно оформить двумя структурами. Одной для терминального токена, другой токена не терминального (хранящего значение). При этом первая структура должна быть обычной (не дженерик), а вторая дженерик. Кроме этого мы должны допускать использования в одном парсере не терминальные токены с разными параметрами типов (хранящие значения разных типов).
сделал два класса. двумя струкутрами так не получилось потому что у них нет наследования. знаю, что структура эффективнее чем класс. как лучше сделать? заврапить?

VD>2. Структуры описывающие токены нужно вынести в отдельную библиотеку (не макросную). В эту же библиотеку нужно вынести все остальные типы и функции требуемые парсеру в рантайме. Макро-библиотеку нужно подключить к проекту через макро-референс (чтобы предотвратить дальнейшее "засасывание" типов из макро-проекта в проекты прасера.

токен исполmзует локейшн, который содержится в nemerle.compilier.dll
Re[10]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 18:20
Оценка:
Здравствуйте, Аноним, Вы писали:

А>сделал два класса. двумя струкутрами так не получилось потому что у них нет наследования.


А зачем нам нужно наследование? Оно нам не нужно.

У нас четко разделяются просто токены и токены содержащие значения. Я же и говорил "создать две структуры".

А>знаю, что структура эффективнее чем класс. как лучше сделать? заврапить?


Лучше сделать две структуры. Типа:
[Record]
struct Token
{
  public  Start : int;
  public  End   : int;
  private _text : string;
  private GetString() { ... }
}

[Record]
struct Data[T]
{
  public  Start : int;
  public  End   : int;
  public  T     : Value;    
  private _text : string;
  private GetString() { ... }
}

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

А>токен исполmзует локейшн, который содержится в nemerle.compilier.dll


Давай как пока что выкинем их. Потом прикрутим в виде методов-расширений или еще как-то.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 18:36
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Лучше сделать две структуры. Типа:

VD>
VD>struct Token
...
VD>struct Data[T]
VD>


Кстати, названия лучше выбрать именно такими (короткими), чтобы не замусаривать описание методов-обработчиков.

По поводу второй структуры можно подумать. Например, ее можно назвать TokenEx, или Value, или ValueToken (последнее уже длинновато).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 19:19
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Особенно если учесть то что оно не правильно использовано...


Погляди на современное состояние дел в парсере. Может какие-то идеи или замечания возникнут.
Я там заменил использование списка на использование переменных.

Кроме того я открыл новую тему
Автор: VladD2
Дата: 22.03.10
. Посвященную развитию PEG-парсера. Если даже те не будешь развивать проект, то по крайней мере помоги обдумать детали дальнейшего развития.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 19:21
Оценка:
Здравствуйте, para, Вы писали:

Я открыл новую тему
Автор: VladD2
Дата: 22.03.10
посвященную обсуждению развитию PEG-парсера. Предлагаю перенести туда все что связано с идеологическими вопросами. Данная тема разжирела. Искать что либо в ней становится все сложнее.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 22.03.10 19:44
Оценка:
Здравствуйте, para, Вы писали:

В общем, преобразовал токены в структуры. Обновись...
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG-парсер
От: para  
Дата: 24.03.10 13:15
Оценка:
Сделал text параметром, а не полем.
Заинлайнил CheckPos, GetChar.
ускорение в 2 раза))
Re[2]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.03.10 16:49
Оценка:
Здравствуйте, para, Вы писали:

P>Сделал text параметром, а не полем.


Отлично!

Но нужно сделать еще более радикальный шаг. Для каждого правила для которого есть обработчик (генерируется метод в парсере) нужно создать публичный метод-обертку которая бы имело сигнатуру:
public RuleName(source : string, startPosition : int = 0) : option[T]
{
  mutable resulr Nemerle.Peg.VToken[int];

  if (__GENERATED_PEG__RULE__RuleName__(startPosition, ref result))
    Some(resulr)
  else
    None()
}

Где T — это тип возвращаемого значения описанный в правиле (после двоеточия).

P>Заинлайнил CheckPos, GetChar.


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

P>ускорение в 2 раза))


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

Попробуй провести эксперимент и объявить их в проекте парсера. Потом скомпилируй проект в релиз и запусти из командной строки (интеграция глючит и запускает дебажную версию).




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

P>Сделал text параметром, а не полем.

P>Заинлайнил CheckPos, GetChar.
P>ускорение в 2 раза))

Сори послал предыдущее письмо не дописал.

Я добавил в проект Parsers еще один класс парсера — CsParser.n. При компиляции он выдает ошибку, так как в сгенерированном коде имеются обращения к несуществующим переменным. Так как для этих правил нет обработчико, то эти переменные генерировать не надо.

Исправь эту ошибку и сделай так чтобы NToken генерировался только там где он действительно нужен (т.е. когда он требуется правилу идущему выше по дереву грамматики).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 24.03.10 20:40
Оценка:
Здравствуйте, VladD2, Вы писали:

P>>Заинлайнил CheckPos, GetChar.


VD>А вот это плохое решение. Эти функции были введены для того чтобы была возможность абстрагировать парсер от источника данных.


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

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

http://rsdn.ru/forum/nemerle/3748141.1.aspx
Автор: VladD2
Дата: 24.03.10
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: para  
Дата: 25.03.10 05:59
Оценка:
Здравствуйте, VladD2, Вы писали:

Ок. Буду думать...

ЗЫ: К сожалению с работы не получается постить длинные сообщения, а дома забываю
Re[4]: PEG-парсер
От: para  
Дата: 25.03.10 06:05
Оценка: +1 :)
Здравствуйте, VladD2, Вы писали:

плюс, если у нас нет члена класса, то что тогда было бы абстрагировать?...(риторически)
Re[3]: PEG-парсер
От: para  
Дата: 25.03.10 06:17
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Я добавил в проект Parsers еще один класс парсера — CsParser.n.

не нашёл файл))
Re[3]: PEG-парсер
От: para  
Дата: 25.03.10 07:12
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Но нужно сделать еще более радикальный шаг. Для каждого правила для которого есть обработчик (генерируется метод в парсере) нужно создать публичный метод-обертку которая бы имело сигнатуру:

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

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

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


VD>>Я добавил в проект Parsers еще один класс парсера — CsParser.n.

P>не нашёл файл))

Это я похоже лажанулся.

Исправился. Обновись.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 25.03.10 17:12
Оценка:
Здравствуйте, para, Вы писали:

P>как быть с заинлайнеными на этапе оптимизации грамматики правилами?

P>например, отдельного метода для правила "num" не генерируется по этой причине.

P>предполагаемое решение:

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

Не много не понял, но если это сработает, то действуй!

Надеюсь это не приведет к тому, что пропадет инлайнинг?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG-парсер
От: WolfHound  
Дата: 26.03.10 20:06
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Я добавил в проект Parsers еще один класс парсера — CsParser.n. При компиляции он выдает ошибку, так как в сгенерированном коде имеются обращения к несуществующим переменным. Так как для этих правил нет обработчико, то эти переменные генерировать не надо.

Вот это не правильно
newLine                   = "\r\n" / '\n' / '\r' / '\u2028' / '\u2029' / '\u0085';
singleLineComment         = "//" (!('\n' / '\r') any)* newLine?; // newLine необезательный так как комментарий может находиться в конце файла

правильно так:
newLine                   = "\r\n" / '\n' / '\r' / '\u2028' / '\u2029' / '\u0085' / !any;
singleLineComment         = "//" (!newLine any)* newLine;
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 26.03.10 23:09
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Вот это не правильно

WH>правильно так:
WH>
WH>newLine                   = "\r\n" / '\n' / '\r' / '\u2028' / '\u2029' / '\u0085' / !any;
WH>singleLineComment         = "//" (!newLine any)* newLine;
WH>


Собственно первые проблемы выявленные при опытной эксплуатации:
1. Из-за тотального инлайнинга правила повторяются по много раз, что приводит к сильному разбуханию кода. Игрушечная грамматика порождает кода почти на 200 Кб.
2. Код получается весьма не оптимален. Взять к примеру "(!newLine any)*". Во первых отрицание здесь совершенно лишнее. Намного лучше было бы иметь оператор вычитания позволяющий получить отрицание некоторого Rule.Chars:
notNewLine  = any - newLine

3. Далее, any не требует никаких проверок. Любой символ, если он есть может быть сопоставлен с диапазаоном ['\0' .. '\uFFFF'], но у нас генерируется бредовый код проверки.
4. Правило !newLine any нужно вообще воспринимать как паттерн и генерировать для него специализированный код. Собственно для любых предикатов имеет смысл генерировать специализированный код, так как иначе получается дополнительная проверка инвертирующая результат.
5. Оптимизации... Мне кажется, что самыми действенными оптимизациями будут:
* Генерация match-а для Sequence. Чтобы вместо последовательного входа в каждое правило проходилась проверка того какие правила могут быть достигнуты для текущего символа. Особенно это актуально для терминальных правил (в терминологии para). Скажем для newLine. И вообще правила вроде newLine нужно реализовывать на match-е. Глупо ведь перебирать все варианты засерая пространство тоннами временных переменных и проверок в то время когда вопрос решается одной простой командой?
* Выборочная мемоизация. Уже понятно, что мемоизация бесполезна для большинства случаев. Нужно понять, можем ли мы как-то выявлять правила которые требуется мемоизировать или нужно вводить специальное расширение синтаксиса?
* Собственно реализация мемоизации. Не факт, что использование хэш-таблицы — это лучший выбор. Возможно будет лучше использовать некую специализированную структуру данных.

6. Ну, и вопросы расширяемости (статической и динамической) остаются так же не обдуманными. Для динамики наверно достаточно вставлять вызов метода который будет это делать. Статическое расширение тоже нужно. Но не ясно как его лучше выразить синтаксически.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG-парсер
От: WolfHound  
Дата: 27.03.10 12:06
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>1. Из-за тотального инлайнинга правила повторяются по много раз, что приводит к сильному разбуханию кода. Игрушечная грамматика порождает кода почти на 200 Кб.

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

VD>2. Код получается весьма не оптимален. Взять к примеру "(!newLine any)*". Во первых отрицание здесь совершенно лишнее. Намного лучше было бы иметь оператор вычитания позволяющий получить отрицание некоторого Rule.Chars:

VD>
VD>notNewLine  = any - newLine
VD>

1)Это уже работает. См оптимизатор
        | Rule.Not(Rule.Chars([chars1])) :: Rule.Chars([chars2]) :: rules =>
          catChars(Rule.Chars([chars2.Sub(chars1)]) :: rules);

2)В данном случае не все так просто ибо newLine содержит "\r\n" и !any.

VD>3. Далее, any не требует никаких проверок. Любой символ, если он есть может быть сопоставлен с диапазаоном ['\0' .. '\uFFFF'], но у нас генерируется бредовый код проверки.

Вставь в кодогенератор проверку. Делов то на несколько строк кода.

VD>4. Правило !newLine any нужно вообще воспринимать как паттерн и генерировать для него специализированный код. Собственно для любых предикатов имеет смысл генерировать специализированный код, так как иначе получается дополнительная проверка инвертирующая результат.

Тут можно отптимизировать только через конечные автоматы.
Если все сделать правильно то вот этот код раскрутится в конечный автомат полностью
newLine                   = "\r\n" / '\n' / '\r' / '\u2028' / '\u2029' / '\u0085' / !any;
singleLineComment         = "//" (!newLine any)* newLine;

Кстати тут проблема. Ибо конечные автоматы на немерле естественней всего генерировать через взаиморекурсивные локальные функции.
Проблема в том что немерле их в конечный автомат не раскручивает.

VD>5. Оптимизации... Мне кажется, что самыми действенными оптимизациями будут:

хъ
VD>6. Ну, и вопросы расширяемости (статической и динамической) остаются так же не обдуманными. Для динамики наверно достаточно вставлять вызов метода который будет это делать. Статическое расширение тоже нужно. Но не ясно как его лучше выразить синтаксически.
Для этого придется пределовать все чуть менее чем полностью. По этому я этим парсером и не занимаюсь.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[6]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.03.10 13:20
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Первое что нужно попробовать инлайнить только правила для которых нет обработчиков.

WH>Думаю эта эвристика даст наилучший баланс.

Это почти делается. Нужно что-то большее.

WH>1)Это уже работает. См оптимизатор

WH>
WH>        | Rule.Not(Rule.Chars([chars1])) :: Rule.Chars([chars2]) :: rules =>
WH>          catChars(Rule.Chars([chars2.Sub(chars1)]) :: rules);
WH>


Что-то на практике в генерируемом коде этого незаметно. В генерируемом коде идет честная реализация правила внутри предиката, далее его инверсия и далее следущее правило с any. В итоге получается совсем не эффективный код.

WH>2)В данном случае не все так просто ибо newLine содержит "\r\n" и !any.


Это как раз не проблема. Вычитать, конечно, нужно не newLine, а '\n' и '\r', т.е. код должен быть таким:
notNewLine         = any - '\n' - '\r'
singleLineComment  = "//" notNewLine* newLine;


VD>>3. Далее, any не требует никаких проверок. Любой символ, если он есть может быть сопоставлен с диапазаоном ['\0' .. '\uFFFF'], но у нас генерируется бредовый код проверки.

WH>Вставь в кодогенератор проверку. Делов то на несколько строк кода.

Для тебя на несколько минут. Для меня — несколько часов. Было бы лучше если это вставил бы ты. А я тем временем продолжил бы переносить грамматику C# в PEG.

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

VD>>4. Правило !newLine any нужно вообще воспринимать как паттерн и генерировать для него специализированный код. Собственно для любых предикатов имеет смысл генерировать специализированный код, так как иначе получается дополнительная проверка инвертирующая результат.

WH>Тут можно отптимизировать только через конечные автоматы.
WH>Если все сделать правильно то вот этот код раскрутится в конечный автомат полностью
WH>
WH>newLine                   = "\r\n" / '\n' / '\r' / '\u2028' / '\u2029' / '\u0085' / !any;
WH>singleLineComment         = "//" (!newLine any)* newLine;
WH>


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

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

Алгоритм построения ДКА включает две функции FIRST(u) и FOLLOW(A). Так вот нам нужна только FIRST(u). По ней уже можно будет создать match который уберет оверхэд.

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

WH>Кстати тут проблема. Ибо конечные автоматы на немерле естественней всего генерировать через взаиморекурсивные локальные функции.

WH>Проблема в том что немерле их в конечный автомат не раскручивает.

Последнюю фразу я не понял, но взаиморекурсивные фукнции не поддерживают устранение хвостовой рекурсии (наверно ты об этом, так как функции есть функции, они к КА никаким боком), так что их применять нельзя.
Но есть два классических способа реализации КА:
1. На базе swith-ей (т.е. match) в нашем случае.
2. На базе таблиц переходов.

Теоретически, лучший вариант это использование match-ей. Но в Немерле match к сожалению не превращается в MSIL-swith. Так что нужно будет докручивать генератор кода для получения максимальной эффективности.

Собственно задача имеет интеллектуальную сложность. Боюсь para с ней не справится. Давай ка ты возьмешь ее на себя. Она как раз для тебя! А то ты обещал помочь, но не помогаешь совсем. А это будет очень полезной помощью!

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

WH>Для этого придется пределовать все чуть менее чем полностью. По этому я этим парсером и не занимаюсь.

Это пустопорожний треп. Если ты видишь какие-то конструкционные недостатки, то будь добр описать свое видение.
А просто так бросаться громкими заявлениями не надо.
Лично я не вижу каких-то практических проблем с расширяемостью. Точки расширения есть. Их можно вставлять в нужных местах (в начале или конце приоритетных выборов — Choice-ов).
Со статическим расширением вообще нет никаких проблем, так как всегда можно объединить описания из разных источников. Вопрос только в том, как это лучше оформить синтаксически?

Позволю себе напомнить, что данная реализация не является тем, что будет являться основой парсера Nemerle 2.0. Это пока что макрос который является полигоном для исследования идей которые в последствии будут использованы для создания парсера Nemerle 2.0. Так что не стоит предъявлять к данному макросу уж очень строгие требования. У нас другая задача — получить достоверные и максимально полные сведения о возможностях и недостатках применения PEG на практике, а так же получить мощный макрос который можно будет с успехом использовать уже сейчас!
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: PEG-парсер
От: WolfHound  
Дата: 27.03.10 14:49
Оценка: 129 (1)
Здравствуйте, VladD2, Вы писали:

VD>Это почти делается. Нужно что-то большее.

Почти или уже? Это может дать очень большую разницу.

VD>Что-то на практике в генерируемом коде этого незаметно. В генерируемом коде идет честная реализация правила внутри предиката, далее его инверсия и далее следущее правило с any. В итоге получается совсем не эффективный код.

За то в нем заметно что кое кто навставлял капчурей куда попало. По этому и не работает.

VD>Для тебя на несколько минут. Для меня — несколько часов. Было бы лучше если это вставил бы ты. А я тем временем продолжил бы переносить грамматику C# в PEG.

Держи.

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

Нет. Не нахожу.

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

Если ты сам знаешь что делать то что ты ко мне то пристаешь?

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

Их нельзя применять только по тому что немерле не устраняет хвостовую рекурсию взаиморекурсивных функций.

Представь что функция это состояние.
Вызов функции это переход в другое состояние.
Если хвостовая рекурсия оптимизирована то хвостовой вызов это goto.
Получаем еще один классический вариант генерации ДКА.
Кстати работающий быстрее тех двух что ты перечислил.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[8]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.03.10 17:04
Оценка:
Здравствуйте, WolfHound, Вы писали:

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


VD>>Это почти делается. Нужно что-то большее.

WH>Почти или уже? Это может дать очень большую разницу.

Это лучше уточнить у par-а. Скажем для грамматики калькулятора у нас получаются следующие функции:
private __GENERATED_PEG__RULE__mulOrDiv__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
private __GENERATED_PEG__RULE__parenthesesExpr__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
private __GENERATED_PEG__RULE__simplExpr__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
private __GENERATED_PEG__RULE__start__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
private __GENERATED_PEG__RULE__sumOrSub__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
private __GENERATED_PEG__RULE__unaryMinus__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int

из следующих обработчиков:
    private num(digit : NToken, _ : NToken) : int
    private unaryMinus(_ : NToken, _ : NToken, se : VToken[int]) : int
    private parenthesesExpr(_ : NToken, _ : NToken, se : VToken[int], _ : NToken, _ : NToken) : int
    private simplExpr(se : VToken[int]) : int
    private start(_ : NToken, se : VToken[int], _ : NToken) : int
    private mulOrDiv(se : VToken[int], lst : List[NToken * NToken * VToken[int]]) : int
    private sumOrSub(se : VToken[int], lst : List[NToken * NToken * VToken[int]]) : int

то есть не генерируется только метод для обработчика num. Он идет инлайном.

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

VD>>Что-то на практике в генерируемом коде этого незаметно. В генерируемом коде идет честная реализация правила внутри предиката, далее его инверсия и далее следущее правило с any. В итоге получается совсем не эффективный код.

WH>За то в нем заметно что кое кто навставлял капчурей куда попало. По этому и не работает.

Это из-за этого не делаются оптимизации?
Ну, так объяснил бы этому кому-то в чем он не прав и как лучше делать.
А еще лучше просто поправь код, так чтобы он был корректным.
Кстати, а зачем он их вообще вставлял? Ведь была какая-то причина?

VD>>Для тебя на несколько минут. Для меня — несколько часов. Было бы лучше если это вставил бы ты. А я тем временем продолжил бы переносить грамматику C# в PEG.

WH>Держи.

Вот! Другое дело! Огромное человеческое спасибо тебе!

Но все равно код сейчас получается весьма уродливым. Вот во что превращается банальная инструкция "!any":
            if (pos >= 0) 
            {
              _  = "Not (sl:0): !Term[any](['\\0'.. char.MaxValue])";
              def newPos = 
              {
                _  = "CaptureNamedTerminalSymbol (sl:0): Term[any](['\\0'.. char.MaxValue])";
                def newPos = 
                {
                  _  = "Chars (sl:0): ['\\0'.. char.MaxValue]";
                  if (pos < text.Length) pos + 1; else -1
                };
                ();
                newPos
              };
              if (newPos < 0) pos; else -1

И это все вместо банального:
pos >= text.Length

Жуть да и только!

Сдается мне, что даже если убрать лишние CaptureNamedTerminalSymbol, все равно код не станет таким как хочется. Нужны специализированные оптимизации.

Кстати, все же что с ними делать? Как я понял он ввел их чтобы формировать токены для параметров методов-обработчиков. Но похоже их и правда намного больше чем нужно.

Наверно нужно устранять лишние CaptureNamedTerminalSymbol еще в оптимизаторе?
Или можно как-то извернуться и генерировать только нужные CaptureNamedTerminalSymbol?
Я тут что-то недопетриваю.

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

WH>Если ты сам знаешь что делать то что ты ко мне то пристаешь?

Я с тобой обсуждаю проблему. Знать чужие мысли на проблему всегда полезно. У тебя может быть взгляд, у меня другой. В итоге может получиться некое другое решение.

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

WH>Их нельзя применять только по тому что немерле не устраняет хвостовую рекурсию взаиморекурсивных функций.

Ясно.

WH>Представь что функция это состояние.

WH>Вызов функции это переход в другое состояние.
WH>Если хвостовая рекурсия оптимизирована то хвостовой вызов это goto.
WH>Получаем еще один классический вариант генерации ДКА.
WH>Кстати работающий быстрее тех двух что ты перечислил.

swith — это тоже goto в итоге. Так что быстрее не получится. По любому любая реализация ДКА (даже только для проверки первого символа — FIRST() без FOLLOW()) значительно ускорит парсер и (скорее всего) сократит его код.

Устранение же хвостовой рекурсии для групп функций связанно с какими-то проблемами. Об этом в свое время Москаль писал. Боюсь, что на это можно потратить много времени и ничего не получить. Проще позволить в генерируемом коде использовать явные goto.

В прочем, можно генерировать код в виде TExpr в котором есть:
    | Label                 { id : int; body : TExpr; }
    | Goto                  { target : int; mutable try_block : int; }

но так, конечно, будет значительно сложнее работать.

ЗЫ

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

Задача интересная. Хотя, конечно, согласен, что она весьма сложная и может занять много времени. Тебе наверно опять в лом будет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.03.10 19:10
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Вот это не правильно

WH>
WH>newLine                   = "\r\n" / '\n' / '\r' / '\u2028' / '\u2029' / '\u0085';
WH>singleLineComment         = "//" (!('\n' / '\r') any)* newLine?; // newLine необезательный так как комментарий может находиться в конце файла
WH>

WH>правильно так:
WH>
WH>newLine                   = "\r\n" / '\n' / '\r' / '\u2028' / '\u2029' / '\u0085' / !any;
WH>singleLineComment         = "//" (!newLine any)* newLine;
WH>


Попробовал... Твой вариант не работает. Так как newLine используется в правиле spaces, а правило spaces является необязательным (может разбирать пустую строку, так как содержим в себе цикл "*"), то это правило зацикливается. Дойдя до конца строки правило newLine (и стало быть spaces) всегда (в цикле).

В следующий раз прежде чем советовать проверяй свои предположения. Я на отладку минут 20 убил.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: PEG-парсер
От: para  
Дата: 27.03.10 19:11
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Это лучше уточнить у par-а. Скажем для грамматики калькулятора у нас получаются следующие функции:

VD>
VD>private __GENERATED_PEG__RULE__mulOrDiv__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
VD>private __GENERATED_PEG__RULE__parenthesesExpr__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
VD>private __GENERATED_PEG__RULE__simplExpr__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
VD>private __GENERATED_PEG__RULE__start__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
VD>private __GENERATED_PEG__RULE__sumOrSub__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
VD>private __GENERATED_PEG__RULE__unaryMinus__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int
VD>

VD>из следующих обработчиков:
VD>
VD>    private num(digit : NToken, _ : NToken) : int
VD>    private unaryMinus(_ : NToken, _ : NToken, se : VToken[int]) : int
VD>    private parenthesesExpr(_ : NToken, _ : NToken, se : VToken[int], _ : NToken, _ : NToken) : int
VD>    private simplExpr(se : VToken[int]) : int
VD>    private start(_ : NToken, se : VToken[int], _ : NToken) : int
VD>    private mulOrDiv(se : VToken[int], lst : List[NToken * NToken * VToken[int]]) : int
VD>    private sumOrSub(se : VToken[int], lst : List[NToken * NToken * VToken[int]]) : int
VD>

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

это происходит в оптимизаторе грамматики. я там практически ничего не менял.

WH>>За то в нем заметно что кое кто навставлял капчурей куда попало. По этому и не работает.

VD>Кстати, а зачем он их вообще вставлял? Ведь была какая-то причина?

поясню :чтобы в методе
private mulOrDiv(se : VToken[int], lst : List[NToken * NToken * VToken[int]]) : int

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

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

естественно, я понимаю, что так слишком просто и много и планировал это улучшать, о чём написал, в частности здесь

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

сейчас пришла ещё одна мысль: можно ли в макросе узнать что параметр метода имеет имя "_" и не используется?
private num(digit : NToken, _ : NToken) : int

по всей видимости возможно. тогда это возможно использовать для автоматической оптимизации

пока это мысли, естественно обсуждение приветствуется
я собираюсь постепенно воплощать эти и другие фичи
Re[10]: PEG-парсер
От: WolfHound  
Дата: 27.03.10 19:34
Оценка:
Здравствуйте, para, Вы писали:

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

Лучше разясни откуда их тут столько?
Function: private __GENERATED_PEG__RULE__simplExpr__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int;

    _  = "Capture (sl:-1): NTerm[simplExpr](NTerm[num](Term[digit](['0'..'9']+) Term[spaces]([' ']*)) / parenthesesExpr / unaryMinus)";


Внутри предикатов им вообще делать нечего.
    _  = "Capture (sl:-1): NTerm[start](Term[spaces]([' ']*) sumOrSub !Term[any](['\\0'.. char.MaxValue]))";


P>я планировал ввести параметры макроса, в которых описывать какие терминальные символы нужны, а какие нет.

А чем тебя не устраивает указание типов в грамматике?

P>я собираюсь постепенно воплощать эти и другие фичи

Главное что тебе нужно сделать это избавится от всех mutable в коде.
Ибо эту императивщину ни понять ни запомнить.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[6]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.03.10 21:12
Оценка:
Здравствуйте, WolfHound, Вы писали:

VD>>2. Код получается весьма не оптимален. Взять к примеру "(!newLine any)*". Во первых отрицание здесь совершенно лишнее. Намного лучше было бы иметь оператор вычитания позволяющий получить отрицание некоторого Rule.Chars:

VD>>
VD>>notNewLine  = any - newLine
VD>>

WH>1)Это уже работает. См оптимизатор
WH>
WH>        | Rule.Not(Rule.Chars([chars1])) :: Rule.Chars([chars2]) :: rules =>
WH>          catChars(Rule.Chars([chars2.Sub(chars1)]) :: rules);
WH>


Как оказалось все таки не работает. Я устранил лишние терминальные капчуры, но код все же получается вот такой:
              _  = "Not (sl:0): !['\\0'.. char.MaxValue]";
              def newPos = 
              {
                _  = "Chars (sl:0): ['\\0'.. char.MaxValue]";
                if (pos < text.Length) pos + 1; else -1
              };
              if (newPos < 0) pos; else -1
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: PEG-парсер
От: WolfHound  
Дата: 27.03.10 21:44
Оценка:
Здравствуйте, VladD2, Вы писали:

WH>>1)Это уже работает. См оптимизатор

WH>>
WH>>        | Rule.Not(Rule.Chars([chars1])) :: Rule.Chars([chars2]) :: rules =>
WH>>          catChars(Rule.Chars([chars2.Sub(chars1)]) :: rules);
WH>>


VD>Как оказалось все таки не работает. Я устранил лишние терминальные капчуры, но код все же получается вот такой:

Разумеется все предикаты оно не устранит.
Но там где можно оно работает.

_ = "Capture (sl:-1): NTerm[start](Term[spaces]((['\\t', ' '] / [['\\r', '\\n']] / ['\\n', '\\r', '\\u0085', '\u2028'..'\u2029'] / [['/', '/']] ['\\0'..'\\t', '\\u000B'..'\\u000C', '\\u000E'.. char.MaxValue]* ([['\\r', '\\n']] / ['\\n', '\\r', '\\u0085', '\u2028'..'\u2029'])? / [['/', '*']] (![['*', '/']] ['\\0'.. char.MaxValue])* [['*', '/']] / ['\\u000B'..'\\u000C'])*) NTerm[identifier](Term[identifierValue](['@']? ['A'..'Z', '_', 'a'..'z', 'А'..'я'] ['0'..'9', 'A'..'Z', '_', 'a'..'z', 'А'..'я']*) Term[spaces]((['\\t', ' '] / [['\\r', '\\n']] / ['\\n', '\\r', '\\u0085', '\u2028'..'\u2029'] / [['/', '/']] ['\\0'..'\\t', '\\u000B'..'\\u000C', '\\u000E'.. char.MaxValue]* ([['\\r', '\\n']] / ['\\n', '\\r', '\\u0085', '\u2028'..'\u2029'])? / [['/', '*']] (![['*', '/']] ['\\0'.. char.MaxValue])* [['*', '/']] / ['\\u000B'..'\\u000C'])*)) !['\\0'.. char.MaxValue])";

Вот конкретно однострочный комментарий

[['/', '/']] ['\\0'..'\\t', '\\u000B'..'\\u000C', '\\u000E'.. char.MaxValue]* ([['\\r', '\\n']] / ['\\n', '\\r', '\\u0085', '\u2028'..'\u2029'])?

Как видишь тут из any вычли \n и \r.

А вот код в который оно генерируется.
                                def pos = 
                                {
                                  _  = "RepeatMin (sl:1): ['\\0'..'\\t', '\\u000B'..'\\u000C', '\\u000E'.. char.MaxValue]*";
                                  ();
                                  def rep [] (pos : int)  
                                  {
                                    def newPos = 
                                    {
                                      _  = "Chars (sl:2): ['\\0'..'\\t', '\\u000B'..'\\u000C', '\\u000E'.. char.MaxValue]";
                                      if (pos < text.Length) 
                                      {
                                        c = text[pos];
                                        if ('\0' <= c && c <= '\t' || '\v' <= c && c <= '\f' || '\u000E <= c && c <= 'char.MaxValue') pos + 1; else -1
                                      }; else -1
                                    };
                                    if (newPos >= 0) 
                                    {
                                      ();
                                      rep(newPos)
                                    }; else pos
                                  } : _ ;
                                  rep(pos)


Ща я его заоптимизирую.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[10]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.03.10 21:54
Оценка:
Здравствуйте, para, Вы писали:

WH>>>За то в нем заметно что кое кто навставлял капчурей куда попало. По этому и не работает.

VD>>Кстати, а зачем он их вообще вставлял? Ведь была какая-то причина?

P>поясню :чтобы в методе

P>
P>private mulOrDiv(se : VToken[int], lst : List[NToken * NToken * VToken[int]]) : int
P>

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

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


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

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

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

P>я планировал ввести параметры макроса, в которых описывать какие терминальные символы нужны, а какие нет.


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

P>сейчас пришла ещё одна мысль: можно ли в макросе узнать что параметр метода имеет имя "_" и не используется?


Можно. Но ты дела капчуры сверх меры.

Кстати, капчуры для выражений вложенных в Not() так же не нужны. От них тоже нужно избавиться.

P>
P>private num(digit : NToken, _ : NToken) : int
P>

P>по всей видимости возможно. тогда это возможно использовать для автоматической оптимизации

Надо еще не забывать о проверке ошибок. А то эта оптимизация выйдет боком. Если параметр не используется, то это как-то нужно декларировать.

P>я собираюсь постепенно воплощать эти и другие фичи


Давай. Мы тоже потихонечку будем дорабатывать это дело. Вот сегодня пару оптимизаций внесли. За одно устранили лишние капчуры. Но это лучше их не создавать.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: PEG-парсер
От: WolfHound  
Дата: 27.03.10 22:23
Оценка: 129 (1)
Здравствуйте, VladD2, Вы писали:

VD>Как оказалось все таки не работает. Я устранил лишние терминальные капчуры, но код все же получается вот такой:

Теперь перед генерацией условия проверяется что будет если инвертировать RangeSet.
И если после инвертирования получется меньше проверок то используется инвертированный вариант.
        _  = "Chars (sl:2): ['\\0'..'\\t', '\\u000B'..'\\u000C', '\\u000E'.. char.MaxValue]";
        if (pos < text.Length) 
        {
            c = text[pos];
            if (!c == '\n' || c == '\r') pos + 1; else -1
        }; else -1

Только печать подвела.
Должно быть так if (!(c == '\n' || c == '\r')) pos + 1; else -1
Кстати печать вообще плохо работает. Локейшены не адекватны чуть более чем полностью.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[8]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.03.10 23:23
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Теперь перед генерацией условия проверяется что будет если инвертировать RangeSet.

WH>И если после инвертирования получется меньше проверок то используется инвертированный вариант.
WH>
WH>        _  = "Chars (sl:2): ['\\0'..'\\t', '\\u000B'..'\\u000C', '\\u000E'.. char.MaxValue]";
WH>        if (pos < text.Length) 
WH>        {
WH>            c = text[pos];
WH>            if (!c == '\n' || c == '\r') pos + 1; else -1
WH>        }; else -1
WH>


Супре! Теперь почти так же как написал бы человек!

WH>Только печать подвела.

WH>Должно быть так if (!(c == '\n' || c == '\r')) pos + 1; else -1

Это баг в ПретиПринте компилятора?

WH>Кстати печать вообще плохо работает. Локейшены не адекватны чуть более чем полностью.


Обнови код компилятора.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[11]: PEG-парсер
От: para  
Дата: 28.03.10 07:20
Оценка:
Здравствуйте, WolfHound, Вы писали:

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


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

WH>Лучше разясни откуда их тут столько?
WH>
WH>Function: private __GENERATED_PEG__RULE__simplExpr__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int;

WH>    _  = "Capture (sl:-1): NTerm[simplExpr](NTerm[num](Term[digit](['0'..'9']+) Term[spaces]([' ']*)) / parenthesesExpr / unaryMinus)";
WH>

их тут два: Term[digit] Term[spaces] и разделены они для того, чтобы отличить мухи от котлет.
да их можно было бы передавать одним термом и внутри метода-обработчика делать трим. а как тогда делать для более сложных правил? например Term[digit]+Term[comment] если они сольются, тогда придётся заново парсить эту строку в методе-обработчике, что былобы неразумно imho.
разумно сделать так:
Function: private __GENERATED_PEG__RULE__simplExpr__(pos : int, result : ref Nemerle.Peg.VToken[int], text : string) : int;

    _  = "Capture (sl:-1): NTerm[simplExpr](NTerm[num](Term[digit](['0'..'9']+) ([' ']*)) / parenthesesExpr / unaryMinus)";

для этого надо тем или иным образом, определить, какие термы нужны, а какие нет

WH>Внутри предикатов им вообще делать нечего.

WH>
WH>    _  = "Capture (sl:-1): NTerm[start](Term[spaces]([' ']*) sumOrSub !Term[any](['\\0'.. char.MaxValue]))";
WH>

если это нужно, я сделаю
    _  = "Capture (sl:-1): NTerm[start](Term[spaces]([' ']*) sumOrSub !(['\\0'.. char.MaxValue]))";

аналогично для предиката &
как: в грамматике если подправило предиката(! или &) CaptureNamedTerminalSimbol(name, rule), заменю его на rule

CaptureNamedTerminalSimbol я сделал по тому, что мне кажется такой способ очевидным и необходимым, для того чтобы парсер вообще заработал. да получилось неоптимально и избыточно, но я не вижу препятствий убрать эту избыточность
главное определить где оно нужно, а где нет. и в некоторых местах это действительно нужно
(Term[digit](['0'..'9']+)
(Term[unnamed_terminal_rule_xxx]('+' / '-'))

WH>Главное что тебе нужно сделать это избавится от всех mutable в коде.

WH>Ибо эту императивщину ни понять ни запомнить.
Хорошо.
Спасибо за советы.

ЗЫ: не капли не обижусь, если вы назовёте мои идеи (про код понятно) отстоем, но в этом случае мне действительно интересно, как правильно (с системной точки зрения) решить ту либо иную подзадачу.
Re[11]: PEG-парсер
От: para  
Дата: 28.03.10 07:49
Оценка:
Здравствуйте, VladD2, Вы писали:

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


да мой косяк здесь
        else if(id.ToString() != string.Empty)
          Rule.CaptureNamedTerminalSymbol(id.ToString(), rule);

добавлю проверки: не внутри капчура или предиката
для именованных исправлю

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

я это учитывал:
    private CanBeSplited(rule : Rule) : bool
    {
      | Chars                       => true
      | CaptureNamedTerminalSymbol  
      | Capture                     
      | Call                        => false

т.е. внутри капчура и вызова, неименованные термы не ищутся.

P>>я планировал ввести параметры макроса, в которых описывать какие терминальные символы нужны, а какие нет.

VD>Вот это как-то очень сложно. Нужны только те терминалы, что передаются в параметры методов обработчиков. Никаких дополнительных описаний не нужно.

я это и имею в виду.
вопрос в том, в каком виде макросу дать понять какие термы нужны, с точки зрения использования макроса
например, как обозначить что
    //в обрабочике
    
    private mulOrDiv(se : VToken[int], lst : List[NToken * NToken * VToken[int]]) : int
    
    //на саммом деле нужно

    private mulOrDiv(se : VToken[int], lst : List[NToken * VToken[int]]) : int

    //где первый элемент кортежа в списке это Term[unnamed_terminal_rule_xxx]('/' / '*')
Re[12]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.03.10 11:12
Оценка:
Здравствуйте, para, Вы писали:

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

P>например, как обозначить что
P>
P>    //в обрабочике
    
P>    private mulOrDiv(se : VToken[int], lst : List[NToken * NToken * VToken[int]]) : int
    
P>    //на саммом деле нужно

P>    private mulOrDiv(se : VToken[int], lst : List[NToken * VToken[int]]) : int

P>    //где первый элемент кортежа в списке это Term[unnamed_terminal_rule_xxx]('/' / '*')
P>


Нужно сформировать описание сигнатуры и сравнить ее с сигнатурой метода-обработчика. Если они не совпадают нужно выдать сообщение об ошибке в котором сказать: "Неверная сигнатура метода-обработчика 'mulOrDiv'. Требуется сигнатура mulOrDiv(secondExpr : VToken[int], loop : List[NToken /* '+' / '_' */ * VToken[int] /* secondExpr */]) : int". При этом в сообщении должен быть задан локешон этого скамого метода обработчика.
Тогда программист использующих макрос сможет понять в чем он был не прав и исправить ошибку. За одно он сможет использовать текст из сообщения об ошибки для формирования каркаса метода-обработчика (методом копи-пэст).

Если программист хочет игнорировать какие-то правила в конкретном обработчике, то можно попробовать ввести дополнительную аннотацию. Скажем не нужные правила он может перечислять в мета-атрибуте, или просто давать им вместо имени "_" (что делается и сейчас). Проблема только в том, что при этом придется описывать тип параметра, так как боюсь что Немерле не позволит опускать его у параметров. В прочем, можно подкрутить компилятор так чтобы он позволял это делать, а проверял наличие типов у методов на более поздних стадиях.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 29.03.10 10:06
Оценка:
Здравствуйте, para, Вы писали:

Я изменил конфигурацию проектов.

1. Вынес парсеры в отдельные проекты. CsParser в проект CSharpParser. CalcParser в проект Calculator. Это dll-проекты по этому напрямую их запускать нельзя. Для отладки я настроил для них запуск nunit-console.exe.

2. Проекты Test и Parser я удалил.

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