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

Существует стандартный способ придать выражениям смысл: сначала ввести символы, а затем собрать их в лексемы (как мы и сделали). Поэтому, если мы введем выражение

программа должна создать список лексем

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

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

означает , а не , но как объяснить программе, что деление имеет более высокий приоритет, чем сложение? Стандартный ответ — написать грамматику, определяющую синтаксис ввода, а затем программу, реализующую правила этой грамматики. Рассмотрим пример.

Это набор простых правил. Последнее правило читается так: “

— это ”. Предыдущее правило утверждает: “ — это или скобка, , за которой следует и скобка, ”. Правила для и аналогичны; каждый из них определяется в терминах одного из предыдущих правил.

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

•

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

•

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

•

, (скобки).

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

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

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

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

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