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#-код!
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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. Не могу ни разу обещать, что займусь, т.к. грамматическим разбором начал интересоваться совсем недавно, а потому туп в этом деле как пробка. Но чем чёрт не шутит...


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

В общем, пока более опытные товарищи борются с ленью и старыми проблемами можно внести свое имя в аналы истории и очень существенно помочь проекту. Макрос и правда очень интересный и вызовет, на мой взгляд, серьезный интерес.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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-грамматике. Это даст нам возможность опробовать нужные идеи и в дальнейшем или расширить его до нужных кондиций, или написать новую версию учитывающую полученный опыт.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>Естественно, не буду заливать пока, чтоб кому-нибудь не сбить мысль...


Ну, учитывая что пока что статус у проекта "никто толком не взялся", то можешь и заливать. Особых проблем возникнуть не должно.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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-ый символ распознанной области (или исключение)
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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).

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

В прочем, все это опять же детали. Важно само наличие возможности получения информации о токене.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>Все что для этого нужно два инта.

По два параметра на один токен? Нафиг такую оптимизацию.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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, ...)
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>Зачем по два? В чем проблема упаковать их в структуру?

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

В прочем, можно передавать ее по ссылке.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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() (с разным набором параметров: строка, строка и виртуальная начальная позиция и т.п.).
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>мне такое положение дел пока тоже кажется не самым лучшим, но я хотел бы отложить решение проблемы вида интерфейса на потом, когда я там получше разбирусь...


ОК
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.