Здравствуйте, 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],а так как там хранятся ссылки на элементы в дереве то обновление происходит в дереве тоже автоматически.
) реализация алгоритма на lisp. Отличия от оригинальной версии только в способе создания и представления результата разбора- стороится одно дерево (точнее напавленный граф), в котором специальными вершинами кодируются неоднозначности,это дерево содержит все варианты разбора входной строки.
