Парсер Эрли
| Сорт | Анализ грамматик, которые являются контекстно-свободными |
|---|---|
| Структура данных | Нить |
| Худшая производительность | |
| Лучшая производительность | |
| Средняя производительность |
В информатике парсер Эрли — это алгоритм анализа 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] Дэниел Джурафски и Джеймс Х. Мартин,
ОБЪЯВИТЬ МАССИВ S ;
функция INIT ( слова )
S ← CREATE_ARRAY ( LENGTH ( слова ) + 1 )
for k ← от 0 до LENGTH ( слова ) do
S [ k ] ← EMPTY_ORDERED_SET
функция EARLEY_PARSE ( слова , грамматика )
INIT ( слова )
ADD_TO_SET (( γ → • S , 0 ) , S [ 0 ])
for k ← от 0 до LENGTH ( слова ) do
для каждого состояния в S [ k ] do // S[k] может расширяться во время этого цикла,
если не FINISHED ( state ) , то
если NEXT_ELEMENT_OF ( state ) является нетерминалом do then
PREDICTOR ( state , k , grammar ) // не_терминал
else do
SCANNER ( state , k , words ) // терминал
else COMPLETER
( state , k ) end
end
return
диаграмма процедура
PREDICTOR ( ( A → α • B β , j ) , k , grammar )
для каждого ( B → γ ) в GRAMMAR_RULES_FOR ( B , grammar ) do
ADD_TO_SET (( B → •γ , k ) , S [ k ])
завершить
процедуру SCANNER (( A → α • a β , j ) , k , слова ),
если j < ДЛИНА ( слова ) и a ⊂ ЧАСТИ_РЕЧИ ( слова [ k ]) , то
ADD_TO_SET (( A → α a •β , j ) , S [ k + 1 ])
end
процедура COMPLETER (( B → γ• , x ) , k )
для каждого ( A → α• B β , j ) в S [ x ] do
ADD_TO_SET (( A → α B •β , j ) , S [ k ])
конец
Пример [ править ]
Рассмотрим следующую простую грамматику для арифметических выражений:
<P> ::= <S> # правило запуска
<S> ::= <S> "+" <M> | <М>
<M> ::= <M> "*" <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.