Nano Hash - криптовалюты, майнинг, программирование

Разбор контекстно-свободных языков в потоке токенов

Проблема

Учитывая контекстно-свободную грамматику с произвольными правилами и потоком токенов, как можно эффективно идентифицировать фрагменты потока, соответствующие грамматике?

Пример:

Грамматика

S -> ASB | AB
A -> a 
B -> b

(По сути, количество a с последующим равным количеством b с)

Ручей:

aabaaabbc...

Ожидаемый результат:

  1. Соответствие, начинающееся с позиции 1: ab
  2. Соответствие, начинающееся с позиции 4: aabb

Конечно, ключ "эффективно". без слишком долгого тестирования слишком многих безнадежных кандидатов. Единственное, что я знаю о своих данных, это то, что хотя грамматика произвольна, на практике совпадающие последовательности будут относительно короткими (‹20 терминалов), а сам поток будет довольно длинным (>10000 терминалов).

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

С чего начать? Какой тип парсера можно приспособить для такого рода работы?

parsing algorithm context-free-grammar
14.10.2011

  • Для произвольной грамматики я не вижу другого выбора, кроме как начать новую попытку сопоставления для каждого символа. Если вы можете кодировать свой синтаксический анализатор с определенным знанием, только тогда вы можете обманывать (т.е. если первым символом должен быть X, нет необходимости начинать новые попытки сопоставления, кроме как с X). 14.10.2011
  • Рекомендую изменить первое грамматическое правило на S -> AB | ASB или что-то подобное. Прямо сейчас кажется, что ваша грамматика соответствует только бесконечным строкам сбалансированного ab. 14.10.2011
  • @ccoakley Спасибо, хорошо замечено. Я так старался придумать действительно простой пример, что в итоге ошибся. :) 14.10.2011
  • Трудно сказать. Вы так и не сказали, что это за работа. Может ли грамматика быть распознана парсером LALR? ЛЛ(к)? ЛР(к)? ГЛР? Другой? 15.10.2011
  • @harold Я как бы надеялся, что это будет частью ответа. Грамматика может быть любой, как сейчас обстоят дела, но если есть очень хорошее решение для класса CFG, это веский аргумент в пользу ограничения или преобразования грамматики. 15.10.2011
  • Проблема в том, что большинство алгоритмов разбора контекстно-свободных грамматик требуют знания конца строки — будь то специальный символ, такой как $, или пустая строка λ. Если вы собираетесь анализировать входящую последовательность токенов на совпадения, я не вижу другого варианта, кроме как анализировать каждую отдельную подстроку. В этом случае синтаксический анализ с использованием алгоритма CYK, вероятно, является лучшим вариантом, поскольку он имеет лучшую сложность в наихудшем случае из алгоритмов синтаксического анализа для контекстно-свободных языков. Однако я уверен, что есть исследования по контекстно-свободному синтаксическому анализу на лету, которые вы могли бы поискать. 15.10.2011

Ответы:


1

«Произвольная грамматика» заставляет меня предложить вам взглянуть на комментарий wberry.

Насколько сложны эти грамматики? Есть ли шаг ручного вмешательства?

Я сделаю попытку. Если бы я изменил ваш пример грамматики из:

S -> ASB | AB
A -> a 
B -> b

включать:

S' -> S | GS' | S'GS' | S'G
G -> sigma*

Так что G = мусор, а S' - это множество фрагментов S с мусором между ними (возможно, я был небрежен с моими правилами производства. Вы поняли идею), я думаю, мы можем решить вашу проблему. Вам просто нужен синтаксический анализатор, который будет соответствовать другим правилам до G. Возможно, вам придется изменить эти производственные правила на основе синтаксического анализатора. Я почти гарантирую, что порядок правил будет меняться в зависимости от парсера. Поскольку большинство библиотек синтаксических анализаторов отделяют лексический анализ от синтаксического анализа, вам, вероятно, понадобится универсальная лексема с последующей модификацией G, чтобы включить все возможные лексемы. В зависимости от ваших особенностей это может быть не лучше (с точки зрения эффективности), чем просто начинать каждую попытку с каждого места в потоке.

Но... Предполагая, что мои правила производства фиксированы (как для правильности, так и для конкретной разновидности синтаксического анализатора), это должно не только соответствовать фрагментам в потоке, но и должно дать вам дерево синтаксического анализа для всего потока. Вас интересуют только поддеревья с корнями в узлах типа S.

14.10.2011
  • Я не уверен, что это решение будет работать так, как задумано. В примере грамматики строка типа ababababab должна пять раз совпадать с выводом S => AB -> ab. Но добавление правил мусора даст вам такие производные, как S' => GS' => ababababS' => ababababAB => ababababab. Таким образом, вывод мусора означает, что вам нужно будет перечислить все возможные выводы, а затем выбрать вывод с наибольшим числом выводов, не связанных с мусором, или упорядочить правила выводов так, чтобы выводы, не связанные с мусором, шли последними. Является ли это более оптимальным решением, чем просто сопоставление подпоследовательностей с использованием CYK или чего-то еще? 16.10.2011
  • @danportin: в зависимости от инструмента генератора парсеров должны быть способы выполнять неохотное сопоставление. К сожалению, я не знаю универсально применимого способа. Вот почему я загрузил свой ответ оговорками и особо упомянул о необходимости изменить порядок правил для достижения желаемых результатов. Я по-прежнему предполагаю, что легче заставить работать парсер, чем писать его с нуля. Я внедрил Earley, чтобы выполнить статический анализ на C, только чтобы понять, что мой грамматик был неоднозначным (он работал в yacc), и я потратил жалкое время, модифицируя код, чтобы сгенерировать правильное дерево синтаксического анализа из таблицы. 17.10.2011
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..