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


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

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


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

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

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

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

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

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

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

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


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

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


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

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

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

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

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

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

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

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


Не понял вопроса.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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].
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: PEG-парсер
От: VladD2 Российская Империя www.nemerle.org
Дата: 18.03.10 23:07
Оценка:
Здравствуйте, para, Вы писали:

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


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

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

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

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

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

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

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

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

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


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

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


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

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

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

Я немного причешу код. Не забудь обновиться и не делай пока изменений.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.