Лексический и синтаксический анализ

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

Definition

Лексический анализ — это фаза, которая группирует входные символы в токены, а синтаксический анализ (парсинг) — это фаза, которая определяет, образуют ли и как эти токены действительную программу в соответствии с грамматикой, создавая синтаксическое дерево.

Scope

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

Core questions

• Как регулярные и контекстно-свободные языки используются для описания структуры программы?
• Каковы компромиссы между LL- и LR-парсингом?
• Как обнаруживаются и обрабатываются неоднозначности и ошибки парсинга?
• Как строится абстрактное синтаксическое дерево из потока токенов?

Key theories

LR-парсинг

Кнут представил LR-парсинг, восходящую технику, которая детерминированно разбирает широкий класс LR-грамматик за линейное время, формируя основу многих генераторов парсеров.

Общий контекстно-свободный парсинг

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

Регулярные и контекстно-свободные основы внешнего интерфейса

Книга «Dragon Book» систематизирует использование регулярных выражений и конечных автоматов для сканирования и контекстно-свободных грамматик для парсинга, включая стандартные алгоритмы построения LL и LR.

Clinical relevance

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

History

Иерархия формальных языков Хомского в конце 1950-х годов заложила теорию регулярных и контекстно-свободных языков. Кнут формализовал LR-парсинг в 1965 году, а Эрли предложил общий контекстно-свободный алгоритм в 1970 году. Генераторы парсеров, такие как yacc, сделали LR-парсинг практичным, в то время как более поздние работы исследовали грамматики выражений для парсинга и парсеры на основе комбинаторов.

Debates

Генерируемые против написанных вручную парсеров

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

Key figures

• Donald Knuth
• Jay Earley
• Alfred Aho
• Noam Chomsky

Seminal works

• knuth1965
• earley1970
• aho2006

Frequently asked questions

В чем разница между лексером и парсером?

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

В чем разница между LL- и LR-парсингом?

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