VD>Я так понл есть два подхода: VD>1. Заглядывание вперед. VD>2. Построение LR(0)-атомата (ДКА).
VD>Второй подход описан здесь: http://rsdn.ru/File/73/deep-2.pdf
Deep же использует хитрую оптимизацию когда item [A --> B . C, i] заменяется на пару (i,указатель на функцию которая возвращает результат действия Completer Predictor Reducer для данного item).
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>А как ты предлагаешь? Базовый класс Symbol и два наследника — Terminal и NonTerminal? Или сделать их абсолютно одинаковыми и распознавать просто по списку, в котором хранится? Но как тогда, имея экземпляр Rule, определится какой конкретно символ в правой части по некоторой позиции х?
Да, просто сравнивать позицию. Для идущих первыми терминалов это максимальное число. Если номер символа больше этого числа, то значит это нетерминал, меньше или равно, значит терминал.
Здравствуйте, mefrill, Вы писали:
M>В оригинале у Эрли это называется item. Ситуация — это удачный перевод Тихомирова.
Ну, раз удачный и ты его используешь при объяснении, то и в коде надо так называть.
VD>>origin_ VD>>Я назвал это поле CreationState. Я правильно понял суть этого поля?
M>Ага, верно, но в оригинале origin называется. Я, кстати, хорошего перевода для этого так и не придумал.
Всегда говорил, что у математиков фигово с фонтазией когда речь заходит о именах. Ну, да хорошо, что не X, Y, Z.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Если учесть, что код слишком большой для стольк простой задачи я бы предпочел бы изучать алгоритм на безе шарповского варианат приведенного мной здесь: VD>Re: Адаптированный алгоритм Эрли — описание
Здравствуйте, VladD2, Вы писали:
VD>Про использование хэш-таблицы как set. Если тебе не нужно значение, то задавай в качестве его типа какой-нить простой тип. Пойми, для ЖЦ любая ссылка это повод полазить полазить по ссылкам. Плюс райт-барьер.
Ок.
У меня сейчас возникла совершенно шальная мысль: А что если выкинуть к чертовой бабушке List<State> _states и в Situation заменить int _creationState на Situation _parentSituation.
Мотив: При парсинге порождается масса объектов класса Situation подавляющие число которых не используются для дальнейшего вывода. Но из-за List<State> _states на них хранятся ссылки и GC с ними возится. Если же на них не будет ссылок то подавляющее колличество ситуаций будут умирать в нулевом поколении. Плюс мы избавляемся от поиска в Completer'е.
Вобщем я завтра это реализую и посмотрим что получится.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Только одно но. Быстро восоздать алгоритм по твоей статье и коду на С++ мне явно не удастся. Нужно более простое объяснение. Можно попробывать сделать что-то в интерактивном режиме. VD>Если есть желание можно попробовать.
Нет проблем. За базу можно взять какой-нибудь простой пример. Сначала разобраться что такое ситуация, затем что такое эти самые три процедуры: Scanner, Completer и Predictor. Параллельно можно смотреть мой код, там на самом деле несложно, просто пришлось от STL отказаться, поиск по спискам очень сильно тормозил, на создание итератора до фига времени шло. А сама реализация занимает всего несколько функций. Вообще, алгоритм очень простой, но вот объяснить его сложно, к сожалению. Давай начнем с примера? Предлагаю заинтересованным лицам присоедениться.
Итак, что такое ситуация? Это, на самом деле, просто пара из помеченного правила (т.е. правила с точкой в правой части) и некоторого числа в диапазоне от нуля до длины входной строки. Например, имеем правила
S --> A B
A --> a
B --> b
можно построить следующие помеченные правила (точку для удобства обозначим звездочкой):
S --> * A B, S --> A * B, S --> A B *
A --> * a, A --> a *
B --> * b, B --> b *
Вот ситуация, это например, такая пара [S --> A * B, 0] или такая [B --> b *, 5].
полагаем, что входная строка это omega = a1...an состоит из n символов.
Алгоритм Эрли строит списки таких ситуаций, один список для каждого символа входной строки. Есть еще список для нулевой позиции при чтении строки. Т.е. если входная строка имеет длины n, то списков у нас будет построено n+1, и пронумерованы они будут от 0 до n.
Считается, что входная строка распознана успешно в данной грамматике, если в последнем списке, т.е. в списке, соответствующем последнему символу входной строки, есть ситуация вида [S --> X1...Xk *, 0]. Т.е. помеченное правило должно иметь точку в самом конца правой части и символ в левой части правила должен быть начальным нетерминалом грамматики, а второй элемент ситуации — число, должно быть равно нулю.
В чем состоит таинственный смысл понятия ситуации? Он не так уж и сложен. Если мы имеем ситуацию вида [A --> alpha * beta, i], принадлежащую списку номер p, то это значит, что из строки alpha в правой части правила A --> alpha beta выводится часть ai...ap нашей входной сnроки omega. Т.е. мы имеем дерево
alpha
/ \
a1......ai.......ap.....an
Но дерево это не произвольно, а в контексте всей грамматики, т.е. нетерминал A для правила A --> alpha beta реально задействован в каком-то дереве для вывода всеей подстроки a1...ap. Поэтому, если мы имеем ситуацию вида [S --> X1...Xk *, 0], это значит мы реально имеем дерево
S
/ \
X1...Xk
/ \
a1.........an
что нам и нужно.
Итак, каждая ситуация Эрли на самом деле означает некотрое конкретное дерево, а точнее — узел некоторого дерева вывода какой-то подстроки нашей входной строки omega. Алгоритм Эрли на самом деле состоит в последовательном потсроении всех таких деревьев-ситуаций начиная с первого символа входной тсроки. Какие-то деревья дальше не продолжаются, какие-то продолжаются, растут и, в конце-концов, выростают в деревья с вершинами в начальном нетерминале грамматики, покарывающие всю входную строку.
Теперь надо выяснить каким образом эти списки узлов деревьев (ситуаций) строятся и как вообще из одних ситуаций следуют другие. Но, прежде чем перейти к этому вопросу, хотелось бы выяснить, все-ли понятно с понятием ситуации?
О том что такое ситуация, лично мне, было примерно понятно еще из статьи. Но все равно спасибо за более доступное изложение.
Единственное замечание которое хочется сделать — это то что не все хорошо воспринимают обстрактные примеры. Книги и статьи по теории парсинга постоянно оперируют этими абстрактными примерами, и это неизменно вызвает непонимание у многих читателей. По этому предлагаю взять в качестве примеров нечто знакомое всем окружающим. Например в статье использовалось сложение. Если нужно что-то более сложное, то можно взять граматику оператора "?:" из С и т.п. В общем, чтобы примеры были более реальны. Так проще их уложить в голове.
Ну, а что до алгоритма, то лично у меня вызвают вопросы именно реализация функций Scanner, Completer и Predictor. Собственно интересна не только реализация, но и их смысл.
Как я понимаю ситуацию можно описать так (C#):
class Situation
{
public int RuleIndex; // индекс в некотором массиве правилpublic int PosInRule; // позиция в правиле (та самая звездочка/точка)public int TokenIndex; // Номер символа разбираемой строки
}
Хранить их наверно лучше в динамическом массиве для которого заранее занимать по больше памяти (чтобы небыло перезаемов). Если нужен их поиск, то вместо массива наверно стоит хранить их в хэш-таблице (точнее даже хэш-сете).
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
VD>О том что такое ситуация, лично мне, было примерно понятно еще из статьи. Но все равно спасибо за более доступное изложение.
VD>Единственное замечание которое хочется сделать — это то что не все хорошо воспринимают обстрактные примеры. Книги и статьи по теории парсинга постоянно оперируют этими абстрактными примерами, и это неизменно вызвает непонимание у многих читателей. По этому предлагаю взять в качестве примеров нечто знакомое всем окружающим. Например в статье использовалось сложение. Если нужно что-то более сложное, то можно взять граматику оператора "?:" из С и т.п. В общем, чтобы примеры были более реальны. Так проще их уложить в голове.
Хорошо, как раз дошла очередь и до примеров.
VD>Ну, а что до алгоритма, то лично у меня вызвают вопросы именно реализация функций Scanner, Completer и Predictor. Собственно интересна не только реализация, но и их смысл.
В соседней ветке это оптсараююсь описать.
VD>Как я понимаю ситуацию можно описать так (C#): VD>
VD>class Situation
VD>{
VD> public int RuleIndex; // индекс в некотором массиве правил
VD> public int PosInRule; // позиция в правиле (та самая звездочка/точка)
VD> public int TokenIndex; // Номер символа разбираемой строки
VD>}
VD>
VD>Хранить их наверно лучше в динамическом массиве для которого заранее занимать по больше памяти (чтобы небыло перезаемов). Если нужен их поиск, то вместо массива наверно стоит хранить их в хэш-таблице (точнее даже хэш-сете).
Я храню (и убежден, что это самое лучшее решение) списки ситуаций в состоянии как множество отдельных списков, каждый из которых соответствует определенному символу грамматики. Дело в том, что операции Completer и Scanner осуществляют поиск по спискам ситуаций с целью найти ситуации, где определенный символ стоит после точки в правой части правила. Чтобы такого поиска не осуществлялось, я просто храню для каждого символа все ситуации, где этот символ стоит после точки. Тогда и поиска, фактически, производить не нужно будет.
Каким образом заполняются списки ситуаций для каждого символа входной строки? (их еще называют состояниями Эрли)
Вообще говоря, с помощью сдвига точки на один символ вправо, т.е. ситуация вида [A --> X1...Xk * Xk+1...Xp, i], принадлежащая списку под номером j, может попасть в какой-то список с большим номером только передвинув точку вправо т.е. трансформируясь в ситуацию вида [A --> X1...Xk+1 * Xk+2...Xp, i]. Одни ситуации попадают в списки правее, другие нет. Каким образом и почему это происходит?
С помощью трех операций:
Scanner — работает только с терминальными символами. Scanner работает на некотором списке Si когда тот уже заполнен плностью, т.е. туда больше ничего добавить нельзя. Поэтому настает время перейти к заполнению следующего списка Si+1. Т.е. Scanner вызывается для инициализации каждого списка S1...Sn, а список S0 инициализируется особым образом. Что делает Scanner? Он сравнивает символ ai+1 во входной терминальной строке с символом после точки в каждой ситуации из списка Si и, если символ после точки совпадает с символом ai+1, то Scanner добавляет эту ситуацию в список Si+1, преварительно передвинув точку в правой части правила ситуации на символ правее. Например, у нас в списке Si были такие ситуации:
[A --> Bc*gA, 0]
[A --> c*B, 3]
[S --> *gf,1]
и текущий символ во входной строке есть g. Тогда Scanner пройдет по списку ситуаций, найдет две из них [A --> Bc*gA, 0] и [S --> *gf,1], где символо после точки равен g, и добавит в следующщий список Si+1 ситуации
[A --> Bcg*A, 0]
[S --> g*f,1]
Каким деревьям соответсвуют ситуации из списка Si? Вот каким:
A
/ \
Bc gA
/ \
/ \
a1....ak+1.......ai ai+1.......an
A
/ \
c B
/ \
/ \
a1....al+1.......ai ai+1.......an
S
/ \
g f
a1....ai+1.......an
Обратим внимане, что в последнем дереве фактически из символа S пока ничего не выводится, так как точка в правой части правила стоит крайней слева, т.е. пока ни один символ з правой части правила не выводился.
Теперь надо пройти дальше, т.е. продолжить вывод деревьев. Из трех деревьев только два могут быть продолжены, ведь ai+1 равен символу g. Итак, продолжаем вывод этих деревьев, получаем деревья.
A
/ \
Bcg A
/ \
/ \
a1....ak+1.......ai+1.......an
S
/ \
g f
|
a1...ai+1.......an
Процедура Completer осуществляет такой же сдвиг точки, как и процедура Scanner, но работает на нетерминальных символах. Как она работает? Предположим, что в каком-то списке Si у нас ситуация, в которой точка стоит в самом конца правой части правила. т.е. ситуация вида [A --> X1...Xk *, j]. Что это значит на дереве вывода? Это значит, что у нас есть такое дерево вывода:
A
/ \
X1...Xk
/ \
/ \
a1....aj+1...........ai.......an
Т.е. символ A полностью вывелся в строку aj+1...ai. Почему именно aj+1...ai? Обратим внимание на вторую компоненту ситуации [A --> X1...Xk *, j] — это число j. Что такое j? Это номер списка, в котором эта ситуация "родилась", т.е. в который была добавлена ситуация вида [A --> * X1...Xk, j] с точкой в самом начале правой части правила. А номер i — это номер списка Si, которому принадлежит ситуация [A --> X1...Xk *, j].
Теперь. предположим, что в списке Sj у нас есть ситуация вида [B --> alpha * A beta, l]. Это значит, что есть дерево
B
/ \
alpha A beta
/ \
/ \
a1....al+1........aj.......an
Сравнивая деревья для обеих ситуаций, имеем дерево
B
/ \
/ \
alpha A beta
/ \ / \
al+1.....aj X1....Xk
/ \
a1... aj+1........ai.....an
Иначе говоря, в списке Si мы должны иметь ситуацию вида [B --> alpha A * beta, l], соответсвующую дереву
B
/ \
/ \
alpha A beta
/ \
a1...al+1........ai.....an
Где символ A вывелся через строку X1...Xk ==> aj+1...ai.
Как добавить такую ситуацию в список Si? Простым вычислимым процессом. Мы идем в список Sj, ищем там все ситуации, где символ после точки есть символ A. и добаляем их в список Si, предварительно сдвинув точку на символ правее. Т.е. для ситуации [B --> alpha * A beta, l] мы действительно добавим в список Si ситуацию [B --> alpha A * beta, l].
Итак, операция Completer, примененная к ситуации [A --> X1...Xk *, j], принадлежащей списку Si, делает следующее:
1. Проходит по всем ситуациям списка Sj.
2. Если в ситуации символ после точки есть символ A, то добавляет эту ситуацию в список Si, сдвинув предварительно точку в правой части на символ правее.
И последняя операция — это Predictor. Название для нее предсказатель и функция как раз в предсказании и состоит. Что она делает? Она добавляет в текущий список ситуации, в которых точка стоит в самом начале правой части правила. Ведь ни Scanner ни Completer такого не делают, кто-то должен такие ситуации-заготовки добавлять? Ситуация, в которой точка стоит в начале правой части помеченного правила, на самом деле означает, что из правой части правила пока ничего не вывелось, но потенциально может быть выведено. Вот эту потенциальную возможность выводимости и предсказывает Predictor. Как он это делает? Предположим, что в некотором списке Si есть ситуация вида [B --> alpha * A beta, j]. Это значит есть дерево
B
/ \
/ \
alpha A beta
/ \
a1...aj+1......ai.....an
Как может быть выведен символ A? Конечно, через правила грамматики вида A --> delta, где символ в левой части есть нетерминал A. Во операция Predictor и добавляет ситуации для всех таких правил, т.е. добавляет ситуации вида [A --> * delta, i] для каждого правила вида A --> delta из нашей грамматики. Обратим внимание, что вторая компонента ситуации есть номер текущего списка Si, т.е. число i. Но это и естественно, ведь вывод правила A --> delta в текущем контексте начнется (если начнется) с символа ai+1, т.е. мы как раз перед ним и находимся и еще пока ни одного символа из строки delta не выведено.
Итак, операция Predictor, примененная к ситуации [B --> alpha * A beta, j], принадлежащей списку Si, делает следующее:
1. Проходит по правилам грамматики.
2. Для каждого правила вида A --> delta, где символ в левой части совпадает с символом после точки, добаляет в список Si ситуацию [A --> * delta, i].
Для заоплнения списков мы сначала инициализируем список операцией Scanner, примененной к предыдущему списку, а затем, к каждой ситуации из списка применяем процедуры Completer и Predictor. Эти процедуры добавляют новые, и к ним тоже применяем процедуры Completer и Predictor, и т.д. пока в списко не перестанут добавляться новые ситуации. Этот процесс обязательно закончится, это доказано.
Единственное исключение — это инициализация нулевого списка, ведь Scanner здесь не применишь, не к чему. Нулевой список инициализируется операцией Predictor, примененной к начальному символу грамматики. Т.е. для каждого правила грамматики вида S --> alpha, где символ слева — это начальный нетерминал грамматики S, добавляем в нулевой список ситуацию вида [S --> * alpha, 0]. И дальше точно также начинаем применять операции Completer и Predictor.
Пока все, будут вопросы — с удовольствием отвечу. Когда то, что я написал, достточно переварится, можно посмотреть работу алгоритма на конкретном примере, а также кое-какой код написать, ведь алгоритм очень простой для реализации.
Здравствуйте, mefrill, Вы писали:
M>Я храню (и убежден, что это самое лучшее решение) списки ситуаций в состоянии как множество отдельных списков, каждый из которых соответствует определенному символу грамматики. Дело в том, что операции Completer и Scanner осуществляют поиск по спискам ситуаций с целью найти ситуации, где определенный символ стоит после точки в правой части правила. Чтобы такого поиска не осуществлялось, я просто храню для каждого символа все ситуации, где этот символ стоит после точки. Тогда и поиска, фактически, производить не нужно будет.
Я пока что не очень понимаю алгритм, но храниние списков в 99% случаев == тормоза. Так как сапски это:
1. Вечные поиски перебором.
2. Расход лишней памяти.
3. Плохая локализация связанных элементов.
Как показывает мой опыт связка массивов и хэш-таблиц обычно бывает быстрее любых других решений.
Ну, да когда я пойму алгоритм целиком можно будет подумать и провести ряд эксперементов. Оптимальную структуру для неизвесного алгоритма подобрать невозможно.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Я пока что не очень понимаю алгритм, но храниние списков в 99% случаев == тормоза. Так как сапски это: VD>1. Вечные поиски перебором. VD>2. Расход лишней памяти. VD>3. Плохая локализация связанных элементов.
VD>Как показывает мой опыт связка массивов и хэш-таблиц обычно бывает быстрее любых других решений.
В том-то и дело, что чпецифика алгоритма такова, что поиска в этом случае вообще не будет. Ведь поиск идет по каждой из операций Scanner, Completer и Predictor. Scanner ищет все ситуации, где символ после точки — это терминал, совпадающий со следующим входным символом. Если мы держим в отдельном списке все ситуации, у которых после точки этот символ стоит, тогда мы ничего не ищем, просто берем и обрабатываем каждый из них. Для операции Completer точно такая же картина. А вот Predictor работает уже с исходной грамматикой. Эта операция ищет в грамматике все правила, у которых символ слева — это нужный нетерминал. Точно так-же можно разбить грамматику на такие списки для каждого нетерминала и поиска тогда вообще не будет. Т.е. на самом деле, это и есть хэш-таблица, где роль хэш-функции играет простое вычисление номера символа грамматики. Почему так важно хорошо пронумеровать символы грамматики перед запуском алгоритма.
Теперь приведу пример. Пусть грамматика имеет следующий вид:
S --> S + n
S --> n
где, S — нетерминальный и начальный символ грамматики, а n и + — терминалы.
Пусть на вход подается строка n+n. Посмотрим как алгоритм Эрли проведет разбор данной строки на основе грамматики выше.
Первым шагом алгоритма является добавление в нулевой список S0 ситуаций для правил с начальным нетерминалом S в левой части. В нашей грамматике оба правила имеют нетерминал S в левой части, поэтому добавляем в список S0 две ситуации [S --> * S + n, 0] и [S --> * n, 0]. Запускаем на этом списке Predictor и Completer. Completer работать не будет, т.к. он работает только на ситуациях, у которых точка стоит в самом конце правой части правила, а у нас сейчас в списке таких нет. Predictor сканирует каждую ситуацию в списке чтбы найти нетерминал после точки. В нашем случае, мы имеем в первой ситуации [S --> * S + n, 0] нетерминал S после точки и надо добавить в список S0 ситуации для всех правил грамматики, у которых нетерминал S (после точки) стоит в левой части. Но, так как неетрминал S — начальный нетерминал грамматики, мы уже добавили все правила с ним в левой части в наш список S0, так что ничего больше не добавляем. Следующая ситуация — это [S --> * n, 0]. В ней после точки стоит терминальный символ n, так что ничего не добавляем. Т.о. обработка списка S0 операциями Predictor и Completer ничего нового в этот список не добавили, поэтому переходим к заполнению списка S1. Для этого запускаем процедуру Scanner на списке S0 и читаем первый входной символ строки n+n, это терминал n. Проходим по списку S0:
в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки, поэтому пропускаем эту ситуацию. Следующая ситуация — это [S --> * n, 0]. Вот у нее символ после точки равен n. Поэтому, добавляем эту ситуацию в список S1, сдвинув точку на символ правее, имеем ситуацию [S --> n *, 0] в списке S1. Применяем теперь операции Predictor и Completer. Применение Predictor ничего не дает, ведь после точки нет никакого символа. А вот Completer здесь применить можно, т.к. точка в ситуации [S --> n *, 0] стоит в конце правой части. Итак, смотрим на второй элемент ситуации — это число 0. Идем в список S0 и ищем там ситуации, у которых символ S стоит после точки. Такая ситуация есть, это [S --> * S + n, 0]. Добавляем ее в наш список S1, сдвинув точку на символ правее. Имеем в списке S1 две ситуации:
уже обработанную процедурами Predictor и Completer ситуацию [S --> n *, 0] и еще не обработанную ситуацию [S --> S * + n, 0].
обрабатываем последнюю ситуацию. Predictor на ней не работает, т.к. символ после точки — нетерминальный, а Completer работаь также не может, ведь точка стоит не в конце правой части. Поэтому список остается тем же.
Запускаем операцию Scanner для инициализации списка S2. Второй символ входной строки n+n — это символ +. Проходим по списку S1 и сравниваем символ после точки в ситуации [S --> n *, 0] с символом +. Там вообще никакого символа нет, поэтому переходим к ситуации [S --> S * + n, 0]. У нее символ после точки равен символу +, поэтому добавляем эту ситуацию в список S2, передвинув точку вправо. Имеем в списке S2 одну ситуацию [S --> S + * n, 0]. Очевидно, что ни Predictor ни Completer на этой ситуации не работают, в первом случае символ после точки — терминальный, во втором — точка не в конце правой части.
переходим к заполнению списка S3. Третий список входной строки n+n — это n. Сканируем список S2, он сотоит из одной ситуации [S --> S + * n, 0]. Символ после точки равен символу n, поэтому добавляем эту ситуацию в список S3, предварительно сдвинув точку на символ правее. Имеем в списке S3 ситуацию [S --> S + n *, 0]. Операция Predictor, очевидно, к этой ситуации не применима, а вот Completer работает. Смотрим второй элемент ситуации — это число 0, идем в список S0 и ищем в нем ситуации, в которых символ S (который в помеченном правиле S --> S + n * стоит в левой части) стоит после точки. Такая ситуация есть, это [S --> * S + n, 0]. Добавляем ее в список S3, передвинув точку на символ вправо. Имеем ситуацию [S --> S * + n, 0]. Обрабатываем ее операциями Predictor и Completer, ни одна из них не добавляет новой ситуации в список S3, входная строка закончена, поэтому завершаем работу алгоритма. Итак, имеем списки:
S0
[S --> * S + n, 0]
[S --> * n, 0]
S1
[S --> * n, 0]
[S --> S * + n, 0]
S2
[S --> S + * n, 0]
S3
[S --> S + n *, 0]
[S --> S * + n, 0]
Выводится ли строка n+n в нашей граматике? Да, ведь список S3 содержит ситуацию [S --> S + n *, 0], в котрой точка стоит в конце правой части правила, символ в левой части есть начальный нетерминал грамматики и второй компонент правила есть 0.
Следующим шагом может быть попытка написать работающий алгоритм Эрли.
Здравствуйте, mefrill, Вы писали:
M>В том-то и дело, что чпецифика алгоритма такова, что поиска в этом случае вообще не будет. Ведь поиск идет по каждой из операций Scanner, Completer и Predictor. Scanner ищет все ситуации, где символ после точки — это терминал, совпадающий со следующим входным символом. Если мы держим в отдельном списке все ситуации, у которых после точки этот символ стоит, тогда мы ничего не ищем, просто берем и обрабатываем каждый из них. Для операции Completer точно такая же картина. А вот Predictor работает уже с исходной грамматикой. Эта операция ищет в грамматике все правила, у которых символ слева — это нужный нетерминал. Точно так-же можно разбить грамматику на такие списки для каждого нетерминала и поиска тогда вообще не будет. Т.е. на самом деле, это и есть хэш-таблица, где роль хэш-функции играет простое вычисление номера символа грамматики. Почему так важно хорошо пронумеровать символы грамматики перед запуском алгоритма.
Но ведь есть списки по которым нужно каждый раз пробегаться. Это и вызовет замедление алгоритма. Единственная возможность сделать алгоритм O(n) — это сделать так, чтобы в списках в 99% случаев было по одному элементу. Но боюсь это не реально.
Пока думал над алгоритмом в голову пришла мысль...
А что если спарить этот алгоритм с LL(1)-автоматом? Ну, пока граматика однозначна для LL(1)-парсера, парсим супер эффективным ДКА. А как толко появляется неоднозначность переходим на Эрли. Проблема тольк в том, как возвращаться обратно когда найдено две подветки или устрнена LL(1)-неоднозначность?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Но ведь есть списки по которым нужно каждый раз пробегаться. Это и вызовет замедление алгоритма. Единственная возможность сделать алгоритм O(n) — это сделать так, чтобы в списках в 99% случаев было по одному элементу. Но боюсь это не реально.
Почему каждый раз? Предиктор только один раз работает, также каждая ситуация тоже обрабатывается не более одного раза. Если нет альтернатив, то вообще только один раз все будет работать. Вот в примере, который я привел в соседней ветке, там ведь по одному разу обходится. Scanner работает тоже один раз. Весь вопрос только в операции Completer, это самая дорогостоящая операция. Но и там, если грамматика позволяет парсить без ворзвратов, то все будет нормально, тоже только раз такой список будет пройден.
VD>Пока думал над алгоритмом в голову пришла мысль... VD>А что если спарить этот алгоритм с LL(1)-автоматом? Ну, пока граматика однозначна для LL(1)-парсера, парсим супер эффективным ДКА. А как толко появляется неоднозначность переходим на Эрли. Проблема тольк в том, как возвращаться обратно когда найдено две подветки или устрнена LL(1)-неоднозначность?
Немного непонятно, что подразумевается под LL(1)-автоматом? Если имеется ввиду те First и Follow множетсва, то конечно, можно. Этот вопрос еще в 1974 году (если правильно помню) исследовался и было показано, что использование таких множеств может уменьшить количество ситуаций с списках и улучшить производительность операции Predictor (которая и так достаточно быстрая), но не намного. У меня этот метод реализован в первом варианте парсера, который я для диссертации писал. Но особых преимуществ я не получил, только в специальных случаях. В общем, особого смысла я в этом не вижу. На неоднозначность это не влияет никаки образом, а если надо быстрый парсер для простой грамматики, то гораздо легче и эффективнее построить LR-анализатор.
Здравствуйте, mefrill, Вы писали:
M>Немного непонятно, что подразумевается под LL(1)-автоматом? Если имеется ввиду те First и Follow множетсва, то конечно, можно.
Почти. Я имею введу ДКА построеный на основе тех самых множеств. Удобно создать таблицу и проверять возможность выполения операции по ней, а не делать кучу ифов/свитчей.
M> Этот вопрос еще в 1974 году (если правильно помню) исследовался и было показано, что использование таких множеств может уменьшить количество ситуаций с списках и улучшить производительность операции Predictor (которая и так достаточно быстрая), но не намного. У меня этот метод реализован в первом варианте парсера, который я для диссертации писал. Но особых преимуществ я не получил, только в специальных случаях. В общем, особого смысла я в этом не вижу. На неоднозначность это не влияет никаки образом, а если надо быстрый парсер для простой грамматики, то гораздо легче и эффективнее построить LR-анализатор.
Я уже устал повторять, что LR годятся только для помойки. Таких грамматик которые они могут парсить (без костылей) и которые не могут парсить куда более простые LL(1)-парсеры я просто не видел. А учитывая геморрой с их отладкой и качество сообщений об ошибках которые они порождают, то я бы вообще их век не видел.
Нужен парсер который съедает граматику современных ЯП. Это не простой или очень сложный случай. Это просто конкреный случай. В нем почти всегда есть места проблемыне как для LR-парсеров, так и для LL. С другой стороны процентов 90 грамматики таки подпадает под LL(1)-правила.
Вот я и думаю. Нельзя ли сделать LL(1)-парсер переходящий на более изощьренные алгоритмы только в 10% случаев где действительно LL-парсер уже бессилен?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, mefrill, Вы писали:
M>в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки
Почему? Требуется чтобы после точки был терминал и он совпадал с текущим терминалом?
M>уже обработанную процедурами Predictor и Completer ситуацию [S --> n *, 0] и еще не обработанную ситуацию [S --> S * + n, 0]. M>обрабатываем последнюю ситуацию. Predictor на ней не работает, т.к. символ после точки — нетерминальный
То есть как это?
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, AndrewVK, Вы писали:
M>>в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки AVK>Почему? Требуется чтобы после точки был терминал и он совпадал с текущим терминалом?
Да точно.
M>>уже обработанную процедурами Predictor и Completer ситуацию [S --> n *, 0] и еще не обработанную ситуацию [S --> S * + n, 0]. M>>обрабатываем последнюю ситуацию. Predictor на ней не работает, т.к. символ после точки — нетерминальный AVK>То есть как это?
Пардон, терминальный, именно поэтому Предиктор не работает.
Здравствуйте, AndrewVK, Вы писали:
AVK>Понятно. Но пример не очень удачный — слишком редуцированная ситуация.
Да, предиктор фактически не работает. Но, я хотел проще простого пример сделать. В принципе, следующим шагом можно написать прямо в комментариях код работающего алгоритма. Ведь там совсем все просто, если без оптимизаций. Тогда понятно должно совсем стать. как насчет этого?
Здравствуйте, mefrill, Вы писали:
M>Да, предиктор фактически не работает. Но, я хотел проще простого пример сделать. В принципе, следующим шагом можно написать прямо в комментариях код работающего алгоритма. Ведь там совсем все просто, если без оптимизаций. Тогда понятно должно совсем стать. как насчет этого?
Давай. Только при абсолютном минимуме всяких оптимизаций и наворотов. Лишь бы работал.
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Давай. Только при абсолютном минимуме всяких оптимизаций и наворотов. Лишь бы работал.
Ага, на си++. Влад может тоже самое на си шарп реализовать. Надо сначала реализовать грамматику, так чтобы по символам поиск предиктором делать. А затем уже совсем несложно сам алгоритм реализовать.
символы грамматики мы будем держать в векторе, чтобы дать каждому символу индекс. И еще необходимы два ассоциативных массива, чтобы держать соответсвие между именами символов и их индексами.
typedef std::vector< symbol > symbols_t;
typedef std::map< std::string, unsigned int > name2index_t;
typedef std::map< unsigned int, std::string > index2name_t;
нужны еще правила. Каждое правило содержит нетерминал в левой части и вектор символов в правой части.
теперь грамматика. Содержит коллекцию символов и несколько методов чтобы добавлять новые символы и производить поиск по ним. Также содержит коллекцию правил и методы для добавления в правила символов.
А что, на C# никак? Тогда желательно с минимальным использованием STL и без всяких boost и loki.
M> Влад может тоже самое на си шарп реализовать. Надо сначала реализовать грамматику, так чтобы по символам поиск предиктором делать.
Достаточно пока реализовать AST грамматики и для тестов заполнять ее программно. А потом уже сделать ее парсер на себе самом.
M>символ грамматики можно закодировать так:
M>
А зачем конструктор без параметров? При его наличии придется делать доступ к полям по записи, а это снижает защиту.
M>нужны еще правила. Каждое правило содержит нетерминал в левой части и вектор символов в правой части. M>
А почему хранятся индексы, а не указатели?
M>теперь грамматика. Содержит коллекцию символов и несколько методов чтобы добавлять новые символы и производить поиск по ним. Также содержит коллекцию правил и методы для добавления в правила символов.
M>
Совсем не понял? Зачем нам глобальный список Symbol? Почему нельзя локально хранить их список внутри каждого правила? Просто чтобы обеспечить быстрое сравнение по указателям одних и тех же символов в разных правилах? Тогда куда лучше сделать NameTable, который при добавлении будет имя ресолвить в приделах грамматики (тем более что ты один фиг их ресолвишь по имени конструировании правила). В итоге получим и сравнение по указателям и чистый несвязный код.
M>ну как это можно использовать? Типа такого:
M>
M>grammar gr;
M>gr.add_symbol( "S", false, true );
M>gr.add_symbol( "n", true );
M>gr.add_symbol( "+", true );
Вот это лишнее ИМХО.
M>unsigned int S_S_plus_n = gr.add_rule( "S --> S + n" );
M>gr.add_left_nonterminal_to_rule( S_S_plus_n, "S" );
M>gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "S" );
M>gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "+" );
M>gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "n" );
M>unsigned int S_n = gr.add_rule( "S --> n" );
M>gr.add_left_nonterminal_to_rule( S_n, "S" );
M>gr.add_symbol_to_right_part_of_rule( S_n, "n" );
M>
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Вот мой вариант. На C#, но там все очень просто, думаю разберешься.
Использование:
Grammar g = new Grammar();
g.AddRule("S --> S + n", "S", "S", "+", "n");
g.AddRule("S --> n", "S", "n");
g.PrintRules(Console.Out);
Вывод:
S --> S + n: S --> S(n) +(t) n(t)
S --> n: S --> n(t)
Единственный момент — нетерминальный символ Х может использоваться в правой части только после (или в момент) добавления правила с этим символом в левой части. Т.е. нельзя добавить сначала правило B --> A + t, а потом A --> t2.
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, mefrill, Вы писали:
M>>Ага, на си++.
AVK>А что, на C# никак? Тогда желательно с минимальным использованием STL и без всяких boost и loki.
ну мне удобнее на си++. Можно потом легко переписать.
M>>символ грамматики можно закодировать так:
M>>
AVK>А зачем конструктор без параметров? При его наличии придется делать доступ к полям по записи, а это снижает защиту.
Дело в том, что я символы в векторе размещаю, а там конструктор по умолчанию необходим. На самом деле делать так нехорошо и в рабочей версии такого быть не должно. Но здесь, ради простоты, можно так реализовать. Качество кода в данном случае мне кажется неважным, главное чтобы идея аллгоритма была понятна.
M>>нужны еще правила. Каждое правило содержит нетерминал в левой части и вектор символов в правой части. M>>
Я считаю, что это самый быстрый способ для хранения. Вообще, лучший способ хранить грамматику — это использовать три вектора: вектор терминалов, вектор нетерминалов и вектор правил, где каждый элемент правила — это просто индекс в первых двух векторах. В алгоритм Эрли это все легко укладывается и работает хорошо. Хотя, все несомненно, обсуждается.
M>>теперь грамматика. Содержит коллекцию символов и несколько методов чтобы добавлять новые символы и производить поиск по ним. Также содержит коллекцию правил и методы для добавления в правила символов.
M>>
AVK>Совсем не понял? Зачем нам глобальный список Symbol? Почему нельзя локально хранить их список внутри каждого правила? Просто чтобы обеспечить быстрое сравнение по указателям одних и тех же символов в разных правилах? Тогда куда лучше сделать NameTable, который при добавлении будет имя ресолвить в приделах грамматики (тем более что ты один фиг их ресолвишь по имени конструировании правила). В итоге получим и сравнение по указателям и чистый несвязный код.
Ну да, в реальности ничего не сравнивается по строкам. Каждому символу грамматики дается индекс в векторах, о которых я говорил выше. И все сравнения идут на индексах. Получается очень быстро и удобно.
В общем, код я щас написал рабочий и без оптимизации. Даю ниже, мне кажется там несложно. С удовольствием отвечу на все вопросы. И еще, код этот только для иллюстрации работаы алгоритма, так об эффективности и красоте я совсем не думал.
Я использовал три класса:
класс грамматики, описанный выше.
класс лексера, примитивный, в несколько строк, легко понятен.
класс алгоритма Эрли, называется earley. Оперирует состояниями Эрли (класс state) и ситуациями Эрли (класс item). Вроде ничего там сложного не должно быть. Ниже включаю код по файлам. Код постарался подробно прокомментировать.
lexer.h
#ifndef LEXER_H__
#define LEXER_H__
#include <string>
#include <vector>
typedef std::vector< std::string > input_t;
class lexer{
input_t input_;
int pos_;
public:
lexer():pos_(0){}
void add_to_input( const std::string& _str ) { input_.push_back( _str ); }
std::string get_next()
{
if( pos_ < input_.size() )
{
return input_[ pos_ ++ ];
}
return"EOF";
}
};
#endif// LEXER_H__
grammar.h
#ifndef GRAMMAR_H__
#define GRAMMAR_H__
#include <vector>
#include <map>
#include <string>
struct symbol{
std::string name_;
bool is_terminal_;
symbol(){}
symbol( const std::string& _name, bool _is_terminal )
:
name_(_name),
is_terminal_(_is_terminal)
{}
};
typedef std::vector< symbol > symbols_t;
typedef std::map< std::string, unsigned int > name2index_t;
typedef std::map< unsigned int, std::string > index2name_t;
typedef std::vector< unsigned int > indexes_t;
struct rule{
std::string rule_name_;
unsigned int left_nonterminal_;
indexes_t right_part_;
rule(){}
rule( const std::string& _rule_name )
:
rule_name_(_rule_name)
{}
};
typedef std::vector< rule > rules_t;
class grammar{
unsigned int start_nonterminal_index_;
symbols_t symbols_;
name2index_t name2index_;
index2name_t index2name_;
rules_t rules_;
public:
unsigned int add_symbol( const std::string& _name, bool _is_terminal, bool _is_start = false )
{
unsigned int _cur_index = symbols_.size();
symbols_.push_back( symbol( _name, _is_terminal ) );
if( _is_start ) start_nonterminal_index_ = _cur_index;
name2index_[ _name ] = _cur_index;
index2name_[ _cur_index ] = _name;
return _cur_index;
}
unsigned int add_rule( const std::string& _name )
{
unsigned int _cur_index = rules_.size();
rules_.push_back( rule( _name ) );
return _cur_index;
}
void add_left_nonterminal_to_rule( unsigned int _rule_index, const std::string& _nonterminal_name )
{
rules_[ _rule_index ].left_nonterminal_ = name2index_[ _nonterminal_name ];
}
void add_symbol_to_right_part_of_rule( unsigned int _rule_index, const std::string& _symbol_name )
{
rules_[ _rule_index ].right_part_.push_back( name2index_[ _symbol_name ] );
}
friend class earley;
};
#endif// GRAMMAR_H__
earley.h
#ifndef EARLEY_H__
#define EARLEY_H__
#include"grammar.h"#include"lexer.h"struct item{
unsigned int rule_index_;
unsigned int dot_pos_;
unsigned int origin_;
item(){}
item( unsigned int _rule_index, unsigned int _dot_pos, unsigned int _origin )
:
rule_index_(_rule_index),
dot_pos_(_dot_pos),
origin_(_origin)
{}
};
typedef std::vector< item > items_t;
struct state{
items_t items_;
};
typedef std::vector< state > states_t;
class earley{
grammar& gr_;
lexer& lex_;
states_t states_;
public:
earley( grammar& _gr, lexer& _lex )
:
gr_(_gr),
lex_(_lex)
{}
bool parse();
void print();
private:
bool scanner( unsigned int _state_num );
void predictor( unsigned int _state_num, unsigned int _symbol );
void completer( unsigned int _state_num, unsigned int _item_index );
};
#endif// EARLEY_H__
earley.cpp
#include <iostream>
#include"earley.h"bool earley::parse()
{
// сначала добавляем в нулевое состояние все ситуации, где в правиле тоит начальный
// нетерминал грамматики
states_.push_back( state() );
// проходим по правилам грамматикиfor( unsigned int _rule_index = 0; _rule_index < gr_.rules_.size(); ++ _rule_index )
{
// и добавляем в нулевое состояние ситуации с правилами,
// в которых нетерминал слева - это начальный нетерминал грамматикиif( gr_.start_nonterminal_index_ == gr_.rules_[ _rule_index ].left_nonterminal_ )
{
states_[ 0 ].items_.push_back( item( _rule_index, 0, 0 ) );
}
}
// запускаем последовательно Predictor и Completer на нулевом состоянииfor( unsigned int _item_index = 0; _item_index < states_[ 0 ].items_.size(); ++ _item_index )
{
// если в текущей ситуации точка в конце правой части, то вызываем Completerif( states_[ 0 ].items_[ _item_index ].dot_pos_ == gr_.rules_[ states_[ 0 ].items_[ _item_index ].rule_index_ ].right_part_.size() )
{
completer( 0, _item_index );
}
// если символ после точки - это нетерминал, то вызываем Predictorelse if( ! gr_.symbols_[ gr_.rules_[ states_[ 0 ].items_[ _item_index ].rule_index_ ].right_part_[ states_[ 0 ].items_[ _item_index ].dot_pos_ ] ].is_terminal_ )
{
predictor( 0, gr_.rules_[ states_[ 0 ].items_[ _item_index ].rule_index_ ].right_part_[ states_[ 0 ].items_[ _item_index ].dot_pos_ ] );
}
}
// теперь для каждого состояния сначала инициализируем его вызовом scanner
// а затем дополняем вызовами predictor и completerunsigned int _state_index = 1;
do
{
if( scanner( _state_index - 1 ) )
{
// запускаем последовательно Predictor и Completer на нулевом состоянииunsigned int _item_index = 0;
for( ; _item_index < states_[ _state_index ].items_.size(); ++ _item_index )
{
// если в текущей ситуации точка в конце правой части, то вызываем Completerif( states_[ _state_index ].items_[ _item_index ].dot_pos_ == gr_.rules_[ states_[ _state_index ].items_[ _item_index ].rule_index_ ].right_part_.size() )
{
completer( _state_index, _item_index );
}
// если символ после точки - это нетерминал, то вызываем Predictorelse if( ! gr_.symbols_[ gr_.rules_[ states_[ _state_index ].items_[ _item_index ].rule_index_ ].right_part_[ states_[ _state_index ].items_[ _item_index ].dot_pos_ ] ].is_terminal_ )
{
predictor( _state_index, gr_.rules_[ states_[ _state_index ].items_[ _item_index ].rule_index_ ].right_part_[ states_[ _state_index ].items_[ _item_index ].dot_pos_ ] );
}
}
// если scanner не добавил ни одной ситуации в текущее состояниеif( _item_index == 0 ) return false;
}
else break;
} while( _state_index ++ < states_.size() );
// проверяем вывелась ли текущая строка в данной грамматике или нетfor( unsigned int _item_index = 0; _item_index < states_[ _state_index - 1 ].items_.size(); ++ _item_index )
{
item& _cur_item = states_[ _state_index - 1 ].items_[ _item_index ];
// если в текущей ситуации точка в конце правой части и origin равен нулюif( _cur_item.dot_pos_ == gr_.rules_[ _cur_item.rule_index_ ].right_part_.size() && _cur_item.origin_ == 0 )
{
// если символ в левой части правила - это начальные нетерминал грамматикиif( gr_.rules_[ _cur_item.rule_index_ ].left_nonterminal_ == gr_.start_nonterminal_index_ )
{
return true;
}
}
}
return false;
}
// параметр _state_num - номер состояния, которое необходимо обработать, чтобы добавить
// ситуации в следующее состояние _state_num + 1bool earley::scanner( unsigned int _state_num )
{
// читаем следующий символ во входной строке
// если это конец строки, то не добавляем ни одной ситуации в следующее состояние
std::string _next_symbol = lex_.get_next();
if( "EOF" == _next_symbol ) return false;
// индекс следующего символаunsigned int _next_symbol_index = gr_.name2index_[ _next_symbol ];
// новое состояние
states_.push_back( state() );
// проходим по ситуациям в состоянии под номером _state_num
items_t::iterator it = states_[ _state_num ].items_.begin(), end = states_[ _state_num ].items_.end();
for( ; it != end; ++ it )
{
// если точка не последняя в правой части правилаif( gr_.rules_[ (*it).rule_index_ ].right_part_.size() > (*it).dot_pos_ )
{
// если символ после точки совпадает с текущим символом входной строкиif( gr_.rules_[ (*it).rule_index_ ].right_part_[ (*it).dot_pos_ ] == _next_symbol_index )
{
// добавляем эту ситуацию в следующее состояние, предварительно передвинув
// точку в правой части правила на символ правее
states_[ _state_num + 1 ].items_.push_back( item( (*it).rule_index_, (*it).dot_pos_ + 1, (*it).origin_ ) );
}
}
}
return true;
}
// параметр _state_num - номер теущего состояния
// параметр _symbol - нетерминал, для которого мы будем добавлять ситуации в текущее состояние.
// если _symbol - индекс нетерминала A, то добавим в текущее состояние все ситуации вида [A --> * alpha, _state_num]
// для каждого правила A --> alpha грамматикиvoid earley::predictor( unsigned int _state_num, unsigned int _symbol )
{
// проходим по правилам грамматикиfor( unsigned int _rule_index = 0; _rule_index < gr_.rules_.size(); ++ _rule_index )
{
// если символ в левой части правила равен переданному как параметр, то добавляем ситуацию в текущее состояниеif( gr_.rules_[ _rule_index ].left_nonterminal_ == _symbol )
{
// сначала проверим, что такой ситуации еще нет в данном состоянииbool _rule_is_in_state = false;
items_t::iterator it = states_[ _state_num ].items_.begin(), end = states_[ _state_num ].items_.end();
for( ; it != end; ++ it )
{
if( (*it).rule_index_ == _rule_index && (*it).dot_pos_ == 0 && (*it).origin_ == _state_num )
{
_rule_is_in_state = true;
break;
}
}
// если такой ситуации нет в данном состоянии, то добавляем ееif( ! _rule_is_in_state ) states_[ _state_num ].items_.push_back( item( _rule_index, 0, _state_num ) );
}
}
}
// параметр _state_num - номер текущего состояния
// параметр _item_index - номер ситуации вида [A --> alpha *, i]. Мы должны пойти в состояние номер i
// и нацти там все ситуации, где символ после точки равен символу A и добавить их в текущее состояние
// предварительно сдвинув точку в правой части правила на символ правееvoid earley::completer( unsigned int _state_num, unsigned int _item_index )
{
// мы имеем ситуацию вида [A --> alpha *, i]
// проходим по все ситуациям в состоянии под номером i
items_t::iterator it = states_[ states_[ _state_num ].items_[ _item_index ].origin_ ].items_.begin(),
end = states_[ states_[ _state_num ].items_[ _item_index ].origin_ ].items_.end();
for( ; it != end; ++ it )
{
// если точка не последняя в правой части правилаif( gr_.rules_[ (*it).rule_index_ ].right_part_.size() > (*it).dot_pos_ )
{
// если символ после точки равен символу в евой части правила нашей ситуации
// то добавляем эту ситуацию в текущее состоянии, сдвинув точку на символ правееif( gr_.rules_[ (*it).rule_index_ ].right_part_[ (*it).dot_pos_ ] == gr_.rules_[ states_[ _state_num ].items_[ _item_index ].rule_index_ ].left_nonterminal_ )
{
// сначала проверим, что такой ситуации еще нет в текущем состоянииbool _rule_is_in_state = false;
items_t::iterator it_cur = states_[ _state_num ].items_.begin(), end_cur = states_[ _state_num ].items_.end();
for( ; it_cur != end_cur; ++ it_cur )
{
if( (*it_cur).rule_index_ == (*it).rule_index_
&& (*it_cur).dot_pos_ == (*it).dot_pos_
&& (*it_cur).origin_ == (*it).origin_ )
{
_rule_is_in_state = true;
break;
}
}
// если такой ситуации нет в данном состоянии, то добавляем ееif( ! _rule_is_in_state ) states_[ _state_num ].items_.push_back( item( (*it).rule_index_, (*it).dot_pos_ + 1, (*it).origin_ ) );
}
}
}
}
void earley::print()
{
states_t::iterator it = states_.begin(), end = states_.end();
for( ; it != end; ++ it )
{
std::cout << "********************************************************\n";
items_t::iterator it_item = (*it).items_.begin(), end_item = (*it).items_.end();
for( ; it_item != end_item; ++ it_item )
{
std::cout << "[" << gr_.symbols_[ gr_.rules_[ (*it_item).rule_index_ ].left_nonterminal_ ].name_ << "-->";
unsigned int _rp_index = 0;
for( ; _rp_index < gr_.rules_[ (*it_item).rule_index_ ].right_part_.size(); ++ _rp_index )
{
if( _rp_index == (*it_item).dot_pos_ ) std::cout << "*";
std::cout << gr_.symbols_[ gr_.rules_[ (*it_item).rule_index_ ].right_part_[ _rp_index ] ].name_;
}
if( _rp_index == (*it_item).dot_pos_ ) std::cout << "*";
std::cout << ", " << (*it_item).origin_ << "]\n";
}
std::cout << "--------------------------------------------------------\n";
}
}
main.cpp
#include <iostream>
#include"earley.h"int main()
{
grammar gr;
gr.add_symbol( "S", false, true );
gr.add_symbol( "n", true );
gr.add_symbol( "+", true );
unsigned int S_S_plus_n = gr.add_rule( "S --> S + n" );
gr.add_left_nonterminal_to_rule( S_S_plus_n, "S" );
gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "S" );
gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "+" );
gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "n" );
unsigned int S_n = gr.add_rule( "S --> n" );
gr.add_left_nonterminal_to_rule( S_n, "S" );
gr.add_symbol_to_right_part_of_rule( S_n, "n" );
lexer lex;
lex.add_to_input( "n" );
lex.add_to_input( "+" );
lex.add_to_input( "n" );
earley parser( gr, lex );
if( parser.parse() ) std::cout << "parsing well done\n";
else std::cout << "parsing is failed\n";
parser.print();
return 0;
}
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, mefrill, Вы писали:
AVK>Вот мой вариант. На C#, но там все очень просто, думаю разберешься.
Ага, там есть одно неудобство, о котором я пока не хотел говорить. Дело в том, что когда алгоритм Эрли работает, он должен как-то взаимодействовать с обработчиком правил. Это взаимодействие легко реализовать, если использовать перечисления для именования правил. Тогда, при обработке того или иного правила, специальной функции-обработчику будет передаваться это перечисление — индекс правила. и в коде обработчика легко потом можно такую обработку реализовать. Хотя, конечно, можно сделать все как в бизоне, в тексте программы определить непосредственно все процедуры обработки правил, а сам конструктор парсера вставит их в генерируемый текст, но для аллгоритма Эрли такой подход кажется мне не очень хорошим. Хотя, понятно, все это обсуждается и я легко могу ошибаться. В общем, что я имею ввиду: для каждого правила определить перечисление и передавать его как индекс в функцию добавления правила в грамматику. Что-то типа такого.
Здравствуйте, mefrill, Вы писали:
AVK>>А зачем конструктор без параметров? При его наличии придется делать доступ к полям по записи, а это снижает защиту.
M>Дело в том, что я символы в векторе размещаю, а там конструктор по умолчанию необходим.
Т.е. это технический момент и в версии на C# можно без них?
M>Я считаю, что это самый быстрый способ для хранения. Вообще, лучший способ хранить грамматику — это использовать три вектора: вектор терминалов, вектор нетерминалов и вектор правил, где каждый элемент правила — это просто индекс в первых двух векторах. В алгоритм Эрли это все легко укладывается и работает хорошо. Хотя, все несомненно, обсуждается.
Я думал на эту тему. Но вопрос разнесения терминалов и нетерминалов по разным спискам мне не показался бесспорным.
M>Ну да, в реальности ничего не сравнивается по строкам. Каждому символу грамматики дается индекс в векторах, о которых я говорил выше. И все сравнения идут на индексах. Получается очень быстро и удобно.
Так указатели тоже неплохо сравнивать, притом нет лишней косвенности, а код получается проще.
M>typedef std::vector< std::string > input_t;
Т.е. у тебя на вход подается уже порезанная на лексемы строка?
M> std::string get_next()
Надо бы специальный класс для лексемы сделать.
M>struct state{ M> items_t items_; M>};
А смысл в этом классе?
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, mefrill, Вы писали:
M>Ага, там есть одно неудобство, о котором я пока не хотел говорить. Дело в том, что когда алгоритм Эрли работает, он должен как-то взаимодействовать с обработчиком правил.
В прототипе обыкновенные события с экземпляром Rule в парметрах. В реальном парсере автогенеренные свитчи. В качестве промежуточного решения можно использовать класс, размеченный атрибутами с описанием правил.
public delegate void RuleHandler(ParserContext context);
public class ParseHandler
{
[Rule("S", "S", "+", "n")]
public void Rule1(ParserContext context)
{
...
}
[Rule("S", "n")]
public void Rule2(ParserContext context)
{
...
}
}
...
Grammar g = new Grammar(typeof (ParseHandler));
Реализация такая: в конструкторе при помощи рефлекшена пробегаем по методам и собираем грамматику (либо всю грамматику храним отдельно, а в атрибуте тело правила не указываем). Имя правила = имени метода. По самому методу конструируется делегат, который запихивается в Dictionary<string, RuleHandler> или Dictionary<Rule, RuleHandler>. Ну а потом просто вызываем делегат. Совсем в релизе можно в хешике вместо делегата хранить целое число, которое потом пользовать в генеренном свитче.
M>Хотя, конечно, можно сделать все как в бизоне, в тексте программы определить непосредственно все процедуры обработки правил, а сам конструктор парсера вставит их в генерируемый текст, но для аллгоритма Эрли такой подход кажется мне не очень хорошим.
Согласен. Особенно весело становится, когда нужно у парсера делать в разных случаях разный выход. Например (реальный случай) для дизайн-тайма и рантайма нужны по разному оптимизированные разновидности AST. Эмбеддед-подход в таком разе несколько неудобен.
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Т.е. это технический момент и в версии на C# можно без них?
Да, конечно.
M>>Я считаю, что это самый быстрый способ для хранения. Вообще, лучший способ хранить грамматику — это использовать три вектора: вектор терминалов, вектор нетерминалов и вектор правил, где каждый элемент правила — это просто индекс в первых двух векторах. В алгоритм Эрли это все легко укладывается и работает хорошо. Хотя, все несомненно, обсуждается. AVK>Я думал на эту тему. Но вопрос разнесения терминалов и нетерминалов по разным спискам мне не показался бесспорным.
В бизоне используется один вектор и сначала идут терминалы, а только затем нетерминалы. Таким образом, не надо хранить дополнительный булевский параметр в структуре. Здесь, на самом деле, целое поле для фантазии.
M>>typedef std::vector< std::string > input_t;
AVK>Т.е. у тебя на вход подается уже порезанная на лексемы строка?
Нет, это я просто написал для простоты. На самом деле лексер должен возвращать перечисление входного терминальног осимвола, это наверное, лучший вариант.
M>> std::string get_next() AVK>Надо бы специальный класс для лексемы сделать.
Да, конечно.
M>>struct state{ M>> items_t items_; M>>}; AVK>А смысл в этом классе?
Ну это как-бы заготовка пока. Вообще как раз туда разные фигни для оптимизации можно поставить.
Здравствуйте, mefrill, Вы писали:
M>В бизоне используется один вектор и сначала идут терминалы, а только затем нетерминалы. Таким образом, не надо хранить дополнительный булевский параметр в структуре. Здесь, на самом деле, целое поле для фантазии.
А как ты предлагаешь? Базовый класс Symbol и два наследника — Terminal и NonTerminal? Или сделать их абсолютно одинаковыми и распознавать просто по списку, в котором хранится? Но как тогда, имея экземпляр Rule, определится какой конкретно символ в правой части по некоторой позиции х?
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, mefrill, Вы писали:
AVK>>А как ты предлагаешь? Базовый класс Symbol и два наследника — Terminal и NonTerminal? Или сделать их абсолютно одинаковыми и распознавать просто по списку, в котором хранится? Но как тогда, имея экземпляр Rule, определится какой конкретно символ в правой части по некоторой позиции х?
M>Да, просто сравнивать позицию. Для идущих первыми терминалов это максимальное число.
Погоди, ты только что предложил хранить их в разных списках.
M> Если номер символа больше этого числа, то значит это нетерминал, меньше или равно, значит терминал.
ИМХО выглядит на редкость криво.
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Проходим по списку S0:
в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки, поэтому пропускаем эту ситуацию. Следующая ситуация — это [S --> * n, 0]. Вот у нее символ после точки равен n. Поэтому, добавляем эту ситуацию в список S1, сдвинув точку на символ правее, имеем ситуацию [S --> n *, 0] в списке S1.
и:
S1 [S --> * n, 0]
[S --> S * + n, 0]
Где ошибка?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, mefrill, Вы писали:
M>Выводится ли строка n+n в нашей граматике? Да, ведь список S3 содержит ситуацию [S --> S + n *, 0], в котрой точка стоит в конце правой части правила, символ в левой части есть начальный нетерминал грамматики и второй компонент правила есть 0.
А что будет если строка не выводится из грамматики?
M>Следующим шагом может быть попытка написать работающий алгоритм Эрли.
Попытался, на выходных, написать реализацию парсера. Для строчки "n + n" вроде как даже работает. Если подсунуть неверную строку, то начиная с некоторого состояния они идут пустыми. Например, для строки "n + + n" выод получается следующим:
Не обращай внимания на грязь вроде "EarleyParser.State". Это я скопировал массив состояний из VS. Я создал некоторый вывод отладочной информации способствующий отладке.
+ [0] State: "([S : *S + n , 0], [S : *n , 0])" EarleyParser.State
+ [1] State: "([S : n *, 0], [S : S *+ n , 0])" EarleyParser.State
+ [2] State: "([S : S + *n , 0])" EarleyParser.State
+ [3] State: "([S : S + n *, 0], [S : S *+ n , 0])" EarleyParser.State
+ [4] State: "([S : S + *n , 0])" EarleyParser.State
Для строки "1 + 2 + 5" следующий:
+ [0] State: "([S : *S + n , 0], [S : *n , 0])" EarleyParser.State
+ [1] State: "([S : n *, 0], [S : S *+ n , 0])" EarleyParser.State
+ [2] State: "([S : S + *n , 0])" EarleyParser.State
+ [3] State: "([S : S + n *, 0], [S : S *+ n , 0])" EarleyParser.State
+ [4] State: "([S : S + *n , 0])" EarleyParser.State
+ [5] State: "([S : S + n *, 0], [S : S *+ n , 0])" EarleyParser.State
Явно прослеживается, что после несовпадения строки парсер начинает работать в холостую. Видимо наличие пустых состояний свидетельсвует о том, что строка не совпала с грамматикой. Так ли это? И если так, то можно ли останавливать парсинг отталкиваясь от того, что новое состояние пусто?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Будем надеяться, что глюков не много, и я правильно понял алгоритм.
В качестве лексера я взял лексер C# 2.0 сгенерированный с помощью генератора парсеров — CocoR.
Грамматика задается классом Grammar. Точнее его методами:
Естественно, что пока-что парсер не делает ничего кроме определения соотвествия входной строки грамматике.
Следующими шагами должны быть создание олноценного парсера с построением деревьев вывода, и создание парсера способного съесть рельную грамматику.
Поясню последнее. На сегодня парсер есть грамматику в форме:
Rules
: Rule
| Rules Rule
;
Rule
: Symbol ":" Symbols
;
Symbols
: Symbol
| Symbols Symbol
;
Причем грамматика должна быть задана в виде вызова методов класса Grammar.
В реальном парсере грамматика должна задаваться в отдельном текстовом файли и должна допускать вложенные подправила вида "A : { A B c } A [ c ];" где "{...}" вложенное рекурсивное подправило говорящее что вложенное правило должно применяться ноль или более раз, а "[...]" говорит, что вложенное подправило должно применяться ноль или один раз. Так же возможно вуести вложенное подправило определяюющее, то правило должно применяться один или более раз. Это резко упрощает написание грамматик.
Вопрос тольк в том как преобразовать такую сложную грамматику к более простой используемой в алгоритме?
Далее можно попробовать скормить парсеру грамматику C# 2.0 созданную мной для CocoR и посмотреть на то с какой скорость работает этот.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Для большей понятности алгоритма решил привести код основнх методов:
public bool Parse(int startNonterminalId)
{
PrepareToParse(startNonterminalId);
State state = AddState();
// Получаем индексы правил соотвествующих нетерминалу startNonterminalId.
// и добавляем их в список "нулевого" состояния.
AddPredictions(startNonterminalId, state, 0);
do
{
// ! Количество ситуаций в стостянии может измениться в процессе
// их просмотра . По этому кэшируем их число и делаем перебор простым
// for-ом.int count = state.Count;
for (int i = 0; i < count; i++)
{
Situation sit = state[i];
if (IsComplete(sit))
Completer(sit, state);
else
Predictor(sit, state, 0);
}
}
while (Scanner(ref state));
// Если последнее состояние содержит "законченную" ситуацию, т.е.
// ситукациювида [A --> X1...Xk *], значит строка соответствует
// грамматике.return GetLastState().Exists(IsComplete);
}
/// <summary>
/// Обрабатывает следующий терминал входной строки добавляя в новое
/// состояние все правила из предыдущего состояния у которых символ
/// за точкой совпадает со считанный терминальным символом.
/// </summary>
/// <remarks>
/// Описание mefrill:
/// Scanner — работает только с терминальными символами. Scanner работает
/// на некотором списке state когда тот уже заполнен плностью, т.е. туда
/// больше ничего добавить нельзя. Поэтому настает время перейти к
/// заполнению следующего списка nextState. Т.е. Scanner вызывается для
/// инициализации каждого списка S1...Sn, а список S0 инициализируется
/// особым образом. Что делает Scanner? Он сравнивает символ Next() во
/// входной терминальной строке с символом после точки в каждой ситуации
/// из state и, если символ после точки совпадает с символом Next(), то
/// Scanner добавляет эту ситуацию в список nextState, преварительно
/// передвинув точку в правой части правила ситуации на символ правее.
/// </remarks>
/// <param name="state">Текущее состояние.</param>
/// <returns>Нужно ли продолжать сканирование.</returns>bool Scanner(ref State state)
{
Token token = Next(); // Считываем следующий треминал входной строки.if (token.kind == Tokens.EOF)
return false; // Если это конец строки, то прекращаем парсинг.
State nextState = AddState(); // Создаем следующее состоянеие.foreach (Situation sit in state)
if (DotSymId(sit) == token.kind)
// Если символ за точкой совпадает со считанный терминальным символом,
// добавляем символ в новое состояние продвигая в нем точку вперед.
nextState.Add(sit.CloneWithMoveDot());
state = nextState; // Делаем следующее состояние текущем.return true;
}
/// <summary>
/// Операция Predictor, примененная к ситуации
/// [B --> alpha * A beta, j], принадлежащей списку Si, делает следующее:
/// 1. Проходит по правилам грамматики.
/// 2. Для каждого правила вида A --> delta, где символ в левой части
/// совпадает с символом после точки, добаляет в список Si ситуацию
/// [A --> * delta, i].
/// </summary>
/// <param name="sit">Обрабатываемая ситуация.</param>
/// <param name="state">Текущее состояние.</param>
/// <param name="stateIndex">Индекс текущего состояния.</param>void Predictor(Situation sit, State state, int stateIndex)
{
Debug.Assert(!IsComplete(sit));
// Получаем символ на идущий после точки.int dotSymId = DotSymId(sit);
// Если символ после точки в ситуации является нетерминальным
// и он не является самым левым символом правила этой ситуации...if (IsNonterminal(dotSymId) && dotSymId != Rule(sit).LeftSymbol)
// то добавляем правила для нетерминала dotSymId в текущее состояние.
AddPredictions(dotSymId, state, stateIndex);
}
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, 0));
}
/// <summary>
/// Операция Completer, примененная к ситуации [A --> X1...Xk *, j],
/// принадлежащей списку Si, делает следующее:
/// </summary>
/// <param name="sit">Ситуация [A --> X1...Xk *, j]</param>
/// <param name="state">Si</param>void Completer(Situation sit, State state)
{
Debug.Assert(IsComplete(sit));
int leftSymbol = GetLeftSymbol(sit);
// 1. Проходит по всем ситуациям списка Sj.foreach (Situation sit2 in _states[sit.CreationState])
{
// 2. Если в ситуации символ
// /* VladD2: видимо речь идет о текущем ситуации из Sj, t.e. sit2 */
// после точки есть символ A,
// то добавляет эту ситуацию в список Si, сдвинув предварительно
// точку в правой части на символ правее.if (leftSymbol == DotSymId(sit2))
state.Add(sit2.CloneWithMoveDot());
}
}
Собственно очень приятно, что алгоритм очень простенький. Хотя как бы его простота не вышла боком для производительности.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
алгоритм на Шарпе и работающий проект.
M>> Влад может тоже самое на си шарп реализовать. Надо сначала реализовать грамматику, так чтобы по символам поиск предиктором делать.
AVK>Достаточно пока реализовать AST грамматики и для тестов заполнять ее программно. А потом уже сделать ее парсер на себе самом.
Так и сделал. Правила описываются примитивным классом Rule. К сожалению, он весь из int-ов, так что для его визуализации во время отладки пришлось похимичить. В общем, в отладочном режиме грамматика и парсер должны быть в единственном экземлпяре, так как ситуации для своей визуализации используют глобальную ссылку на них.
M>>символ грамматики можно закодировать так:
M>>
Здравствуйте, VladD2, Вы писали:
AVK>>А почему хранятся индексы, а не указатели?
VD>Так проще. Да и на Шарпе так должно быть быстрее. Все же райт-барьер отсекается. VD>А вообще — это же математики. У них указателей в логике нет.
Так не проще, так безопаснее
Вот из-за выделенной строки:
хранение ссылок в виде указателей будет черевато ошибками. Если при очередном добавлении элемента в symbols_ произойдет перераспределение памяти (когда symbols_.size() == symbols.capacity()), то все указатели на элементы в symbols_ окажутся повисшими. Если же ссылки на элементы в symbols_ делаются через индексы, то такой проблемы нет.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Эта тема посвящена обсуждению алгоритма Эрли. Просьба, не устраивать из нее дисскуссионный зал, по не связанной с этой метой вопросам.
Весь остальной офтопик будет удаляться без предупреждения.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Откровенно говоря есть две проблемы. 1. Рабираться, и темболее отлаживать С++-ный код очень не просто. 2. Твоя реализация содежит ряд дизайнерских просчетов, что резко усложняет рабту с ний и приводит к тому, что она не может быть использована в реальных проектах.
Так большой ошибкой является наличие глобальных массивов. Это сразу не позволяет использовать две или более копии пасрсера. Вторая ошибка — это внесение в грамматику стартового символа. Это не позволит парсить отдельные правила (например, отпарсить функцию). В третьих, в коде смешаны понятия Правило и понятие Нетерминальный симовл.
Если учесть, что код слишком большой для стольк простой задачи я бы предпочел бы изучать алгоритм на безе шарповского варианат приведенного мной здесь: Re: Адаптированный алгоритм Эрли — описание
Здравствуйте, mefrill, Вы писали:
M>Я считаю, что это самый быстрый способ для хранения. Вообще, лучший способ хранить грамматику — это использовать три вектора: вектор терминалов, вектор нетерминалов и вектор правил, где каждый элемент правила — это просто индекс в первых двух векторах. В алгоритм Эрли это все легко укладывается и работает хорошо. Хотя, все несомненно, обсуждается.
Я долго думал над тем как лучше хранить символы и пришел к мнению, что лучше их хранить в едином массиве со сквозной нумерацией. Это позволяет упростить в некоторых местах алгоритм.
Правила действительно лучше хранить в отдельном массиве. Хоря не факт, что имеет смыслссылаться на правила с помощью индекса. Возможно лучше правда использовать указатели. Для С++ это скорее всего так. А для дотнета с его райт-барьером не факт. В общем, нужно сначала заполучить полноценный парсер, а потом погонять его под профайлером.
M>Ну да, в реальности ничего не сравнивается по строкам. Каждому символу грамматики дается индекс в векторах, о которых я говорил выше. И все сравнения идут на индексах. Получается очень быстро и удобно.
Я бы не стал пока что говорить о производительности алгоритма. Уж больно у него много корявых сторон. Что касется доступа к правилам, то носвенная адерсация в виде индекса правила действительно является излишней.
M>В общем, код я щас написал рабочий и без оптимизации. Даю ниже, мне кажется там несложно. С удовольствием отвечу на все вопросы. И еще, код этот только для иллюстрации работаы алгоритма, так об эффективности и красоте я совсем не думал.
Фиг бы с ней с эффективностью. А вот то что не думал о красоте — это очень плохо. Разбираться в таком коде не просто.
M>Я использовал три класса:
M>класс грамматики, описанный выше. M>класс лексера, примитивный, в несколько строк, легко понятен. M>класс алгоритма Эрли, называется earley. Оперирует состояниями Эрли (класс state) и ситуациями Эрли (класс item). Вроде ничего там сложного не должно быть. Ниже включаю код по файлам. Код постарался подробно прокомментировать.
А зачем state было делать отдельным классом? По-моему это просто вектор.
И почему Ситуация названа item? Бессмыслица полная. Я назвал ее Situation.
origin_
Я назвал это поле CreationState. Я правильно понял суть этого поля?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
AVK>>>А зачем конструктор без параметров? При его наличии придется делать доступ к полям по записи, а это снижает защиту.
M>>Дело в том, что я символы в векторе размещаю, а там конструктор по умолчанию необходим.
AVK>Т.е. это технический момент и в версии на C# можно без них?
Да.
M>>Я считаю, что это самый быстрый способ для хранения. Вообще, лучший способ хранить грамматику — это использовать три вектора: вектор терминалов, вектор нетерминалов и вектор правил, где каждый элемент правила — это просто индекс в первых двух векторах. В алгоритм Эрли это все легко укладывается и работает хорошо. Хотя, все несомненно, обсуждается.
AVK>Я думал на эту тему. Но вопрос разнесения терминалов и нетерминалов по разным спискам мне не показался бесспорным.
Более того, это усложнит парсер.
M>>Ну да, в реальности ничего не сравнивается по строкам. Каждому символу грамматики дается индекс в векторах, о которых я говорил выше. И все сравнения идут на индексах. Получается очень быстро и удобно.
AVK>Так указатели тоже неплохо сравнивать, притом нет лишней косвенности, а код получается проще.
Я это дело вынес в функцию, так что можно крутить как хочешь. Только нужно сначало запоулчить пример на котором ожно гонять профайлер. А то еще не факт, что устранение косвенности даст выигрышь в дотнете. Ведь вместо этого начнется барьер записи, и что дороже я не знаю.
M>>typedef std::vector< std::string > input_t;
AVK>Т.е. у тебя на вход подается уже порезанная на лексемы строка?
Я использовал готовый лексер. Так что на это можно забить.
M>>struct state{ M>> items_t items_; M>>};
AVK>А смысл в этом классе?
Вот и я говорю. Я пока что унаследовал Состояние от List<Situation>. Так лучше для отладки. А вообще склоняюсь к тому, что бы сделать состояния просто массивами (Situation[]). Думаю, так будет быстрее всего. В большинстве случаев это позволит устранить контроль выхода за пределы массива, что тоже неплохой бонус.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
M>> Если номер символа больше этого числа, то значит это нетерминал, меньше или равно, значит терминал.
AVK>ИМХО выглядит на редкость криво.
На самом деле выглядит это нормально, если писать как следует:
К тому же мест где терминалы нужно отличать от нетерминалов очень не много. IsNonterminal() используется только один раз, в Predictor(), а IsTerminal() вообще ни разу не используется. Так что можно забить. Зато мест где сквозная нумерация символов помогает очень много.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
AVK>В прототипе обыкновенные события с экземпляром Rule в парметрах. В реальном парсере автогенеренные свитчи. В качестве промежуточного решения можно использовать класс, размеченный атрибутами с описанием правил.
Нет особого смысла делать статические обработчики у динамического парсера. Тогда уж нужно продумывать и генерацию неких таблиц ускоряющих парсинг.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Нет особого смысла делать статические обработчики у динамического парсера.
Ты считаешь что разница между прямым вызовом и вызовом через делегат на фоне парсинга будет незаметна?
VD> Тогда уж нужно продумывать и генерацию неких таблиц ускоряющих парсинг.
Здравствуйте, 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>А зачем еще что-то нужно? Символ == некий идентификатор. Для человека — это строка. Для машины целое число.
Здравствуйте, 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;
все же последний символ долженр быть последним в массиве. Так что все же
Здравствуйте, VladD2, Вы писали:
VD>Так что можете пробовать. Те ком нужен логин позволяющий модифицировать исходники шлите мне на мыло имя логина и пароль.
У тебя там косяк на косяке Логин/пароль прислал. Давай доступ буду фиксить и рефакторить.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, VladD2, Вы писали:
VD>>Да, это я конечно лохонулся. И все из-за тог, что пример слишком простой. WH>
WH>Данная грамматика на такой строке "1 + 1 — 1 + 1" не работает. WH>ИМХО собака порылась в функции Predictor она у тебя както совсем странно реализована.
Нам конечно обещали что парсер крут, но для других парсеро это бред какой-то.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Данная грамматика на такой строке "1 + 1 — 1 + 1" не работает. WH>ИМХО собака порылась в функции Predictor она у тебя както совсем странно реализована.
Здравствуйте, VladD2, Вы писали:
AVK>>Или указатель. VD>На фиг там никакие указатели не уперлись. Еще раз повтояю, ты задолбашся этими указателями ссылаться на разные таблицы. Тут int самое то.
Ну на самом деле и через указатели тоже можно. Есть еще такая идея: завести все помеченные правила посредством перечислений. Т.е. не только правила иметь, а еще и для каждого правила — множество помеченных. Тогда, вместо пары (номер правила, позиция точки) можно просто одно число — номер помеченного правила держать. Правда здесь с увеличением позиции точки гемморой небольшой получается. В общем, экономим память таким образом. Для нескольких миллионов ситуаций — уже экономия. Хотя, лично я, по большому счету здесь выгоды не вижу особой, а только усложнение программной логики.
Здравствуйте, mefrill, Вы писали:
M>Ну на самом деле и через указатели тоже можно. Есть еще такая идея: завести все помеченные правила посредством перечислений. Т.е. не только правила иметь, а еще и для каждого правила — множество помеченных. Тогда, вместо пары (номер правила, позиция точки) можно просто одно число — номер помеченного правила держать. Правда здесь с увеличением позиции точки гемморой небольшой получается. В общем, экономим память таким образом. Для нескольких миллионов ситуаций — уже экономия. Хотя, лично я, по большому счету здесь выгоды не вижу особой, а только усложнение программной логики.
Память не проблема. Проблема — скорость. Нужно думать как избавиться от переборов. Они самое большое зло.
Ладно. Это все фигня. Давай добъем алгоритм до работоспособного состояния, а там я уже скоростью сам займусь. А вось что и выйдет.
Ты лучше объясни по доходчивее свою идею построения деревьев вывода. И за одно расскажи как создавать понятные сообщения об ошибках. А то пока что мы можетм только сказать выводится строка из грамматики или нет.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Я долго думал над тем как лучше хранить символы и пришел к мнению, что лучше их хранить в едином массиве со сквозной нумерацией. Это позволяет упростить в некоторых местах алгоритм. VD>Правила действительно лучше хранить в отдельном массиве. Хоря не факт, что имеет смыслссылаться на правила с помощью индекса. Возможно лучше правда использовать указатели. Для С++ это скорее всего так. А для дотнета с его райт-барьером не факт. В общем, нужно сначала заполучить полноценный парсер, а потом погонять его под профайлером.
В бизоне и у меня в проекте правила хранятся в одном массиве подряд. Сначала левый нетерминал (его индекс), потом правая часть и конец правила помечается -1. Есть еще один массив, индексированный номерами правил, каждый элемент содержит индекс начала соответствующего правила в первом массиве.
VD>А зачем state было делать отдельным классом? По-моему это просто вектор. VD>И почему Ситуация названа item? Бессмыслица полная. Я назвал ее Situation.
В оригинале у Эрли это называется item. Ситуация — это удачный перевод Тихомирова.
VD>origin_ VD>Я назвал это поле CreationState. Я правильно понял суть этого поля?
Ага, верно, но в оригинале origin называется. Я, кстати, хорошего перевода для этого так и не придумал.
Э нет я хочу чтобы было с переди n-сложений и с зади n-сложений, а по середине опционально вычитание.
А не даботает это по тому что у тебя Completer и Predictor реализованы не правильно. Да и в Parse ты накосячил...
Я это дело у себя пофиксил Работает
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
VD>>Для особо требовательных можно просто константу отплеваывать. А вообще, на фоне тормозов самого алгоритма, думаю, эти вызовы будут незаметны. Меня вообще пока что волнует вопрс будет ли этот алгоритм пригоден для реального использования? WH>Скорость это деое техники. Я вот чего не понял так это как сообщения об ошибках получать?
Здравствуйте, VladD2, Вы писали:
VD>Добавил. Пробуй.
Ща отрефакторю и залью.
Кстати у тебя там в некоторых местах в качестве отступов пробелы, а в других табы. Как должно быть?
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
VD>Похоже несоотвествие: VD>
Проходим по списку S0:
VD>в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки, поэтому пропускаем эту ситуацию. Следующая ситуация — это [S --> * n, 0]. Вот у нее символ после точки равен n. Поэтому, добавляем эту ситуацию в список S1, сдвинув точку на символ правее, имеем ситуацию [S --> n *, 0] в списке S1.
VD>и: VD>
S1
VD>[S --> * n, 0]
VD>[S --> S * + n, 0]
VD>Где ошибка?
Конечно, ошибка в [S --> * n, 0], надо чистать так: [S --> n *, 0], т.е. точка на символ правее.
Здравствуйте, WolfHound, Вы писали:
WH>Э нет я хочу чтобы было с переди n-сложений и с зади n-сложений, а по середине опционально вычитание.
Ты имеешь дело с рекурсивной грамматикой. Правило что я привел описывает любые сочетания сложений и вычитаний. Если тебе нужно именно фиксированное количество сложений и в середине не обязательное вычитание, то это нужно делать как-то так:
S : n + n X n + n
X : -
X : +
если под необязательным ты понимашь замену на +.
WH>А не даботает это по тому что у тебя Completer и Predictor реализованы не правильно. Да и в Parse ты накосячил... WH>Я это дело у себя пофиксил Работает
Надо еще поглядеть, что ты там наисправлял.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>А что будет если строка не выводится из грамматики?
Тогда сканер не добавит ни одной ситуации в следующее состояние.
VD>Явно прослеживается, что после несовпадения строки парсер начинает работать в холостую. Видимо наличие пустых состояний свидетельсвует о том, что строка не совпала с грамматикой. Так ли это? И если так, то можно ли останавливать парсинг отталкиваясь от того, что новое состояние пусто?
Здравствуйте, VladD2, Вы писали:
VD>Показать символ на котором возникла проблема можно и так. А точно сказать ошибку... Тут придется или анализировать предыдущее состояние, или даже полностью строить деревья вывода (ведь в это место мы могли прийти более чем одним путем). В общем, здесь бы как раз послушать mefrill.
Здравствуйте, VladD2, Вы писали:
VD>Ты имеешь дело с рекурсивной грамматикой. Правило что я привел описывает любые сочетания сложений и вычитаний. Если тебе нужно именно фиксированное количество сложений и в середине не обязательное вычитание, то это нужно делать как-то так:
1)Ты непровильно преобразовал грамматику.
2)Ты занимаешься подгонкой грамматики под убогие парсеры. Этот и так все сожрет.
VD>Надо еще поглядеть, что ты там наисправлял.
Вобщем залил. Смотри.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Ща отрефакторю и залью.
На будующее. Не совмещай правку логики с правкой форматирования и т.п. В коментариях описывай что изменил. Я вот тупо сижу и смотрю на код не понимая, что реально изменилось.
Не ясно зачем ты всабачил этот билдер. Там и так с производительностью будет кранты, а тут еще одна абстракция.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>public bool Parse(int startNonterminalId)
VD>{
VD> PrepareToParse(startNonterminalId);
VD> State state = AddState();
VD> // Получаем индексы правил соотвествующих нетерминалу startNonterminalId.
VD> // и добавляем их в список "нулевого" состояния.
VD> AddPredictions(startNonterminalId, state, 0);
VD> do
VD> {
VD> // ! Количество ситуаций в стостянии может измениться в процессе
VD> // их просмотра . По этому кэшируем их число и делаем перебор простым
VD> // for-ом.
VD> int count = state.Count;
VD> for (int i = 0; i < count; i++)
VD> {
VD> Situation sit = state[i];
VD> if (IsComplete(sit))
VD> Completer(sit, state);
VD> else
VD> Predictor(sit, state, 0);
VD> }
VD> }
VD> while (Scanner(ref state));
VD> // Если последнее состояние содержит "законченную" ситуацию, т.е.
VD> // ситукациювида [A --> X1...Xk *], значит строка соответствует
VD> // грамматике.
VD> return GetLastState().Exists(IsComplete);
VD>}
VD>/// <summary>
VD>/// Обрабатывает следующий терминал входной строки добавляя в новое
VD>/// состояние все правила из предыдущего состояния у которых символ
VD>/// за точкой совпадает со считанный терминальным символом.
VD>/// </summary>
VD>/// <remarks>
VD>/// Описание mefrill:
VD>/// Scanner — работает только с терминальными символами. Scanner работает
VD>/// на некотором списке state когда тот уже заполнен плностью, т.е. туда
VD>/// больше ничего добавить нельзя. Поэтому настает время перейти к
VD>/// заполнению следующего списка nextState. Т.е. Scanner вызывается для
VD>/// инициализации каждого списка S1...Sn, а список S0 инициализируется
VD>/// особым образом. Что делает Scanner? Он сравнивает символ Next() во
VD>/// входной терминальной строке с символом после точки в каждой ситуации
VD>/// из state и, если символ после точки совпадает с символом Next(), то
VD>/// Scanner добавляет эту ситуацию в список nextState, преварительно
VD>/// передвинув точку в правой части правила ситуации на символ правее.
VD>/// </remarks>
VD>/// <param name="state">Текущее состояние.</param>
VD>/// <returns>Нужно ли продолжать сканирование.</returns>
VD>bool Scanner(ref State state)
VD>{
VD> Token token = Next(); // Считываем следующий треминал входной строки.
VD> if (token.kind == Tokens.EOF)
VD> return false; // Если это конец строки, то прекращаем парсинг.
VD> State nextState = AddState(); // Создаем следующее состоянеие.
VD> foreach (Situation sit in state)
VD> if (DotSymId(sit) == token.kind)
VD> // Если символ за точкой совпадает со считанный терминальным символом,
VD> // добавляем символ в новое состояние продвигая в нем точку вперед.
VD> nextState.Add(sit.CloneWithMoveDot());
VD> state = nextState; // Делаем следующее состояние текущем.
VD> return true;
VD>}
Сканер нормальный.
VD>/// <summary>
VD>/// Операция Predictor, примененная к ситуации
VD>/// [B --> alpha * A beta, j], принадлежащей списку Si, делает следующее:
VD>/// 1. Проходит по правилам грамматики.
VD>/// 2. Для каждого правила вида A --> delta, где символ в левой части
VD>/// совпадает с символом после точки, добаляет в список Si ситуацию
VD>/// [A --> * delta, i].
VD>/// </summary>
VD>/// <param name="sit">Обрабатываемая ситуация.</param>
VD>/// <param name="state">Текущее состояние.</param>
VD>/// <param name="stateIndex">Индекс текущего состояния.</param>
VD>void Predictor(Situation sit, State state, int stateIndex)
VD>{
VD> Debug.Assert(!IsComplete(sit));
VD> // Получаем символ на идущий после точки.
VD> int dotSymId = DotSymId(sit);
VD> // Если символ после точки в ситуации является нетерминальным
VD> // и он не является самым левым символом правила этой ситуации...
VD> if (IsNonterminal(dotSymId) && dotSymId != Rule(sit).LeftSymbol)
VD> // то добавляем правила для нетерминала dotSymId в текущее состояние.
VD> AddPredictions(dotSymId, state, stateIndex);
VD>}
Предиктор непонятный. Мы смотрим, если символ после точки — нетерминальный, то добавляем в наше состояние для каждого правила грамматики с этим символом в левой части — ситуацию, где точка стоит в самом начале правила и номер creation state — номер нашего состояния. В своем коде я сначала проверял не является ли точка в правой части правила — последней. Ведь тогда и проверять нечего за этой точкой никакого символа нет.
VD>private void AddPredictions(int nonterminalId, State state, int stateIndex)
VD>{
VD> Debug.Assert(IsNonterminal(nonterminalId));
VD> foreach (int ruleId in _grammar.NontermRules[nonterminalId])
VD> state.Add(new Situation(ruleId, 0, 0));
VD>}
VD>/// <summary>
VD>/// Операция Completer, примененная к ситуации [A --> X1...Xk *, j],
VD>/// принадлежащей списку Si, делает следующее:
VD>/// </summary>
VD>/// <param name="sit">Ситуация [A --> X1...Xk *, j]</param>
VD>/// <param name="state">Si</param>
VD>void Completer(Situation sit, State state)
VD>{
VD> Debug.Assert(IsComplete(sit));
VD> int leftSymbol = GetLeftSymbol(sit);
VD> // 1. Проходит по всем ситуациям списка Sj.
VD> foreach (Situation sit2 in _states[sit.CreationState])
VD> {
VD> // 2. Если в ситуации символ
VD> // /* VladD2: видимо речь идет о текущем ситуации из Sj, t.e. sit2 */
VD> // после точки есть символ A,
VD> // то добавляет эту ситуацию в список Si, сдвинув предварительно
VD> // точку в правой части на символ правее.
VD> if (leftSymbol == DotSymId(sit2))
VD> state.Add(sit2.CloneWithMoveDot());
VD> }
VD>}
VD>
Нормально тоже. Только там при обращении DotSymId(sit2) учитывается что точка крайней справа стоит (хотя это уже детали реализации).
Здравствуйте, VladD2, Вы писали:
VD>На будующее. Не совмещай правку логики с правкой форматирования и т.п. В коментариях описывай что изменил. Я вот тупо сижу и смотрю на код не понимая, что реально изменилось.
Ладно. Я правил только Parser.cs
VD>Не ясно зачем ты всабачил этот билдер. Там и так с производительностью будет кранты, а тут еще одна абстракция.
Без него алгоритм был не рабочим.
ЗЫ Кстати ты зря в репозитории все в корень кинул. Так нельзя бранчи делать, а мне уже захотелось похимичить. Вобщем я сейчас все перенесу в папку Trunk.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Про использование хэш-таблицы как set. Если тебе не нужно значение, то задавай в качестве его типа какой-нить простой тип. Пойми, для ЖЦ любая ссылка это повод полазить полазить по ссылкам. Плюс райт-барьер.
А еще лучше покоцать пауэр-колекшоны.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Ты бы все же описал алгоритмические изменения. А то их так разглядеть на фоне правки тяжело.
1)Добавил проверку на то что такая ситуация уже есть в состояние.
2)Исправил процедуру Parse ибо в Predictor надо пихать номер состояния, а не то что ты туда запихивал.
3)В процедуре Predictor ты совершенно не понятно зачем проверял dotSymId != Rule(sit).LeftSymbol эта проверка совсем не к месту.
4)Буквально толькочто заметил и исправил определение того порождается ли строка грамматикой.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
VD>>/// <summary>
VD>>/// Операция Predictor, примененная к ситуации
VD>>/// [B --> alpha * A beta, j], принадлежащей списку Si, делает следующее:
VD>>/// 1. Проходит по правилам грамматики.
VD>>/// 2. Для каждого правила вида A --> delta, где символ в левой части
VD>>/// совпадает с символом после точки, добаляет в список Si ситуацию
VD>>/// [A --> * delta, i].
VD>>/// </summary>
VD>>/// <param name="sit">Обрабатываемая ситуация.</param>
VD>>/// <param name="state">Текущее состояние.</param>
VD>>/// <param name="stateIndex">Индекс текущего состояния.</param>
VD>>void Predictor(Situation sit, State state, int stateIndex)
VD>>{
VD>> Debug.Assert(!IsComplete(sit));
VD>> // Получаем символ на идущий после точки.
VD>> int dotSymId = DotSymId(sit);
VD>> // Если символ после точки в ситуации является нетерминальным
VD>> // и он не является самым левым символом правила этой ситуации...
VD>> if (IsNonterminal(dotSymId) && dotSymId != Rule(sit).LeftSymbol)
VD>> // то добавляем правила для нетерминала dotSymId в текущее состояние.
VD>> AddPredictions(dotSymId, state, stateIndex);
VD>>}
M>
M>Предиктор непонятный. Мы смотрим, если символ после точки — нетерминальный, то добавляем в наше состояние для каждого правила грамматики с этим символом в левой части — ситуацию, где точка стоит в самом начале правила и номер creation state — номер нашего состояния.
Там была ошибка. Последним параметром конечно нужно было передавать stateIndex (выделено жирным).
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));
}
M> В своем коде я сначала проверял не является ли точка в правой части правила — последней. Ведь тогда и проверять нечего за этой точкой никакого символа нет.
Проверять ничего не нужно "Debug.Assert(!IsComplete(sit));" гарантирует, что в процедуру не прийдет ничего ненужного. А сама проверка делается в процедуре парсинга. Ведь Predictor и Completer взаимо исключающие функции. IsComplete(sit) как раз говорит что точка стоит в позиции за последним символом правила.
ЗЫ
Там Вольфхаунд уже чето-то наваял. Теперь прийдется разбираться, что он там навял.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
VD>>Не ясно зачем ты всабачил этот билдер. Там и так с производительностью будет кранты, а тут еще одна абстракция. WH>Без него алгоритм был не рабочим.
Что там было не рабочего? По пунктам, плиз.
WH>ЗЫ Кстати ты зря в репозитории все в корень кинул. Так нельзя бранчи делать, а мне уже захотелось похимичить. Вобщем я сейчас все перенесу в папку Trunk.
Нелюблю я эту химию. По мне так, хочешь химичить, химичь за пределами репозитория.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>У меня сейчас возникла совершенно шальная мысль: А что если выкинуть к чертовой бабушке List<State> _states и в Situation заменить int _creationState на Situation _parentSituation. WH>Мотив: При парсинге порождается масса объектов класса Situation подавляющие число которых не используются для дальнейшего вывода. Но из-за List<State> _states на них хранятся ссылки и GC с ними возится. Если же на них не будет ссылок то подавляющее колличество ситуаций будут умирать в нулевом поколении. Плюс мы избавляемся от поиска в Completer'е. WH>Вобщем я завтра это реализую и посмотрим что получится.
List<State> необходим для построения деревьев вывода. Так что устранять его нельзя!
Да и как от него можно избавитья в Completer я тоже не понимаю.
ЗЫ
Кстати, поиск по хэш-таблице занимает львиную долю работы алгоритма.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
VD>Попробовал на переделанном Вольфхаундом варианте програть грамматику вида: VD>
VD>S : S - S
VD>S : S + S
VD>S : n
VD>
VD>Это дело тормозит порядка 4 секунд! Правда на грамматике вида: VD>
VD>S : S - n
VD>S : S + n
VD>S : n
VD>
VD>Отрабатывает за 0.07 секунды даже на в пятеро большей строке.
VD>Таким скорость работы алгоритма сильно зависит от грамматики. VD>Не очень любит этот алгоритм и левую рекурсию.
Нет, здесь дело не в рекурсии. Первая грамматика неоднозначная. Там просто огромное количество деревьев вывода входной строки строится. Когда мы добавим в парсер методы дл построения деревьев вывода, увидишь сколько. А вторая грамматика однозначная, поэтому только одно дерево построено. Вот что можно в парсер будет добавить — это операторы разрешения неоднозначности на основе приоритетов, типа как в бизоне. Чтобы на таких грамматиках меньше тормозила.
Здравствуйте, VladD2, Вы писали:
VD>Кстати, а ты эти статьи в чем подготавливашь? А то уж больно неудобно с этими ПДФ-ами. В твоих ПДФ-ах даже номеров страниц нет.
На ворде, на тех все никак не могу сподобиться. Могу вордовские документы присоеденить. Только там нет места уже.
Здравствуйте, VladD2, Вы писали:
VD>Здорово. Но нужно обяснение построения деревьев выводов.
Это только к концу недели, к сожалению, совсем нет времени. Пока можно заняться оптимизацией оригинального алгоритма. Каждую из операций можно оптимизировать. Для этого:
1. Держать в состоянии не один список ситуаций, а столько списков — сколько символов в грамматике + 1. Каждый список, построенный для конкретного символа грамматики, содержит ситуации, у которых этот символ стоит после точки, и еще один список для ситуаций, у которых точка в самом конце. Тогда и комплитер и сканер не будут ничего искать в состоянии, а сразу ходить по спискам для своего символа. Это очень важная вещь, ускоряет разбор сильно.
2. Также организовать хранение правил грамматики, т.е. для каждого нетерминала хранить список правил с этим нетерминалом в левой части. Тогда предиктор тоже по всей грамматике искать не будет и сразу возмет все правила с данным нетерминалов в левой части. Кроме того, чтобы не делать проверку на то, что для данного нетерминала в данном состоянии предиктор уже был проведен (ведь реально он проводится для нетерминала, а не для ситуации!). В общем, держать булевский вектор, индексированный нетерминалами грамматики и ставить проверять соответствующий элемент перед тем как операцию предиктор для данного нетерминала выполнять.
Для парсера можно добиться скорости 30 килобайт текста за секунду на сишной грамматике. Это уже сделано, так что вполне возможно.
Здравствуйте, VladD2, Вы писали:
VD>А что ты собрался хранить в Symbol?
В контексте парсинга пофигу. Главное это то, что указатель на этот объект является идентификатором символа.
VD> Symbol — может быть или строкой или целочисленным идентификатором. Представлять его классом смысла нет.
Представлять его классом появляется смысл, когда строим грамматику и когда формируем сообщение об ошибке. Может еще в каких сервисных кусках.
VD>На фиг там никакие указатели не уперлись. Еще раз повтояю, ты задолбашся этими указателями ссылаться на разные таблицы. Тут int самое то.
Здравствуйте, VladD2, Вы писали:
VD>Не понял. Зачем?
Для того чтобы работал Completer
foreach (Situation sit2 in _states[sit.CreationState])
VD>Так было сказано в описании.
Где? Небыло там такого да и не нужно это.
VD>В общем, если я не правильно понял как должен быть устроен Predictor, то рассказывай как он по-твоему должен быть устроен.
Так как он сейчас устроен.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Что там было не рабочего? По пунктам, плиз.
Если убрать твои косяки то алгорит ничинал зацикливатся.
VD>Нелюблю я эту химию. По мне так, хочешь химичить, химичь за пределами репозитория.
Ну я и буду химичить в отдельной ветке репозитория. Для того бранчи и придуманны.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Адаптированный алгоритм Эрли - описание расширения
Есть немного времени, начну описывать как работает расширение оригинального алгоритма Эрли (ОАЭ) — адаптированный алгоритм Эрли (ААЭ).
Прежде всего, ААЭ работает с расширенной ситуацией Эрли. Как мы помним, оригинальная ситуация содержит два компонента: помеченное правило и номер состояния рождения. Мы дополним ситуацию еще двумя компонентами. Первый из них — это ссылка на другую ситуацию Эрли, в дереве вывода это левый узел-брат узла, который обозначает наша ситуация, а именно: если мы имеем ситуацию вида [A --> X1...Xk * Xk+1...Xn, i, l], то ссылка l будет ссылаться на ситуацию вида [A --> X1...Xk-1 * Xk...Xn, i, l1], т.е. на ситуацию с тем же правилом и номером рождения, но с точкой на символ левее. Еще один дополнительный компонент ситуации — это список ссылок на такие же ситуации Эрли. Заметим, что когда мы держим ситуации в списке состояния, мы различаем в нем состояния с первыми тремя различными компонентами, т.е. для различения ситуаций мы используем помеченное правило, номер сотояния рождения и ссылку l, а четвертый компонент — список ссылок на ситуации, в различении не используется. Например, в списке состояния у нас могут быть две ситуации вида [A --> X1...Xk * Xk+1...Xn, i, l, <s>] и [A --> X1...Xk * Xk+1...Xn, i, l1, <s>], где все компоненты, кроме ссылок l и l1, совпадают. Иначе говоря, при добавлении ситуации в список, мы просматриваем есть ли уже в этом списке ситуация с совпадающими тремя копонентами, и если есть, то не добавляем в список нашу ситуацию. Итак, расширенная ситуация Эрли — это четверка вида [A --> X1...Xk * Xk+1...Xn, i, l, <s>], где A --> X1...Xk * Xk+1...Xn — помеченное правило, i — номер состояния рождения, l — ссылка на ситуацию и <s> — список ссылок на ситуации.
Мы модифицируем операции Predictor, Completer и Scanner так, чтобы они работали с расширенными ситуациями.
1. Predictor — самая простая модификация. При добавлении новой ситуации в состояние этой операцией, мы просто устанавливаем ссылку l в нуль, а список <s> делаем пустым. Все остальное остается как было.
2. Scanner — мы добавляем ситуацию вида [A --> X1...Xk * Xk+1...Xn, i, l, <s>] в состояние Si+1 если мы обрабатываем ситуацию [A --> X1...Xk-1 * Xk...Xn, i, l1, <s1>] в состоянии Si и символ Xk равен символу ai+1 входной строки. Вот мы устанавливаем ссылку l на эту ситуацию. Список <s> также оставляем пустым, все остальное как прежде.
Замечу, что в этих двух операциях при добалении ситуации в список мы уверены, что этих ситуаций в списке еще нет. Для Scanner это справедливо по определению этой операции, а для Predictor проверку на присутсвие тоже можно не устраивать если проверять не ситуацию на присутствие в списке, а обработку нетерминала грамматики, в результате которой эта ситуация попадает в список при обработке этого нетерминала операцией Predictor.
3. Completer. При добавлении ситуации в список прежде всего проверяем нет ли там уже ситуации с первыми тремя компонентами такими же как у нашей. Если нет, добавляем ситуацию в список, ссылку l устанавливаем на ситуацию, у которой точка на символ левее, а в список <s> добавляем единственный элемент — ссылку на ситуацию, которая явилась мотивом для добавления нашей. Т.е. если мы добавляем ситуацию вида [A --> X1...Xk * Xk+1...Xn, i, l, <s>] в состояние Sp, то это значит, что в Sp есть ситуация вида [Xk --> alpha *, j, l1, <s1>], а в Sj есть ситуация вида [A --> X1...Xk-1 * Xk...Xn, i, l2, <s2>]. Вот ссылку l делаем равной [A --> X1...Xk-1 * Xk...Xn, i, l2, <s2>], а в список <s> добавляем ссылку на [Xk --> alpha *, j, l1, <s1>]. Если в списке уже есть такая ситуация, то просто добавляем ссылку на [Xk --> alpha *, j, l1, <s1>] в список <s>.
Буду ждать вопросов и замечаний.
Re[2]: Адаптированный алгоритм Эрли - описание расширения
1.Есть рабочая ( видимо ) реализация алгоритма на lisp. Отличия от оригинальной версии только в способе создания и представления результата разбора- стороится одно дерево (точнее напавленный граф), в котором специальными вершинами кодируются неоднозначности,это дерево содержит все варианты разбора входной строки.
2.Для некоторых грамматик количество вариантов разбора вообще говоря неограничено.
Пример
S --> A
A --> B
B --> A
B --> "a"
Варианты разбора S --> B --> A --> "a" или S --> B --> A --> B --> A --> "a" или S --> B --> A --> B --> A --> "a" и так далее... В таких ситуациях можно либо отбрасывать часть варианов разбора либо закодировать в получившемся дереве возникшую ситуацию. На самом деле достататчно допустить возможность ссылаться на элемент находящийся выше в дереве. В примере выше получается что-то вроде
<----
| |
S-->B-->A -->"a"
То есть дерево превращается в направленный граф.
Понятно что анализатор должен уметь это обрабатывть чтобы не попасть в бескончный цикл.
3.Было бы интересно научить парсер проверять какие нетерминалы в грамматики являются однозначными (хотя бы эмпирический алгоритм).
4.Немного тестов.
a.
S --> "a" S A A A
S -->
A --> "a"
A -->
Вход "a" "aa" "aaa" "aaaa"
b.
S --> "a" S A A A
S -->
A --> "a"
A -->
Вход "a" "aa" "aaa" "aaaa"
c.
S --> "a" D "ad"
S --> B D "ab"
D --> "a" A B
A --> "a" B B
A -->
B -->
Вход "aaab"
d.
S --> "b" A
A --> "a" A B
A -->
B -->
Вход "baa"
Здравствуйте, AndrewVK, Вы писали:
AVK>Да в чем разница то? И то и другое целое число.
Ага. Только одно в диапазоне от intPtr.MinValue до intPtr.MaxValue, а второе в диапазане таблицы символов. В итоге с помощью второго я могу организовывать любые таблицы, а первое только применять в качестве ключа хэш-таблицы.
В общем, идея фиговая.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
V>Попробуйте задавать низкий load factor, должно быть чуть быстрее.
Это скорее всего бессмысленно. Дотнетные хэш-таблицы и так перестраиваются (имеют неплохой load factor).
Надо попробовать другое... создать структру реализующую IEqualityComparer<Situation>. Это позвлит заинлайнить вызовы GetHashCode и Equals. Похоже проблема в их огромном количестве вызовов. Потом нужно еще проверить качество хэш-кода.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, VladD2, Вы писали:
VD>>Не понял. Зачем? WH>Для того чтобы работал Completer WH>
WH> foreach (Situation sit2 in _states[sit.CreationState])
WH>
Ничего не понял. Ты не мог бы отвечать на вопросы так, чтобы было понятно? Неужели ты не понимашь, что тови отмазки никому не нужны? Отвечай по сути, а не "вы на воздушном шаре".
И так, попробуй еще раз обяснить свои слова "2)Исправил процедуру Parse ибо в Predictor надо пихать номер состояния, а не то что ты туда запихивал.".
VD>>Так было сказано в описании. WH>Где?
Ну, объяснение откровенно говря дико запутанное. А формальное объяснение вообще хреновое.
VD>>В общем, если я не правильно понял как должен быть устроен Predictor, то рассказывай как он по-твоему должен быть устроен. WH>Так как он сейчас устроен.
Знаешь, я начинаю сильно злиться когда люди не понимаю разговорный русский. Давай я еще раз процетирую суть свои слов, а ты попробуешь в них вникнуть, и сделать то что тебя просят.
рассказывай как он по-твоему должен быть устроен
Еще раз. Мне нужно доступное объяснение, что ты исправил, почему и (возможно) в чем я был не прав.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, mefrill, Вы писали:
M>На ворде, на тех все никак не могу сподобиться. Могу вордовские документы присоеденить. Только там нет места уже.
Та Тех и не нужно. Клади лучше вордовские файлы. Это куда лучше.
И вот еще, что твои обяснения слишком запутаны. Они то черезчур формальны, то уходят от темы. В общем, хорошо бы попробовать создать более доступное для массового читателя объяснение. Всесто (ну, или хотя бы параллельно) с мат формулами должен быть высокоуровневый псевдогод. Причем все идентификаторы должны быть осмысленными, а не одно-двух-буквенными. Иначе приходится массу времени лазить в их описание и запоминать совершенно не нужные подробности. К тому же в обяснении не должны пропускаться моменты вроде того, что ситуации в состояниях должны быть уникальны. Я, например, из-за этого потерял кучу времени. А понял я это только прочтя описание алгоритма Эрли на английском. Там четко было сказано, что состояние — это set и что все его элементы должны быть уникальны.
Без доступного обяснения в статье разбурутся только еденеицы готовые продираться через горы сложного и не понятного текста.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, mefrill, Вы писали:
M>Это только к концу недели, к сожалению, совсем нет времени. Пока можно заняться оптимизацией оригинального алгоритма. Каждую из операций можно оптимизировать. Для этого: M>1. Держать в состоянии не один список ситуаций, а столько списков — сколько символов в грамматике + 1. Каждый список, построенный для конкретного символа грамматики, содержит ситуации, у которых этот символ стоит после точки, и еще один список для ситуаций, у которых точка в самом конце. Тогда и комплитер и сканер не будут ничего искать в состоянии, а сразу ходить по спискам для своего символа. Это очень важная вещь, ускоряет разбор сильно.
Можно этот момент обяснить по подробнее. Не латая детали.
M>2. Также организовать хранение правил грамматики, т.е. для каждого нетерминала хранить список правил с этим нетерминалом в левой части. Тогда предиктор тоже по всей грамматике искать не будет и сразу возмет все правила с данным нетерминалов в левой части.
Это уже так и сделано. Есть массив NontermRules хранящий список идентификаторов правил для каждого нетерминала.
M>Кроме того, чтобы не делать проверку на то, что для данного нетерминала в данном состоянии предиктор уже был проведен (ведь реально он проводится для нетерминала, а не для ситуации!). В общем, держать булевский вектор, индексированный нетерминалами грамматики и ставить проверять соответствующий элемент перед тем как операцию предиктор для данного нетерминала выполнять.
То есть при формировании состояния заводим битовый массив в котором биты соотвествуют номерам нетерминалов грамматики и поднимаем бит если нетерминал уже обработан. Далее при обработке следующего нетерминала проверяем не был ли обработан этот терминал. И если был, то ничего не делаем. Так?
Такой массив нужен только при формировании состояния? Или их нужно хранить для всех состояний?
M>Для парсера можно добиться скорости 30 килобайт текста за секунду на сишной грамматике. Это уже сделано, так что вполне возможно.
30 в секунду — это не серьежно. За секунду на современной технике должен прарситься мегабайт. А то даже мелкие проекты типа Януса будут парситься 76 секунд (в нем 2.3 метра текста). Что просто ни в какие ворота не лезет. Это уже не парсинг а черепашие бега.
Надеюсь, что оптимизированный вариант покажет хотя бы 1 метр в секнуду (при условии, конечно, что исходники закэшированы в памяти). Хотя и это не быстро.
Иначе прийдется забросить эту идею и попробовать развить LL(1)-парсер до LL(*)++.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Адаптированный алгоритм Эрли - описание расширения
_>1.Есть рабочая ( видимо ) реализация алгоритма на lisp. Отличия от оригинальной версии только в способе создания и представления результата разбора- стороится одно дерево (точнее напавленный граф), в котором специальными вершинами кодируются неоднозначности,это дерево содержит все варианты разбора входной строки.
Здесь надо посмотреть внимательнее. Дело в том, что вся эта фигня с построением деревьев потому такая сложная, что если пытаться строить дерево прямо в лоб, алгоритм на некоторых грамматиках ожет зацикливаться. Там все очень тонко. Та реализация, которую я придумал, работает во всех случаях, что я доказал математически. Я имею ввиду способ как кодируется дерево вывода (или деревья) и влияет ли это кодирование на сам процесс алгоритма Эрли, т.е. на количество ситуаций в состоянии и т.д.
_>2.Для некоторых грамматик количество вариантов разбора вообще говоря неограничено. _>Пример _>
_>S --> A
_>A --> B
_>B --> A
_>B --> "a"
_>
_>Варианты разбора S --> B --> A --> "a" или S --> B --> A --> B --> A --> "a" или S --> B --> A --> B --> A --> "a" и так далее... В таких ситуациях можно либо отбрасывать часть варианов разбора либо закодировать в получившемся дереве возникшую ситуацию. На самом деле достататчно допустить возможность ссылаться на элемент находящийся выше в дереве. В примере выше получается что-то вроде
Да, в таких случаях (когда в грамматике есть циклические правила) мы вообще имеем бесконечное множество деревьев вывода. Но эту проблему можно решить очень простым способом. Именно, факторизовать множество все деревьев вывода, разбив его на группы, у каждой из которых будет только один представитель — дерево без циклов. Алгоритм Эрли устроен таким образом, что он такие циклические повторения не строит, ну вот и получается, что построенное дерево вывода без циклов, но с такими возможностями, будет представителем всего бесконечного семейства деревьев, отличающихся от этого деревав только цкилическими повторениями на цепных правилах. Мне кажется, все логично. Строить дополнительную связь чтобы отметить этот цикл? Честно говоря, не уверен что это необходимо. Ведь, если так уж нужно, всегда можно о таком цикле узнать из дерева и грамматики. Это сделать очень просто, вычислив циклы по грамматике заранее, а затем пр встрече нетерминального узла дерева — начала цикла, просто отмечать этот узел как потенциальный цикл и все.
_>
_> <----
_> | |
S-->>B-->A -->"a"
_>
_>То есть дерево превращается в направленный граф. _>Понятно что анализатор должен уметь это обрабатывть чтобы не попасть в бескончный цикл.
_>3.Было бы интересно научить парсер проверять какие нетерминалы в грамматики являются однозначными (хотя бы эмпирический алгоритм).
Известно, что задача проверки граматики на то, является ли она неоднозначной или нет, — задача алгоритмически неразрешимая. Можно попробовать проверить однозначность на всех строках с длиной не больше некотрого заданного числа. Но смысла в этом я не вижу. Если пользователь задал такую грамматику, значит у него были причины и алгоритм просто построит то множество деревьев, которое необходимо построить для данной строки.
_>4.Немного тестов. _>
_>a.
_>S --> "a" S A A A
_>S -->
_>A --> "a"
_>A -->
_>Вход "a" "aa" "aaa" "aaaa"
_>b.
_>S --> "a" S A A A
_>S -->
_>A --> "a"
_>A -->
_>Вход "a" "aa" "aaa" "aaaa"
_>c.
_>S --> "a" D "ad"
_>S --> B D "ab"
_>D --> "a" A B
_>A --> "a" B B
_>A -->
_>B -->
_>Вход "aaab"
_>d.
_>S --> "b" A
_>A --> "a" A B
_>A -->
_>B -->
_>Вход "baa"
_>
С эпсилон-правилами — это известная проблема в алгоритме Эрли, Completer не всегда работает правильно. Сам Эрли в своей диссертации советовал держать список всез нетерминалов, которые могут выводиться в пустую строку. Т.е. если мы добавили ситуацию в грамматику ,в которой мы имеем [A --> *, i], то запомнить эту ситуацию с тем, чтобы потом, если мы добавим ситуацию вида [B --> alpha * A beta, j], применить к ней Completer на ситуации [A --> *, i]. В реализации, которую я присоединил к ветке, именно такой способ реализован. Есть еще друггие методы, например, если встретилась такая ситуация, просто брать и проходить весь вписок снова. Но это неэкономично и мне лично не нравится. Или другой способ, запомнить перед запуском алгоритма все нетерминалы, выводящиеся в пустую строку и затем, при добалении ситуации, в правиле которой этот нетерминал стоит после точки, двигат сразу эту точку вправо, добавляя таким образом новую ситуацию. Но это тоже неудобно, т.к. здесь мы игнорируем дерево, посредством которого наш нетерминал вывелся в пустую строку, ведь такие деревьея могут в общем случае быть довольно сложными. Хотя и эту рполему можно решить еще до первого запуска алгоритма на самой грамматкие, ведь для пустых строк входа не нужно и все такие деревья вывода дял пустых строк могут быть построены статически.
Здравствуйте, VladD2, Вы писали:
M>>1. Держать в состоянии не один список ситуаций, а столько списков — сколько символов в грамматике + 1. Каждый список, построенный для конкретного символа грамматики, содержит ситуации, у которых этот символ стоит после точки, и еще один список для ситуаций, у которых точка в самом конце. Тогда и комплитер и сканер не будут ничего искать в состоянии, а сразу ходить по спискам для своего символа. Это очень важная вещь, ускоряет разбор сильно.
VD>Можно этот момент обяснить по подробнее. Не латая детали.
Имеется ввиду, что весь наш список ситуаций в состоянии можно разбить на точно определенное число списков, некоторые из которых могут быть пустыми. Именно, на число |N| + |T| + 1, где |N| — количество неетрминалов, |T| — количество терминалов грамматики. Все эти списки вместе образуют один список нашего состояния. Алгоритм Эрли как работал с этим списком, так и работает. Сами списки вводятся только для оптимизции, т.е. внешне они по-прежнему выглядят как один список состояния. Каждый список, соответствует некоторому символу грамматики и содержит только ситуации, в которых этот символ стоит после точки в правой части правила. Так как есть случаи когда точка стоит в самом конце правой части, для таких случаев вводится специальный список (потому еще +1 в количестве списков). Итак, если список для символа X, то в нем будут все ситуации вида [A --> aplha * X beta. i]. Таким образом мы оптимизируем работу операций Scanner и Completer. Как оптимизируем? Мне кажется, что это очевидно, достаточно взглянуть на алгоритмы этих операций.
M>>Кроме того, чтобы не делать проверку на то, что для данного нетерминала в данном состоянии предиктор уже был проведен (ведь реально он проводится для нетерминала, а не для ситуации!). В общем, держать булевский вектор, индексированный нетерминалами грамматики и ставить проверять соответствующий элемент перед тем как операцию предиктор для данного нетерминала выполнять. VD>То есть при формировании состояния заводим битовый массив в котором биты соотвествуют номерам нетерминалов грамматики и поднимаем бит если нетерминал уже обработан. Далее при обработке следующего нетерминала проверяем не был ли обработан этот терминал. И если был, то ничего не делаем. Так? VD>Такой массив нужен только при формировании состояния? Или их нужно хранить для всех состояний?
Можно использовать один массив для всех состояний. Как только очередное осстояние заполнилось, установить снова все его элементы в ложь и использовать при заполнении следующего состояния.
Здравствуйте, VladD2, Вы писали:
VD>Надеюсь, что оптимизированный вариант покажет хотя бы 1 метр в секнуду (при условии, конечно, что исходники закэшированы в памяти). Хотя и это не быстро.
Я вот подумал — а нельзя ли как нибудь, на основе анализа грамматики целиком, сделать для списков ситуаций более жесткие правила, чтобы ситуаций было меньше?
M>Здесь надо посмотреть внимательнее. Дело в том, что вся эта фигня с построением деревьев потому такая сложная, что если пытаться строить дерево прямо в лоб, алгоритм на некоторых грамматиках ожет зацикливаться. Там все очень тонко. Та реализация, которую я придумал, работает во всех случаях, что я доказал математически. Я имею ввиду способ как кодируется дерево вывода (или деревья) и влияет ли это кодирование на сам процесс алгоритма Эрли, т.е. на количество ситуаций в состоянии и т.д.
Просто для каждого символа и для каждой построки хранится список вариантов — во что выводится этот символ в подстроке. array [symbols,1..n,1..n] of list. При редукции состояния [A-->B C D . , j ] (текущая позиция в строке i) мы добавляем альтернативу (B C D) в [A,j,i].Реально достаточно array [symbols,1..n] of list.
Заодно получается сжатие деревьев.
M>Да, в таких случаях (когда в грамматике есть циклические правила) мы вообще имеем бесконечное множество деревьев вывода. Но эту проблему можно решить очень простым способом. Именно, факторизовать множество все деревьев вывода, разбив его на группы, у каждой из которых будет только один представитель — дерево без циклов.
Вообще парсер должен выдавать warning для такой грамматики. И для грамматики с недостижимимы и непроизводящими нетерминалами.Это к слову.
А насколько однозначно строится эта факторизация?
Скажем для примера
A --> B1
A --> B2
B1 --> B2
B2 --> B1
B1 --> D
B2 --> D
A
/ \
B1 <-> B2
\ /
D
Здравствуйте, VladD2, Вы писали:
VD>И так, попробуй еще раз обяснить свои слова "2)Исправил процедуру Parse ибо в Predictor надо пихать номер состояния, а не то что ты туда запихивал.".
Сначала объясни какой смысл у этой строки
for (int i = 0; i < count; i++)
{
Situation sit = state[i];
if (IsComplete(sit))
Completer(sit, state);
else
Predictor(sit, state, ++stateIndex);//!!!
}
Особенно интересует смысл третьего параметра.
VD>Знаешь, я начинаю сильно злиться когда люди не понимаю разговорный русский. Давай я еще раз процетирую суть свои слов, а ты попробуешь в них вникнуть, и сделать то что тебя просят. VD>
рассказывай как он по-твоему должен быть устроен
VD>Еще раз. Мне нужно доступное объяснение, что ты исправил, почему и (возможно) в чем я был не прав.
Мне что надо тебе алгоритм Эрли объяснить? А не прав ты в том что не понял алгоритм.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[5]: Адаптированный алгоритм Эрли - описание расширения
M>>Здесь надо посмотреть внимательнее. Дело в том, что вся эта фигня с построением деревьев потому такая сложная, что если пытаться строить дерево прямо в лоб, алгоритм на некоторых грамматиках ожет зацикливаться. Там все очень тонко. Та реализация, которую я придумал, работает во всех случаях, что я доказал математически. Я имею ввиду способ как кодируется дерево вывода (или деревья) и влияет ли это кодирование на сам процесс алгоритма Эрли, т.е. на количество ситуаций в состоянии и т.д. _>Просто для каждого символа и для каждой построки хранится список вариантов — во что выводится этот символ в подстроке. array [symbols,1..n,1..n] of list. При редукции состояния [A-->B C D . , j ] (текущая позиция в строке i) мы добавляем альтернативу (B C D) в [A,j,i].Реально достаточно array [symbols,1..n] of list. _>Заодно получается сжатие деревьев.
Не понял пока. А как мы потом эти деревья можем обойти? Т.е. я имею ввиду как храняться связи между выводами? Например, у меня есть для начального нетерминала S, что он выводится во всю строку, т.е. хранится [S, 1, n], теперь я хочу дальше пойти по дереву или по деревьям, как это мне сделать?
M>>Да, в таких случаях (когда в грамматике есть циклические правила) мы вообще имеем бесконечное множество деревьев вывода. Но эту проблему можно решить очень простым способом. Именно, факторизовать множество все деревьев вывода, разбив его на группы, у каждой из которых будет только один представитель — дерево без циклов.
_>Вообще парсер должен выдавать warning для такой грамматики. И для грамматики с недостижимимы и непроизводящими нетерминалами.Это к слову.
Честно говоря, не понимаю зачем это делать парсеру? Ведь все равно, если в грамматике есть циклы, всех деревьев вывода не построить, ибо их бесконечное множество. И пользователь только будет озадачен графом ниже вместо вполне естественного множества деревьев вывода. Ведь у меня еще есть другой алгоритм, который по состояниям проходит и в явном виде выдает все деревья вывода. А это и есть, по большому счету, задача разбора. То, что деревья факторизованы — кажется вполне естественным. Конечно, можно выдавать пользователю еще списко возможных циклов в дереве, лучше конечно, делать это отдельно, чтобы не запутывать и так сложный вывод. Ведь для пользователя важна задача полноценного разбора, вполне практическая задача. И циклы там не нужны. Я вот навскидку не могу припомнить ни одного случая, когда нужны были циклы в грамматике, ты можешь?
_>А насколько однозначно строится эта факторизация? _>Скажем для примера _>
_>A --> B1
_>A --> B2
_>B1 --> B2
_>B2 --> B1
_>B1 --> D
_>B2 --> D
_> A
_> / \
_> B1 <-> B2
_> \ /
_> D
_>
_>какие деревья будут построены?
Однозначно, это дерево без циклов. В примере выше будет построено дерево (точнее граф) такое:
A
|
B1
// \\
D B2
|
D
Здесь двойными черточками обозначены альтернативы поддеревьев, а не реальные деревья. Как можно видить, реально мы имеем два дерева (на рисунке ниже) и оба без циклов. Оба дерева будут явно выведены вторым алгоритмом по результатам работы первого. Это два представителя соответствующих фактор-классов деревьев. Первый класс вообще есть сам по себе одно дерево, ведь там нет циклов, а второй класс — есть факторизация бесконечного множества деревьев с циклом B1 ==> B2 ==> B1.
Здравствуйте, AndrewVK, Вы писали:
AVK>Я вот подумал — а нельзя ли как нибудь, на основе анализа грамматики целиком, сделать для списков ситуаций более жесткие правила, чтобы ситуаций было меньше?
Думаю, что вряд ли. Ведь Completer может вернуться к ситуации в любой момент и тогда эта ситуация понадобится. Хотя, и здесь не все ситуации могут быть полезны в дальнейшем. Так с наскока не ответишь, по хорошему это работа на диссертацию, технических наук, но все-таки. Надо посмотреть какие ситуации могут точно уже не могут быть задействованы при выводе и доказать это строго.
Re[6]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, mefrill, Вы писали:
M>Думаю, что вряд ли. Ведь Completer может вернуться к ситуации в любой момент и тогда эта ситуация понадобится. Хотя, и здесь не все ситуации могут быть полезны в дальнейшем. Так с наскока не ответишь, по хорошему это работа на диссертацию, технических наук, но все-таки. Надо посмотреть какие ситуации могут точно уже не могут быть задействованы при выводе и доказать это строго.
Например те в которых терминал после точки не равен следующему терминалу в последовательности. Тут и доказывать вобщемто нечего ни Scanner ни Predictor ни Completer эти ситуации не используют.
Scanner, Predictor и Completer и заинлайнил ибо мне так проще шаманить...
public bool Parse(int startNonterminalId)
{
if (startNonterminalId < FirstNonterminal || startNonterminalId > LastNonterminal)
throw new ArgumentOutOfRangeException("startNonterminalId",
"startNonterminalId не является нетерминальным символом данной грамматики.");
#if DEBUG
Debug.Assert(_debugParse == null);
_debugParse = this;
#endif
_stateBuilder.Reset();
_token = Next();
_states.Clear();
int stateIndex = 0;
AddPredictions(startNonterminalId, stateIndex);
while (true)
{
while (_stateBuilder.HasNewSituation)
{
Situation sit = _stateBuilder.PopNewSituation();
if (IsComplete(sit))
{
int leftSymbol = GetLeftSymbol(sit);
foreach (Situation sit2 in _states[sit.CreationState].NonTerminals)
{
if (leftSymbol == DotSymId(sit2))
{
int nextSymbolId = NextSymbolId(sit2);
if (_token.kind == nextSymbolId || IsNonterminalOrEmpty(nextSymbolId))
_stateBuilder.Add(sit2.CloneWithMoveDot());
}
}
}
else
{
int dotSymId = DotSymId(sit);
if (IsNonterminal(dotSymId))
AddPredictions(dotSymId, stateIndex);
}
}
State state = _stateBuilder.GetState();
_states.Add(state);
//Console.WriteLine("{0} {1}", stateIndex, state);if (_token.kind == Tokens.EOF)
break;
_stateBuilder.Reset();
++stateIndex;
foreach (Situation situation in state.Terminals)
{
int id = DotSymId(situation);
Debug.Assert(id == _token.kind);
_stateBuilder.Add(situation.CloneWithMoveDot());
}
_token = Next();
}
return Array.Exists(GetLastState().Complete, delegate(Situation s)
{
return s.CreationState == 0
&& Rule(s).LeftSymbol == startNonterminalId;
});
}
private void AddPredictions(int nonterminalId, int stateIndex)
{
Debug.Assert(IsNonterminal(nonterminalId));
foreach (int ruleId in _grammar.NontermRules[nonterminalId])
{
int firstSymbol = GetFirstSymbol(ruleId);
if (firstSymbol == _token.kind || IsNonterminal(firstSymbol))
_stateBuilder.Add(new Situation(ruleId, 0, stateIndex));
}
}
WH>Например те в которых терминал после точки не равен следующему терминалу в последовательности. Тут и доказывать вобщемто нечего ни Scanner ни Predictor ни Completer эти ситуации не используют.
Да, но это тривиальный случай. Обычно в состоянии как раз таких ситуаций с терминалом после точки бывает мало. Очень много ситуаций где точка стоит в самом начале правила, если мы раставляем приоритеты посредством правил, то имеем кучу вложенных друг в друга правил, вот всю эту иерархию и добавляет Predictor. Например, для простой грамматики выражений:
E --> E + P | P
P --> P * N | N
N --> n | ( E )
каждый раз, когда мы будем добавлять ситуацию с символом E после точки Predictor будет добавлять кучу ситуаций в соотвествии со всей данной иерахией. Это самый большой мусор, занимает примерно 90 процентов состояния.
Re[6]: Адаптированный алгоритм Эрли - описание расширения
M>Не понял пока. А как мы потом эти деревья можем обойти? Т.е. я имею ввиду как храняться связи между выводами? Например, у меня есть для начального нетерминала S, что он выводится во всю строку, т.е. хранится [S, 1, n], теперь я хочу дальше пойти по дереву или по деревьям, как это мне сделать?
Дерево хранится там, где в оригинальном алгоритме хранится указатель на дочерние подэлементы.
То есть ситуация имеет вид [A --> B . C ,i,l, дерево альтернатив для элемента B (соответвующее строке s[i..j])]
Также ссылки но тоже самое дерево хранятся в структуре [A , i ,j]
Дерево строится во время разбора. При редукции в соответствуещее дерево альтернатив добавляется новая альтернатива. A --> B C . , i , l — строим поддерево B C и добавляем его в [A , i ,j],а так как там хранятся ссылки на элементы в дереве то обновление происходит в дереве тоже автоматически.
Re[7]: Адаптированный алгоритм Эрли - описание расширения
M>E --> E + P | P
M>P --> P * N | N
M>N --> n | ( E )
M>
M>каждый раз, когда мы будем добавлять ситуацию с символом E после точки Predictor будет добавлять кучу ситуаций в соотвествии со всей данной иерахией. Это самый большой мусор, занимает примерно 90 процентов состояния.
Если следующий терминал не n или ( то это дерево можно не добавлять.
Вобще для Predictor'а можно построить таблицу которая будет индексирована парами [терминал;не терминал], а значение каждого узла будет список правил которые можно прямо или косвенно вывести из этой пары.
Если это список разделить на два:список правил с пустой правой частью и список с не пустрой то функцию Predictor для этих правил можно вобще не вызывать, а функцию Completer вызвать только для пустых правил.
Кстати если научить ситуацию ссылатся на список правил то ситуаций может быть на много меньше.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, VladD2, Вы писали:
VD>>Надеюсь, что оптимизированный вариант покажет хотя бы 1 метр в секнуду (при условии, конечно, что исходники закэшированы в памяти). Хотя и это не быстро.
AVK>Я вот подумал — а нельзя ли как нибудь, на основе анализа грамматики целиком, сделать для списков ситуаций более жесткие правила, чтобы ситуаций было меньше?
Я так понл есть два подхода:
1. Заглядывание вперед.
2. Построение LR(0)-атомата (ДКА).
Здравствуйте, mefrill, Вы писали:
M>Думаю, что вряд ли. Ведь Completer может вернуться к ситуации в любой момент и тогда эта ситуация понадобится. Хотя, и здесь не все ситуации могут быть полезны в дальнейшем. Так с наскока не ответишь, по хорошему это работа на диссертацию, технических наук, но все-таки. Надо посмотреть какие ситуации могут точно уже не могут быть задействованы при выводе и доказать это строго.
Здравствуйте, WolfHound, Вы писали:
WH>Если следующий терминал не n или ( то это дерево можно не добавлять. WH>Вобще для Predictor'а можно построить таблицу которая будет индексирована парами [терминал;не терминал], а значение каждого узла будет список правил которые можно прямо или косвенно вывести из этой пары.
Надо поглядеть, что она даст. Но к сожалению, глядеть нужно на реальной грамматике. Для этого нужно сделать полноценный парсер. То есть:
1. Реализовть построение деревьев вывода.
2. Реализовать хоть какое-то сообщение об ошибках.
3. Реализовать чтение грамматики формата Коки. Здесь еще нужно реалзовать преобрзование сложного формата с вложенными правилами, в простой используемый пасрером.
Вот тогда в качестве примера можно будет скормить парсеру грамматику С# 2.0 и сравнивать результаты. Это позволит оценить реальный выигрышь от оптимизаций.
Но сначала нужно решить стоит ли убивать на это дело время?
Может проще взять алгоритм вроде LL() и заточить его на построение множества деревьев вывода. Ведь построить для него автомат куда проще. А проблемы с правой рекурсией в общем-то не так страшны. Еее можно выявлять и переписывать правила.
WH>Если это список разделить на два:список правил с пустой правой частью и список с не пустрой то функцию Predictor для этих правил можно вобще не вызывать, а функцию Completer вызвать только для пустых правил. WH>Кстати если научить ситуацию ссылатся на список правил то ситуаций может быть на много меньше.
А как?
ЗЫ
Надо бы создат отдельную ветку в которой перечислить возможные оптимизации и обсудить их по отдельности.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, VladD2, Вы писали:
VD>>И так, попробуй еще раз обяснить свои слова "2)Исправил процедуру Parse ибо в Predictor надо пихать номер состояния, а не то что ты туда запихивал.". WH>Сначала объясни какой смысл у этой строки WH>
WH> for (int i = 0; i < count; i++)
WH> {
WH> Situation sit = state[i];
WH> if (IsComplete(sit))
WH> Completer(sit, state);
WH> else
WH> Predictor(sit, state, ++stateIndex);//!!!
WH> }
WH>
WH>Особенно интересует смысл третьего параметра.
Смысл простой. Я не мог понять, что означает последний элемент. Из обяснения mefrill я понял, что это просто индекс состояния.
WH>Мне что надо тебе алгоритм Эрли объяснить? А не прав ты в том что не понял алгоритм.
Да. Но понять его по такому объяснению мне очень тяжело. Кстати, более понятное обянение я нашел в http://rsdn.ru/File/73/deep-2.pdf. Оно краткое и простое. Вот прочтя его я кажется понял суть. Там кстати, и про оптимизации не мало говорится.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, mefrill, Вы писали:
M>Здесь надо посмотреть внимательнее. Дело в том, что вся эта фигня с построением деревьев потому такая сложная, что если пытаться строить дерево прямо в лоб, алгоритм на некоторых грамматиках ожет зацикливаться. Там все очень тонко. Та реализация, которую я придумал, работает во всех случаях, что я доказал математически. Я имею ввиду способ как кодируется дерево вывода (или деревья) и влияет ли это кодирование на сам процесс алгоритма Эрли, т.е. на количество ситуаций в состоянии и т.д.
А нельзя все же строить дерево вывода после? А то ведь размер ситуации увеличивается, а это не ускорит работу парсера.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[5]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, VladD2, Вы писали:
VD>А нельзя все же строить дерево вывода после? А то ведь размер ситуации увеличивается, а это не ускорит работу парсера.
Да дерево по любому сразу строится- оно оказывается закодировано в ссылках на предшедствующую ситуацию и дочерние ситуации.
Re[5]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, VladD2, Вы писали:
VD>А нельзя все же строить дерево вывода после? А то ведь размер ситуации увеличивается, а это не ускорит работу парсера.
можно строить и после, как это делается в оригинальном алгоритме. Но это отнюдь не ускорит работу алгоритма. Просто одни и теже ситуации будут обрабатываться комплитером несколько раз.
Re[7]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, little_alex, Вы писали:
_>Дерево хранится там, где в оригинальном алгоритме хранится указатель на дочерние подэлементы. _>То есть ситуация имеет вид [A --> B . C ,i,l, дерево альтернатив для элемента B (соответвующее строке s[i..j])] _>Также ссылки но тоже самое дерево хранятся в структуре [A , i ,j] _>Дерево строится во время разбора. При редукции в соответствуещее дерево альтернатив добавляется новая альтернатива. A --> B C . , i , l — строим поддерево B C и добавляем его в [A , i ,j],а так как там хранятся ссылки на элементы в дереве то обновление происходит в дереве тоже автоматически.
А компонент l что обозначает? И будут ли различаться ситуации с разными элементами l и с различными списками альтернатив? А вообще, кто этот алгоритм придумал? Очень похоже на мою реализацию.
Re[6]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, little_alex, Вы писали:
_>Да дерево по любому сразу строится- оно оказывается закодировано в ссылках на предшедствующую ситуацию и дочерние ситуации.
mefrill предлагает расширить ситуации двумя полями, чтобы строить дерево в один проход. Вот я и опасаюсь, как бы это не замедлело работу парсера.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Адаптированный алгоритм Эрли - описание расширения
Циклы в грамматике языка программирования говорят о ошибке того кто ее составлял, или они могут возникать в виду некоторых других абстаятельств и разрешаться уже на семантическом уровне?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, mefrill, Вы писали:
M>Честно говоря, не понимаю зачем это делать парсеру? Ведь все равно, если в грамматике есть циклы, всех деревьев вывода не построить, ибо их бесконечное множество. И пользователь только будет озадачен графом ниже вместо вполне естественного множества деревьев вывода.
Не. Тут ты явно не прав. Обойти направленный граф с циклами я смогу, так как для этого достаточно помечать ветки как пройденные.
А вот, что мне (как пользователю) делать с множеством деревьев? Они мне на фиг не упали. Мне нужно вычислить одно, подходящее мне дерево. По графу я представляю как это сделать.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, VladD2, Вы писали:
VD>mefrill предлагает расширить ситуации двумя полями, чтобы строить дерево в один проход. Вот я и опасаюсь, как бы это не замедлело работу парсера.
А без этих полей как потом дерево восстанавливать?
Re[8]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, mefrill, Вы писали:
_>>Дерево хранится там, где в оригинальном алгоритме хранится указатель на дочерние подэлементы. _>>То есть ситуация имеет вид [A --> B . C ,i,l, дерево альтернатив для элемента B (соответвующее строке s[i..j])] _>>Также ссылки но тоже самое дерево хранятся в структуре [A , i ,j] _>>Дерево строится во время разбора. При редукции в соответствуещее дерево альтернатив добавляется новая альтернатива. A --> B C . , i , l — строим поддерево B C и добавляем его в [A , i ,j],а так как там хранятся ссылки на элементы в дереве то обновление происходит в дереве тоже автоматически.
M>А компонент l что обозначает? И будут ли различаться ситуации с разными элементами l и с различными списками альтернатив? А вообще, кто этот алгоритм придумал? Очень похоже на мою реализацию.
l — это ссылка на ситуацию с точкой на один элемент левее.
Ситуации с разными l различатся будут. А с разными списками альтернатив нет. Фактически при работе алгоритма существует только одина ситуациия с равными первыми тремя составляющими A -> B . C ,i,l,.
Фактически это то что ты опысывал, только вместо ссылоки на дочернию ситуацию хранится ссылка на дерево вывода им соответсвующее.Это нужно чтобы перечисление поддеревьев для правила было не справа налево(как сейчас после работы алгоритма 1),а слева направо.
Re[7]: Адаптированный алгоритм Эрли - описание расширения
Тут есть один нехороший момент. Пусть есть 10 "локальных неоднозначностей" то есть подстрок разбираемых неоднозначно.Пусть каждый такой фрагмент разбирается двумя способами. Всего деревьев 2^10 !!! Здесь лучше кодировать графом и анализировать каждую такую неоднозначность независимо от остальных.
Пример такой грамматики — C++.
Re[7]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, VladD2, Вы писали:
МD>А вот, что мне (как пользователю) делать с множеством деревьев? Они мне на фиг не упали. Мне нужно вычислить одно, подходящее мне дерево. По графу я представляю как это сделать.
Каждое дерево из множества анализируется на корректность — ненужные отбрасываются. Это даже проще. Проблема только в их количесве.
Re[7]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, VladD2, Вы писали:
VD>Не. Тут ты явно не прав. Обойти направленный граф с циклами я смогу, так как для этого достаточно помечать ветки как пройденные. VD>А вот, что мне (как пользователю) делать с множеством деревьев? Они мне на фиг не упали. Мне нужно вычислить одно, подходящее мне дерево. По графу я представляю как это сделать.
В присоединенной статье есть алгоритм номер три, в котором показан обход вот такого леса графов. По ходу дела разрешается неоднозначность и на самом деле строится только единственное дерево. Алгоритм этот реализован и работает на порядок (а то и на два) быстрее основного адаптированного алгоритма Эрли. Сама структура построенного адаптированным алгоритмом множества графов, по моему мнению, наиболее естественно отражает работу алгоритма. И обход по дереву не составляет трудностей. Я реализовывал парсер на основе этого алгоритма и скажу, что все довольно удобно. Все же советую прочитать статью до конца.
Re[7]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, VladD2, Вы писали:
VD>mefrill предлагает расширить ситуации двумя полями, чтобы строить дерево в один проход. Вот я и опасаюсь, как бы это не замедлело работу парсера.
Как я уже говорил, поверь мне пожалуйста: скорость алгоритма совсем не зависит от этих самых полей. Действия те же самые, только в оригинальном алгоритме они повторяются на одной ситуации, а в адаптироавнном — на разных. Кроме того, это расширение было специально придумано чтобы строить деревья вывода входной строки во время работы алгоритма, без них алгоритм деревьев не построит.
Re[9]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, little_alex, Вы писали:
_>Фактически это то что ты опысывал, только вместо ссылоки на дочернию ситуацию хранится ссылка на дерево вывода им соответсвующее.Это нужно чтобы перечисление поддеревьев для правила было не справа налево(как сейчас после работы алгоритма 1),а слева направо.
Ага, понятно, спасибо. В принципе, это не так принципиально (извини за тавтологию) какой вывод строить, правый или левый. Я во втором алгоритме обхода деревьев просто кладу все узлы деревав в стек, а потом обхожу их слева направо. Занимает время это совсем мало в сравнении с временем всего алгоритма. Вообще, алгоритм обхода гораздо быстрее алгоритма Эрли.
Re[8]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, little_alex, Вы писали:
_>Здравствуйте, VladD2, Вы писали:
VD>>mefrill предлагает расширить ситуации двумя полями, чтобы строить дерево в один проход. Вот я и опасаюсь, как бы это не замедлело работу парсера.
_>А без этих полей как потом дерево восстанавливать?
Насколько я понял, тех полей что есть достаточно для построения деревьев отдельным проходом.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, little_alex, Вы писали:
_>Каждое дерево из множества анализируется на корректность — ненужные отбрасываются. Это даже проще. Проблема только в их количесве.
И делать 10 анализов? Это тормоза.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Адаптированный алгоритм Эрли - описание расширения
Здравствуйте, mefrill, Вы писали:
M>В присоединенной статье есть алгоритм номер три, в котором показан обход вот такого леса графов. По ходу дела разрешается неоднозначность и на самом деле строится только единственное дерево. Алгоритм этот реализован и работает на порядок (а то и на два) быстрее основного адаптированного алгоритма Эрли. Сама структура построенного адаптированным алгоритмом множества графов, по моему мнению, наиболее естественно отражает работу алгоритма. И обход по дереву не составляет трудностей. Я реализовывал парсер на основе этого алгоритма и скажу, что все довольно удобно. Все же советую прочитать статью до конца.
То есть если будет 10 неоднозначностей, то 10 отедьных деревьев анализировать не прийдется?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: Адаптированный алгоритм Эрли - описание расширения
VD>Кстати, господа знатоки, ответте на такой вопрос.
VD>Циклы в грамматике языка программирования говорят о ошибке того кто ее составлял, или они могут возникать в виду некоторых других абстаятельств и разрешаться уже на семантическом уровне?
ИМХО, циклы можно получить даже на правильной грамматике, подав не в том порядке правила, например, для восходящего алгоритма. С т.з. языка не имеет значение приоритетность правил, а с т.з. конкретного алгоритма парсера — очень даже.
Логин/пароль прислал. Давай доступ буду фиксить и рефакторить.
