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>не нашёл файл))

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

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

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

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

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

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

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

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

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

ЗЫ

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

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


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


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

ЗЫ: не капли не обижусь, если вы назовёте мои идеи (про код понятно) отстоем, но в этом случае мне действительно интересно, как правильно (с системной точки зрения) решить ту либо иную подзадачу.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.