По своим выразительным возможностям постфиксная и префиксная записи равноценны, но при вычислении выражения, заданного префиксной записью, требуется рекурсивный алгоритм, а при вычислении выражения в постфиксной записи достаточно линейного алгоритма и стека, поэтому чаще встречается постфиксная форма. Алгоритм вычисления постфиксного выражения очень прост. Если очередная лексема — это число, кладем его в стек. Если очередная лексема — бинарный оператор, выталкиваем из стека два верхних значения, применяем к ним операцию и результат помещаем обратно в стек. Алгоритм легко обобщается на операторы с любым количеством операндов: соответствующая операция выталкивает из стека не два, а нужное ей число параметров. Функция от N аргументов рассматривается как операция, применяющаяся к N операндам.
Простота постфиксной записи делает ее очень привлекательной для низкоуровневого программирования. Метолом рекурсивного спуска достаточно легко создать код, переводящий выражение из инфиксной формы в постфиксную, а затем вычислить выражение уже в постфиксной форме. В простейшем случае такой промежуточный перевод только замедляет вычисления, и поэтому не используется, но иногда (например, при многократном вычислении одного выражения) перевод в постфиксную запись может сильно ускорить вычисления, тем более что выражение в постфиксной форме можно хранить не в виде строки, а в виде списка лексем, что еще больше ускорит его вычисление. В частности, код для стековой Java-машины, вычисляющий выражения, по сути эквивалентен постфиксной записи выражения.
Конечно, синтаксический анализ — вещь непростая, и здесь мы рассмотрели только самые его основы. За рамками книги остались атрибутивные грамматики, семантические деревья, генераторы языков и многое другое. Этим сложным вопросам посвящены специализированные книги. Долгое время ощущалась нехватка книг по данной тематике, но за последние два года вышли сразу три книги ([6–8]), посвященные созданию трансляторов. В этих книгах детально разбираются фундаментальные основы теории и даются примеры ее использования. Особенно стоит отметить книгу [6], в которой описан очень интересный язык программирования — Оберон-2, созданный при участии Никлауса Вирта; в нем развиваются идеи, заложенные Виртом в Паскаль. Ряд идей, предложенных при создании различных версий Оберона, уже позаимствованы другими языками (Java, C#, Ада), и еще многие ждут своего часа, поэтому программисту следует хотя бы ознакомительно изучить Оберон, чтобы понимать, в каком направлении может пойти развитие языков программирования.
В качестве источника полезных сведений можно также посоветовать книги, посвященные не столько теории разработки языков программирования, сколько истории их развития, например, [5, 9]. Теория синтаксического и семантического анализа в них изложена относительно неглубоко, но тесная связь изложения с практическими примерами позволяет существенно расширить кругозор в данной области. Особенно рекомендуем [5]. Книга [9] содержит больше сведений, но написана более тяжелым языком, а ее авторы крайне предвзято относятся к Паскалю, ставя ему в вину его достоинства и упрекая в несуществующих недостатках. Тем не менее эту книгу тоже следует прочитать.
Приложение 1
Сайт "Королевство Delphi"
Эта книга появилась на свет благодаря сайту "Королевство Delphi" (http://www.delphikingdom.com), поэтому будет справедливо, если мы уделим ему здесь немного внимания. Тем более что этот сайт сам по себе интересен для программиста, использующего Delphi. Главная страница сайта показана на рис. П1.1.
Рис. П1.1. Главная станица сайта "Королевство Delphi"
История сайта "Королевство Delphi" началась 20 ноября 1998 года (об истории создания см. страницу http://www.delphikingdom.com/team/about.asp). Он задумывался как виртуальный клуб программистов для взаимопомощи независимо от географии и расстояний (для тех, кто в Интернете недавно заметим, что в 1998 году тематических форумов практически не было, и до такой идеи еще надо было додуматься). На данный момент "Королевство Delphi" является одним из самых популярных сайтов, посвященных Delphi. В Королевстве имеется форум (который называется "Круглый стол"), где можно задавать вопросы и ряд разделов для публикации различных материалов: от небольших советов до серьезных циклов статей. Королевство принципиально не копирует чужие статьи и публикует только оригинальные материалы. написанные специально для сайта и присланные лично авторами. Некоторые количественные характеристики сайта (по состоянию на 7 сентября 2007 года) приведены в табл. П1.1 (информация взята со страницы http://www.delphikingdom.com/asp/tth.asp).
Таблица П1.1. Характеристики сайта "Королевство Delphi"
Наименование показателя Значение Зарегистрировано жителей 15 351 Опубликовано материалов 905 Задано вопросов 48 348 Из них с ответами 47 335 Всего дано ответов 179 704 В среднем в день задается вопросов 26 В среднем в день дается ответов 115
Сайт "Королевство Delphi" был создан Еленой Филипповой (http://www.delphikingdom.com/asp/users.asp?ID=10) и некоторое время она работала в одиночку. Сейчас сайт поддерживается командой из шести человек во главе с Еленой (свои впечатления о ведении этого проекта Елена с недавних пор начала описывать в блоге, который находится по адресу http://delphikingdom.blogspot.com). Команда Королевства поддерживает контакты с российским отделением CodeGear, благодаря чему в новостной ленте появляется информация о проводимых этой компанией мероприятиях и об интересных новостях, связанной с ней. Кроме того, на встречу с генеральным директором CodeGear Джимом Дугласом, посетившим Россию в июне 2007 года, были приглашены два представителя Королевства (с отчетом об этой встрече можно познакомиться по адресу http://www.delphikingdom.com/asp/viewitem.asp?catalogid=1320).
На сайте "Королевство Delphi" присутствует легкий антураж настоящего средневекового королевства, из-за чего разделы имеют непривычные названия. Чтобы разобраться во всех этих непонятных ссылках, требуются определенные усилия, которые, впрочем, вознаграждаются. Для тех, кто заинтересовался сайтом, приведем описание его основных разделов.
Круглый стол. Так в Королевстве называется форум, где каждый может задать вопрос. Вопросы сначала просматривает модератор и только потом они появляются (или не появляются) на Круглом столе. Если модератор принял решение отклонить вопрос, автору вопроса по почте отправляется уведомление с описанием причин, по которым вопрос отклонен. Наиболее частая причина отклонения — такой вопрос уже задавался ранее (и, может быть, много раз), ответы на него уже даны. В этом случае письмо будет содержать ссылки на ответы или рекомендации, как эти ответы быстро найти. Тем не менее не стоит злоупотреблять этой особенностью сайта и сразу задавать вопрос, надеясь, что ответ будет получен если не на форуме, то через модератора. Королевство имеет целый ряд сервисов для самостоятельного поиска ответа, и такой поиск в итоге дает больше знаний, чем готовый ответ. Задать вопрос и написать ответ можно без предварительной регистрации.
Для удобства навигации вопросы на Круглом столе можно сортировать по дате поступления или по дате последнего ответа. Можно также получить список вопросов, заданных за определенный период, и вопросов, на которые даны ответы за определенный период. Для зарегистрированных пользователей доступна также выборка всех своих вопросов, всех вопросов, на которые пользователь давал ответы, и сервис "Избранные вопросы", с помощью которого пользователь может отметить заинтересовавшие его вопросы и отслеживать появление ответов на них. Уведомления о новых вопросах и ответах при желании можно получать с помощью RSS.
Вопросы на Круглом столе остаются навсегда, они не отправляются в архив, и ссылки на них остаются действительными. Обсуждение вопроса не закрывается (за исключением случаев, когда модератор закрывает обсуждение из-за нарушения автором правил), поэтому все. даже самые старые вопросы, можно не только прочитать, но и что-то ответить или попросить уточнить, если это потребуется.
Существует список offtopic-вопросов. Туда попадают проблемы, которые обсуждаются часто, и их решения уже есть на Круглом столе. Каждый, кто спрашивает о чем-то, согласно правилам Королевства сначала должен ознакомиться с этим списком, чтобы не задать такой вопрос, который там уже есть.
Круглый стол посвящен только решению конкретных технологических проблем. Вопросы, связанные, например, с обсуждением стоимости работы, прочитанных книг, новостей программирования и т.п., сюда не попадают. Для них есть отдельные форумы.
