Терм:
Первичное выражение
Терм "*" Первичное выражение // умножение
Терм "/" Первичное выражение // деление
Терм "%" Первичное выражение // остаток (деление по модулю)
Первичное выражение:
Число
"(" Выражение ")" // группировка
Число:
литерал_с_плавающей_точкой
Это набор простых правил. Последнее правило читается так: “Число — это литерал с плавающей точкой”. Предыдущее правило утверждает: “Первичное выражение — это Число или скобка, '(', за которой следует Выражение и скобка, ')'”. Правила для Выражения и Терма аналогичны; каждый из них определяется в терминах одного из предыдущих правил.
Как показано в разделе 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 является не открывающей скобкой, (, а литералом_с_плавающей_точкой, который является Числом, которое является Первичным выражением.