Восстановление леса разбора из парсера Эрли?

25

Я недавно читал о парсере Earley и думаю, что это один из самых элегантных алгоритмов, которые я когда-либо видел. Однако алгоритм в его традиционном смысле является распознавателем, а не анализатором, то есть он может определять, соответствует ли строка определенному CFG, но не генерировать для него дерево разбора. Мой вопрос заключается в том, как восстановить не дерево разбора , а лес анализа всех возможных разборов данной входной строки.

В книге Грюна и Джейкоба «Методы синтаксического анализа: практическое руководство» они иллюстрируют алгоритм, который можно использовать для восстановления леса синтаксического анализа из результата распознавателя Earley, но он основан на методе синтаксического анализа Унгера, время выполнения которого равно O (n k +). 1 ) где k - длина самого длинного произведения в грамматике. Это означает, что среда выполнения не является полиномом по размеру грамматики. Более того, оригинальная статья Эрли о алгоритме, в которой предлагается алгоритм восстановления лесов разбора, неверна (см., Например, стр. 762 этой статьи Томита), хотя многие источники все еще ссылаются на него как на подходящий способ восстановления леса разбора. ,

Мой вопрос заключается в том, возможно ли за полиномиальное время восстановить лес разбора для заданной входной строки. Я нашел документ здесь , который обеспечивает алгоритм для получения кубического размера разбора лесного представления для любого синтаксического анализа с помощью моделирования КПК, так что кажется , что это должно быть возможно, но я до сих пор найти способ сделать это. В идеале я хотел бы сделать это без преобразования входной грамматики в CNF (что действительно решило бы проблему), так как результирующий лес синтаксического анализа был бы довольно грязным.

Спасибо за любую помощь, которую вы можете предложить!

templatetypedef
источник
Должен ли это быть алгоритм, основанный на парсинге Эрли, или вы не против использовать другой общий синтаксический анализатор CFG?
Алекс тен Бринк
1
Я бы предпочел алгоритм, основанный на парсере Earley. Я преподавал курс компиляторов и провел несколько дней, пытаясь найти ответ на этот вопрос, и это действительно меня беспокоит.
templatetypedef
Экспоненциальное время выполнения не удивительно, поскольку слова могут иметь экспоненциально много деревьев разбора. На самом деле, их может быть даже бесконечно много, если вы разрешите произвольные CFG.
Рафаэль
3
@Raphael Роль синтаксических лесов состоит именно в том, чтобы иметь механизм совместного использования, который позволит представлять все деревья, даже бесконечно много, с конечной структурой, с небольшой пространственной сложностью. Конечно, это может оставить работу для лесорубов.
Бабу
Вы можете посмотреть на Марпу . Это модуль Perl и библиотека C, которые реализуют парсер Earley и имеют полную поддержку леса синтаксического анализа.
hippietrail

Ответы:

14

Это, конечно, будет зависеть от правильного представления «упакованного леса», представляющего все деревья разбора для данного предложения.

Я думаю, что место, которое вы хотите начать искать, - это тезис Джошуа Гудмана (разбор наизнанку, Гарвард, 1999). По сути, идея заключается в том, что вы можете определить алгоритм синтаксического анализа под определенным полукольцом. В зависимости от полукольца, вы сможете вычислять все виды величин и структур вместо чистого дерева анализа (в качестве распознавателя или анализатора). Одно полукольцо, которое вы можете определить (что Гудман делает в своей диссертации), - это полукольцо, в котором значения являются наборами разборов. Когда вы в конце концов закончите синтаксический анализ предложения, вы получите все деревья разбора в главном узле разбора.

Опять же, вы должны быть осторожны, чтобы сделать это возможным через правильное представление.

gmmodeler
источник
Спасибо за ссылку! Это похоже на отличный ресурс, и я собираюсь потратить некоторое время на его изучение.
templatetypedef
8

Есть документ, который описывает, как это сделать:

Разбор в стиле SPPF от Элизабет Скотт от Earley Recognisers

Он описывает, как построить бинаризованный лес разбора за кубическое время.

Анджело Борсотти
источник
2
Эта связь, кажется, теперь сломана. У вас есть ссылка (название статьи, где опубликовано, список авторов) и / или обновленная ссылка?
DW
1
См web.archive.org/web/20130508170633/http://thor.info.uaic.ro/... : "SPPF-Style Синтаксический От Эрли Recognisers", Элизабет Скотт. Другая ссылка: dinhe.net/~aredridel/.notmine/PDFs/… .
a3nm
Это правильный ответ на вопрос «как получить лес разбора от распознавателя Эрли».
tjvr
Хорошая реализация этого в JS здесь: joshuagrams.github.io/pep
tjvr
Что подразумевается под бинаризованным в этом контексте?
Брюс Адамс
6

Вам никогда не нужен CNF. Недостатком является изменение структуры грамматики. Но вам нужно ввести промежуточные нетерминалы, чтобы ни одна правая сторона не была длиннее 2 (2-форма), поскольку длина RHS определяет сложность. Лучшей попыткой объяснить это на интуитивном уровне является, если память не изменяет, статья Бо Шила «Наблюдения за разбором без контекста», опубликованная в 1976 году на конференции по компьютерной лингвистике. Алгоритм Эрли использует 2-форму неявно. Это просто спрятано в алгоритме. Что касается восстановления и обработки синтаксического леса, вы должны посмотреть в интернете «синтаксический анализ леса пересечения». Это на самом деле очень просто. Многие статьи в Интернете, если вы получаете (из цитат или таблиц содержания) названия или авторов, чтобы искать их напрямую.

На самом деле, вы можете сделать намного больше, чем CF, и при этом получить разбросанные леса за полиномиальное время. Иногда возникает вопрос: что вы можете сделать с ним, когда он у вас есть?

Одна из целей последней статьи, которую вы упомянули, состоит в том, чтобы показать, что сложные алгоритмы (такие как GLR) не обязательно покупают что-либо во времени или в пространстве и могут изменить ваш лес разбора.

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

В литературе по компьютерной лингвистике может быть больше информации, чем в обычных каналах информатики. У меня нет книги Ceriel-Grune-Jacobs, но я был бы удивлен, если бы у них не было всех надлежащих ссылок (хотя я не уверен насчет их критериев отбора).


Дополнить после запроса в комментарии (7 июля 2013 г.)

Это дополнение заключает в себе существование более простых алгоритмов, чем Эрли.

Как я уже сказал, поиск в Интернете в «лесе пересечения» должен быстро дать вам ссылки, из которых вы можете копать дальше.

Основная идея заключается в том, что синтаксический анализ всех путей при построении общего леса - это не что иное, как старая конструкция пересечения Бар Гилеля, Перлеса и Шамира для обычного языка и языка без контекста, использующего конечный автомат и грамматику без контекста. Учитывая грамматику CF, вы применяете конструкцию к тривиальному автомату, который распознает только вашу входную строку. Вот и все. Общий лес - это просто грамматика пересечения. Он связан с исходной грамматикой через гомоморфизм, распознает только заданную строку, но со всеми деревьями разбора исходной грамматики вплоть до этого гомоморфизма (т. Е. Простым переименованием нетерминалов).

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

Затем либо вы должны очистить его хорошей щеткой в ​​конце (возможно, длинной, но алгоритмически простой), либо вы можете попытаться улучшить конструкцию, чтобы в конце было меньше бесполезного пуха, который нужно чистить щеткой.

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

Нисходящие методы (такие как основанные на LR (k)) позволят избежать недостижимых правил и нетерминалов, но создадут непродуктивные.

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

Все существующие алгоритмы фактически следуют этой модели. Так что это действительно суть дела, и это очень просто. Тогда зачем хоронить в сложности?

В литературе предлагается много «оптимизаций», часто основанных на построении синтаксического анализатора семейства LR (k), LL (k), возможно, с некоторым статическим факторингом этих конструкций (у Эрли нет статического факторинга). На самом деле это может быть применено ко всем известным методам, включая старые парсеры старшинства. Я помещаю «оптимизацию» между кавычками, потому что обычно не ясно, что вы оптимизируете, или даже действительно ли вы оптимизируете это, или стоит ли выгода от усовершенствования дополнительной сложности вашего парсера. Вы найдете немного объективных данных, формальных или экспериментальных, по этому (есть некоторые), но гораздо больше претензий. Я не говорю, что нет ничего интересного. Есть несколько умных идей.

Теперь, когда вы знаете основную идею, «оптимизации» или улучшения часто можно вводить статически (возможно, постепенно), создавая автомат из выпадающего из грамматики, следуя интересующему вас виду построения синтаксического анализатора, а затем применяя конструкция перекрестного произведения для пересечения с этим автоматом (почти то же самое, что сделать это с грамматикой) или с грамматикой, полученной из этого автомата.

Тогда вы можете ввести навороты, но это в основном технологические детали.

Философия Naturalis Principia Mathematica Исаака Ньютона, как сообщается, является выдающимся произведением физики и математики. Я не думаю, что это в списке чтения многих студентов. При прочих равных условиях я не думаю, что очень полезно учить алгоритм Эрли, хотя это важная историческая часть. Студентам достаточно учиться, как есть. Риск быть застреленным многими людьми, я думаю, почти то же самое для бумаги Кнута LR (k). Это превосходный теоретический анализ и, вероятно, важная литература для теоретика. Я сильно сомневаюсь, что это так важно для создания синтаксических анализаторов, учитывая современное состояние технологии, как аппаратного, так и программного обеспечения. Прошло время, когда синтаксический анализ был значительной частью времени компиляции, или когда скорость компиляторов была критической проблемой (я знал одну корпорацию, которая умерла от затрат на компиляцию около 30 лет назад). Специалист по синтаксическому анализу может захотеть освоить эти специализированные знания в какой-то момент, но среднестатистическому студенту по информатике, программированию или технике это не нужно.

Если ученики должны тратить больше времени на разбор, существуют другие расширения, которые могут быть более полезными и более полезными, например, используемые в компьютерной лингвистике. Первая роль преподавания состоит в том, чтобы извлечь простые идеи, которые структурируют научное знание, а не заставлять студентов страдать от того, что должны были испытать ученые-исследователи (за исключением докторантов: это обряд :-).

Лицензия CC BY-SA 3.0 от автора

Babou
источник
2
«Эрли ... слишком сложен для преподавания и может быть заменен более простыми алгоритмами ...». Не могли бы вы привести пример такого более простого алгоритма?
13
@wjl Я отвечу вам в добавлении к ответу выше. Я не указываю на конкретный алгоритм, хотя вы можете найти его в литературе, если выполните поиск, как я рекомендую. Я скорее попытался объяснить, почему очень легко создавать более простые, но эффективные алгоритмы. Эрли, наверное, самый сложный из них. Объясняя Бар Гилель и соавт. Конструкция составляет около половины страницы учебника, скажем, страница с доказательством.
Бабу
@wjl Ответ на ваш запрос занял у меня некоторое время. Вам это помогло? , , , , , Если вам нужен реальный алгоритм, он есть в последней ссылке исходного вопроса.
Бабу
Да спасибо; Я ценю дополнительные детали. Я работаю над обобщенной библиотекой синтаксического анализатора для некоторой работы, которую я делаю, и проводил тонну исследований различных алгоритмов. В настоящее время я склоняюсь к реализации раннего стиля, так как мне показалось, что это очень простой для понимания алгоритм, и его легко распространить на конъюнктивные грамматики и терминалы «черного ящика» (возможно, контекстно-зависимые). Я просмотрел и распечатал некоторые бумаги, на которые вы указали; но я еще не прочитал их всерьез.
13
@wjl Если вы этим занимаетесь, вам следует рассмотреть следующие темы: языки с умеренным контекстом, линейные системы безконтекстного переписывания (LCFRS) и грамматики конкатенации диапазонов. Не уверен, что понимаю, что такое терминал "черный ящик". - - электронная почта: babou на inbox.com. - -
Бабу
5

Документ, который описывает, как построить бинаризованный лес синтаксического анализа в кубическом времени (упомянутый в посте Анджело Борсотти): «Анализ в стиле SPPF от распознавателей Earley» Элизабет Скотт. Вы можете найти его здесь: http://dx.doi.org/10.1016/j.entcs.2008.03.044

В этой статье описывается построение общего упакованного леса анализа (SPPF), который представляет все возможные деревья анализа. Поддерева совместно используются, когда это возможно, и узлы, соответствующие разным производным одной и той же подстроки из одного и того же нетерминала, объединяются.

гага
источник
Спасибо за указатель. Построение разбитых бинаризованных лесов в кубическое время является стандартным. Бинаризация - единственный способ получить кубическое время, так что замечание ОП по сложности относительно размера грамматики не имеет значения. Другая проблема заключается в том, чтобы понять, каким образом синтаксический лес разбивается на двоичные. Это может зависеть от алгоритма. Другими проблемами являются количество общего доступа в общем лесу и практическая эффективность стратегии синтаксического анализа (Эрли может быть плохой идеей). Все это разработано в последнем обращении ОП. Общий официальный взгляд на проблему изложен в моем ответе.
Бабу
1

Я хотел бы повторить ответы выше, предлагая вам прочитать эту статью:

http://dx.doi.org/10.1016/j.entcs.2008.03.044

Я хотел бы уточнить, сказав, что я реализовал алгоритм в этой статье, и я считаю, что есть ошибка. В частности, первое предложение второго абзаца раздела 4. Метки предшественника, которые вы делаете для того, что Эрли назвал бы фазой «сканирования», должны указывать от p до q, а не наоборот.

В частности, следующая строка:

Установите E0 для элементов (S :: = · α, 0). Для i> 0 инициализируйте Ei, добавив элемент p = (A :: = αai · β, j) для каждого q = (A :: = α · aiβ, j) ∈ Ei − 1 и, если α =, создайте указатель предшественника с меткой i - 1 от q до p

Следует читать «от р до д», а не «от д до р»

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

Джереми Доман
источник