Лекция 6 Определение синтаксического разбора

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

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

Определение. Пусть G=(N,,P,S) - КС-грамматика, правила которой пронумерованы 1,2, ...,р, (NU)*. Тогда

левым разбором цепочки  называется последовательность правил, примененных при левом выводе цепочки  из S;

правым разбором цепочки  называется обращение последовательности правил, примененных при правом выводе цепочки  из S.

Эти разборы можно представить в виде последовательности номеров из множества {1, 2, . . . , р}.

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

(1) E  E+T,

(2) E  T,

(3) T  T*F,

(4) T  F,

(5) F  (E),

(6) F  a,

а так же цепочку a*(a+a) и ее левый и правый разборы. Имеем:

левый вывод: Е₂  Т₃  Т*F₄  F*F₆a*F₅  a*(E)₁  a*(E+T)₂ a*(T+T)₄ a*(F+T)₆ a*(a+T)₄a*(a+F)₆  a*(a+a) ;

левый разбор: 23465124646;

правый вывод: Е  ₂Т  ₃Т*F  ₅ T*(E)  ₁ T*(E+T)  ₄ T*(E+F) ₆ T*(E+a)  ₂ T*(T+a)  ₄ T*(F+a)  ₆ T*(a+a)  ₄ F*(a+a)  ₆ a*(a+a);

правый разбор: 64642641532.

Понятию разбора можно дать и графическую интерпретацию: говорят, что для некоторой КС-грамматики G цепочка   L(G) разобрана, или проанализирована, если известно одно (или, быть может, все) из ее деревьев выводов. При трансляции такое дерево можно “физически” построить в памяти машины.

Нисходящий и восходящий разборы

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

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

Пусть  = i₁ ... i_n — левый разбор цепочки   L(G), где G — КС-грамматика. Зная  можно построить левый вывод и соответствующее дерево вывода цепочки .

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

(1) Е  Е + Т,

(2) Е  Т,

(3) Т  Т * F,

(4) T  F,

(5) F  (E),

(6) F  a

и цепочку =a*(a+a). Если  = 23465124646, то дерево вывода имеет вид, показанный на рис.5.1.

Рис.

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

Изменим теперь исходные данные. Пусть задана грамматика G=(N,,P,S) с занумерованными правилами и цепочка   L(G). Требуется построить ее левый разбор , т.е. решить задачу разбора. Можно считать, что нам известны корень и крона дерева. Стратегия нисходящего разбора заключается в попытках построения дерева, начиная с его корня и двигаясь сверху вниз, слева направо, восполняя недостающие вершины, пока не будет достигнута крона дерева. На каждом шаге выбирается только одно правило грамматики (и запоминается его номер), которое приводит к построению очередной внутренней вершины.

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

Левый анализатор можно моделировать при помощи МП -преобразователя.

Определение. Пусть G=(N, ,P,S) – КС-грамматика и ее правила пронумерованы от 1 до р. Определим левый анализатор как недетерминированный МП - преобразователь:

M_l=({q}, , N  , {1,2,...,p},, q, S, ),

где  определяется следующим образом:

1. для всех АN  (q, e, A)={(q,, i) | если А  - правило с номером i};

2. для всех а (q, a, a)={(q, e, e)}. 

Пример . Пусть G-грамматика из примера и

М_l=({q}, {a, *, +, (, )}, {E, T, F, a, *, +, (, )}, {1, 2, ..., 6}, , q, E, ),

где (q, e, E)={(q, E+T, 1), (q, T, 2)};

(q, e, T)={(q, T*F, 3), (q, F, 4)};

(q, e, F)={(q,( E), 5), (q, a, 6)};

(q, b, b)={(q, e, e)} для всех b.

Пусть на входе анализатора цепочка =a+a*a, и начальная конфигурация анализатора имеет вид (q, a+a*a, E, e).

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

(q, e, e, 12463466).

Легко убедиться, что выходная цепочка =12463466 - левый разбор входной цепочки .

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

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

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