Я недавно читал о парсере Earley и думаю, что это один из самых элегантных алгоритмов, которые я когда-либо видел. Однако алгоритм в его традиционном смысле является распознавателем, а не анализатором, то есть он может определять, соответствует ли строка определенному CFG, но не генерировать для него дерево разбора. Мой вопрос заключается в том, как восстановить не дерево разбора , а лес анализа всех возможных разборов данной входной строки.
В книге Грюна и Джейкоба «Методы синтаксического анализа: практическое руководство» они иллюстрируют алгоритм, который можно использовать для восстановления леса синтаксического анализа из результата распознавателя Earley, но он основан на методе синтаксического анализа Унгера, время выполнения которого равно O (n k +). 1 ) где k - длина самого длинного произведения в грамматике. Это означает, что среда выполнения не является полиномом по размеру грамматики. Более того, оригинальная статья Эрли о алгоритме, в которой предлагается алгоритм восстановления лесов разбора, неверна (см., Например, стр. 762 этой статьи Томита), хотя многие источники все еще ссылаются на него как на подходящий способ восстановления леса разбора. ,
Мой вопрос заключается в том, возможно ли за полиномиальное время восстановить лес разбора для заданной входной строки. Я нашел документ здесь , который обеспечивает алгоритм для получения кубического размера разбора лесного представления для любого синтаксического анализа с помощью моделирования КПК, так что кажется , что это должно быть возможно, но я до сих пор найти способ сделать это. В идеале я хотел бы сделать это без преобразования входной грамматики в CNF (что действительно решило бы проблему), так как результирующий лес синтаксического анализа был бы довольно грязным.
Спасибо за любую помощь, которую вы можете предложить!
источник
Ответы:
Это, конечно, будет зависеть от правильного представления «упакованного леса», представляющего все деревья разбора для данного предложения.
Я думаю, что место, которое вы хотите начать искать, - это тезис Джошуа Гудмана (разбор наизнанку, Гарвард, 1999). По сути, идея заключается в том, что вы можете определить алгоритм синтаксического анализа под определенным полукольцом. В зависимости от полукольца, вы сможете вычислять все виды величин и структур вместо чистого дерева анализа (в качестве распознавателя или анализатора). Одно полукольцо, которое вы можете определить (что Гудман делает в своей диссертации), - это полукольцо, в котором значения являются наборами разборов. Когда вы в конце концов закончите синтаксический анализ предложения, вы получите все деревья разбора в главном узле разбора.
Опять же, вы должны быть осторожны, чтобы сделать это возможным через правильное представление.
источник
Есть документ, который описывает, как это сделать:
Разбор в стиле SPPF от Элизабет Скотт от Earley Recognisers
Он описывает, как построить бинаризованный лес разбора за кубическое время.
источник
Вам никогда не нужен 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 от автора
источник
Документ, который описывает, как построить бинаризованный лес синтаксического анализа в кубическом времени (упомянутый в посте Анджело Борсотти): «Анализ в стиле SPPF от распознавателей Earley» Элизабет Скотт. Вы можете найти его здесь: http://dx.doi.org/10.1016/j.entcs.2008.03.044
В этой статье описывается построение общего упакованного леса анализа (SPPF), который представляет все возможные деревья анализа. Поддерева совместно используются, когда это возможно, и узлы, соответствующие разным производным одной и той же подстроки из одного и того же нетерминала, объединяются.
источник
Я хотел бы повторить ответы выше, предлагая вам прочитать эту статью:
Я хотел бы уточнить, сказав, что я реализовал алгоритм в этой статье, и я считаю, что есть ошибка. В частности, первое предложение второго абзаца раздела 4. Метки предшественника, которые вы делаете для того, что Эрли назвал бы фазой «сканирования», должны указывать от p до q, а не наоборот.
В частности, следующая строка:
Следует читать «от р до д», а не «от д до р»
Я реализовал алгоритм в том виде, в котором он был заявлен изначально, что давало мне ошибки в некоторых тестовых примерах, которые были исправлены после того, как я изменил направление указателя здесь.
источник