Здравствуйте, VladD2, Вы писали:
VD>А то еще не факт, что устранение косвенности даст выигрышь в дотнете. Ведь вместо этого начнется барьер записи, и что дороже я не знаю.
Какой райт барьер у структуры грамматики? Она модифицируется один раз — при формировании. А при парсинге ее никто не меняет, только читает. Ну а скорость формирования собственно грамматики меня не особо волнует, это нужно сделать один раз на все время жизни приложения.
VD>Я использовал готовый лексер. Так что на это можно забить.
Да я не к тому чтобы использовать, а к тому чтобы разобраться.
VD>Вот и я говорю. Я пока что унаследовал Состояние от List<Situation>. Так лучше для отладки. А вообще склоняюсь к тому, что бы сделать состояния просто массивами (Situation[]).
Да я вот тоже сегодня утром подумал. В том коде, что я кидал я по инерции для правой части правила использовал List<Symbol> с преобразованием в массив, а можно ведь просто в массиве хранить (хотя защищенность при этом упадет).
Здравствуйте, AndrewVK, Вы писали:
AVK>Какой райт барьер у структуры грамматики?
Ты вель про указатели говорил? Вот копирование кадого из них вызовет барьер записи.
AVK> Она модифицируется один раз — при формировании. А при парсинге ее никто не меняет, только читает. Ну а скорость формирования собственно грамматики меня не особо волнует, это нужно сделать один раз на все время жизни приложения.
Ссылки на правила есть в каждой ситуации. Ситуации создаются динамически по дцать штук для каждого символа входной строки (минимум по одному).
VD>>Я использовал готовый лексер. Так что на это можно забить.
AVK>Да я не к тому чтобы использовать, а к тому чтобы разобраться.
Ну, я привел уже рабочий код.
VD>>Вот и я говорю. Я пока что унаследовал Состояние от List<Situation>. Так лучше для отладки. А вообще склоняюсь к тому, что бы сделать состояния просто массивами (Situation[]).
AVK>Да я вот тоже сегодня утром подумал. В том коде, что я кидал я по инерции для правой части правила использовал List<Symbol> с преобразованием в массив, а можно ведь просто в массиве хранить (хотя защищенность при этом упадет).
В правилах и вообще везде нужно хранить не ссылки, а индексы символов. Это нужно для анализа. Индесы терминалов совпадают с kind-ми токенов.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
VD>>Нет особого смысла делать статические обработчики у динамического парсера.
AVK>Ты считаешь что разница между прямым вызовом и вызовом через делегат на фоне парсинга будет незаметна?
Для особо требовательных можно просто константу отплеваывать. А вообще, на фоне тормозов самого алгоритма, думаю, эти вызовы будут незаметны. Меня вообще пока что волнует вопрс будет ли этот алгоритм пригоден для реального использования?
VD>> Тогда уж нужно продумывать и генерацию неких таблиц ускоряющих парсинг.
AVK>Придумать бы еще каких.
Здравствуйте, VladD2, Вы писали:
AVK>> Она модифицируется один раз — при формировании. А при парсинге ее никто не меняет, только читает. Ну а скорость формирования собственно грамматики меня не особо волнует, это нужно сделать один раз на все время жизни приложения.
VD>Ссылки на правила есть в каждой ситуации.
Я присал про ссылки на символы внутри правила. В оригинале там был глобальный массив символов и индексы в этом массиве в правиле. Потому я и спросил, почему внутри правила не хранить сразу указатели на символы.
Здравствуйте, VladD2, Вы писали:
VD>Для особо требовательных можно просто константу отплеваывать. А вообще, на фоне тормозов самого алгоритма, думаю, эти вызовы будут незаметны. Меня вообще пока что волнует вопрс будет ли этот алгоритм пригоден для реального использования?
Скорость это деое техники. Я вот чего не понял так это как сообщения об ошибках получать?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, AndrewVK, Вы писали:
AVK>Я присал про ссылки на символы внутри правила. В оригинале там был глобальный массив символов и индексы в этом массиве в правиле. Потому я и спросил, почему внутри правила не хранить сразу указатели на символы.
Потому что суть алгоритма в сравнении этих самых индексов. Символ — это всего лишь идентификатор. Строковое представление нужно исключительно для визуализации.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Потому что суть алгоритма в сравнении этих самых индексов.
Так я и спрашиваю — чем хуже стравнение указателей?
VD> Символ — это всего лишь идентификатор. Строковое представление нужно исключительно для визуализации.
Здравствуйте, AndrewVK, Вы писали:
VD>>Потому что суть алгоритма в сравнении этих самых индексов.
AVK>Так я и спрашиваю — чем хуже стравнение указателей?
<C++ specific>
Насколько я понимаю, ничем не хуже и не лучше (в C++).
Но использование индексов и хранение описаний символов в виде std::vector мне представляется более простым и безопасным решением (причины см. здесь
). Если бы использовались указатели, то либо символы нужно было хранить как динамические объекты (и тогда пришлось бы определять политики владения и моменты уничтожения), либо в качестве контейнера для символов использовать std::list. Но std::vector с индексами все же предпочтительнее, имхо, т.к.:
-- при работе с неверными индексами отладочные версии STL могут вызывать ассерты, что упростит отладку;
-- все символы в памяти располагаются рядышком, а не в различных местах, как в случае с std::list. Что в release может сделать обращение к символу по индексу очень эффективным.
</C++ specific>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, VladD2, Вы писали:
VD>>Для особо требовательных можно просто константу отплеваывать. А вообще, на фоне тормозов самого алгоритма, думаю, эти вызовы будут незаметны. Меня вообще пока что волнует вопрс будет ли этот алгоритм пригоден для реального использования? WH>Скорость это деое техники.
К сожалению скорость определяется алгоритмом. И на мой взгляд только она важна для данного алгоритма.
WH> Я вот чего не понял так это как сообщения об ошибках получать?
Какие? Если не корректна грамматика, то класс ее формирующий спокойно их отловит. А не соотвествие входной строки грамматике будет выражаться в наличии "пустых" состояний и в итоге конечное состояниен не должно иметь ситуации где точка указывает за последний символ правила.
Если по набору ситуаций можно буедт постороить неполное дерево выдоа, а вроде как это возможно, то можно будет легко установить где строка начала несоотвествовать грамматике. Хотя, наверно, это можно сделать и без построения деревьев вывода. Ведь с каждым состоянием связан символ входной строки. Так что если состояние пусто, то соотвестующий ему символ входной строки некорректен.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>А не соотвествие входной строки грамматике будет выражаться в наличии "пустых" состояний
Безусловно. Сам факт пустого списка означает, что строка не попадает ни под одно из правил. Тут другое интересно — как сформировать сообщение об ошибке? Информация у нас для этого — список на предыдущем шаге. Если там одна ситуация, то все понятно. А вот если их там несколько? Навскидку — можно по всем ситуациям ошибки писать, объединяя их союзом "или", можно выбирать с наибольшей позицией точки, можно ввести вес правила и выбирать ситуацию с наибольшим весом.
Здравствуйте, AndrewVK, Вы писали:
VD>>Потому что суть алгоритма в сравнении этих самых индексов.
AVK>Так я и спрашиваю — чем хуже стравнение указателей?
Тем что их нельзя использовать в качестве индексов массивов. Например, каждому нетерминальному символу соотвествует список правил. Если символ это целое число, то достаточно создать массив "int[][] _nontermRules" и заполнить его при инициализации грамматики. Если же символы — это строки, то прийдется использовть хэш-таблицы, что явно не быстро. Потом для терминалов лексер уже предоставляет целочисленные константы, их обратный перевод в строки — это маразм. В общем, строки тут испльзовть просто не нужно.
VD>> Символ — это всего лишь идентификатор. Строковое представление нужно исключительно для визуализации.
AVK>А при чем тут строковое представление?
А зачем еще что-то нужно? Символ == некий идентификатор. Для человека — это строка. Для машины целое число.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Списки сиволов и правил задаются грамматикой и не изменяются в процессе парсинга. Так что их достаточно положить в соотвествующие массивы. А сатло быть политики владения тут не причем.
А причем тут банальные вычислительные сложности. Адреса плохо использовать для идентификации объектов.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
AVK>Безусловно. Сам факт пустого списка означает, что строка не попадает ни под одно из правил. Тут другое интересно — как сформировать сообщение об ошибке? Информация у нас для этого — список на предыдущем шаге. Если там одна ситуация, то все понятно. А вот если их там несколько? Навскидку — можно по всем ситуациям ошибки писать, объединяя их союзом "или", можно выбирать с наибольшей позицией точки, можно ввести вес правила и выбирать ситуацию с наибольшим весом.
Показать символ на котором возникла проблема можно и так. А точно сказать ошибку... Тут придется или анализировать предыдущее состояние, или даже полностью строить деревья вывода (ведь в это место мы могли прийти более чем одним путем). В общем, здесь бы как раз послушать mefrill.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Тем что их нельзя использовать в качестве индексов массивов. Например, каждому нетерминальному символу соотвествует список правил. Если символ это целое число, то достаточно создать массив "int[][] _nontermRules" и заполнить его при инициализации грамматики. Если же символы — это строки, то прийдется использовть хэш-таблицы, что явно не быстро. Потом для терминалов лексер уже предоставляет целочисленные константы, их обратный перевод в строки — это маразм. В общем, строки тут испльзовть просто не нужно.
Влад, о каких строках речь? Я имел ввиду указатели на Symbol.
AVK>>А при чем тут строковое представление?
VD>А зачем еще что-то нужно? Символ == некий идентификатор. Для человека — это строка. Для машины целое число.
public bool Parse(int startNonterminalId)
{
PrepareToParse(startNonterminalId);
State state = AddState();
// Получаем индексы правил соотвествующих нетерминалу startNonterminalId.
// и добавляем их в список "нулевого" состояния.
AddPredictions(startNonterminalId, state, 0);
int stateIndex = 0;
do
{
++stateIndex;// ! Количество ситуаций в стостянии может измениться в процессе
// их просмотра . По этому кэшируем их число и делаем перебор простым
// for-ом.for (int i = 0; i < state.Count; i++)
{
Situation sit = state[i];
if (IsComplete(sit))
Completer(sit, state);
else
Predictor(sit, state, stateIndex);
}
}
while (Scanner(ref state));
// Если последнее состояние содержит "законченную" ситуацию, т.е.
// ситукациювида [A --> X1...Xk *], значит строка соответствует
// грамматике.return GetLastState().Exists(IsComplete);
}
private void AddPredictions(int nonterminalId, State state, int stateIndex)
{
Debug.Assert(IsNonterminal(nonterminalId));
foreach (int ruleId in _grammar.NontermRules[nonterminalId])
state.Add(new Situation(ruleId, 0, stateIndex));
}
И вобще залил бы это дело в SVN.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, VladD2, Вы писали:
VD>>Тем что их нельзя использовать в качестве индексов массивов. Например, каждому нетерминальному символу соотвествует список правил. Если символ это целое число, то достаточно создать массив "int[][] _nontermRules" и заполнить его при инициализации грамматики. Если же символы — это строки, то прийдется использовть хэш-таблицы, что явно не быстро. Потом для терминалов лексер уже предоставляет целочисленные константы, их обратный перевод в строки — это маразм. В общем, строки тут испльзовть просто не нужно.
AVK>Влад, о каких строках речь? Я имел ввиду указатели на Symbol.
А что ты собрался хранить в Symbol? Symbol — может быть или строкой или целочисленным идентификатором. Представлять его классом смысла нет.
VD>>А зачем еще что-то нужно? Символ == некий идентификатор. Для человека — это строка. Для машины целое число.
AVK>Или указатель.
На фиг там никакие указатели не уперлись. Еще раз повтояю, ты задолбашся этими указателями ссылаться на разные таблицы. Тут int самое то.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, VladD2, Вы писали:
WH>В парсере обноружены и исправлены следующие ошибки WH> FirstNonterminal = _grammar.LastTerinalId + 1;
Это да. А это ты уже сам накосячил: WH> LastNonterminal = _grammar.SymbolNames.Length;
все же последний символ долженр быть последним в массиве. Так что все же
