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

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

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

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

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

Контент может содержать байты, напоминающие какой-то заголовок, поэтому необходимо «знать», что следующие x байтов не подлежат «разбору», т. е. их следует пропустить. Как это выразить, скажем, с помощью ПЭГ? Другими словами, «закрывающая скобка» представлена ​​длиной содержимого.


parsing ll lr context-free-grammar peg
person Ecir Hana    schedule 18.09.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

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

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

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

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

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

Примечания:

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

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

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

person rici    schedule 18.09.2014

arrow_upward
0
arrow_downward

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

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

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

person Ira Baxter    schedule 18.09.2014