Дизайн компилятора - синтаксический анализ

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

Мы видели, что лексический анализатор может идентифицировать токены с помощью регулярных выражений и шаблонных правил. Но лексический анализатор не может проверить синтаксис данного предложения из-за ограничений регулярных выражений. Регулярные выражения не могут проверять балансировочные токены, такие как скобки. Таким образом, на этом этапе используется грамматика без контекста (CFG), которая распознается автоматами.

CFG, с другой стороны, является надмножеством регулярной грамматики, как показано ниже:

Соотношение CFG и обычной грамматики

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

Контекстная грамматика

В этом разделе мы сначала увидим определение контекстно-свободной грамматики и введем терминологию, используемую в технологии синтаксического анализа.

Контекстная грамматика имеет четыре компонента:

  • Набор нетерминалов (V). Нетерминалы являются синтаксическими переменными, которые обозначают наборы строк. Нетерминалы определяют наборы строк, которые помогают определить язык, генерируемый грамматикой.

  • Набор токенов, известный как терминальные символы (Σ). Терминалы являются основными символами, из которых формируются строки.

  • Набор производств (П). Продукция грамматики определяет способ, которым терминалы и нетерминалы могут быть объединены, чтобы сформировать строки. Каждое производство состоит из нетерминала, называемого левой стороной производства, стрелки и последовательности токенов и / или терминалов , называемых правой стороной производства.

  • Один из нетерминалов обозначен как начальный символ (S); откуда начинается производство.

Строки извлекаются из начального символа путем многократной замены нетерминала (первоначально начального символа) правой стороной производства для этого нетерминала.

пример

Мы берем проблему языка палиндрома, который нельзя описать с помощью регулярных выражений. То есть L = {w | w = w R } не является обычным языком. Но это можно описать с помощью CFG, как показано ниже:

G = ( V, Σ, P, S )

Где:

V = { Q, Z, N }
Σ = { 0, 1 }
P = { Q → Z | Q → N | Q → ℇ | Z → 0Q0 | N → 1Q1 }
S = { Q }

Эта грамматика описывает язык палиндрома, такой как: 1001, 11100111, 00100, 1010101, 11111 и т. Д.

Синтаксические анализаторы

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

Синтаксический анализатор

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

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

отвлечение

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

  • Решение нетерминала, который должен быть заменен.
  • Принятие решения о производственном правиле, по которому будет заменен нетерминал.

Чтобы решить, какой нетерминал следует заменить производственным правилом, у нас может быть два варианта.

Самый левый вывод

Если форма предложения ввода сканируется и заменяется слева направо, она называется самой левой производной. Форма предложения, полученная самым левым выводом, называется формой слева.

Самый правый вывод

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

пример

Правила производства:

E → E + E
E → E * E
E → id 

Входная строка: идентификатор + идентификатор * идентификатор

Самый левый вывод:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Обратите внимание, что крайний левый нетерминал всегда обрабатывается первым.

Самый правый вывод:

E → E + E
E → E + E * E
E → E + E * id
E → E + id * id
E → id + id * id

Parse Tree

Дерево разбора - это графическое изображение деривации. Удобно видеть, как строки получаются из начального символа. Начальный символ деривации становится корнем дерева разбора. Давайте посмотрим на это на примере из последней темы.

Мы берем самый левый вывод a + b * c

Самый левый вывод:

E → E * E
E → E + E * E
E → id + E * E
E → id + id * E
E → id + id * id

Шаг 1:

E → E * E Разбор дерева

Шаг 2:

E → E + E * E Разбор дерева

Шаг 3:

E → id + E * E Разбор дерева

Шаг 4:

E → id + id * E Разбор дерева

Шаг 5:

E → id + id * id Разбор дерева

В дереве разбора:

  • Все конечные узлы являются терминалами.
  • Все внутренние узлы не являются терминалами.
  • Упорядоченный обход дает исходную строку ввода.

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

неоднозначность

Грамматика G называется неоднозначной, если она имеет более одного дерева синтаксического анализа (деривация слева или справа) хотя бы для одной строки.

пример

E → E + E
E → E – E
E → id

Для строки id + id - id вышеприведенная грамматика генерирует два дерева разбора:

Разбор дерева

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

Ассоциативность

Если операнд имеет операторы с обеих сторон, то сторона, на которой оператор берет этот операнд, определяется ассоциативностью этих операторов. Если операция левоассоциативна, то операнд будет взят левым оператором или, если операция ассоциативно справа, правый оператор примет операнд.

пример

Такие операции, как сложение, умножение, вычитание и деление, остаются ассоциативными. Если выражение содержит:

id op id op id

это будет оценено как:

(id op id) op id

Например, (id + id) + id

Такие операции, как Exponentiation, являются ассоциативными справа, т. Е. Порядок вычисления в том же выражении будет:

id op (id op id)

Например, id ^ (id ^ id)

старшинство

Если два разных оператора совместно используют общий операнд, приоритет оператора решает, какой из них будет операндом. Таким образом, 2 + 3 * 4 может иметь два разных дерева разбора, одно из которых соответствует (2 + 3) * 4, а другое соответствует 2+ (3 * 4). Установив приоритет среди операторов, эту проблему можно легко устранить. Как и в предыдущем примере, математически * (умножение) имеет приоритет над + (сложение), поэтому выражение 2 + 3 * 4 всегда будет интерпретироваться как:

2 + (3 * 4)

Эти методы уменьшают вероятность неоднозначности в языке или его грамматике.

Левая рекурсия

Грамматика становится леворекурсивной, если в ней есть какой-либо нетерминальный «A», чье происхождение содержит «A» в качестве самого левого символа. Леворекурсивная грамматика считается проблемной ситуацией для синтаксических анализаторов сверху вниз. Нисходящие парсеры начинают разбор с символа Start, который сам по себе не является терминальным. Таким образом, когда синтаксический анализатор встречает тот же нетерминал в своем выводе, ему становится трудно судить, когда прекратить синтаксический анализ левого нетерминала, и он входит в бесконечный цикл.

Пример:

(1) A => Aα | β

(2) S => Aα | β 
    A => Sd 

(1) является примером немедленной левой рекурсии, где A - любой нетерминальный символ, а α - строка нетерминалов.

(2) является примером косвенной левой рекурсии.

Левая рекурсия

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

Удаление левой рекурсии

Один из способов удалить левую рекурсию - использовать следующую технику:

Производство

A => Aα | β

превращается в следующие производства

A => βA'
A'=> αA' | ε

Это не влияет на строки, полученные из грамматики, но устраняет немедленную левую рекурсию.

Второй метод заключается в использовании следующего алгоритма, который должен исключить все прямые и косвенные левые рекурсии.

START

Arrange non-terminals in some order like A1, A2, A3,…, A n

   for each i from 1 to n
      {
      for each j from 1 to i-1
         {
         replace each production of form A i ⟹Aj𝜸
         with A i ⟹ δ1𝜸  | δ2𝜸 | δ3𝜸 |…| 𝜸 
         where A j ⟹ δ 1 | δ 2 |…| δ n  are current A j productions
         }
      }
   eliminate immediate left-recursion
   
END

пример

Производственный набор

S => Aα | β 
A => Sd

после применения вышеуказанного алгоритма, должно стать

S => Aα | β 
A => Aαd | βd

и затем удалите немедленную левую рекурсию, используя первую технику.

A  => βdA'
A' => αdA' | ε

Теперь ни у одного производства нет ни прямой, ни косвенной левой рекурсии.

Левый Факторинг

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

пример

Если нисходящий синтаксический анализатор встречает производство как

A ⟹ αβ | α𝜸 | …

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

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

пример

Вышеуказанные произведения могут быть записаны как

A => αA'
A'=> β | 𝜸 | … 

Теперь у парсера есть только одна продукция на префикс, что облегчает принятие решений.

Первый и последующие сеты

Важной частью построения таблицы анализатора является создание первого и последующих наборов. Эти наборы могут предоставить фактическую позицию любого терминала в деривации. Это делается для создания таблицы синтаксического анализа, где принимается решение о замене T [A, t] = α на некоторое производственное правило.

Первый сет

Этот набор создан, чтобы знать, какой символ терминала выводится в первой позиции нетерминалом. Например,

α → t β

То есть α выводит t (терминал) в самой первой позиции. Итак, t ∈ FIRST (α).

Алгоритм расчета первого набора

Посмотрите на определение первого набора (α):

  • если α терминал, то ПЕРВЫЙ (α) = {α}.
  • если α нетерминал и α → ℇ - произведение, то ПЕРВЫЙ (α) = {ℇ}.
  • если α нетерминально и α → 𝜸1 𝜸2 𝜸3… 𝜸n и любой FIRST (𝜸) содержит t, то t находится в FIRST (α).

Первый набор можно рассматривать как:

Следовать сет

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

Алгоритм расчета следующий набор:

  • если α является начальным символом, то FOLLOW () = $

  • если α нетерминален и имеет произведение α → AB, то FIRST (B) находится в следующем (A), кроме ℇ.

  • если α нетерминален и имеет произведение α → AB, где B ℇ, то FOLLOW (A) находится в FOLLOW (α).

Следующий набор можно увидеть как: FOLLOW (α) = {t | S * αt *}

Ограничения синтаксических анализаторов

Синтаксические анализаторы получают свои входные данные в виде токенов от лексических анализаторов. Лексические анализаторы несут ответственность за достоверность токена, предоставленного синтаксическим анализатором. Синтаксические анализаторы имеют следующие недостатки:

  • он не может определить, является ли токен действительным,
  • он не может определить, объявлен ли токен перед его использованием,
  • он не может определить, инициализирован ли токен перед его использованием,
  • он не может определить, действительна ли операция над типом токена или нет.

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