Имя для этого типа синтаксического анализатора, ИЛИ почему он не существует

27

Обычные синтаксические анализаторы используют весь свой ввод и создают одно дерево синтаксического анализа. Я ищу тот, который использует непрерывный поток и создает лес синтаксического анализа [ править: см. Обсуждение в комментариях относительно того, почему такое использование этого термина может быть нетрадиционным ]. Моя интуиция говорит, что я не могу быть первым человеком, которому нужен (или думаю, что мне нужен) такой синтаксический анализатор, но я искал и продолжал месяцами безрезультатно.

Я признаю, что я могу быть захвачен проблемой XY. Моя конечная цель - проанализировать поток текста, игнорируя большую его часть, и создать поток деревьев синтаксического анализа из распознанных разделов.

Поэтому мой вопрос условен: если класс парсеров с этими характеристиками существует, как он называется? А если нет, то почему нет? Какая альтернатива? Возможно, мне не хватает способа заставить обычные парсеры делать то, что я хочу.

Кевин Крумвиде
источник
1
По сути, ваш синтаксический анализатор анализирует один документ и выдает дерево синтаксического анализа, затем сразу же начинает синтаксический анализ другого документа и т. Д. Я полагаю, что это изменение поведения является тривиальным по сравнению с множеством методов синтаксического анализа, применяемых к одному документу. Отсюда и отсутствие специального термина для него.
9000
3
Я выполнил поиск в Google для «Parse Forest» и обнаружил, что их производит Earley Parser .
Роберт Харви
7
Возможно, вы ищете монадические парсеры - то есть больший парсер, состоящий из нескольких меньших парсеров. Они удобны для ситуаций, когда «остров» одного языка встроен в другой. У моего бывшего коллеги по команде разработчиков C # Люка Хобана есть хорошая статья о них: blogs.msdn.com/b/lukeh/archive/2007/08/19/…
Эрик Липперт
3
Есть некоторая путаница. Вы имеете в виду, что вам нужно дерево разбора для каждого документа в потоке и что они вместе образуют лес разбора. Это не обычное значение разбора леса. Лес разбора - это набор деревьев разбора для одного неоднозначного документа (немного упрощенного), который можно анализировать различными способами. И это то, о чем все ответы. Ваш поток состоит из множества полных документов, разделенных мусором, или это один документ, который частично искажен. Ваш документ должен быть синтаксически правильным или нет? Правильный технический ответ зависит от этого.
Бабу
1
Тогда забудьте все ответы о разборе лесов, а также Earley, GLR, Marpa, производные. Они явно не то, что вы хотите, если не появится другая причина. Являются ли ваши документы синтаксически правильными? Некоторые методы синтаксического анализа могут воссоздать контекст для частично искаженных документов. У вас есть точный синтаксис для этих документов. Это один и тот же для всех? Вы действительно хотите деревья разбора, или вы будете удовлетворены, изолируя документы, и, возможно, проанализировать их позже, отдельно. Я думаю, я знаю, что может улучшить вашу обработку, но я не уверен, что вы можете получить это с полки.
Бабу

Ответы:

48

Парсер, который возвращает (частичный) результат до того, как весь вход был использован, называется инкрементным парсером . Инкрементальный синтаксический анализ может быть затруднен, если в грамматике есть локальные неоднозначности, которые решаются только позже во входных данных. Еще одна сложность - симулировать те части дерева разбора, которые еще не были достигнуты.

Парсер, который возвращает лес всех возможных деревьев синтаксического анализа, то есть возвращает дерево синтаксического анализа для каждого возможного вывода неоднозначной грамматики, называется ... Я не уверен, что у этих вещей есть имя. Я знаю, что генератор парсеров Marpa способен на это, но любой парсер, основанный на Earley или GLR, должен справиться с этим.


Тем не менее, вы, кажется, не хотите ничего этого. У вас есть поток с несколькими внедренными документами, между которыми находится мусор:

 garbagegarbage{key:42}garbagegarbage[1,2,3]{id:0}garbage...

Похоже, вам нужен парсер, который пропускает мусор и (лениво) выдает последовательность AST для каждого документа. Это можно рассматривать как инкрементальный синтаксический анализатор в самом общем смысле. Но вы бы на самом деле реализовали цикл следующим образом:

while stream is not empty:
  try:
    yield parse_document(stream at current position)
  except:
    advance position in stream by 1 character or token

parse_docmentФункция затем будет обычный, ненаращиваемый анализатор. Существует небольшая сложность убедиться, что вы прочитали достаточно входного потока для успешного анализа. Как это можно сделать, зависит от типа используемого вами анализатора. Возможности включают увеличение буфера при определенных ошибках синтаксического анализа или использование ленивого токенизации.

Ленивый токенизация, вероятно, является наиболее элегантным решением из-за вашего потока ввода. Вместо того, чтобы фаза лексера создавала фиксированный список токенов, парсер лениво запрашивал следующий токен из обратного вызова лексера [1] . Затем лексер будет потреблять столько потока, сколько необходимо. Таким образом, синтаксический анализатор может потерпеть неудачу только тогда, когда достигнут реальный конец потока или когда произошла реальная ошибка синтаксического анализа (т. Е. Мы начали анализ, находясь еще в мусоре).

[1] Лексер, управляемый обратным вызовом, является хорошей идеей и в других контекстах, потому что это может избежать некоторых проблем с сопоставлением длинных токенов .

Если вы знаете, какие документы вы ищете, вы можете оптимизировать пропуск, чтобы остановиться только на перспективных местах. Например, документ JSON всегда начинается с символа {или [. Следовательно, мусором является любая строка, которая не содержит эти символы.

Амон
источник
5
Твой псевдокод - это то, чем я занимаюсь, но я подумал, что это просто уродливый хак. Парсер выдает два вида исключений ( NO_MATCHи UNDERFLOW), которые позволяют мне определить, следует ли мне продвигать позицию потока или ждать большего ввода.
Кевин Крумвиде,
5
@Kevin: Я тоже использую это, с некоторыми функциями безопасности, для обработки входящих данных из сети в проприетарном формате. Ничего хакерского в этом нет!
Легкость гонок с Моникой
5

Нет определенного имени для парсера, который это делает. Но я выделю один алгоритм, который делает это: разбор с производными .

Он потребляет вход, по одному токену за раз. Это будет производить анализ леса в конце ввода. В качестве альтернативы, вы также можете получить весь лес синтаксического анализа в процессе синтаксического анализа ( частичный синтаксический анализ).

Синтаксический анализ с производными обрабатывает грамматики без контекста и создает лес синтаксического анализа для неоднозначных грамматик.

Это действительно элегантная теория, но она только зарождается и не получила широкого распространения. Matt Might имеет список ссылок на различные реализации в Scala / Racket / и т.д.

Эту теорию легче освоить, если вы начнете с распознавания с производными (то есть начните с получения производных языков , с целью распознавания некоторого ввода, чтобы определить, является ли он действительным или нет), а затем измените программу для анализа с производными ( то есть измените его так, чтобы он не брал производные от языков , он брал производные от синтаксических анализаторов и вычислял лес разбора).

кукурузные стебли
источник
4
Downvoter: не могли бы вы объяснить, что было достойно downvote? Если есть что-то, что мне нужно исправить или улучшить, это было бы неплохо узнать.
Кукурузные початки
Я не downvoter, и я бы не мечтал о понижении голосов без комментариев. Но ваша энтузиастическая статья не имеет никакого отношения ко многим существующим анализаторам, которые достигают того же результата, касающемуся сложности и разбора леса. Функциональное программирование великолепно, но сравнивать результаты с существующей литературой по этому вопросу тоже приятно. Насколько удобен ваш синтаксический лес для дальнейшего использования?
Бабу
@babou: для записи, я не автор этого блога / бумаги. Но да, я согласен, я мог бы добавить больше деталей, сравнивая этот алгоритм с другими, и объяснить его подробно. У Мэтта Мэйта есть целая лекция об этом , но было бы хорошо объединить это в этот ответ. Если у меня будет время, я постараюсь расширить этот ответ.
Кукурузные початки
1
Не тратьте слишком много времени на его расширение. Насколько я могу судить, это не то, что после ОП. Его вопрос требует внимательного прочтения. Его использование разбора леса не ваше. - Что касается деривативов ... звучит так, как будто это должно быть интересно, но нужно связать это с предыдущей работой ... и есть значительная часть этого. Но я не имею ввиду в этом ответе, а в статьях M Might или его блога.
Бабу
2

Далеко от идеала, но я видел, как это делалось не раз: в каждой строке ввода попытайтесь разобрать. если не получится, оставьте строку и добавьте следующую. В псевдокоде:

buffer = ''
for each line from input:
    buffer = buffer + line
    if can parse buffer:
        emit tree
        buffer = ''

Большая проблема в том, что в некоторых языках вы не можете знать, завершено ли выражение, прежде чем читать следующую строку. В этом случае вам кажется, что вы могли бы прочитать следующий и проверить, является ли это правильным началом или допустимым продолжением ... Но для этого вам нужен точный синтаксис языка

Хуже того, в этих языках нетрудно создать патологический случай, который не может быть проанализирован до конца файла, даже если это не было одно длинное утверждение.

Хавьер
источник
0

В двух словах

Кажется, что быстрое решение вашей проблемы - определить REGEX или FSA (конечный автомат), который распознает все возможные начала документов (допускаются ложные срабатывания, которые на самом деле не соответствуют документу). Затем вы можете очень быстро запустить его на своем входе, чтобы определить следующее место, где документ может начинаться с небольшим количеством ошибок. Это может вызвать несколько ошибочных позиций для начала документа, но они будут распознаны синтаксическим анализатором и отменены.

Таким образом, Finite State Automaton может быть именем парсера, которое вы искали. :)

Проблема

Всегда трудно понять практическую проблему, особенно когда словарь может иметь много толкований. Лес синтаксического анализа слов был придуман (afaik) для анализа без контекста (CF) неоднозначных предложений, имеющих несколько деревьев синтаксического анализа. Это может быть несколько обобщено для разбора решетки предложений или для других типов грамматики. Отсюда все ответы о Earley, GLR, Marpa и производных парсерах (есть много других), которые не были уместны в этом случае.

Но это, очевидно, не то, что вы имеете в виду. Вы хотите проанализировать уникальную строку, которая является последовательностью однозначных документов, и получить дерево синтаксического анализа для каждого , или какое-то структурированное представление, поскольку вы на самом деле не говорите, как определяется синтаксис ваших документов, откуда он стоит формальная языковая точка зрения. То, что у вас есть, - это алгоритм и таблицы, которые будут выполнять работу разбора при запуске в начале документа. Быть по сему.

Фактическая проблема заключается в том, что ваш поток документов содержит значительный мусор, который разделяет документы. И, похоже, ваша сложность состоит в том, чтобы сканировать этот мусор достаточно быстро. Ваша текущая техника заключается в том, чтобы начать с самого начала и попытаться выполнить сканирование с первого символа и переходить к перезапуску на следующем символе каждый раз, когда происходит сбой, до тех пор, пока не будет отсканирован весь документ. Затем вы повторяете, начиная с первого символа после того, как документ только что отсканирован.

Это также решение, предложенное @amon во второй части его ответа .

Это может быть не очень быстрое решение (у меня нет возможности проверить), потому что маловероятно, что код синтаксического анализатора оптимизирован для очень эффективного запуска в начале документа. При обычном использовании он делает это только один раз, так что это не горячая точка с точки зрения оптимизации. Следовательно, ваше умеренное счастье с этим решением не слишком удивительно.

Так что вам действительно нужен алгоритм, который может быстро найти начало документа, который начинается с массы мусора. И вам повезло: такие алгоритмы существуют. И я уверен, что вы это знаете: это называется поиском REGEX.

Простое решение

Что вам нужно сделать, это проанализировать спецификацию ваших документов, чтобы найти, как эти документы начинаются. Я не могу точно сказать вам, как, поскольку я не уверен, как их синтаксическая структура организована формально. Возможно, все они начинаются с какого-то слова из конечного списка, возможно, смешанного с некоторыми пунктуацией или цифрами. Это для вас, чтобы проверить.

Вам нужно определить конечный автомат (FSA) или, что то же самое, для большинства программистов регулярное выражение (REGEX), которое может распознавать первые несколько символов документа: чем больше, тем лучше, но это не обязательно должно быть очень большой (так как это может занять время и пространство). Это должно быть относительно легко сделать из спецификации ваших документов, и, вероятно, это можно сделать автоматически с помощью программы, которая читает спецификацию ваших документов.

После того, как вы создали свое регулярное выражение, вы можете запустить его в своем входном потоке, чтобы очень быстро перейти к началу вашего первого (или следующего) документа следующим образом:

Я предполагаю:
- docstartэто регулярное выражение, которое соответствует началу всех документов
- search(regex, stream)это функция, которая ищет streamподстроку, которая соответствует regex. Когда он возвращается, поток сводится к своему подпотоку суффикса, начинающемуся с начала первой совпадающей подстроки, или к пустому потоку совпадение не найдено.
- parse(stream)пытается разобрать документ с начала потока (то, что от него осталось) и возвращает дерево разбора в любом формате, или происходит сбой. Когда он возвращается, поток сводится к своему подпотоку суффикса, начиная с позиции, следующей сразу за концом проанализированного документа. Это вызывает исключение, если анализ не удался.

forest = empty_forest
search(docstart, stream)
while stream is not empty:
  try:
    forest = forest + parse(stream)
  except
    remove first character from stream
  search(docstart, stream)

Обратите внимание, что удаление первого символа необходимо, чтобы при следующем поиске снова не было найдено такое же совпадение.

Конечно, сокращение потока - это изображение. Это может быть просто указатель на поток.

И последнее замечание: ваше регулярное выражение не обязательно должно быть слишком точным, если оно распознает все начала. Если он иногда распознает строку, которая не может быть началом документа (ложное срабатывание), то единственным штрафом является стоимость одного бесполезного вызова парсера.

Так что это может помочь упростить регулярное выражение, если это полезно.

О возможности более быстрого решения

Вышеупомянутое решение должно работать довольно хорошо в большинстве случаев. Однако, если у вас действительно много мусора и терабайт файла для обработки, могут быть другие алгоритмы, которые работают быстрее.

Идея основана на алгоритме поиска строк Бойера-Мура . Этот алгоритм может очень быстро найти поток для отдельной строки, поскольку он использует структурный анализ строки, чтобы пропустить чтение большей части потока, перепрыгивая фрагменты, даже не глядя на них. Это самый быстрый алгоритм поиска для одной строки.

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

Я оставляю вам один или два указателя, которые я нашел в Интернете, в том числе один, который, по-видимому, является рецензируемым исследовательским документом , но вы должны рассматривать это как более умозрительный, возможно, исследовательский, который следует рассматривать, только если у вас были серьезные проблемы с производительностью. И, вероятно, нет программы полки, которая сделает это.

Babou
источник
-2

То, что вы описываете, может быть описано как SAX против SOM.

SAX - (Простой API для XML) - это API синтаксического анализатора последовательного доступа, разработанный списком рассылки XML-DEV для документов XML.

SOM - (объектная модель схемы XML) произвольный доступ к представлению в памяти файла XML

Существуют реализации обоих типов в C # и Java, и, возможно, многие другие. Обычно XSD или DTD является необязательным.

Радость SAX заключается в том, что она занимает мало памяти, что отлично подходит для больших файлов XML. Компромисс в том, что произвольный доступ с использованием SAX либо не существует, либо медленен, и, что еще хуже, время разработки обычно значительно больше, чем при использовании SOM. Очевидная проблема с SOM - потенциально большие требования к оперативной памяти.

Этот ответ не применим для всех платформ и всех языков.

D-Mac
источник
1
Как вы думаете, почему OP анализирует XML?
Дэн Пичельман,
1
Это не отвечает на вопрос.
@ Снеговик До сих пор почти ничего не отвечало на вопрос, включая первую половину принятого ответа. Нет смысла ковыряться на ком-либо. Вопрос требует внимательного прочтения.
Бабу
@babou Я никого не подбирал, я объяснял свое отрицательное мнение.
@ Снеговик, объясняющий мое понижение . Это справедливо, и я бы хотел, чтобы больше пользователей делали это. Я не являюсь носителем языка: выбор его может быть слишком сильным выражением. Просто все делают необоснованные предположения. Так что это даже не стоит замечать. Это правда, что этот кажется немного больше, чем другие.
Бабу