Парсер Эрли

Алгоритм парсинга контекстно-свободных языков

В информатике парсер Эрли — это алгоритм анализа строк , принадлежащих данному контекстно-свободному языку , хотя (в зависимости от варианта) у него могут возникнуть проблемы с некоторыми грамматиками, допускающими значение NULL . ^[1] Алгоритм, названный в честь его изобретателя Джея Эрли , представляет собой анализатор диаграмм , использующий динамическое программирование ; он в основном используется для синтаксического анализа в компьютерной лингвистике . Впервые оно было введено в его диссертацию ^[2] в 1968 году (а позже появилось в сокращенной, более разборчивой форме в журнале ^[3] ).

Парсеры Earley привлекательны тем, что могут анализировать все контекстно-свободные языки, в отличие от парсеров LR и LL , которые чаще используются в компиляторах , но могут обрабатывать только ограниченные классы языков. В общем случае парсер Эрли выполняется за кубическое время , где n — длина анализируемой строки, квадратичное время для однозначных грамматик ^[4] и линейное время для всех детерминированных контекстно-свободных грамматик . Он работает особенно хорошо, когда правила написаны леворекурсивно . ${\displaystyle {O}(n^{3})}$ ${\displaystyle {O}(n^{2})}$

Распознаватель Эрли

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

Алгоритм

В следующих описаниях α, β и γ представляют собой любую строку терминалов /нетерминалов (включая пустую строку ), 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 ) является нетерминалом , то PREDICTOR ( state , k , grammar ) // не_терминал else do SCANNER ( state , k , words ) // терминал else do КОМПЛЕТЕР ( состояние , k ) диаграмма конца конца возврата                                                   процедура PREDICTOR (( A → α• B β , j ) , k , grammar ) для каждого ( B → γ ) в GRAMMAR_RULES_FOR ( B , grammar ) do ADD_TO_SET (( B → •γ , k ) , S [ k ]) end                     процедура СКАНЕР (( A → α• a β , j ) , k , слова ) если j < ДЛИНА ( слова ) и a ⊂ ЧАСТИ_РЕЧИ ( слова [ k ]) , то ADD_TO_SET (( A → α a •β , j ) , S [ k + 1 ]) конец                     процедура 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

Это последовательность наборов состояний:

Состояние (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): вместо этого они помечаются символом, который создается таким образом, что все производные элементы объединяются под одним узлом независимо от того, из какого альтернативного производства они происходят.

Оптимизации

Филипп Маклин и Р. Найджел Хорспул в своей статье «Быстрый анализатор Эрли» сочетают анализ Эрли с анализом LR и достигают улучшения на порядок.

Смотрите также

• Алгоритм CYK
• Контекстно-свободная грамматика
• Алгоритмы разбора

Цитаты

1. Кеглер, Джеффри. «Что такое алгоритм Марпа?» . Проверено 20 августа 2013 г.
2. Эрли, Джей (1968). Эффективный алгоритм контекстно-свободного анализа (PDF) . Диссертация Карнеги-Меллона. Архивировано из оригинала (PDF) 22 сентября 2017 г. Проверено 12 сентября 2012 г.
3. Эрли, Джей (1970), «Эффективный алгоритм контекстно-свободного анализа» (PDF) , Communications of the ACM , 13 (2): 94–102, doi : 10.1145/362007.362035, S2CID  47032707, заархивировано из оригинала (PDF) ) 8 июля 2004 г.
4. Джон Э. Хопкрофт и Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг/Массачусетс: Аддисон-Уэсли. ISBN 978-0-201-02988-8.стр.145
5. Юрафски, Д. (2009). Обработка речи и языка: введение в обработку естественного языка, компьютерную лингвистику и распознавание речи. Пирсон Прентис Холл. ISBN 9780131873216.
6. Эрли, Джей (1968). Эффективный алгоритм контекстно-свободного анализа (PDF) . Диссертация Карнеги-Меллона. п. 106. Архивировано из оригинала (PDF) 22 сентября 2017 г. Проверено 12 сентября 2012 г.
7. Томита, Масару (17 апреля 2013 г.). Эффективный анализ естественного языка: быстрый алгоритм для практических систем. Springer Science and Business Media. п. 74. ИСБН 978-1475718850. Проверено 16 сентября 2015 г.
8. Скотт, Элизабет (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++

Хаскелл

• «Earley» - DSL- парсер Earley на Haskell.

Джава

• [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.