Здравствуйте, VladD2, Вы писали:
VD>Я немного причешу код. Не забудь обновиться и не делай пока изменений.
я днём добавил изменения которые позволяют вызывать отдельные методы-обработчики напрямую.
основной код на эту тему в здесь
там довольно сумбурно, но когда сделаю, как говорилось выше [уменьшение использования списков и отказ от дженирика в базовом классе, а затем и от самого базового класса], то этот код в месте со всем сумбуром сильно сократится, это так сказать пробная, но необходимая итерация разработки, перед передачей параметров напрямую, а не через список. (необходимая, потому что сначала надо чтобы было куда эти параметры передавать.) сократится код, потому что не будет параметров в списке и не надо будет анализировать этот список.
на следующей неделе сделаю))
меня только одно смущает:
private unaryMinus(_ : Token[int].TerminalToken, _ : Token[int].TerminalToken, se : Token[int].NonTerminalToken) : int
{
-se.ComputedValue
}
какие-то названия типов слишком длинные получились. Хотя в них важен и параметр дженирика, потому-что как говорилось, правила могут возвращать разные значения важно различие терминальный-нетерминальный
наверное надо сократить названия типов?
private unaryMinus(_ : Token[int].Terminal, _ : Token[int].Terminal, se : Token[int].NonTerminal) : int
{
-se.ComputedValue
}
ещё можно предложить макросу параметры отсечения ненужных параметров правил, это заодно положительно должно сказаться на производительности парсера:
[CapturesOnly(simplExpr)]
private unaryMinus(se : Token[int].NonTerminal) : int
{
-se.ComputedValue
}
как-то так?
что-то мне часто приходится делать списки с заполнением, путём добавления элементов в конец.
я неправильно проектирую алгоритм?, или тут надо использовать какой-то другой тип контейнера?
scg.List мне что-то не очень нравися. может какой-нибудь двусвязный список?
Здравствуйте, para, Вы писали:
P>Здравствуйте, VladD2, Вы писали:
VD>>Я немного причешу код. Не забудь обновиться и не делай пока изменений.
P>я днём добавил изменения которые позволяют вызывать отдельные методы-обработчики напрямую. P>основной код на эту тему в здесь
Понял.
P>там довольно сумбурно, но когда сделаю, как говорилось выше [уменьшение использования списков и отказ от дженирика в базовом классе, а затем и от самого базового класса], то этот код в месте со всем сумбуром сильно сократится, это так сказать пробная, но необходимая итерация разработки, перед передачей параметров напрямую, а не через список.
ОК.
P>меня только одно смущает:...какие-то названия типов слишком длинные получились.
Названия — это то что меня интересует меньше всего. К тому же поверь моему попыту, чем ближе код будет к финальной стадии, тем меньше проблем будет оставаться. Думаю, что сегодняшнее положение дел с типами тоже не окончательное. В конечном варианте типы должны стать более контертынми, что приведет к тому, что их имена не будут мешать.
P>ещё можно предложить макросу параметры отсечения ненужных параметров правил, это заодно положительно должно сказаться на производительности парсера
+1
P>что-то мне часто приходится делать списки с заполнением, путём добавления элементов в конец. P>я неправильно проектирую алгоритм?, или тут надо использовать какой-то другой тип контейнера?
У меня сейчас есть немного времени. Я посижу с твоим кодом и постараюсь его во-первых, отрефакторить, а во-вторых, возможно, постараюсь выбрасить списки где это можно или заменить их на более правильные типы. Ну, а ты потом поглядешь на результат. Если будет не ясно могу прокоментировать свои действия.
Пока что я не очень понимаю логику в соответствии с которой ты формируешь список токенов для вызова метода-обработчика. Было бы замечательно, если бы ты описал алгоритм словами. (в форуме)
P>scg.List мне что-то не очень нравися. может какой-нибудь двусвязный список?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>Пока что я не очень понимаю логику в соответствии с которой ты формируешь список токенов для вызова метода-обработчика. Было бы замечательно, если бы ты описал алгоритм словами. (в форуме)
тогда рассажу свои изменения с начала.
1. добавил тип правила Rule.CaptureNamedTerminalSymbolтут — оно отвечает за обнаружение терминальных токенов (те, которые не возвращают значения, имеют только строки)
2. добавил соответствующую логику их создания здесь
3. добавил преобразование скрытых терминальных правил (не имеют имени, но стоят в правой части терминального правила и имеют смысловую нагрузку только в виде строки) — максимальное сочетание правил выбора, последовательности и т.д., которое не включает вызов нетерминальных правил, но обобщает правила Rule.Char.
4. доработал оптимизатор грамматики для поддержки нового правила
5. Компилятор правил :
Добавил поддержку нового правила и обобщил с Rule.Capture
поскольку компиляция правил происходит рекурсивно, то на каждом уровне происходит следующее:
в глобальной переменной _captures, содержится список токенов, которые обработчики этого уровня должны вернуть
но чтобы рассчитать значение на текущем уровне, надо знать список токенов, полученных с предыдущего уровня
поэтому сохраняем список, который надо вернуть, глобальную переменную обнуляем и запускаем компиляцию всех элементов нижнего уровня.
каждый из этих элементов добавляет в глобальный список по токену.
используем полученный список, чтобы рассчитать значение в текущем правиле на текущем уровне.
восстанавливаем список, в котором находятся результаты других правил на этом же уровне.
добавляем в этот список полученный результат.
возвращаем управление правилу верхнего уровня.
Разница правил Capture и CaptureNamedTerminalSymbol, состоит в том что первое добавляет в список нетерминальные символы, а второе — терминальные
тут же для нетерминальных правил подставляется метод, который будет рассчитывать результат этого правила.
определение нужного метода происходит
определение метода происходит на основе анализа грамматики
имя метода-имя правила список необходимых параметров-токенов и их тип раскручивется по вложенным правилам
и подставляются из списка _captures
...
этот кусок допишу, если надо.
ЗЫ: гугл отрубился, поэтому ссылки проставить не смог.
Здравствуйте, para, Вы писали:
немного неправильно сформулировал P> поскольку компиляция правил происходит рекурсивно, то на каждом уровне происходит следующее:
я имел в виду "разбор правил парсером происходит рекурсивно"
Я прошелся по проекту парсера, сделал рефакторинг и заменил список на генерацию локальных переменных (хранящих токены). Погляди изменения (diff-ом).
Теперь что касается структур данных, алгоритмов и скорости.
Первое что нужно понимать — список (list[T]) обладает как преимуществами, так и недостатками.
Его преимущества:
1. Линейная скорость добавления элементов в начало.
2. Неизменяемость (любое изменение списка порождает копию).
3. Инкрементальность изменений (если элементы добавляются в начало, новый список включает в себя все элементы строго).
4. Возможность анализа с помощью паттен-матчинга.
5. Позволяет эффективно перебирать элементы с начала к концу.
Именно списки используются для представления последовательностей выражений в квази-цитатах.
Недостатки списка:
1. Добавление каждого элемента создает новый объект (размещаемый в куче).
2. Склеивание списков приводит к тому что первый список полностью копируется.
3. Не эффективен перебор элементов в обратном порядке (от конца к началу).
4. Не эффективен индексный доступ.
Теперь о конкатенации списков.
Такая необходимость может возникнуть оправданно и не оправдано. У тебя в коде в большинстве случаев она возникает неоправданно. В прочем, оправданность этого весьма условна. Ведь почти всегда можно обойтись без конкатинации (если правильно составить алгоритм).
Так вот в твоем случае основной проблемой является то, что ты пытаешься работать со списком не верными (императивными, можно сказать) методами.
Запомни на будущее – цикл для обработки списков приемлем только для перебора элементов. Для формирования или изменения списков циклы лучше не применять. Это почти всегда указывает на ошибку в выборе алгоритмов.
Лучшим способом обработки списков является применение функций высшего порядка (таких как Map, Filter, Find, Fold и функций Linq).
Если требуется индексный доступ, то лучше выбрать массив или List[T]. При этом надо понимать, что конвертация чего-то в массив приемлема не всегда. Надо стараться делать это реже. Возможно лучше просто выбрать другую структуру данных для хранения информации.
Ну, и если уж список формируется императивно, то нужно учитывать то, что элементы добавляются в начало. Зачастую лучше сформировать список задом наперед и потом развернуть его.
Другие ошибки
1. Не надо оставлять мертвый код. Не стоит скрывать код комментариями или забивать на предупреждения. Код который не используется в системе нужно удалять. Если есть подозрение, что он может понадобиться позднее, то нужно или взять его позднее из SVN, или (если его не было в SVN-е) поместить код в некий катлог на своей машине (как вариант послать себе же по почте).
2. Полные пути внутри кода. Это плохо, так как с одной стороны приводит к распуханию кода, а с другой по списку юсингов нельзя понять, какие зависимости есть у данного файла.
3. Форматирование и отступы. Погляди как я его изменил и придерживайся тех же принципов.
4. Лишние скобки (как фигурные, так и круглые). Принцип должен быть одним. Если без скобок можно, то нужно обойтись без них. Опять же см. изменения в коде. Например, не стоит брать в скобки сплайс в квази-цитате, если в нем есть только одна переменная и за ней не идет символ или подчеркивание. Так же не нужно оборачивать в скобки тела циклов и тела вхождений оператора match.
5. Мало внимания уделяемого отладке. Первое что программист должен делать – это прощать свой труд. Отладка в процессе разработки занимает очень большую (если не бОльшую) часть времени. Стало быть нужно делать так, чтобы во время отладки было как можно больше информации. В первую очередь нужно переопределять метод ToString у объектов (особенно тех, что создаются в больших объемах и являются значениями для алгоритма). В нашем случае нам нужно определить ToString для токенов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Текущие задачи у нас такие:
1. Токен нужно оформить двумя структурами. Одной для терминального токена, другой токена не терминального (хранящего значение). При этом первая структура должна быть обычной (не дженерик), а вторая дженерик. Кроме этого мы должны допускать использования в одном парсере не терминальные токены с разными параметрами типов (хранящие значения разных типов).
2. Структуры описывающие токены нужно вынести в отдельную библиотеку (не макросную). В эту же библиотеку нужно вынести все остальные типы и функции требуемые парсеру в рантайме. Макро-библиотеку нужно подключить к проекту через макро-референс (чтобы предотвратить дальнейшее "засасывание" типов из макро-проекта в проекты прасера.
3. Реализовать обработку ошибок. Это нужно сделать максимально эффективно! Надо подумать как это можно сделать. Возможно надо генерировать два парсера. Один скоростной, а второй запускаемый повторно, специально для выявления ошибок. А может быть получится обойтись незначительными проверками, и соответственно, выявлять их при первом проходе.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Текущие задачи у нас такие:...
4. Еще надо автоматом формировать код для транзитных обработчиков вроде parenthesesExpr и simplExpr.
5. Надо сделать возможным парсить разные строки (и подстроки) одним экземпляром парсера:
* Долой свойства!
* Создаем публичные методы позволяющие вызвать любое правило в любой позиции.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: PEG-парсер
От:
Аноним
Дата:
22.03.10 17:21
Оценка:
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, para, Вы писали:
VD>Текущие задачи у нас такие: VD>1. Токен нужно оформить двумя структурами. Одной для терминального токена, другой токена не терминального (хранящего значение). При этом первая структура должна быть обычной (не дженерик), а вторая дженерик. Кроме этого мы должны допускать использования в одном парсере не терминальные токены с разными параметрами типов (хранящие значения разных типов).
сделал два класса. двумя струкутрами так не получилось потому что у них нет наследования. знаю, что структура эффективнее чем класс. как лучше сделать? заврапить?
VD>2. Структуры описывающие токены нужно вынести в отдельную библиотеку (не макросную). В эту же библиотеку нужно вынести все остальные типы и функции требуемые парсеру в рантайме. Макро-библиотеку нужно подключить к проекту через макро-референс (чтобы предотвратить дальнейшее "засасывание" типов из макро-проекта в проекты прасера.
токен исполmзует локейшн, который содержится в nemerle.compilier.dll
Здравствуйте, Аноним, Вы писали:
А>сделал два класса. двумя струкутрами так не получилось потому что у них нет наследования.
А зачем нам нужно наследование? Оно нам не нужно.
У нас четко разделяются просто токены и токены содержащие значения. Я же и говорил "создать две структуры".
А>знаю, что структура эффективнее чем класс. как лучше сделать? заврапить?
Лучше сделать две структуры. Типа:
[Record]
struct Token
{
public Start : int;
public End : int;
private _text : string;
private GetString() { ... }
}
[Record]
struct Data[T]
{
public Start : int;
public End : int;
public T : Value;
private _text : string;
private GetString() { ... }
}
Ну, и подставлять в качестве типов параметров. В генерируемом коде типы переменных не задаются, так что они выведутся на основании присвоений.
А>токен исполmзует локейшн, который содержится в nemerle.compilier.dll
Давай как пока что выкинем их. Потом прикрутим в виде методов-расширений или еще как-то.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Особенно если учесть то что оно не правильно использовано...
Погляди на современное состояние дел в парсере. Может какие-то идеи или замечания возникнут.
Я там заменил использование списка на использование переменных.
посвященную обсуждению развитию PEG-парсера. Предлагаю перенести туда все что связано с идеологическими вопросами. Данная тема разжирела. Искать что либо в ней становится все сложнее.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, para, Вы писали:
P>Сделал text параметром, а не полем.
Отлично!
Но нужно сделать еще более радикальный шаг. Для каждого правила для которого есть обработчик (генерируется метод в парсере) нужно создать публичный метод-обертку которая бы имело сигнатуру:
public RuleName(source : string, startPosition : int = 0) : option[T]
{
mutable resulr Nemerle.Peg.VToken[int];
if (__GENERATED_PEG__RULE__RuleName__(startPosition, ref result))
Some(resulr)
else
None()
}
Где T — это тип возвращаемого значения описанный в правиле (после двоеточия).
P>Заинлайнил CheckPos, GetChar.
А вот это плохое решение. Эти функции были введены для того чтобы была возможность абстрагировать парсер от источника данных.
P>ускорение в 2 раза))
Думаю, что ты тестировал в дебаге. В релизе дотнет эти функции сам должен был бы заинлайнить. Возможно что проблема в том, что ты их вынес в отдельную сборку.
Попробуй провести эксперимент и объявить их в проекте парсера. Потом скомпилируй проект в релиз и запусти из командной строки (интеграция глючит и запускает дебажную версию).
Я добавил в проект
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, para, Вы писали:
P>Сделал text параметром, а не полем. P>Заинлайнил CheckPos, GetChar. P>ускорение в 2 раза))
Сори послал предыдущее письмо не дописал.
Я добавил в проект Parsers еще один класс парсера — CsParser.n. При компиляции он выдает ошибку, так как в сгенерированном коде имеются обращения к несуществующим переменным. Так как для этих правил нет обработчико, то эти переменные генерировать не надо.
Исправь эту ошибку и сделай так чтобы NToken генерировался только там где он действительно нужен (т.е. когда он требуется правилу идущему выше по дереву грамматики).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
P>>Заинлайнил CheckPos, GetChar.
VD>А вот это плохое решение. Эти функции были введены для того чтобы была возможность абстрагировать парсер от источника данных.
Подумал немножко... и понял, что лучше оставить так как сделал ты. PEG принципиально требует индексированног доступа к разбираемой строке. Смысл в абстрагировании от представления строки стремится к нулю.
Так что это замечание отменяется. Будем считать, что я его не говорил.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
