Как написать программу, которая будет получать на входе строку, содержащую числовое выражение, например (10 - 5) * 3, и выдавать соответствующий результат? Если среди программистов и есть «высшие священники», то это те, кто знает, как решить подобную задачу. Многие, притом высококвалифицированные в других областях программисты не имеют представления о том, как трансляторы, разработанные для компиляции программ, написанных на языках высокого уровня, преобразовывают алгебраические выражения в команды, выполняемые компьютером. Эта процедура называется синтаксический разбор выражений (expression parsing) и является основой всех компиляторов и интерпретаторов языков, электронных таблиц и всех остальных программ, в которых требуется превращать числовые выражения в форму, понятную компьютеру.
Несмотря на свою загадочность, синтаксический разбор выражений является довольно прямолинейным процессом и во многих аспектах проще, чем некоторые другие задачи программирования. Это обусловлено тем, что задача синтаксического разбора четко определена и решается в соответствии со строгими правилами алгебры. В настоящей главе будет разработан рекурсивный нисходящий синтаксический анализатор, или синтаксический анализатор методом рекурсивного спуска (recursive-descent parser), a также все функции, необходимые для вычисления выражений. Освоив принцип действия этой программы, вы с легкостью сможете доработать и модифицировать ее в соответствии со своими задачами.
| На заметку | В интерпретаторе языка С, представленном в части VI данной книги, применяется улучшенный вариант разработанного здесь синтаксического анализатора. Если вы будете изучать интерпретатор С, материал данной главы будет вам особенно полезен. |