Анализатор Early

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

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

Парсеры Early привлекательны тем, что они могут анализировать все контекстно-свободные языки, в отличие от парсеров LR и парсеров LL , которые чаще используются в компиляторах , но могут обрабатывать только ограниченные классы языков. Парсер Earley выполняется за кубическое время в общем случае , где 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 ( ДЛИНА ( слова ) + 1 ) для k ← от 0 до ДЛИНА ( слова ) сделать S [ k ] ← EMPTY_ORDERED_SET                 function EARLEY_PARSE ( words , grammar ) INIT ( words ) ADD_TO_SET ( ( γ → • S , 0 ) , S [ 0 ]) for k ← от 0 до LENGTH ( words ) do для каждого состояния в S [ k ] do // S[k] может расширяться во время этого цикла if not FINISHED ( state ) then if NEXT_ELEMENT_OF ( state ) is nonterminal then PREDICTOR ( state , k , grammar ) // non_terminal else do SCANNER ( state , k , words ) // terminal else do COMPLETER ( state , k ) end end return chart                                                   процедура PREDICTOR (( A → α• B β , j ) , k , грамматика ) для каждого ( B → γ ) в GRAMMAR_RULES_FOR ( B , грамматика ) сделать ADD_TO_SET (( B → •γ , k ) , S [ k ]) конец                     процедура СКАНЕР (( A → α• a β , j ) , k , слова ) если j < ДЛИНА ( слова ) и a ⊂ ЧАСТИ_РЕЧИ ( слова [ k ]) тогда ДОБАВИТЬ_В_НАБОР (( A → α a •β , j ) , S [ k + 1 ]) конец                     процедура COMPLETER (( B → γ• , x ) , k ) для каждого ( A → α• B β , j ) в S [ x ] сделать ADD_TO_SET (( A → α B •β , j ) , S [ k ]) конец                    

Пример

Рассмотрим следующую простую грамматику арифметических выражений:

<P> ::= <S> # начальное правило<С> ::= <С> "+" <М> | <М><М> ::= <М> "*" <Т> | <Т><Т> ::= "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] заключается в построении леса разбора по мере продвижения, дополняя каждый элемент Earley указателем на узел общего упакованного леса разбора (SPPF), помеченный тройкой (s, i, j), где s — это символ или элемент LR(0) (правило производства с точкой), а i и j задают раздел входной строки, полученный этим узлом. Содержимое узла — это либо пара дочерних указателей, дающих один вывод, либо список «упакованных» узлов, каждый из которых содержит пару указателей и представляет один вывод. Узлы SPPF уникальны (существует только один с заданной меткой), но могут содержать более одного вывода для неоднозначных разборов. Таким образом, даже если операция не добавляет элемент Earley (потому что он уже существует), она все равно может добавить вывод в лес разбора элемента.

• Прогнозируемые элементы имеют нулевой указатель SPPF.
• Сканер создает узел SPPF, представляющий сканируемый им нетерминал.
• Затем, когда сканер или завершитель продвигает элемент, они добавляют производную, дочерними элементами которой являются узел элемента, точка которого была продвинута, и узел для нового символа, через который был продвинут (нетерминальный или завершенный элемент).

Узлы SPPF никогда не помечаются завершенным элементом LR(0): вместо этого они помечаются символом, который создается, так что все производные объединяются под одним узлом независимо от того, из какого альтернативного производства они происходят.

Оптимизации

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

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

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

Цитаты

1. Кеглер, Джеффри. «Что такое алгоритм Марпы?» . Получено 20 августа 2013 г.
2. Эрли, Джей (1968). Эффективный контекстно-свободный алгоритм синтаксического анализа (PDF) . Диссертация Карнеги-Меллона. Архивировано из оригинала (PDF) 2017-09-22 . Получено 2012-09-12 .
3. Эрли, Джей (1970), «Эффективный контекстно-свободный алгоритм синтаксического анализа» (PDF) , Communications of the ACM , 13 (2): 94–102, doi :10.1145/362007.362035, S2CID  47032707, архивировано из оригинала (PDF) 2004-07-08
4. Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Чтение/MA: Addison-Wesley. ISBN 978-0-201-02988-8.стр.145
5. Jurafsky, D. (2009). Обработка речи и языка: Введение в обработку естественного языка, компьютерную лингвистику и распознавание речи. Pearson Prentice Hall. ISBN 9780131873216.
6. Эрли, Джей (1968). Эффективный контекстно-свободный алгоритм синтаксического анализа (PDF) . Диссертация Карнеги-Меллона. стр. 106. Архивировано из оригинала (PDF) 22-09-2017 . Получено 12-09-2012 .
7. Томита, Масару (17 апреля 2013 г.). Эффективный синтаксический анализ естественного языка: быстрый алгоритм для практических систем. Springer Science and Business Media. стр. 74. ISBN 978-1475718850. Получено 16 сентября 2015 г.
8. Скотт, Элизабет (1 апреля 2008 г.). «SPPF-Style Parsing From Early Recognizers». Electronic Notes in Theoretical Computer Science . 203 (2): 53–67. doi : 10.1016/j.entcs.2008.03.044 .

Другие справочные материалы

• Aycock, John; Horspool, R. Nigel (2002). «Практический анализ Early». The Computer Journal . 45 (6): 620–630. CiteSeerX  10.1.1.12.4254 . doi :10.1093/comjnl/45.6.620.
• Лео, Йоп МИМ (1991), «Общий контекстно-свободный алгоритм синтаксического анализа, работающий за линейное время на каждой грамматике LR( k ) без использования опережающего просмотра», Теоретическая информатика , 82 (1): 165–176, doi : 10.1016/0304-3975(91)90180-A , MR  1112117

• Томита, Масару (1984). «LR-парсеры для естественных языков» (PDF) . COLING . 10-я Международная конференция по компьютерной лингвистике. стр. 354–357.

Реализации

С, С++

• «Еще один ранний парсер (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 — анализатор Эрли, который объединяет усовершенствования, принятые Марпой, и демонстрирует алгоритм построения дерева Элизабет Скотт.
• ellisonch/CFGLib - Библиотека вероятностной контекстно-свободной грамматики (PCFG) для C# (Earley + SPPF, CYK)

JavaScript

• Nearley – анализатор Early, который начинает интегрировать усовершенствования, принятые Marpa
• Парсер Earley размером с пинту – игрушечный парсер (с аннотированным псевдокодом) для демонстрации методики Элизабет Скотт по созданию общего упакованного леса парсинга
• lagodiuk/earley-parser-js – небольшая реализация парсера Earley на JavaScript (включая генерацию parsing-forest)
• digitalheir/probabilistic-earley-parser-javascript — реализация вероятностного анализатора Эрли на JavaScript

OCaml

• Simple Earley — реализация простого алгоритма синтаксического анализа типа Earley с документацией.

Перл

• Marpa::R2 – модуль Perl . Marpa, архив 2013-03-07 на Wayback Machine, представляет собой алгоритм Эрли, включающий улучшения, сделанные Джупом Лео, а также Эйкоком и Хорспулом.
• Parse::Earley – модуль Perl, реализующий оригинальный алгоритм Джея Эрли

Питон

• Lark — объектно-ориентированная, процедурная реализация парсера Эрли, которая выводит SPPF.
• NLTK – набор инструментов Python с анализатором Earley
• Spark – небольшой объектно-ориентированный языковой фреймворк для Python, реализующий парсер Earley
• spark_parser – обновленная и упакованная версия анализатора Spark, представленного выше, которая работает как в Python 3, так и в Python 2
• earley3.py – автономная реализация алгоритма менее чем в 150 строках кода, включая генерацию синтаксического леса и образцов
• tjr_python_earley_parser — минимальный парсер Эрли на Python
• Анализ Earley — подробное и полное руководство по анализу Earley на Python с обработкой эпсилон и оптимизацией Leo для правой рекурсии.

Ржавчина

• Сантьяго – набор инструментов для лексического анализа и синтаксического анализа для Rust, реализующий синтаксический анализатор Эрли.

Общий Лисп

• CL-Earley-parser – библиотека Common Lisp, реализующая анализатор Earley

Схема, Рэкет

• Charty-Racket – реализация синтаксического анализатора Earley на языке Scheme - Racket

Вольфрам

• properEarleyParser — базовая минимальная реализация парсера Earley на языке программирования Wolfram с некоторыми необходимыми тестовыми примерами.

Ресурсы

• Компилятор Accent-компилятор Архивировано 2011-07-18 на Wayback Machine