Перед тем как приступить к разработке интерпретатора языка С, необходимо уяснить структуру языка С. Формальное определение языка С (например, в стандарте ANSI/ISO) очень длинное, к тому же в нем довольно много зашифрованных для неискушенного читателя положений. Однако совершенно формальное определение языка С для разработки интерпретатора не понадобится, потому что этот язык является довольно прямолинейным. Полное формальное определение языка С необходимо для создания коммерческого компилятора, а для Little С оно не является необходимым. (Фактически, в одной главе невозможно изложить формальный синтаксис, определяющий С; это заняло бы целую книгу.)
Эта глава предназначена для широкого круга читателей. Она не была задумана как формальное введение в теорию структурированных языков в целом и языка С в частности. Поэтому здесь некоторые концепции изложены упрощенно и разработка интерпретатора подмножества С ведется так, что от читатели не потребуется формальная подготовка по теории языков (структурной лингвистике).
Несмотря на это для реализации и понимания интерпретатора Little С некоторые сведения об определении языка все же необходимы. Материал, изложенный далее, является вполне достаточным для наших целей. Желающим ознакомиться с более формализованным изложением материала следует обратиться к стандарту ANSI/ISO языка С.
Все программы на С представляют собой набор из одной или более функций плюс глобальные переменные (если они есть). Функция состоит из спецификатора типа функции, имени функции, списка параметров и блока операторов, ассоциированного с функцией. Блок начинается скобкой {, за которой следует последовательность из одного или нескольких операторов, и заканчивается скобкой }. Оператор языка С либо начинается с одного из зарезервированных слов, например if, либо является выражением. (Что представляет собой выражение, будет рассмотрено в следующем разделе.) Изложенные выше порождающие правила могут быть сведены в следующую таблицу:
программа -> набор функций плюс глобальные переменные
функция -> спецификатор список_параметров блок_операторов
блок_операторов -> { последовательность_операторов }
оператор -> зарезервированное_слово, выражение или блок_операторов
Выполнение любой программы на С начинается вызовом функции main() и кончается последней закрывающейся скобкой } или первым оператором return, встретившимся в main(), если до этого не встретились exit() или abort(). Любая другая функция программы должна быть непосредственно или косвенно вызвана функцией main(). Таким образом, выполнение программы начинается с началом выполнения main() и кончается выходом из нее. Интерпретатор Little С именно так и работает.
В языке С роль выражений несколько шире, чем в других языках программирования. В общем случае в программе на С оператор может начинаться с зарезервированного слова языка С, например, while или switch, а может и не начинаться с него. Для удобства дальнейшего изложения все операторы, начинающиеся с зарезервированного слова языка С, будем называть операторами с зарезервированным словом. Все остальные операторы (не начинающиеся с зарезервированного слова) будем называть операторами-выражениями. Таким образом, все следующие операторы языка С являются операторами-выражениями:
count = 100; /* Строка 1 */
sample = i / 22 * (c-10); /* Строка 2 */
printf("Этo выражение"); /* Строка 3 */
Рассмотрим каждый из этих операторов-выражений подробно. В языке С знак равенства является оператором присваивания[1]. Здесь оператор присваивания работает не так, как, например, в BASIC. В языке BASIC значение, вычисленное в правой части знака равенства, присваивается переменной в левой части, однако, и это весьма существенно, это значение не является значением оператора присваивания. В то же время в языке С знак равенства является оператором присваивания и значение результата оператора присваивания равно значению, полученному в правой части. Следовательно, в языке С оператор присваивания фактически является выражением присваивания. Оператор присваивания имеет значение, поэтому он является выражением. Именно по этой причине правильными являются, например, следующие выражения:
а = b = с = 100;
printf("%d", a=4+5);
Эти выражения в языке С допустимы, потому что присваивание является оператором, имеющим значение, как и любая другая операция.
Продолжим рассмотрение предыдущего примера. Строка 2 содержит более сложное присваивание. В строке 3 вызывается функция printf(), выводящая на экран строку. В языке С все функции базовых типов, отличных от void, возвращают значение независимо от того, определен тип явно или нет. Следовательно, вызов функции, возвращающей значение, является выражением, имеющим значение, опять же независимо от того, присваивается оно чему-либо или нет. Вызов функции, не возвращающей значения (определенной со спецификатором void), также является выражением, однако его результат имеет тип void.
Перед тем как приступить к разработке программы, способной правильно вычислить значение выражения, нужно дать более формальное определение выражения. Фактически в каждом языке программирования выражения определяются рекурсивно с помощью порождающих правил, или продукций. Интерпретатор Little С поддерживает следующие операции: +, -, *, /, %, =, операторы сравнения (<, ==, > и так далее) и скобки. В языке Little С выражения определяются с помощью следующих порождающих правил:
выражение -> [присваивание] [значение_переменной] присваивание -> именующее_выражение = значение_переменной именующее_выражение -> переменная значение_переменной -> часть [оператор_сравнения часть] часть -> терм [+терм] [-терм] терм -> множитель [*множитель] [/множитель] [%множитель] множитель -> [+ или -] атом атом -> переменная, константа, функция, или(выражение)
Здесь термин оператор_сравнения может обозначать любой из операторов сравнения. Термины именующее_выражение и значение_переменной означают объекты в левой и правой частях оператора присваивания. Старшинство оператора определяется порождающим правилом. Чем выше старшинство оператора, тем ниже в списке операторов он расположен.
Рассмотрим применение порождающих правил на примере вычисления выражения
count = 10 - 5 * 3;
Сначала применяется правило 1, разделяющее выражение на три части:
count = 10-5*3
^ ^ ^
| | |
именующее_выражение присваивание значение_переменной
Поскольку значение нетерминала значение_переменной не содержит операторов сравнения, то оно может быть сгенерировано в результате применения порождающего правила для нетерминала терм:
10 - 5*3 ^ ^ ^ | | | терм минус терм
Несомненно, второй терм составлен из двух множителей: 5 и 3. Эти два множителя являются константами, они порождаются с помощью порождающих правил более низкого уровня.
Теперь, чтобы вычислить значение выражения, будем двигаться, следуя порождающим правилам, в обратном направлении. Сначала выполняется умножение 5*3, что дает 15. Потом это значение вычитается из 10, получается -5. И, наконец, последний шаг — присваивание этого значения переменной count, оно же является значением всего выражения.
При создании интерпретатора Little С в первую очередь нужно построить алгоритмический эквивалент рассмотренной только что процедуры вычисления выражения.
[1]Сам знак равенства является, конечно, знаком операции присваивания.