Что такое разбор пакетов?

Question

Я знаю и использую бизонов / яков. Но в мире синтаксического анализа существует много шума вокруг синтаксического анализа пакетов.

Что это? Стоит ли учиться?

Answer 1

синтаксический анализ Packrat - это способ обеспечить асимптотически лучшую производительность для синтаксического анализа грамматик выражения (PEG); специально для PEG можно гарантировать линейное время разбор.

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

Answer 2

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

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