13

Синтактичен анализ и намиране на стойност на израз. Търсене с връщане назад

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

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

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

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

или

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

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

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

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