Рекурсия

(допълнение)

1. Синтактичен анализ и намиране на стойност на изрази

В много случаи синтаксисът на различни езикови конструкции има рекурсивна структура. За формалното описание на такива конструкции се използва широкоразпространения език на Бекус-Наур. Например, цяло число без знак можем да опишем по следните два начина:

<цяло_без_знак> ::= <цифра>|

<цяло_без_знак><цифра>

или

<цяло_без_знак> ::= <цифра>|

<цифра><цяло_без_знак>

Да се направи синтактичен анализ на символен низ според някакви правила означава да се провери дали низът е получен според тези правила и се определи видът на съставящите го части и връзките между тях. За целта се конструира т. нар. дърво на синтактичния разбор.

Например символните низове (9+7) и ((8-5)/2) са изрази според правилата:

<израз> ::= <цифра>|(<израз><знак><израз>)

<знак> ::= +|-|*|/;