Синтаксический анализ или синтаксический анализ — это вторая фаза компилятора. В этой главе мы изучим основные понятия, используемые при построении парсера.
Мы видели, что лексический анализатор может идентифицировать токены с помощью регулярных выражений и шаблонных правил. Но лексический анализатор не может проверить синтаксис данного предложения из-за ограничений регулярных выражений. Регулярные выражения не могут проверять балансировочные токены, такие как скобки. Таким образом, на этом этапе используется грамматика без контекста (CFG), которая распознается автоматами.
CFG, с другой стороны, является надмножеством регулярной грамматики, как показано ниже:
Это означает, что каждая регулярная грамматика также не зависит от контекста, но существуют некоторые проблемы, которые выходят за рамки обычной грамматики. CFG — полезный инструмент для описания синтаксиса языков программирования.
Контекстная грамматика
В этом разделе мы сначала увидим определение контекстно-свободной грамматики и введем терминологию, используемую в технологии синтаксического анализа.
Контекстная грамматика состоит из четырех компонентов:
-
Набор нетерминалов (V). Нетерминалы являются синтаксическими переменными, которые обозначают наборы строк. Нетерминалы определяют наборы строк, которые помогают определить язык, генерируемый грамматикой.
-
Набор токенов, известный как терминальные символы (Σ). Терминалы являются основными символами, из которых формируются строки.
-
Набор производств (П). Продукция грамматики определяет способ, которым терминалы и нетерминалы могут быть объединены, чтобы сформировать строки. Каждое производство состоит из нетерминала, называемого левой стороной производства, стрелки и последовательности токенов и / или терминалов , называемых правой стороной производства.
-
Один из нетерминалов обозначен как начальный символ (S); откуда начинается производство.
Набор нетерминалов (V). Нетерминалы являются синтаксическими переменными, которые обозначают наборы строк. Нетерминалы определяют наборы строк, которые помогают определить язык, генерируемый грамматикой.
Набор токенов, известный как терминальные символы (Σ). Терминалы являются основными символами, из которых формируются строки.
Набор производств (П). Продукция грамматики определяет способ, которым терминалы и нетерминалы могут быть объединены, чтобы сформировать строки. Каждое производство состоит из нетерминала, называемого левой стороной производства, стрелки и последовательности токенов и / или терминалов , называемых правой стороной производства.
Один из нетерминалов обозначен как начальный символ (S); откуда начинается производство.
Строки извлекаются из начального символа путем многократной замены нетерминала (первоначально начального символа) правой стороной производства для этого нетерминала.
пример
Мы берем проблему языка палиндрома, который нельзя описать с помощью регулярных выражений. То есть L = {w | w = w R } не является обычным языком. Но это можно описать с помощью CFG, как показано ниже: