65 (Вопросы по разным темам с ответами (программирование))

65 Формальные грамматики и синтаксический контроль. Алгоритмы синтаксического анализа для LL(K)-грамматик, LR(K)-грамматик. Основы синтаксического контроля: нисходящий и восходящий синтаксический анализ

Синтаксический анализ – это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. В принципе, по любой грамматике можно построить синтаксический анализатор, но грамматики, используемые на практике, имеют специальную форму. Например, известно, что для любой контекстно-свободной грамматики может быть построен анализатор, сложность которого не превышает O(n³) для входной строки длины n, но в большинстве случаев по заданному языку программирования мы можем построить такую грамматику, которая позволит сконструировать и более быстрый анализатор. Анализаторы реально используемых языков обычно имеют линейную сложность; это достигается, например, за счет просмотра исходной программы слева направо с заглядыванием вперед на один терминальный символ (лексический класс).

Вход синтаксического анализатора – последовательность лексических и таблицы, например, таблица внешних представлений, которые являются выходом лексического анализатора.

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

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

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

Большинство известных методов анализа принадлежат одному из двух классов, один из которых объединяет нисходящие (top-down) алгоритмы, а другой – восходящие (bottom-up) алгоритмы. Происхождение этих терминов связано с тем, каким образом строятся узлы синтаксического дерева: либо от корня (аксиомы грамматики) к листьям (терминальным символам), либо от листьев к корню.

Нисходящие анализаторы строят вывод, начиная от аксиомы грамматики и заканчивая цепочкой терминальных символов. С нисходящими анализаторами связаны так называемые LL-грамматики, которые обладают следующими свойствами:

• Они могут быть проанализированы без возвратов

• Первая буква L означает, что мы просматриваем входную цепочку слева направо (left-to-right scan)

• Вторая буква L означает, что строится левый вывод цепочки (leftmost derivation).

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

С другой стороны, восходящие анализаторы могут анализировать большее количество грамматик, чем нисходящие, и поэтому именно для таких методов существуют программы, которые умеют автоматически строить анализаторы. С восходящими анализаторами связаны LR-грамматики. В этом обозначении буква L по-прежнему означает, что входная цепочка просматривается слева направо (left-to-right scan), а буква R означает, что строится правый вывод цепочки (rightmost derivation). С помощью LR-грамматик можно определить большинство использующихся в настоящее время языков программирования.

Метод рекурсивного спуска

Одним из наиболее простых и потому одним из наиболее популярных методов нисходящего синтаксического анализа является метод рекурсивного спуска (recursive descent method).

Для объяснения принципов, лежащих в основе метода рекурсивного спуска, рассмотрим задачу вычисления значения арифметической формулы. Будем рассматривать формулы, состоящие из целочисленных значений, бинарных операций сложения (+), вычитания (–), умножения (*) и деления нацело (/), а также круглых скобок. Как обычно, приоритеты операций умножения и деления равны и их приоритет больше, чем приоритеты операций сложения и вычитания, причем приоритеты этих операций также равны. Будем называть операции + и – операциями типа сложения, а операции * и / – операциями типа умножения. Круглые скобки используются для изменения стандартного порядка выполнения операций. Наша задача заключается в написании программы, вычисляющей значение формулы.

Изучаемые нами формулы можно представить следующим образом:

T₁+T₂+…+T_n,

где T_i – это формула вида F_1i*F_2i*…*F_mi. В свою очередь, F_ji – это либо число, либо произвольная формула, заключенная в круглые скобки.

Представим себе процесс вычисления значения формулы. Вначале вычисляется F₁₁, далее мы выясняем, какая операция следует за F₁₁. Если это операция типа умножения, то мы, зная ее левый операнд, вычисляем правый операнд и выполняем операцию. Тем самым, мы получим левый операнд для возможных следующих операций типа умножения. Когда мы закончим вычисление формулы F₁*F₂*…*F_n, то, возможно, увидим далее операцию типа сложения, и процесс вычисления такой формулы будет аналогичен только что описанному процессу.

Условия использования метода рекурсивного спуска

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

Определение. Для КС-грамматики G и цепочки w, состоящей из терминальных и нетерминальных символов, определим множество FIRST_k(w) следующим образом:

FIRST_k (w) = {x | w =>* xv, |x| = k или w =>* x, |x| < k}, где k – натуральное число.

Иными словами, множество FIRST_k(w) состоит из всех терминальных префиксов длины k терминальных цепочек, выводимых из w.

Пример. Рассмотрим грамматику, порождающую подмножество типов языка Pascal.

type → simple

type → ^id

type → array [simple] of type

simple → integer

simple → char

simple → num .. num

Для этой грамматики мы имеем:

FIRST₁(simple) = {integer, char, num}

FIRST₁(^id) = {^}

FIRST₁(array [simple] of type) = {array}

Понятно, что если цепочка w состоит только из терминалов, то FIRST_k(w) – это первые k символов цепочки w, если |w| ≥ k , или это сама цепочка w, если |w| < k.

Алгоритм построения множества FIRST

Прежде всего, определим множество FIRST для всех символов грамматики:

1. если X – терминал, то FIRST (X) = X

2. для правила X→ε добавим ε к множеству FIRST (X)

3. если X – нетерминал и X → Y₁Y₂ … Y_k – правило грамматики, то добавим терминал а в FIRST (X), если для некоторого i этот терминал a принадлежит FIRST (Y_i) и ε принадлежит всем множествам FIRST (Y₁), …, FIRST (Y_i-1), то есть Y₁, …, Y_i-1 =>*ε. Если ε принадлежит FIRST (Y_j) для всех j =1, 2, …, k, то добавим ε в FIRST (Y).

Теперь сформулируем сам алгоритм построения множества FIRST(w).

Вход. КС-грамматика G=(N, T, P, S) и цепочка w терминальных и нетерминальных символов.

Выход. FIRST (w).

Метод. Добавим в FIRST (X₁X₂…X_k) все непустые символы из FIRST (X₁). Затем, если ε принадлежит FIRST (X₁), то добавим все непустые символы из FIRST (X₂), и так далее. Наконец, если для всех j FIRST (X_j) содержит пустой символ, то мы добавим ε в множество FIRST (X₁X₂…X_k).

Пример. Рассмотрим грамматику с правилами:

S → B A

A → +B A

A → ε

B → D C

C → * D C

C → ε

D → (S)

D → a

Для этой грамматики множества FIRST определяются следующим образом:

FIRST (D) = {(, a}, FIRST (C) = {*, ε }, FIRST (B) = FIRST (D), FIRST (A)={+, ε },

FIRST (S) = {(, a}

LL(k)-грамматика

Определение. Грамматика G = (V_T, V_N, P, S) называется LL(k)-грамматикой, если для любых двух левых выводов

S =>* wAv => wuv =>* wx

S =>* wAv => wu₁v =>* wy,

для которых FIRST_k (x) = FIRST_k (y) верно, что u=u₁.

То есть если для данной цепочки wAv, состоящей из терминальных и нетерминальных символов и k первых символов (если они есть), выводящихся из Av, существует не более одного правила, которое можно применить к A, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w и продолжающейся упомянутыми k терминалами.

Пример. Рассмотрим грамматику с правилами:

S → aAS

S → b

A → a

A → bSA

и два вывода

1. S =>* wSv => wuv =>* wx

2. S =>* wSv => wu₁v =>* wy

Пусть цепочки x и y начинаются с a. Это означает, что в выводе участвовало правило S→aAS. Следовательно, u = u₁ = aAS. Пусть цепочки x и y начинаются с b. Это означает, что в выводе участвовало правило S→b. Следовательно, u = u₁ = b.

Для выводов

1. S =>* wAv => wuv =>* wx

2. S =>* wAv => wu₁v =>* wy

рассуждение аналогично. Таким образом, грамматика обладает свойством LL(1).

Для LL(1)-грамматик может быть построен анализатор методом рекурсивного спуска без возвратов.

Леворекурсивные грамматики

LL(k)-свойство накладывает сильные ограничения на грамматику. Иногда имеется возможность преобразовать грамматику так, чтобы получившаяся грамматика обладала свойством LL(1). Такое преобразование далеко не всегда удается, но если нам удалось получить LL(1)-грамматику, то для построения анализатора можно использовать метод рекурсивного спуска без возвратов.

Предположим, что мы хотим построить анализатор языка, порождаемого следующей грамматикой (мы уже приводили неформальное рассмотрение этого примера в лекции 4):

E → E + T | E – T | T

T → T * F | T / F | F

F → num | (E)

Заметим, что терминалы множества FIRST(T) принадлежат также множеству FIRST(E+T). В силу этого мы не сможем однозначно определить последовательность вызовов процедур, которую мы должны выполнить при анализе входной цепочки. Проблема заключается в том, что нетерминал E встречается на первой позиции правой части правила, левая часть которого также E. В такой ситуации нетерминал E называется непосредственно леворекурсивным.

Определение. Нетерминал A КС-грамматики G называется леворекурсивным, если в грамматике существует вывод A =>* Aw.

Грамматика, имеющая хотя бы одно леворекурсивное правило, не может быть LL(1)-грамматикой. С другой стороны, известно, что каждый КС-язык определяется хотя бы одной нелеворекурсивной грамматикой.

Алгоритм устранения леворекурсивности

Опишем алгоритм устранения непосредственной леворекурсивности. Пусть G = (N, T, P, S) – КС-грамматика и правило A→Aw₁ | Aw₂ | … | Aw_n | v₁ | v₂ | … | v_m представляет собой все правила из P, содержащие A в левой части, причем ни одна из цепочек v_i не начинается с нетерминала A. Добавим к множеству N еще один нетерминал A' и заменим правила, содержащие A в левой части, на следующие:

A → v₁ | v₂ | … | v_m | v₁A’ | v₂ A’ | … | v_m A'

A’ → w₁ | w₂ | … | w_n | w₁ A’ | w₂ A’ | … | w_n A'

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

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

E → T | TE'

E' → +T | +TE'

T → F | FT'