<- Список новостей
В этой статье мы постарались быть практичными. Наша цель — помочь практикам, а не объяснить всю теорию. Мы просто объясняем, что вам нужно знать, чтобы понять и построить парсер. Есть несколько способов определить значение парсинга. Однако суть остается прежней: парсинг означает поиск базовой структуры данных, которые нам даны.
В некотором смысле синтаксический анализ можно считать обратным шаблону: идентификация структуры и извлечение данных. В шаблонах у нас есть структура, и вместо этого мы заполняем ее данными. В случае синтаксического анализа вы должны определить модель из необработанного представления. В то время как для создания шаблонов вам необходимо объединить данные с моделью, чтобы создать необработанное представление. Необработанное представление обычно представляет собой текст, но также может быть и двоичными данными.
Фундаментальный синтаксический анализ необходим, потому что разным сущностям нужны данные в разных формах. Синтаксический анализ позволяет преобразовывать данные так, чтобы их могло понять конкретное программное обеспечение. Очевидным примером являются программы: они написаны людьми, но должны выполняться компьютерами. Поэтому люди записывают их в понятной им форме, а затем программное обеспечение преобразует их таким образом, чтобы их мог использовать компьютер.
Однако синтаксический анализ может потребоваться даже при передаче данных между двумя программами, которые имеют разные потребности. Например, это необходимо, когда вам нужно сериализовать или десериализовать класс.
Большая картинка
В этом разделе мы собираемся описать основные компоненты парсера. Мы пытаемся дать вам не формальные объяснения, а практические.
Обычные выражения
(Последовательность символов, которая может быть определена шаблоном)
Регулярные выражения часто рекламируются как вещь, которую вы не должны использовать для парсинга. Это не совсем правильно, потому что вы можете использовать регулярные выражения для разбора простого ввода. Проблема в том, что некоторые программисты знают только регулярные выражения. Поэтому они используют их, чтобы попытаться разобрать все, даже то, что не следует. Результатом обычно является серия регулярных выражений, собранных воедино, которые очень слабые.
Вы можете использовать регулярные выражения для анализа некоторых более простых языков, но это исключает большинство языков программирования, даже те, которые выглядят достаточно простыми, как HTML. На самом деле языки, которые можно анализировать только с помощью регулярных выражений, называются регулярными языками. Существует формальное математическое определение, но оно выходит за рамки данной статьи.
Обычный язык может быть определен серией регулярных выражений, в то время как более сложные языки нуждаются в чем-то большем. Простое эмпирическое правило: если грамматика языка имеет рекурсивные или вложенные элементы, это не обычный язык. Например, HTML может содержать произвольное количество тегов внутри любого тега, поэтому он не является обычным языком, и его нельзя анализировать с использованием исключительно регулярных выражений, какими бы умными они ни были.
Регулярные выражения в грамматике
Знакомство типичного программиста с регулярными выражениями часто позволяет использовать их для определения грамматики языка. Точнее, их синтаксис используется для определения правил лексера или парсера. Например, звезда ( *) используется в правиле, чтобы указать, что конкретный элемент может присутствовать ноль или бесконечное количество раз.
Определение правила не следует путать с тем, как реализован фактический лексер или парсер. Вы можете реализовать лексер, используя механизм регулярных выражений, предоставляемый вашим языком. Однако обычно регулярные выражения, определенные в грамматике, фактически преобразуются в конечный автомат для повышения производительности.
Структура парсера
Теперь, прояснив роль регулярных выражений, мы можем взглянуть на общую структуру синтаксического анализатора. Полный синтаксический анализатор обычно состоит из двух частей: лексера , также известного как сканер или токенизатор , и собственно синтаксического анализатора. Парсеру нужен лексер, потому что он работает не непосредственно с текстом, а с выводом, созданным лексером. Не все синтаксические анализаторы принимают эту двухэтапную схему: некоторые синтаксические анализаторы не зависят от отдельного лексера и объединяют два этапа. Их называют бессканерными парсерами .
Лексер и синтаксический анализатор работают последовательно: лексер сканирует ввод и создает совпадающие символы, затем парсер сканирует токены и выдает результат парсинг.
Бессканерные парсеры
Парсеры без сканирования работают по-другому, потому что они обрабатывают непосредственно исходный текст, а не список токенов, созданный лексером. То есть парсер без сканера работает как лексер и парсер вместе взятые.
Хотя для целей отладки, безусловно, важно знать, является ли конкретный инструмент синтаксического анализа синтаксическим анализатором без сканера или нет, во многих случаях это не имеет отношения к определению грамматики. Это потому, что вы обычно все еще определяете шаблоны, которые группируют последовательность символов для создания (виртуальных) токенов; затем вы комбинируете их, чтобы получить окончательный результат. Просто потому, что так удобнее.
Другими словами, грамматика парсера без сканера очень похожа на грамматику инструмента с отдельными шагами. Опять же, вы не должны путать то, как вещи определяются для вашего удобства, и то, как они работают за кулисами.
Лексер
Лексеры также известны как сканеры или токенизаторы . Лексеры играют роль в парсинге, потому что они преобразуют первоначальный ввод в форму, более подходящую для соответствующего синтаксического анализатора, который работает на более позднем этапе. Обычно лексеры написать проще, чем парсеры.
Очень важной частью работы лексера является работа с пробелами. В большинстве случаев вы хотите, чтобы лексер отбрасывал пробелы. Это связано с тем, что в противном случае парсеру пришлось бы проверять наличие пробелов между каждым знаком, что быстро стало бы раздражать.
Есть случаи, когда вы не можете этого сделать, потому что пробел имеет отношение к языку, как в случае с Python, где он используется для идентификации блока кода. Однако даже в этих случаях обычно именно лексер занимается проблемой отличия релевантных пробелов от нерелевантных. Это означает, что вы хотите, чтобы лексер понимал, какие пробелы имеют отношение к синтаксическому анализу.
Где заканчивается лексер и начинается парсер?
Учитывая, что лексеры почти всегда используются вместе с синтаксическими анализаторами, граница между ними иногда может быть размыта. Это связано с тем, что парсинг должен давать результат, полезный для конкретной потребности программы. Таким образом, существует не только один правильный способ разбора чего-либо, но вы заботитесь только о том способе, который соответствует вашим потребностям.
Например, представьте, что вы создаете программу, которая должна анализировать журналы сервера, чтобы сохранить их в базе данных. Для этой цели лексер идентифицирует серию чисел и точек и преобразует их в токен IPv4.
IPv4: [ 0 — 9 ] + «.» [ 0 — 9 ] + «.» [ 0 — 9 ] + «.» [ 0 — 9 ] +
Затем синтаксический анализатор проанализирует последовательность токенов, чтобы определить, является ли это сообщением, предупреждением и т. д.
Что произошло бы, если бы вы разрабатывали программное обеспечение, которое должно было бы использовать IP-адрес для определения страны посетителя? Возможно, вы захотите, чтобы лексер идентифицировал октеты адреса для последующего использования и сделал IPv4 элементом парсера.
Это один из примеров того, как одна и та же информация может анализироваться по-разному из-за разных целей.
Парсер
В контексте синтаксического анализа «парсер» может относиться как к программному обеспечению, которое выполняет весь процесс, так и к соответствующему парсеру, который анализирует токены, созданные лексером. Это просто следствие того, что синтаксический анализатор берет на себя самую важную и сложную часть всего процесса синтаксического анализа. Под наиболее важным мы подразумеваем то, что больше всего интересует пользователя и что он действительно увидит. На самом деле, как мы уже сказали, лексер работает как помощник, облегчающий работу парсера.
В любом смысле, который вы выберете, вывод парсер представляет собой организованную структуру кода, обычно дерево. Дерево может быть деревом парсинга или абстрактным синтаксическим деревом . Оба они являются деревьями, но отличаются тем, насколько близко они представляют фактически написанный код и промежуточные элементы, определенные парсером.
С помощью этой замечательной (или, по крайней мере, большой) статьи мы надеемся разрешить большинство сомнений по поводу синтаксического анализа терминов и алгоритмов: что означают эти термины и почему следует выбрать определенный алгоритм вместо другого. Мы не только объяснили их, но и дали несколько советов по общим проблемам с разбором языков программирования.
Наши менеджеры свяжутся с вами в ближайшее время.