В информатике , то Эрел анализатор является алгоритмом для разбора строк , которые принадлежат к данному контекстно-свободному языку , хотя ( в зависимости от варианта) может пострадать проблемы с некоторым обнуляемым грамматиком. [1] Алгоритм, названный в честь его изобретателя Джея Эрли , представляет собой анализатор диаграмм , использующий динамическое программирование ; в основном он используется для синтаксического анализа в компьютерной лингвистике . Впервые он был представлен в его диссертации [2] в 1968 г. (а затем в сокращенной, более разборчивой форме был опубликован в журнале [3] ).
Эрел парсеры являются привлекательными , поскольку они могут анализировать все контекстно-свободные языки, в отличии от LR парсеров и LL анализаторов , которые чаще используются в компиляторах , но которые могут обрабатывать только ограниченные классы языков. В Алгоритме Эрел выполняется в кубическое время в общем случае , где п есть длина анализируемой строки, квадратичное время для однозначных грамматик , [4] и линейное время для всех детерминированных контекстно-свободных грамматик . Это особенно хорошо работает, когда правила написаны леворекурсивно .
Опознаватель Эрли [ править ]
Следующий алгоритм описывает распознаватель Эрли. Распознаватель может быть легко модифицирован для создания дерева синтаксического анализа, как он распознает, и таким образом может быть превращен в синтаксический анализатор.
Алгоритм [ править ]
В нижеследующем описании, α, β, и у представляют собой любую последовательность из терминалов / нетерминалы ( в том числе пустой строки ), Х и Y представляют собой одиночные нетерминалы и представляет собой терминальный символ.
Алгоритм Эрли - это нисходящий алгоритм динамического программирования . Далее мы используем точечную нотацию Эрли: для заданной продукции X → αβ запись X → α • β представляет условие, при котором α уже проанализировано, а β ожидается.
Позиция ввода 0 - это позиция до ввода. Входная позиция n - это позиция после принятия n- го токена. (Неформально позиции ввода можно рассматривать как места на границах токенов .) Для каждой позиции ввода синтаксический анализатор генерирует набор состояний . Каждое состояние представляет собой набор (X → α • β, i ), состоящий из
- согласованная добыча (X → α β)
- текущая позиция в этом производстве (обозначена точкой)
- позиция i во входных данных, с которой началось сопоставление этой продукции: исходная позиция
(Первоначальный алгоритм Эрли включал прогнозирование состояния; более поздние исследования показали, что это практически не влияет на эффективность синтаксического анализа, и впоследствии он был исключен из большинства реализаций.)
Состояние, установленное во входной позиции k , называется S ( k ). Парсер заполняется S (0), состоящим только из правила верхнего уровня. Затем синтаксический анализатор повторно выполняет три операции: прогнозирование , сканирование и завершение .
- Прогноз : для каждого состояния в S ( k ) вида (X → α • Y β, j ) (где j - позиция начала координат, как указано выше), добавьте (Y → • γ, k ) к S ( k ) для каждого продукция в грамматике с Y в левой части (Y → γ).
- Сканирование : если a является следующим символом во входном потоке, для каждого состояния в S ( k ) формы (X → α • a β, j ) добавьте (X → α a • β, j ) к S ( k +1).
- Завершение : для каждого состояния в S ( k ) вида (Y → γ •, j ) найти все состояния в S ( j ) вида (X → α • Y β, i ) и добавить (X → α Y • β, i ) в S ( k ).
Дублирующие состояния не добавляются в набор состояний, только новые. Эти три операции повторяются до тех пор, пока в набор не перестанут быть добавлены новые состояния. Набор обычно реализуется как очередь состояний для обработки, при этом операция должна выполняться в зависимости от того, какое это состояние.
Алгоритм принимает, если (X → γ •, 0) заканчивается в S ( n ), где (X → γ) - правило верхнего уровня, а n - длина ввода, в противном случае он отклоняет.
Псевдокод [ править ]
Взято из речи и языка обработки [5] по Дэниел Джурафски и Джеймс Х. Мартин,
DECLARE ARRAY S;функция INIT (слова) S ← СОЗДАТЬ-Массив (ДЛИНА (слова) + 1) для k ← от 0 до ДЛИНЫ (слова) сделать S [k] ← ПУСТО-ЗАКАЗАННЫЙ НАБОРфункция EARLEY-PARSE (слова, грамматика) INIT (слова) ДОБАВИТЬ В НАБОР ((γ → • S, 0), S [0]) для k ← от 0 до ДЛИНЫ (слова) сделать для каждого состояния в S [k] do // S [k] может расширяться во время этого цикла если не ЗАВЕРШЕНО (состояние), то если NEXT-ELEMENT-OF (состояние) нетерминал, то ПРЕДИКТОР (состояние, k, грамматика) // нетерминальный еще делать СКАНЕР (состояние, k, слова) // терминал еще делать КОМПЛЕТЕР (состояние, k) конец конец график возвратапроцедура PREDICTOR ((A → α • Bβ, j), k, грамматика) для каждого (B → γ) в ГРАММАТИКЕ-ПРАВИЛА-ДЛЯ (B, грамматика) сделать ДОБАВИТЬ В НАБОР ((B → • γ, k), S [k]) конецпроцедура СКАНЕР ((A → α • aβ, j), k, слова) если a ⊂ ЧАСТИ РЕЧИ (слова [k]), то ДОБАВИТЬ В НАБОР ((A → αa • β, j), S [k + 1]) конецпроцедура COMPLETER ((B → γ •, x), k) для каждого (A → α • Bβ, j) в S [x] do ДОБАВИТЬ В НАБОР ((A → αB • β, j), S [k]) конецПример [ править ]
Рассмотрим следующую простую грамматику для арифметических выражений:
<P> :: = <S> # стартовое правило<S> :: = <S> «+» <M> | <M><M> :: = <M> «*» <T> | <T><T> :: = "1" | «2» | «3» | «4»При вводе:
2 + 3 * 4
Это последовательность наборов состояний:
| (указать номер) | Производство | (Источник) | Комментарий |
|---|---|---|---|
| S (0): • 2 + 3 * 4 | |||
| 1 | P → • S | 0 | стартовое правило |
| 2 | S → • S + M | 0 | предсказывать из (1) |
| 3 | S → • M | 0 | предсказывать из (1) |
| 4 | М → • М * Т | 0 | предсказать из (3) |
| 5 | М → • Т | 0 | предсказать из (3) |
| 6 | T → • число | 0 | предсказать из (5) |
| S (1): 2 • + 3 * 4 | |||
| 1 | T → число • | 0 | сканирование из S (0) (6) |
| 2 | M → T • | 0 | полное из (1) и S (0) (5) |
| 3 | М → М • * Т | 0 | полное из (2) и S (0) (4) |
| 4 | S → M • | 0 | полное из (2) и S (0) (3) |
| 5 | S → S • + M | 0 | полное из (4) и S (0) (2) |
| 6 | P → S • | 0 | полное из (4) и S (0) (1) |
| S (2): 2 + • 3 * 4 | |||
| 1 | S → S + • M | 0 | сканирование из S (1) (5) |
| 2 | М → • М * Т | 2 | предсказывать из (1) |
| 3 | М → • Т | 2 | предсказывать из (1) |
| 4 | T → • число | 2 | предсказать из (3) |
| S (3): 2 + 3 • * 4 | |||
| 1 | T → число • | 2 | сканирование из S (2) (4) |
| 2 | M → T • | 2 | полное из (1) и S (2) (3) |
| 3 | М → М • * Т | 2 | полное из (2) и S (2) (2) |
| 4 | S → S + M • | 0 | полное из (2) и S (2) (1) |
| 5 | S → S • + M | 0 | полное из (4) и S (0) (2) |
| 6 | P → S • | 0 | полное из (4) и S (0) (1) |
| S (4): 2 + 3 * • 4 | |||
| 1 | М → М * • Т | 2 | сканирование из S (3) (3) |
| 2 | T → • число | 4 | предсказывать из (1) |
| S (5): 2 + 3 * 4 • | |||
| 1 | T → число • | 4 | сканирование из S (4) (2) |
| 2 | M → M * T • | 2 | полное из (1) и S (4) (1) |
| 3 | М → М • * Т | 2 | полное из (2) и S (2) (2) |
| 4 | S → S + M • | 0 | полное из (2) и S (2) (1) |
| 5 | S → S • + M | 0 | полное из (4) и S (0) (2) |
| 6 | P → S • | 0 | полное из (4) и S (0) (1) |
Состояние (P → S •, 0) представляет собой завершенный синтаксический анализ. Это состояние также появляется в S (3) и S (1), которые являются полными предложениями.
Построение синтаксического леса [ править ]
В диссертации Эрли [6] кратко описывается алгоритм построения синтаксических деревьев путем добавления набора указателей от каждого нетерминала в элементе Эрли обратно к элементам, которые заставили его распознать. Но Томита заметил [7], что это не принимает во внимание отношения между символами, поэтому, если мы рассмотрим грамматику S → SS | b и строка bbb, он только отмечает, что каждый S может соответствовать одному или двум b, и, таким образом, производит ложные выводы для bb и bbbb, а также два правильных вывода для bbb.
Другой метод [8] - построить лес синтаксического анализа по мере продвижения, добавляя каждый элемент Эрли указателем на узел совместно используемого упакованного леса синтаксического анализа (SPPF), помеченный тройкой (s, i, j), где s - символ или LR (0) элемент (производственное правило с точкой), а i и j задают раздел входной строки, полученный этим узлом. Содержимое узла - это либо пара дочерних указателей, дающих одно происхождение, либо список «упакованных» узлов, каждый из которых содержит пару указателей и представляет одно происхождение. Узлы SPPF уникальны (есть только один с заданной меткой), но могут содержать более одного производного для неоднозначного синтаксического анализа. Таким образом, даже если операция не добавляет элемент Эрли (потому что он уже существует), она все равно может добавить производную в лес синтаксического анализа элемента.
- Прогнозируемые элементы имеют нулевой указатель SPPF.
- Сканер создает узел SPPF, представляющий нетерминал, который он сканирует.
- Затем, когда сканер или устройство завершения продвигают элемент, они добавляют производную, дочерние элементы которой являются узлом от элемента, точка которого была продвинута вперед, и одного для нового символа, который был продвинут (нетерминальный или завершенный элемент).
Узлы SPPF никогда не помечаются завершенным элементом LR (0): вместо этого они помечаются символом, который создается, так что все производные объединяются под одним узлом независимо от того, из какого альтернативного производства они происходят.
См. Также [ править ]
- CYK алгоритм
- Бесконтекстная грамматика
- Алгоритмы парсинга
Цитаты [ править ]
- ^ Кеглер, Джеффри. "Что такое алгоритм Марпы?" . Проверено 20 августа 2013 года .
- ^ Эрли, Джей (1968). Эффективный алгоритм анализа без контекста (PDF) . Карнеги-Меллон.
- ^ Эрли, Джей (1970), "Эффективный алгоритм синтаксического анализа контекстно-свободной" (PDF) , связь по АКМ , 13 (2): 94-102, DOI : 10,1145 / 362007,362035 , S2CID 47032707 , архивируются от оригинала (PDF ) на 2004-07-08
- ^ Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Чтение / МА: Аддисон-Уэсли. ISBN 978-0-201-02988-8. стр.145
- ^ Jurafsky, D. (2009). Обработка речи и языка: введение в обработку естественного языка, компьютерную лингвистику и распознавание речи . Пирсон Прентис Холл. ISBN 9780131873216.
- ^ Эрли, Джей (1968). Эффективный алгоритм анализа без контекста (PDF) . Карнеги-Меллон. п. 106.
- ↑ Томита, Масару (17 апреля 2013 г.). Эффективный синтаксический анализ естественного языка: быстрый алгоритм для практических систем . Springer Science and Business Media. п. 74. ISBN 978-1475718850. Проверено 16 сентября 2015 года .
- ↑ Скотт, Элизабет (1 апреля 2008 г.). «Разбор в стиле SPPF от распознавателей Earley» . Электронные заметки по теоретической информатике . 203 (2): 53–67. DOI : 10.1016 / j.entcs.2008.03.044 .
Другие справочные материалы [ править ]
- Эйкок, Джон; Хорспул, Р. Найджел (2002). «Практический разбор Эрли». Компьютерный журнал . 45 (6): 620–630. CiteSeerX 10.1.1.12.4254 . DOI : 10.1093 / comjnl / 45.6.620 .
- Лео, Joop MIM (1991), "Общий контекстно-свободный алгоритм синтаксического анализа работает в линейное время на каждом LR ( к ) грамматику без использования предпросмотра", Теоретическая информатика , 82 (1): 165-176, DOI : 10.1016 / 0304 -3975 (91) 90180-А , Руководство по ремонту 1112117
- Томита, Масару (1984). «Парсеры LR для естественных языков» (PDF) . ОГРАНИЧЕНИЕ . 10-я Международная конференция по компьютерной лингвистике. С. 354–357.
Реализации [ править ]
C, C ++ [ править ]
- 'Another Earley Parser (YAEP)' - библиотеки C / C ++
- 'C Earley Parser' - синтаксический анализатор Earley C
Haskell [ править ]
- 'Earley' - DSL- анализатор Earley в Haskell
Java [ править ]
- [1] - Java-реализация алгоритма Эрли.
- PEN - библиотека Java, реализующая алгоритм Эрли
- Pep - библиотека Java, которая реализует алгоритм Эрли и предоставляет диаграммы и деревья синтаксического анализа в качестве артефактов синтаксического анализа.
- digitalheir / java-probabilistic-earley-parser - библиотека Java, реализующая вероятностный алгоритм Эрли, который полезен для определения наиболее вероятного дерева синтаксического анализа из неоднозначного предложения
C # [ править ]
- coonsta / Earley - синтаксический анализатор Earley в C #
- patrickhuber / pliant - синтаксический анализатор Эрли, который объединяет улучшения, принятые Marpa, и демонстрирует алгоритм построения дерева Элизабет Скотт.
- ellisonch / CFGLib - Библиотека вероятностной контекстно-свободной грамматики (PCFG) для C # (Earley + SPPF, CYK)
JavaScript [ править ]
- Неарли - парсер Эрли, который начинает интегрировать улучшения, принятые Марпой.
- Парсер Эрли размером с пинту - игрушечный синтаксический анализатор (с аннотированным псевдокодом) для демонстрации техники Элизабет Скотт для построения совместно используемого упакованного синтаксического леса.
- lagodiuk / earley-parser-js - крошечная реализация парсера Earley на JavaScript (включая генерацию синтаксического леса)
- digitalheir / probabilistic-earley-parser-javascript - JavaScript-реализация вероятностного парсера Эрли
OCaml [ править ]
- Simple Earley - реализация простого алгоритма синтаксического анализа, подобного Earley, с документацией.
Perl [ править ]
- Marpa :: R2 - модуль Perl . Марпа - это алгоритм Эрли, который включает улучшения, сделанные Джупом Лео, Эйкоком и Хорспулом.
- Parse :: Earley - модуль Perl, реализующий оригинальный алгоритм Джея Эрли
Python [ править ]
- Lark - объектно-ориентированная процедурная реализация синтаксического анализатора Эрли, который выводит SPPF.
- NLTK - набор инструментов Python с парсером Earley
- Spark - объектно-ориентированный небольшой языковой фреймворк для Python, реализующий синтаксический анализатор Эрли.
- spark_parser - обновленная и упакованная версия парсера Spark выше, который работает как в Python 3, так и в Python 2
- earley3.py - автономная реализация алгоритма менее чем в 150 строках кода, включая генерацию синтаксического леса и образцов
- tjr_python_earley_parser - минимальный парсер Эрли в Python
Common Lisp [ править ]
- CL-Earley-parser - библиотека Common Lisp, реализующая парсер Earley
Схема, Ракетка [ править ]
- Charty-Racket - Схема - Racket реализация парсера Эрли
Ресурсы [ править ]
- Компилятор-компилятор Accent
