В соответствии с определением, рассмотренным в начале, имеем q-грамматику, так как:

ВЫБОР(1) ВЫБОР(2) = ,

ВЫБОР(3) ВЫБОР(4) = .

Построение нисходящего автомата

Рассмотренные понятия и методы их использования приводят к небольшой корректировке правил порождения АМП по S-грамматике, чтобы получить процедуру создания автомата по q-грамматике. Эта корректировка касается только пункта 5. Можно, конечно, полностью переписать исправленный алгоритм создания автомата, тем более, что использование современных редакторов позволяет осуществить эту процедуру без проблем. К тому же компания Microsoft приучила нас не экономить ресурсы. Но я не буду оригинальным и воспользуюсь авторским текстом [Льюис]. Пятое правило заменяется двумя следующими:

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

A b,

используется переход:

Если правило имеет вид:

A b,

то используется:

Вытолкнуть, Сдвиг.

Для того, чтобы применить правило:

используется переход

Вытолкнуть.

5.2. Если имеется правило с нетерминалом A в левой части и элемент, соответствующий магазинному A и входному символу b не был создан по правилу 5.1., то таким элементом м.б. либо применение пустого правила (A ) или операция "Отвергнуть".

Примеры построения АМП по q-грамматике

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

Следующий пример иллюстрирует использование правила 5.2, когда описанное в нем ячейка таблицы переходов может быть реализована любым из двух вариантов. Я бы предпочел второй, чтобы меньше мучиться. Грамматика G_7.5(S) описывается следующими правилами:

Множества выбора для каждого из правил будут выглядеть следующим образом:

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

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

Во втором варианте цепочка отвергается уже на втором шаге.

Распознавание вложенности скобок и q-грамматика

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

1. S (B)B
2. B (B)B
3. B

Правила выбора выглядят следующим образом:

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

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

Понятие множества выбора можно обобщить таким образом, чтобы применять его к КС-грамматикам произвольного вида.

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

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

1. S AbB
2. S d
3. A Cab
4. A B
5. B cSd
6. B
7. C a
8. C ed

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

В книге Льюиса и пр. [Льюис] приводится описание доказательства принадлежности заданной грамматики к LL(1)-грамматике. Оно занимает одиннадцать страниц, использует демонстрационные примеры, разреженные матрицы и т.д. Я неоднократно принимался за его чтение, но каждый раз с грустью убеждался, что мой IQ (надо как-нибудь, хоть разок, проверить его значение) является недостаточно высоким, чтобы осилить материал. Поэтому были попытки перескочить эти страницы, выбросить нисходящий разбор из головы и обратиться к другой религии, проповедующей восходящий разбор. Но и здесь мне не хватило веры в истинность избранного пути. Поэтому, как это часто бывает в жизни, я нашел одну маленькую религию, которую подогнал под свои воззрения. После этого я смог не только успокоить свою душу, но и нести новый свет в массы. Эта религия зиждется на диаграммах Вирта, источая дальше свои идеи на распознаватели и реализацию. Подробно она будет раскрыта в следующей теме. Ее применение позволило обойти мне непереваримое доказательство и остаться в лоне нисходящего разбора.

Программная реализация нисходящего автомата с магазинной памятью

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

Разработка программы по таблице переходов АМП

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

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

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

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

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

// BrackStack.cpp - автомат с магазинной памятью,
// распознающий вложенность круглых скобок.
// Построен на основе таблицы переходов,
// созданной по следующей q-грамматике:
// 1. S -> (B)B
// 2. B -> (B)B
// 3. B -> empty

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

// Магазинными символами автомата являются:
// S, B, маркер дна (bottom).

// Их значение должно быть за пределами видимых символов.
enum stackSymb {S = 256, B, bottom}; 

// Строка с входной цепочкой, имитирующая входную ленту
string str;
int i; // Текущее положение входной головки
stack <int, vector<int> > stck; // Стек для магазинных символов



// Функция, реализующая чтение символов в буфер из входного потока.
// Используется для ввода с клавиатуры распознаваемой строки.
// Ввод осуществляется до нажатия на клавишу Enter.
// Символ '\n' яляется концевым маркером входной строки.

void GetOneLine(istream &is, string &str) {
  char ch;
  str = "";
  for(;;) {
    is.get(ch);
    if(is.fail() || ch == '\n') break;
    str += ch;
  }
  str += '\n'; // Добавляется концевой маркер
}



// Инициализация устройств АМП

void Init() {
  // Инициализация стека
  while(!stck.empty())  stck.pop();
  stck.push(bottom);
  stck.push(S);

  // Инициализация входной головки
  i = 0;
}



// Устройство управления АМП, анализирующего вложенность скобок.
// Имитирует таблицу переходов АМП.

bool Parser() {

  // Инициализация устройств АМП
  Init();
  int step = 0;

  // Цикл анализа состояний
  for(;;) {
    // Тестовый вывод информации о текущем шаге, 
    // текущем символе, вершине стека
    cout <<"step " << step++ << ": str[" << i << "] = "<< str[i] 
         << " Top = "<< stck.top() << "\n";

    // Проверка содержимого на вершине стека
    switch(stck.top()) {
    // Анализ первой строки таблицы переходов
    case S:
        switch(str[i]) {
        case '(': // [S, (]
            stck.top() = B; // эквивалентно stck.pop(); stck.push(B);
            stck.push(')');
            stck.push(B);
            i++; // следующий входной символ
            break;
        case ')': // [S, )] - ) не может стоять в начале
            cout << "Position " << i << ", " 
                 << "Error 1: \')\' can not is in begin!\n";
            return false;
        case '\n': // [S, концевой маркер]
            cout << "Position " << i << ", " 
                 << "Error 2: Empty string!\n";
            return false;
        default: // Ошибка, такой символ не допустим
            cout << "Position " << i << ", " 
                 << "Incorrect symbol! " << str[i] << "\n";
            return false;
        }
        break;
    // Анализ второй строки таблицы переходов
    case B:
        switch(str[i]) {
        case '(': // [B, (]
            stck.top() = B; // эквивалентно stck.pop(); stck.push(B);
            stck.push(')');
            stck.push(B);
            i++; // следующий входной символ
            break;
        case ')': // [B, )] - вытолкнуть без сдвига 
            stck.pop();
            break;
        case '\n': // [B, концевой маркер] - вытолкнуть без сдвига
            stck.pop();
            break;
        default: // Ошибка, такой символ не допустим
            cout << "Position " << i << ", " 
                 << "Incorrect symbol! " << str[i] << "\n";
            return false;
        }
        break;
    // Анализ третьей строки таблицы переходов
    case ')':
        switch(str[i]) {
        case '(': // [), (] - в принципе недостижимо
            cout << "Position " << i << ", " 
                 << "Error 3: I want \')\'!\n";
            return false;
        case ')': // [), )] - вытолкнуть со сдвигом 
            stck.pop(); // вытолкнуть
            i++;  // сдвиг
            break;
        case '\n': // [), концевой маркер]
            cout << "Position " << i 
                 << ", Error 4: I want \')\'!\n";
            return false;
        default: // Ошибка, такой символ не допустим
            cout << "Position " << i << ", " 
                 << "Incorrect symbol! " << str[i] << "\n";
            return false;
        }
        break;
    // Анализ четвертой строки таблицы переходов
    case bottom:
        switch(str[i]) {
        case '(': // [bottom, (] - невозможно при пустом магазине
            cout << "Position " << i << ", "
                 << "Error 4: Impossible situation [bottom, \'(\']!\n";
            return false;
        case ')': // [bottom, )] - лишняя )
            cout << "Position " << i << ", "
                 << "Error 5: unnecessary \')\'!\n";
            return false;
        case '\n': // [bottom, концевой маркер] - допустить!
            return true;
        default: // Ошибка, такой символ не допустим
            cout << "Position " << i << ", " 
                 << "Incorrect symbol! " << str[i] << "\n";
            return false;
        }
        break;
    }
  }
}



// Главная функция используется для инициализации устройств
// АМП перед каждым новым прогоном и тестирования до тех пор,
// пока не будет прочитана пустая строка.
int main () {
  string strCursor;
  str = "";

  // Цикл распознавания различных входных цепочек
  do {
    // Чтение очередной входной цепочки в буфер
    cout << "Input bracket\'s expression!: ";

    // Формируем очередную строку скобок для распознавания.
    GetOneLine(cin, str);

    // Здесь начинается разбор принятой строки.
    if(Parser())
        cout << "+++++ OK! +++++\n";
    else
        cout << "--- Fatal error (look upper error message)! ---\n";

    // Вывод разобранной строки и значения позиции входой головки.
    cout << "Line: " << str;
    strCursor = " Pos: " + string(i, '-');
    strCursor +='^';
    cout << strCursor << " i = " << i << "\n\n";
  } while(str != "\n");

  cout << "Goodbye!\n";
  return 1;
}

Исходные тексты распознавателей на C++, C# и Go можно скачать с сайта. Помимо этого можно посмотреть работу распознавателя на основе автомата с магазинной памятью, написанного на JavaScript или скачать соответствующие исходники.

Разработка программы с использованием метода рекурсивного спуска

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

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

// Рекурсивный распознаватель вложенности круглых скобок.
// Построен на основе правил следующей q-грамматики:
// 1. S -> (B)B
// 2. B -> (B)B
// 3. B -> empty

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;
// Строка с входной цепочкой, имитирующая входную ленту
string str;
int i;  // Текущее положение входной головки
int erFlag;  // Флаг, фиксирующий наличие ошибок в середине правила



// Функция, реализующая чтение символов в буфер из входного потока.
// Используется для ввода с клавиатуры распознаваемой строки.
// Ввод осуществляется до нажатия на клавишу Enter.
// Символ '\n' яляется концевым маркером входной строки.

void GetOneLine(istream &is, string &str) {
  char ch;
  str = "";
  for(;;) {
    is.get(ch);
    if(is.fail() || ch == '\n') break;
    str += ch;
  }
  str += '\n'; // Добавляется концевой маркер
}



// Функция, реализующая распознавание нетерминала B.

bool B() {
  if(str[i] == '(') {
    i++;
    if(B()) {
      if(str[i] == ')') {
        i++;
        if(B()) { // Если последний нетерминал корректен, 
                  // то корректно и все правило.
          return true;
        } else { // Ошибка в нетерминале B
          erFlag++;
          cout << "Position " << i << ", " 
               << "Error 1: Incorrect last B!\n";
          return false;
        }
      } else { // Это не ')'
        erFlag++;
        cout << "Position " << i << ", "
             << "Error 2: I want \')\'!\n";
        return false;
      }
    } else {
      erFlag++;
      cout << "Position " << i << ", " 
           << "Error 3: Incorrect first B!\n";
      return false;
    }
  } else  // Смотрим другую альтернативу:
    return true; // Пустая цепочка допустима
}



// Функция, реализующая распознавание нетерминала S.

bool S() {
  if(str[i] == '(') {
    i++;
    if(B()) {
      if(str[i] == ')') {
        i++;
        if(B()) {
          if(str[i] == '\n') {
            return true; // за последним нетерминалом - конец
          } else { // Там ничего не должно быть
            erFlag++;
            cout << "Position " << i << ", "
              << "Error 4: I want string end after last right bracket!\n";
            return false;
          }
        } else {
          erFlag++;
          cout << "Position " << i << ", "
               << "Error 4: Incorrect last B!\n";
          return false;
        }
      } else {
        erFlag++;
        cout << "Position " << i << ", "
             << "Error 5: I want \')\'!\n";
        return false;
      }
    } else {
      erFlag++;
      cout << "Position " << i << ", "
           << "Error 6: Incorrect first B!\n";
      return false;
    }
  }
  return false; // Первый символ цепочки некорректен
  // то, что это ошибка, лучше определить снаружи
}



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

bool Parser() {
  // Начальная инициализация.
  erFlag = 0;
  i = 0;
  // Процесс пошел!
  if(S())
    return true; // Все прошло нормально
  else {
    if(erFlag)
      cout << "Position " << i << ", "
           << "Error 7: Internal Error!\n";
    else
      cout << "Position " << i << ", "
           << "Error 8: Incorrect first symbol of S!\n";
    return false; // Есть ошибки
  }
}



// Главная функция используется для тестирования до тех пор, 
// пока не будет прочитана пустая строка

int main () {
  string strCursor;
  str = "";
  // Цикл распознавания различных входных цепочек
  do {
    // Чтение очередной входной цепочки в буфер
    cout << "Input bracket\'s expression!: ";

    // Формируем очередную строку скобок для распознавания.
    GetOneLine(cin, str);
    
    // Здесь начинается разбор принятой строки.
    if(Parser())
      cout << "+++++ OK! +++++\n";
    else
      cout << "----- Fatal error (look upper error message)! -----\n";

    // Вывод разобранной строки и значения позиции входой головки.

    cout << "Line: " << str;
    strCursor = " Pos: " + string(i, '-');
    strCursor +='^';
    cout << strCursor << " i = " << i << "\n\n";
  } while(str != "\n");
  cout << "Goodbye!\n";
  return 1;
}

Исходные тексты данного примера на C++, C# и Go также доступны для скачивания. Помимо этого можно посмотреть работу распознавателя, написанного на JavaScript или скачать соответствующие исходники.

Следует отметить, что две представленные программы отличаются только фрагментами, осуществляющими разбор. Тестовая функция у них совпадает. Трудно сказать, какой из методов лучше. Использование рекурсивного спуска позволяет написать программу быстрее, так как не надо строить автомат. Ее текст может быть и менее ступенчатым, если использовать инверсные условия проверки или другие методы компоновки текста. Лично я не вижу причин заменять рекурсивный спуск автоматом с магазинной памятью, особенно в том случае, если грамматику задавать с использованием диаграмм Вирта. Но в общем (в который раз!) можно сказать, что о вкусах не спорят.

Контрольные вопросы и задания

1. Зачем, при синтаксическом разборе нужны автоматы с магазинной памятью?
2. Как организован автомат с магазинной памятью?
3. Основные операции автомата с магазинной памятью.
4. Каким образом ограничения, накладываемые на грамматику, определяют реализацию автомата?
5. Приведите примеры известных Вам ограниченных грамматик.
6. Каким образом можно построить АМП по s-грамматике?
7. Недостатки S-грамматики.
8. Разработка АМП по q-грамматике.
9. Приведите определения и краткие характеристики S-, q-, L-грамматик.
10. Методы программной реализации нисходящих автоматов с магазинной памятью.
11. Какие возможны варианты программной реализации нисходящего распознавателя при непосредственном использовании таблицы переходов АМП?
12. В чем специфика распознавателя, построенного с применением рекурсивного спуска?

[ содержание | предыдущая тема | следующая тема ]