Разбор особых случаев

Если я правильно понимаю, синтаксический анализ превращает последовательность символов в дерево. У меня вопрос: возможно ли использовать какую-то стандартную процедуру (LR, LL, PEG, ..?) Для разбора следующих двух примеров или необходимо написать специализированный парсер вручную?

  1. Исходный код Python, то есть блоки с пробелами

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

  1. Формат изображения PNG, где блок начинается с заголовка и размера блока, после чего идет содержимое блока

Содержимое может содержать байты, которые напоминают некоторый заголовок, поэтому необходимо "знать", что следующие x байтов не должны быть "проанализированы", то есть они должны быть пропущены. Как это выразить, скажем, с помощью PEG? Другими словами, "закрывающая скобка" представлена ​​длиной содержимого.

Источник

2 ответа

Решение

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

Алгоритм python хорошо описан в справочном руководстве по Python (хотя вы должны прочитать его в контексте.). Описанный шаг предварительной обработки состоит в том, что пробел в начале строки систематически заменяется на INDENT а также DEDENT жетоны.

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

С практической точки зрения как алгоритмы соединения строк, так и алгоритмы отступов могут выполняться программно; как правило, это делается внутри пользовательского сканера (токенизатора), который поддерживает как набор скобок, так и уровни отступов. Затем поток токенов может быть проанализирован с помощью обычных контекстно-свободных алгоритмов, но токенизатор - хотя он может использовать регулярные выражения - нуждается в контекстно-зависимой логике (например, подсчет пробелов). [Примечание 1]

Точно так же форматы, которые содержат явные размеры (такие как большинство форматов сериализации, включая PNG-файлы, протобуфы Google и фрагментированное кодирование HTTP), не являются контекстно-свободными, но их, очевидно, легко маркировать, поскольку токенизатор просто должен прочитать длину и затем прочитать столько байтов.

Существует множество контекстно-зависимых формализмов, и они определенно имеют свое применение, но при практическом разборе наиболее распространенной стратегией является использование эквивалентного по Тьюрингу формализма (такого как любой язык программирования, возможно дополненный генератором сканера, таким как flex) для токенизатора и контекстно-свободный формализм для парсера. [Заметка 2]

Заметки:

  1. Может быть не сразу очевидно, что отступ Python не является контекстно-свободным, поскольку контекстно-свободные грамматики могут принимать некоторые категории соглашений. Например, {ωω-1 | ω∈Σ*} (язык всех палиндромов четной длины) не зависит от контекста, как {anbn},

    Тем не менее, эти примеры не могут быть расширены, потому что единственное возможное соглашение по количеству в языке без контекста - это заключение в скобки. Таким образом, в то время как палиндромы не зависят от контекста (вы можете реализовать проверку одним стеком), внешне очень похожи {ωω | ω∈Σ*} нет и не есть {anbncn}

  2. Одним из таких формализмов являются обратные ссылки в "регулярных" выражениях, которые могут быть доступны в некоторых реализациях PEG. Обратные ссылки позволяют выражать различные контекстно-зависимые языки, но не допускают выражение всех контекстно-свободных языков. К сожалению, регулярные выражения с обратными ссылками на практике не работают, потому что проблема определения соответствия строки регулярному выражению с обратными ссылками является полной. Вы можете найти этот вопрос на интересном сайте SE. (И, возможно, вы захотите переформулировать свой вопрос таким образом, чтобы его можно было задать на этом сайте, http://cs.stackexchange.com/.)

Источник

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

Чистые контекстно-свободные парсеры не могут делать Python; все технологии парсера, которые вы перечислили, слабее, чем чистый контекст, поэтому они не могут этого сделать. Взлом в лексере для отслеживания отступов и генерации токенов INDENT/DEDENT превращает проблему отступа в явные "круглые скобки", которые легко обрабатываются безконтекстными синтаксическими анализаторами.

Большинство двоичных файлов также не могут быть обработаны, так как они обычно содержат где-то список длины N, где N указывается до того, как будет найдено тело списка (это пример вашего примера). Опять же, вы можете обойти это, с более сложным хаком; что-то должно содержать стек длин вложенных списков, и анализатор должен сигнализировать, когда он перемещается от одного элемента списка к следующему. Самый верхний счетчик длины уменьшается, а анализатор получает сигнал "уменьшить" или "сдвинуть". Другие более сложные связанные структуры, как правило, довольно сложно проанализировать таким образом. Заставить парсер сотрудничать таким образом не всегда легко.

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