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

Страуструп Бьерн

Как показано в разделе 6.3.2, наши лексемы, позаимствованные из определения языка C++, таковы:

•

литерал_с_плавающей_точкой

(по правилам языка C++, например,

3.14

,

0.274e2

или

42

);

•

+

,

–

,

*

,

/

,

%

(операторы);

•

(

,

)

(скобки).

Переход от нашего пробного псевдокода к подходу, основанному на лексемах и грамматиках, представляет собой

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

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

1–2*3

,

1+2–3

и

3*2+4/2

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

Как читать грамматику? Получив некое входное выражение, мы ищем среди правил совпадения для считанной лексемы, начиная с первого правила Выражение. Считывание потока лексем в соответствии с грамматикой называется синтаксическим разбором (parsing), а программа, выполняющая эту работу, называется синтаксическим анализатором (parser, или syntax analyser). Синтаксический анализатор считывает лексемы слева направо, точно так же, как мы печатаем, а затем читаем слова. Рассмотрим простой пример: 2 — это выражение?

1. Выражение должно быть Термом или заканчиваться Термом. Этот Терм должен быть Первичным выражением или заканчиваться Первичным выражением. Это Первичное выражение должно начинаться с открывающей скобки, (, или быть Числом. Очевидно, что 2 — не открывающая скобка, (, а литерал_с_плавающей_точкой, т.е. Число, которое является Первичным выражением.

2. Этому Первичному выражению (Число 2) не предшествует ни символ /, ни *, ни %, поэтому оно является завершенным Термом (а не выражением, которое заканчивается символом /, * или %).

3. Этому Терму (Первичное выражение 2) не предшествует ни символ +, ни –, поэтому оно является завершенным Выражением (а не выражением, которое заканчивается символами + или –).

Итак, в соответствии с нашей грамматикой 2 — это выражение. Этот просмотр грамматики можно описать так.

Этот рисунок иллюстрирует путь, который мы прошли, перебирая определения. Повторяя этот путь, мы видим, что 2 — это выражение, поскольку 2 — это литерал_с_плавающей_точкой,

который является Числом, которое является Первичным выражением, которое является Термом, который является Выражением.

Попробуем проделать более сложное упражнение: 2+3 — это Выражение? Естественно, большинство рассуждений совпадает с рассуждениями для числа 2.

1. Выражение должно быть Термом или заканчиваться Термом, который должен быть Первичным выражением или заканчиваться Первичным выражением, а Первичное выражение должно начинаться с открывающей скобки, (, или быть Числом. Очевидно, что 2 является не открывающей скобкой, (, а литералом_с_плавающей_точкой, который является Числом, которое является Первичным выражением.

2. Этому Первичному выражению (Число 2) не предшествует ни символ /, ни *, ни %, поэтому оно является завершенным Термом (а не выражением, которое заканчивается символом /, * или %).

3. За этим Термом (Числом 2) следует символ +, поэтому он является окончанием первой части Выражения, и мы должны поискать Терм, который следует за символом +. Точно так же мы приходим к выводу, что 2 и 3 — это Термы. Поскольку за Термом 3 не следует ни символ +, ни –, он является завершенным Термом (а не первой частью Выражения, содержащего символ + или – ). Следовательно, 2+3 соответствует правилу Выражение+Term и является Выражением.

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

Этот рисунок иллюстрирует путь, который мы прошли, перебирая определения. Повторяя его, мы видим, что 2+3 — это Выражение, так как 2 — это Терм, который является Выражением, 3 — это Терм, а Выражение, за которым следует символ + и Терм, является Выражением.

Действительная причина, по которой мы так интересуемся грамматиками, заключается в том, что с их помощью можно решить проблему корректного грамматического разбора выражений, содержащих символы + и *, такие как 45+11.5*7. Однако заставить компьютер анализировать правила так, как это сделали мы, очень трудно. Поэтому пропустим промежуточные этапы, которые проделали для выражений 2 и 2+3. Очевидно, что 45, 11.5 и 7 являются литералами_с_ плавающей_точкой, которые являются Числами, которые являются Первичными выражениями, так что можем игнорировать все остальные правила.