Арифметические выражения

 

При описании арифметических выражений рекурсия означает возможность вложенности, т.е. использование в выражениях в качестве операндов подвыражений, заключенных в круглые скобки. Синтаксис языков программирования принято описывать с помощью рекурсивной нотации, называемой формой Бэкуса-Наура (БНФ). Она состоит из правил подстановки, определяющих как нетерминальный символ (т.е. символ, требующий дальнейшего уточнения) может быть замещен другим нетерминальным или терминальным символом (т.е. символом, не требующим уточнения). В правилах подстановки используется знак “|” для разделения альтернативных подстановок. Нетерминальные символы заключаются в угловые скобки “<>”. Символ “::=” означает “это есть”.

Определение простейшего арифметического выражения с помощью БНФ выглядит следующим образом:

 

<арифметическое выражение> ::= < операнд> <знак операции> < операнд>

<операнд> :: = <идентификатор> | (<арифметическое выражение>)

<знак операции> :: = + | - | * | /

<идентификатор> :: = a | b | …| z | A | B | … | Z

 

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

Примеры простейших арифметических выражений, соответствующих данному определению: X+Y X * (Y + Z) (Y * Z) – X (X + Y) * (Z – W )

(X / (Y + Z)) * W и т.п.

6.3.2. Динамические линейные структуры данных: списки

 

Рекурсивное определение списка: список - это пустая структура или структура, состоящая из особого элемента (первого или головного) и списка. Рекурсивную интерпретацию линейного односвязного списка иллюстрирует рис. 61.