определяется в терминах одного из предыдущих правил.
Как показано в разделе 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 являются литералами_с_ плавающей_точкой, которые являются Числами, которые являются Первичными выражениями, так что можем игнорировать все остальные правила.
1. 45 — это Выражение, за которым следует символ +, поэтому следует искать Терм, чтобы применить правило Выражение+Терм.
2. 11.5 — это Терм, за которым следует символ *, поэтому следует искать Первичное выражение, чтобы применить правило Терм*Первичное выражение.
3. 7 — это первичное выражение, поэтому 11.5*7 — это Терм в соответствии с правилом Терм*Первичное выражение. Теперь можем убедиться, что 45+11.5*7 — это Выражение в соответствии с правилом Выражение+Терм. В частности, это Выражение, которое сначала выполняет умножение 11.5*7, а затем сложение 45+11.5*7 так, будто мы написали выражение 45+(11.5*7).
Еще раз проиллюстрируем эти рассуждения графически (как и ранее, для простоты останавливая разбор на правиле для литерала_с_плавающей_точкой).
Как и прежде, этот рисунок иллюстрирует путь, который мы прошли, перебирая определения. Обратите внимание на то, что правило Терм*Первичное выражение гарантирует, что 11.5 умножается на 7, а не добавляется к 45.
Эта логика может показаться запутанной, но многие люди читают грамматики, и простые грамматики несложно понять. Тем не менее мы не собираемся учить вас вычислять выражение 2+2 или 45+11.5*7. Очевидно, вы это и так знаете. Мы лишь стараемся выяснить, как выполняет эти вычисления компьютер. Разумеется, для того чтобы выполнять такие вычисления, людям грамматики не нужны, а вот компьютерам они очень хорошо подходят. Компьютер быстро и правильно применяет правила грамматики. Точные правила — вот что нужно компьютеру.
6.4.1. Отступление: грамматика английского языка
Если вы еще никогда не работали с грамматиками, то ваша голова может закружиться. Но, даже если вы уже сталкивались с грамматиками раньше, ваша голова может закружиться, когда вы увидите следующую грамматику, описывающую очень небольшую часть английского языка.
Предложение:
