Почему использование лексера / парсера для двоичных данных так неправильно?

13

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

Может ли кто-нибудь объяснить, почему анализ двоичных данных с помощью лексера / парсера является настолько неправильным с достаточной ясностью для учащегося CS, который не посещал занятия по анализу, но имел теоретические знания?

Гай Кодер
источник
Я предполагаю, что лексер, вероятно, не может найти токены, которые меньше байта / слова. Если вам это нужно, Erlang имеет отличную поддержку для анализа двоичных файлов: user.it.uu.se/~pergu/papers/JFP_06.pdf
Дейв Кларк
3
Я не думаю, что ваше предположение верно. Очевидно, что неконтекстные данные создают проблемы (которые часто можно обойти), но вы можете дать грамматику для двоичных слов. Вероятно, вы не сможете использовать популярные генераторы парсеров, так как они предполагают ввод текста. Это еще одна проблема.
Рафаэль
S0S|10S
1
28
5
@GuyCoder: Все данные, которые генерируются другой программой, можно описать грамматикой. Это, возможно, не является контекстно-свободным, хотя.
Рафаэль

Ответы:

10

В принципе в этом нет ничего плохого.

На практике,

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

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

    Затем вы можете начать играть трюки, такие как наличие написанного вручную лексера, способного справиться с этим с помощью обратной связи от синтаксического анализатора (например, при обработке lex / yacc языка C используются такие трюки для обработки typedef). Но затем мы подходим ко второму пункту.

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

AProgrammer
источник
«языки - это обычные слова« если », но также контекстно-зависимые» означают, что двоичные данные - это грамматика, я поясню в ответе. Это относится к части проблемы; люди склонны думать грамматики или обычные языки, как только вы упоминание парсера.
Guy Coder
7

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

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

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

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

Компьютерные программы почти всегда производят данные в формате, который имеет четкую структуру. Если мы анализируем некоторые входные данные, мы, по сути, пытаемся выяснить структуру входных данных. С двоичными данными эта структура, как правило, очень проста и легко анализируется компьютерами.

Другими словами, как правило, немного бесполезно выяснять структуру входных данных, для которых вы уже знаете структуру. Поскольку разбор не бесплатный (он требует времени и усложняет вашу программу), поэтому использование лексеров / парсеров для двоичных данных «так неправильно».

Алекс тен Бринк
источник
2
Это хорошая перспектива, но я чувствую, что она не отвечает на вопрос.
Рафаэль
LANGSEC: Language-theoretic Securityпредлагает интересную перспективу. Одна из статей рассказывает о «странных машинах»: специальных синтаксических анализаторах известного формата, формирующих средства обработки ввода в системе. Они могут на самом деле работать не так, как задумано. Из-за неверных допущений неисправный компьютер будет выполнять непредвиденные переходы состояний с учетом специально созданного ввода, выполняя вычисления, которые не должны быть возможными. Это создает вектор атаки. Использование формальных грамматик дало бы достоверно правильные алгоритмы.
Матеус Морейра
0

a+б×(с-d)+е(+ a (* b (- c d)) e)a b c d - * + e +, Обычная математическая нотация имеет больше избыточности, чем Lisp (который требует больше скобок, но получает переменные арты бесплатно, поэтому требует меньше символов для выражения выражений, используя большие арности) или RPL (который никогда не нуждается в скобках). Такая избыточность редко бывает полезна для компьютеров - и там, где она есть, то есть когда могут быть ошибки в данных, логика исправления ошибок обычно отделена от функционального значения данных, например, с использованием кодов с исправлением ошибок, которые применяются к произвольным последовательности байтов независимо от того, что они представляют.

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

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

Жиль "ТАК - прекрати быть злым"
источник
Какой смысл первых двух абзацев? Даже если у вас нет избыточности, вам нужен парсер. Кроме того, первый абзац неверен: есть примеры, где разрешены все слова, но вы анализируете, чтобы получить структуру (например, предсказание вторичной структуры РНК).
Рафаэль
@Raphael Нетривиальный синтаксический анализатор обычно подразумевает избыточность (да, как вы заметили, есть исключения). Я не рассматривал языки, предназначенные ни для людей, ни для компьютеров, это интересный пример. В первых двух параграфах обсуждаются типичные различия между двоичными и читаемыми человеком форматами (обычно это означает, что если вы будете искать исключения, вы их найдете).
Жиль "ТАК - перестать быть злым"