Как восстановить лес синтаксических деревьев из вектора Эрли?

9

Использовать вектор Эрли в качестве распознавателя довольно просто: когда достигается конец строки, вам просто нужно проверить завершенную аксиоматическую постановку, начатую в позиции 0. Если у вас есть хотя бы один, тогда строка принимается.

Использование вектора Эрли для восстановления дерева (ов) синтаксического анализа менее очевидно. На самом деле, я не могу понять, как будет работать алгоритмическая процедура, более того, единственные ссылки, которые я нашел, были либо расплывчатыми, либо сверхтехническими. Кто-нибудь может пролить свет на это?

Стефано Санфилиппо
источник
2
Было бы полезно, если бы вы перечислили ссылки, которые вы нашли, и которые, по вашему мнению, были расплывчаты, и которые вы считали слишком техническими. В противном случае ответом может быть указатель на ссылки, которые вы уже нашли.
Блуждающая логика
1
Может случиться так, что то, что вы называете вектором, не то, что Эрли называет вектором в своей оригинальной статье. Или может быть, что это не играет точно такую ​​же роль. Авторы вводят вариации в алгоритмах. Нет никакой возможности узнать, так как вы не даете никаких ссылок на документы, которые вы использовали ... и мы, возможно, не будем иметь к ним доступ в любом случае. Что может помочь, так это более четко определить определения. Отвечая, я просто предположил, что вы использовали те же определения, что и у Эрли.
Бабу
@babou, то, что я назвал «вектор Эрли», является табличным представлением структуры данных, созданной синтаксическим анализатором. Это был термин, используемый моим профессором формальных языков при обращении к нему. Следует отметить, что мой основной язык не английский, так что это может быть просто неудачной попыткой перевести терминологию. Технический справочник, который я упомянул, - это статья Эрли. Я подошел к нему, но это было немного пугающим для такого начинающего, как я.
Стефано Санфилиппо
Вы можете проверить, использует ли «вектор Эрли» вашего профессора для обозначения той же структуры, что и то, что Эрли называет «вектором» в своей статье. Может быть полезно для общения. В остальном, как вы можете видеть, вы должны хранить дополнительную информацию, чтобы иметь возможность восстановить деревья разбора, но Эрли на самом деле не вдавался в подробности. В настоящее время существуют другие алгоритмы, и я боюсь, что сложности алгоритма Эрли скрывают несколько ключевых идей этого типа методов. Удачи.
Бабу
Мое объяснение было полезным, или вам нужно более подробное описание технической части?
Бабу

Ответы:

9

Я использую терминологию и обозначения из статьи Эрли . Возможно, что прочитанное вами описание отличается.

Часто кажется, что общие алгоритмы синтаксического анализа CF сначала представляются в форме распознавателя, а затем управление информацией, необходимое для фактического построения деревьев разбора и разбора лесов, добавляется в качестве запоздалой мысли. Одной из причин может быть то, что для хранения информации, необходимой для построения общего леса, требуется кубическое пространство где n - длина анализируемой входной строки, но требование к пространству составляет только квадрат O ( n 2 )O(n3)nO(n2) для распознавания для распознавания, когда эта информация не сохраняется. Причина такого увеличения сложности пространства довольно проста: размер разбора леса может быть кубическим.

Как известно, сложность времени в наихудшем случае составляет .O(n3)

Лучшая ссылка на алгоритм Эрли - это, конечно , статья Эрли , но она не очень ясна о построении леса разбора. Это на самом деле может быть грязным делом, гораздо больше, чем позволят появиться быстрые разговоры о разделе 7 на странице 101. По правде говоря, Эрли говорит не о лесе разбора или о лесу, а о « факторизованном представлении всех возможных деревьев разбора ». И для этого есть веская причина: если он попытается создать лес в соответствии со своей грамматикой, его пространственная (следовательно, временная) сложность возрастет до где sO(ns+1)sэто размер самого длинного правила с правой стороны. Вот почему другие алгоритмы используют грамматики в двоичной форме (не обязательно в нормальной форме Хомского (CNF)).

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

Один хороший способ понять, как получается лес, - это, вероятно, посмотреть на него в более простом случае - на алгоритм CYK . Это также часто описывается как распознаватель, и аспект парсера добавляется в конце. Вы можете посмотреть описание в википедии. Информация, необходимая для построения леса, хранится в таблице «обратных ссылок». Обратные указатели - это, по сути, указатели на подстроки (связанный символ), которые формируют составляющие строки согласно некоторому правилу. Они дают все возможные способы разбора подстроки. Напомним, что CYK использует двоичную форму, обычно CNF, так что все проще. Синтаксический анализатор CYK имеет в основном ту же структуру динамического программирования, что и Earley, но намного проще. Так что понимание этого может быть значительной помощью.

Возвращаясь к алгоритму Эрли, я не верю, что вам нужен вектор Эрли, чтобы принять решение о принятии или построить анализ деревьев и лесов. То, что Эрли называет вектором в своей статье, появляется только на странице 97 в третьем абзаце реализации. Это всего лишь устройство для ускорения поиска состояний, указывающих назад на некоторую заданную позицию строки k, чтобы получить лучшую сложность. Но вся информация находится в наборах состояний, реализованных в виде списков состояний. Однако этой информации недостаточно для построения леса деревьев разбора, потому что алгоритм не отслеживает пути, по которым может быть получено состояние. Действительно, вектор даже используется для эффективного удаления уже найденного состояния независимо от того, как оно было найдено.

В разделе 7 статьи Эрли он объясняет, что для того, чтобы «превратить распознаватель в синтаксический анализатор», т. Е. Чтобы иметь возможность восстанавливать деревья синтаксического анализа, необходимо следить за выполнением завершений.

Каждый раз , когда мы выполняем операцию Completer добавив состояния (не обращая внимания) мы строим указатель из экземпляра D в этом состоянии в состояние D γ .EαD.βgD который заставил нас сделать операцию. Это указывает на то, что D был проанализирован как γ . В случае D неоднозначен будет множество указателей из него,одному для каждой операции завершивших вызвавшего E & alpha ; D . βDγ.fDγ который будет добавлен к определенному набору состояний. Каждый символ в гамма также будет иметь указатели от него (если это не терминал), и так далее, таким образомпредставляя дерево дифференцирования D .EαD.βgγD

Обратите внимание, что в этом тексте и g являются индексами в разобранной строке, указывающими, где началось распознавание левой части правила (так как символ правой стороны был предсказан. Так что f - это строковый индекс, где распознавание Начался D γ и закончился в индексе G. Эти «указатели завершения» являются эквивалентом Эрли описанных обратных указателей (не слишком хорошо в википедии) для версии синтаксического анализатора CYK.fgfDγg

От такого указателя (как описано в цитате) мы знаем , что в экземплярноге правила E & alpha ; D . βDСамо g может быть превращено в дерево (или лес), которое анализирует входную строку w из индекса f + 1 в индекс g , который мы отмечаем как w f + 1 : g . Узлы, расположенные непосредственно под D , задаются правилом D γ . В поисках завершения, которое приводит к D γ .EαD.βgwf+1gwf+1:gDDγ затем мы можем найти другие такие указатели, которые сообщают, какбыл полученпоследний символ D , и, следовательно, больше информации о возможных деревьях разбора. Также, взглянув на завершение, которое распознало символ перед последним в наборах состояний ранее, вы узнаете, как он был получен и так далее.Dγ.fD

Предполагая, что вы сохранили все необходимые указатели, как указано в документе, вы можете получить все общие представления дерева, начиная с последнего символа, распознанного синтаксическим анализатором, который, конечно, является начальным символом грамматики.

Но я также пропустил грязную часть . Предположим, у вас есть правило , которое я выбираю с правой стороны длиннее 2 символов, а другое правило W U V для неоднозначной грамматики.UXYZWUV

Вполне может случиться так, что синтаксический анализатор будет анализировать в X , ш г + 1 : ч в Y и оба ш ч + 1 : я и ш ч + 1 : J в Z . Итак, с правилом U X Y Z оба w f + 1 : i и w f + 1 : jwf+1:gXwg+1:hYwh+1:iwh+1:jZUXYZwf+1:iwf+1:jразобрать на .U

wi+1:kwj+1:kVWUVwf+1:kW

wf+1:gwg+1:hXYUUXYZUXY.ZfShZWUV.fSk

Таким образом, лес синтаксических деревьев может быть очень странным, с видом сиамских двойных поддеревьев, которые могут иметь первые два ребра некоторого узла, но не третье ребро. Другими словами, это может быть очень неудобная структура. Это может объяснить, почему Эрли называет это « факторизованным представлением всех возможных деревьев разбора », не будучи более конкретным.

Любой желающий хирургически отделить сиамских близнецов без изменения грамматики приведет к увеличению сложности. Правильный способ сделать это состоит в том, чтобы преобразовать грамматику в двоичную форму.

Я надеюсь, что это поможет вам. Дай мне знать. Но я настаиваю на том, что хорошее понимание синтаксического анализа CYK может помочь. Существуют другие алгоритмы, более простые, чем у Эрли, которые могут эффективно анализировать все языки CF.

Вы можете найти более общую информацию об этой проблеме леса анализа в двух других ответах, которые я дал: /cstheory/7374#18006 и https://linguistics.stackexchange.com/questions/4619#6120 . Но они не входят в конкретные детали алгоритма Эрли.

Babou
источник
Так же, как и разбор CYK, стоит обратить внимание и на разбор GLR.
псевдоним
1
@ Псевдоним. Знание и понимание различных форм общего синтаксического анализа CF определенно не повредит, и я предлагаю так же две ссылки в конце ответа. Тем не менее, мой выбор CYK не был случайным. Он разделяет с алгоритмом Эрли свойство интерпретации, используя непосредственно грамматику, а не таблицы, созданные путем компиляции грамматики в автомат Push-Down (как в GLR, GLL, GPrec). Следовательно, связь между процессом распознавания и образованием дерева / леса становится более отчетливой. CKY также самый простой алгоритм, за одним исключением.
Бабу