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

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

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

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

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

Парсер, который возвращает лес всех возможных деревьев синтаксического анализа, то есть возвращает дерево синтаксического анализа для каждого возможного вывода неоднозначной грамматики, называется ... Я не уверен, что у этих вещей есть имя. Я знаю, что генератор парсеров 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 всегда начинается с символа {или [. Следовательно, мусором является любая строка, которая не содержит эти символы.

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

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

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

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

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

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

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

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

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

В двух словах

Кажется, что быстрое решение вашей проблемы - определить 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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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