Синтаксический анализ — это этап компиляции, на котором проверяется соответствие программы правилам языка программирования. Для этого используется формальное описание синтаксиса языка, называемое грамматикой.

Абстрактный синтаксис

Абстрактный синтаксис языка определяет значимые компоненты каждой конструкции языка, не завися от их конкретного представления в тексте программы. Например, выражение a + b может быть записано в префиксной, инфиксной или постфиксной форме, но его абстрактный синтаксис останется неизменным: операция сложения + и операнды a и b.

Абстрактный синтаксис удобно представлять в виде абстрактного синтаксического дерева (АСД). АСД — это древовидная структура, где каждый узел представляет конструкцию языка, а его потомки — составляющие ее компоненты. Например, АСД для выражения D = b * b – 4 * a * c выглядит следующим образом:

    =
   / \\
  D   -
     / \\
    *   *
   / \\ / \\
  b b 4  *
         / \\
        a   c

Грамматики

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

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

Контекстно-свободная грамматика состоит из:

• Терминалов: атомарные символы языка (лексемы), например: +, -, *, /, (, ), число, идентификатор.
• Нетерминалов: "сборки", представляющие конструкции языка, например: выражение, терм, фактор.
• Правил подстановки: задают компонентный состав конструкций. Каждое правило имеет вид <нетерминал> ::= <строка из терминалов и нетерминалов>, например:
  • выражение ::= выражение + терм
  • выражение ::= выражение - терм
  • выражение ::= терм
• Стартового нетерминала: представляет главную конструкцию языка, например: программа.

Форма Бэкуса — Наура (БНФ)

БНФ — это формальная нотация для записи контекстно-свободных грамматик. В БНФ используются следующие обозначения:

• <нетерминал>: нетерминальный символ, заключенный в угловые скобки.
• терминал: терминальный символ, может заключаться в кавычки.
• ::=: метасимвол, означающий "определяется как".
• |: метасимвол, означающий "или", разделяет альтернативы.

Пример записи грамматики арифметических выражений в БНФ: