Парсер Эрли
| Сорт | Анализ грамматик, которые являются контекстно-свободными |
|---|---|
| Структура данных | Нить |
| Худшая производительность | |
| Лучшая производительность | |
| Средняя производительность |
В информатике парсер Эрли — это алгоритм анализа , строк принадлежащих данному контекстно-свободному языку , хотя (в зависимости от варианта) у него могут возникнуть проблемы с некоторыми грамматиками, допускающими значение NULL . [1] Алгоритм, названный в честь его изобретателя Джея Эрли , представляет собой анализатор диаграмм , использующий динамическое программирование ; он в основном используется для синтаксического анализа в компьютерной лингвистике . Впервые он был представлен в своей диссертации. [2] в 1968 году (а позже в сокращенном, более разборчивом виде появился в журнале [3] ).
Парсеры Earley привлекательны тем, что они могут анализировать все контекстно-свободные языки, в отличие от парсеров LR и LL , которые чаще используются в компиляторах , но могут обрабатывать только ограниченные классы языков. В общем случае парсер Эрли выполняется в кубическом времени. , где n — длина анализируемой строки, квадратичное время для однозначных грамматик , [4] и линейное время для всех детерминированных контекстно-свободных грамматик . Он работает особенно хорошо, когда правила написаны леворекурсивно .
Распознаватель Эрли
[ редактировать ]Следующий алгоритм описывает распознаватель Эрли. Распознаватель можно модифицировать для создания дерева разбора по мере распознавания, и таким образом превратить его в анализатор.
Алгоритм
[ редактировать ]В следующих описаниях α, β и γ представляют любую строку терминалов /нетерминалов (включая пустую строку ), X и Y представляют собой отдельные нетерминалы, а a представляет символ терминала.
Алгоритм Эрли представляет собой алгоритм динамического программирования сверху вниз . Далее мы используем точечную нотацию Эрли: для данной продукции 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;
function INIT(words)
S ← CREATE_ARRAY(LENGTH(words) + 1)
for k ← from 0 to LENGTH(words) do
S[k] ← EMPTY_ORDERED_SET
function EARLEY_PARSE(words, grammar)
INIT(words)
ADD_TO_SET((γ → •S, 0), S[0])
for k ← from 0 to LENGTH(words) do
for each state in S[k] do // S[k] can expand during this loop
if not FINISHED(state) then
if NEXT_ELEMENT_OF(state) is a nonterminal then
PREDICTOR(state, k, grammar) // non_terminal
else do
SCANNER(state, k, words) // terminal
else do
COMPLETER(state, k)
end
end
return chart
procedure PREDICTOR((A → α•Bβ, j), k, grammar)
for each (B → γ) in GRAMMAR_RULES_FOR(B, grammar) do
ADD_TO_SET((B → •γ, k), S[k])
end
procedure SCANNER((A → α•aβ, j), k, words)
if j < LENGTH(words) and a ⊂ PARTS_OF_SPEECH(words[k]) then
ADD_TO_SET((A → αa•β, j), S[k+1])
end
procedure COMPLETER((B → γ•, x), k)
for each (A → α•Bβ, j) in S[x] do
ADD_TO_SET((A → αB•β, j), S[k])
end
Пример
[ редактировать ]Рассмотрим следующую простую грамматику для арифметических выражений:
<P> ::= <S> # the start rule
<S> ::= <S> "+" <M> | <M>
<M> ::= <M> "*" <T> | <T>
<T> ::= "1" | "2" | "3" | "4"
С вводом:
2 + 3 * 4
Это последовательность наборов состояний:
| (государственный номер) | Производство | (Источник) | Комментарий |
|---|---|---|---|
| С(0): • 2 + 3 * 4 | |||
| 1 | П → • С | 0 | начать правило |
| 2 | С → • С + М | 0 | прогнозировать по (1) |
| 3 | С → • М | 0 | прогнозировать по (1) |
| 4 | М → • М * Т | 0 | предсказать по (3) |
| 5 | М → • Т | 0 | предсказать по (3) |
| 6 | Т → • номер | 0 | предсказать по (5) |
| С(1): 2 • + 3 * 4 | |||
| 1 | Т → номер • | 0 | сканирование из S(0)(6) |
| 2 | М → Т • | 0 | полное из (1) и S(0)(5) |
| 3 | М → М • * Т | 0 | полное из (2) и S(0)(4) |
| 4 | С → М • | 0 | полное из (2) и S(0)(3) |
| 5 | С → С • + М | 0 | полное из (4) и S(0)(2) |
| 6 | П → С • | 0 | полное из (4) и S(0)(1) |
| С(2): 2 + • 3 * 4 | |||
| 1 | С → С + • М | 0 | сканирование из S(1)(5) |
| 2 | М → • М * Т | 2 | прогнозировать по (1) |
| 3 | М → • Т | 2 | прогнозировать по (1) |
| 4 | Т → • номер | 2 | предсказать по (3) |
| С(3): 2 + 3 • * 4 | |||
| 1 | Т → номер • | 2 | сканирование из S(2)(4) |
| 2 | М → Т • | 2 | полное из (1) и S(2)(3) |
| 3 | М → М • * Т | 2 | полное из (2) и S(2)(2) |
| 4 | С → С + М • | 0 | полное из (2) и S(2)(1) |
| 5 | С → С • + М | 0 | полное из (4) и S(0)(2) |
| 6 | П → С • | 0 | полное из (4) и S(0)(1) |
| С(4): 2 + 3 * • 4 | |||
| 1 | М → М * • Т | 2 | сканирование из S(3)(3) |
| 2 | Т → • номер | 4 | прогнозировать по (1) |
| С(5): 2 + 3 * 4 • | |||
| 1 | Т → номер • | 4 | сканирование из S(4)(2) |
| 2 | М → М * Т • | 2 | полное из (1) и S(4)(1) |
| 3 | М → М • * Т | 2 | полное из (2) и S(2)(2) |
| 4 | С → С + М • | 0 | полное из (2) и S(2)(1) |
| 5 | С → С • + М | 0 | полное из (4) и S(0)(2) |
| 6 | П → С • | 0 | полное из (4) и S(0)(1) |
Состояние (P → S •, 0) представляет собой завершенный синтаксический анализ. Это состояние также появляется в S(3) и S(1), которые являются полными предложениями.
Построение леса разбора
[ редактировать ]Диссертация Эрли [6] кратко описывает алгоритм построения деревьев синтаксического анализа путем добавления набора указателей от каждого нетерминала в элементе Эрли обратно к элементам, которые привели к его распознаванию. Но Томита заметил [7] что при этом не учитываются отношения между символами, поэтому, если мы рассмотрим грамматику S → SS | b и строку bbb, он только отмечает, что каждое S может соответствовать одному или двум b, и, таким образом, создает ложные выводы для bb и bbbb, а также два правильных вывода для bbb.
Другой метод [8] заключается в построении леса синтаксического анализа по ходу дела, дополняющем каждый элемент Earley указателем на узел общего упакованного леса синтаксического анализа (SPPF), помеченный тройкой (s, i, j), где s — символ или элемент LR (0). (продукционное правило с точкой), а i и j обозначают часть входной строки, полученную этим узлом. Содержимое узла представляет собой либо пару дочерних указателей, дающих одно производное, либо список «упакованных» узлов, каждый из которых содержит пару указателей и представляет одно производное. Узлы SPPF уникальны (есть только один с заданной меткой), но могут содержать более одного вывода для неоднозначного анализа. Таким образом, даже если операция не добавляет элемент Эрли (поскольку он уже существует), она все равно может добавить производный элемент в лес синтаксического анализа элемента.
- Прогнозируемые элементы имеют нулевой указатель SPPF.
- Сканер создает узел SPPF, представляющий сканируемый нетерминал.
- Затем, когда сканер или средство завершения продвигает элемент, они добавляют деривацию, дочерними элементами которой являются узел элемента, точка которого была продвинута, и узел для нового символа, над которым была продвинута (нетерминальный или завершенный элемент).
Узлы SPPF никогда не помечаются завершенным элементом LR(0): вместо этого они помечаются символом, который создается таким образом, что все производные элементы объединяются под одним узлом независимо от того, из какого альтернативного производства они происходят.
Оптимизации
[ редактировать ]Филипп Маклин и Р. Найджел Хорспул в своей статье «Быстрый анализатор Эрли» сочетают анализ Эрли с анализом LR и достигают улучшения на порядок.
См. также
[ редактировать ]Цитаты
[ редактировать ]- ^ Кеглер, Джеффри. «Что такое алгоритм Марпа?» . Проверено 20 августа 2013 г.
- ^ Эрли, Джей (1968). Эффективный алгоритм контекстно-свободного анализа (PDF) . Диссертация Карнеги-Меллона. Архивировано из оригинала (PDF) 22 сентября 2017 г. Проверено 12 сентября 2012 г.
- ^ Эрли, Джей (1970), «Эффективный алгоритм контекстно-свободного анализа» (PDF) , Communications of the ACM , 13 (2): 94–102, doi : 10.1145/362007.362035 , S2CID 47032707 , заархивировано из оригинала (PDF) 8 июля 2004 г.
- ^ Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг/Массачусетс: Аддисон-Уэсли. ISBN 978-0-201-02988-8 . стр.145
- ^ Юрафский, Д. (2009). Обработка речи и языка: введение в обработку естественного языка, компьютерную лингвистику и распознавание речи . Пирсон Прентис Холл. ISBN 9780131873216 .
- ^ Эрли, Джей (1968). Эффективный алгоритм контекстно-свободного анализа (PDF) . Диссертация Карнеги-Меллона. п. 106. Архивировано из оригинала (PDF) 22 сентября 2017 г. Проверено 12 сентября 2012 г.
- ^ Томита, Масару (17 апреля 2013 г.). Эффективный анализ естественного языка: быстрый алгоритм для практических систем . Springer Science and Business Media. п. 74. ИСБН 978-1475718850 . Проверено 16 сентября 2015 г.
- ^ Скотт, Элизабет (1 апреля 2008 г.). «Разбор в стиле SPPF от распознавателей Earley» . Электронные заметки по теоретической информатике . 203 (2): 53–67. дои : 10.1016/j.entcs.2008.03.044 .
Другие справочные материалы
[ редактировать ]- Эйкок, Джон; Хорспул, Р. Найджел (2002). «Практический анализ Эрли». Компьютерный журнал . 45 (6): 620–630. CiteSeerX 10.1.1.12.4254 . дои : 10.1093/comjnl/45.6.620 .
- Лео, Джуп МИМ (1991), «Общий алгоритм контекстно-свободного анализа, работающий в линейном времени для каждой грамматики LR( k ) без использования опережающего просмотра», Theoretical Computer Science , 82 (1): 165–176, doi : 10.1016/0304 -3975(91)90180-А , МР 1112117
- Томита, Масару (1984). «LR-парсеры для естественных языков» (PDF) . ОХЛАЖДЕНИЕ . 10-я Международная конференция по компьютерной лингвистике. стр. 354–357.
Реализации
[ редактировать ]С, С++
[ редактировать ]- «Еще один Earley Parser (YAEP)» — C / C++ библиотеки
Хаскелл
[ редактировать ]Ява
[ редактировать ]- [1] - Java-реализация алгоритма Эрли.
- PEN — библиотека Java, реализующая алгоритм Эрли.
- Pep — библиотека Java, реализующая алгоритм Эрли и предоставляющая диаграммы и деревья синтаксического анализа в качестве артефактов синтаксического анализа.
- digitalheir/java-probabilistic-earley-parser — библиотека Java, реализующая вероятностный алгоритм Эрли, полезный для определения наиболее вероятного дерева разбора из неоднозначного предложения
С#
[ редактировать ]- coonsta/earley — парсер Earley на C#.
- patrickhuber/pliant — парсер Earley, который объединяет улучшения, принятые Marpa, и демонстрирует алгоритм построения дерева Элизабет Скотт.
- ellisonch/CFGLib — библиотека вероятностной контекстно-свободной грамматики (PCFG) для C# (Earley + SPPF, CYK)
JavaScript
[ редактировать ]- Nearley - парсер Earley, который начинает интегрировать улучшения, принятые Marpa.
- Парсер Earley размером с пинту - игрушечный парсер (с аннотированным псевдокодом), демонстрирующий технику Элизабет Скотт для построения общего упакованного леса синтаксического анализа.
- lagodiuk/earley-parser-js — крошечная JavaScript-реализация парсера Earley (включая генерацию леса синтаксического анализа)
- digitalheir/probabilistic-earley-parser-javascript — JavaScript-реализация вероятностного парсера Earley
OCaml
[ редактировать ]- Simple Earley — реализация простого алгоритма анализа, подобного Эрли, с документацией.
Перл
[ редактировать ]- Marpa::R2 — модуль Perl . Марпа. Архивировано 7 марта 2013 г. в Wayback Machine. Это алгоритм Эрли, включающий улучшения, внесенные Джупом Лео, а также Эйкоком и Хорспулом.
- Parse::Earley — модуль Perl, реализующий оригинальный алгоритм Джея Эрли.
Питон
[ редактировать ]- Lark — объектно-ориентированная процедурная реализация парсера Earley, выдающая SPPF.
- NLTK — набор инструментов Python с парсером Earley
- Spark - небольшая объектно-ориентированная языковая среда для Python, реализующая парсер Earley.
- spark_parser — обновленная и упакованная версия парсера Spark, описанного выше, который работает как в Python 3, так и в Python 2.
- Earley3.py — автономная реализация алгоритма, состоящая менее чем из 150 строк кода, включая генерацию леса синтаксического анализа и выборок.
- tjr_python_earley_parser — минимальный парсер Эрли на Python
- Earley Parsing — хорошо объясненное и полное руководство по парсеру Earley на Python с обработкой эпсилона и оптимизацией Leo для правой рекурсии.
Ржавчина
[ редактировать ]- Сантьяго — набор инструментов для лексического анализа и синтаксического анализа для Rust, реализующий парсер Earley.
Общий Лисп
[ редактировать ]- CL-Earley-parser — библиотека Common Lisp, реализующая парсер Earley.
Схема, Ракетка
[ редактировать ]- Charty-Racket – Схема – Рэкетная реализация парсера Earley
Вольфрам
[ редактировать ]- надлежащийEarleyParser — базовая минимальная реализация парсера Earley на языке программирования Wolfram с некоторыми важными тестовыми примерами.
Ресурсы
[ редактировать ]- Компилятор Accent. Архивировано 18 июля 2011 г. на Wayback Machine.