Программирование. Принципы и практика использования C++ Исправленное издание - Бьёрн Страуструп

  Предложение Союз Предложение // например, Birds fly but

                               // fish swim

Союз:

 "and"

 "or"

 "but"

Имя существительное:

 "birds"

 "fish"

 "C++"

Глагол:

 "rules"

 "fly"

 "swim"

Предложение состоит из частей речи (например, имен существительных, глаголов и союзов). В соответствии с этими правилами предложение можно разложить на слова — имена существительные, глаголы и т.д. Эта простая грамматика также включает в себя семантически бессмысленные предложения, такие как “C++ fly and birds rules,” но решение этой проблемы выходит далеко за рамки рассмотрения нашей книги.

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

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

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

6.4.2. Запись грамматики

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

  2. Записывать правила одно за другим (последовательно).

  3. Выражать альтернативные варианты (разветвление).

  4. Выражать повторяющиеся варианты (повторение).

  5. Распознавать начальное правило.

В разных учебниках и системах грамматического разбора используются разные соглашения и терминология. Например, иногда лексемы называют терминалами (terminals), а правила — нетерминалами (non-terminals), или продукциями (productions). Мы просто заключаем лексемы в двойные кавычки и начинаем с первого правила. Альтернативы выражаются с помощью линий. Рассмотрим пример.

Список:

  "{"Последовательность"}"

Последовательность:

  Элемент

  Элемент "," Последовательность

Элемент:

  "A"

  "B"

Итак, Последовательность — это Элемент или Элемент, за которым следует разделяющая запятая и другая Последовательность. Элемент — это либо буква A, либо B. Список — это Последовательность в фигурных скобках. Можно сгенерировать следующие Списки (как?):

{A}

{B}

{A,B}

{A,A,A,A,B}

Однако то, что перечислено ниже, списком не является (почему?):

{}

A

{A,A,A,A,B

{A,A,C,A,B}

{A B C}

{A,A,A,A,B,}

Этим правилам вас в детском садике не учили, и в вашем мозге они не “встроены”, но понять их не сложно. Примеры их использования для выражения синтаксических идей можно найти в разделах 7.4 и 7.8.1.

6.5. Превращение грамматики в программу

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

6.5.1. Реализация грамматических правил

Для реализации калькулятора нам нужны четыре функции: одна — для считывания лексем и по одной для каждого грамматического правила.

get_token()  // считывает символы и составляет лексемы

             // использует поток cin

expression() // реализует операции + и –

             // вызывает функции term() и get_token()

term()       // реализует операции *, / и %

             // вызывает функции primary() и get_token()

primary()    // реализует числа и скобки

             // вызывает функции expression() и get_token()

Что же эти функции должны делать в действительности? Каждая из них должна вызывать другие грамматические функции в соответствии с грамматическим правилом, которое она реализует, а также функцию get_token(), если в правиле упоминается лексема. Например, когда функция primary() пытается следовать правилу (Выражение), она должна вызвать следующие функции:

get_token()  // чтобы обработать скобки ( и )

expression() // чтобы обработать Выражение

Что должен возвращать такой грамматический анализатор? Может быть, реальный результат вычислений? Например, для выражения 2+3 функция expression() должна была бы возвращать 5. Теперь понятно! Именно это мы и должны сделать! Поступая таким образом, мы избегаем ответа на один из труднейших вопросов: “Как представить выражение 45+5/7 в виде данных, чтобы его можно было вычислить?” Вместо того чтобы хранить представление этого выражения в памяти, мы просто вычисляем его по мере считывания входных данных. Эта простая идея коренным образом изменяет ситуацию! Она позволяет в четыре раза уменьшить размер программы по сравнению с вариантом, в котором функция expression() возвращает что-то сложное для последующего вычисления. Таким образом, мы сэкономим около 80% объема работы.

Функция get_token() стоит особняком: поскольку она обрабатывает лексемы, а не выражения, она не может возвращать значения подвыражений. Например, + и ( — это не выражения. Таким образом, функция get_token() должна возвращать объект класса Token.

// функции, подчиняющиеся грамматическим правилам

Token get_token()   // считывает символы и составляет лексемы

double expression() // реализует операции + и –

double term()       // реализует операции *, / и %

double primary()    // реализует числа и скобки

6.5.2. Выражения

Сначала напишем функцию expression(). Грамматическое правило Выражение выглядит следующим образом:

Выражение:

  Терм

  Выражение '+' Терм

  Выражение '–' Терм

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

6.5.2.1. Выражения: первая попытка

Посмотрев на правило Выражение '+' Терм, сначала попытаемся вызвать функцию expression(), поищем операцию + (и