Деревья вывода

Порождение и свертывание можно также представлять с помощью деревьев вывода.

Пусть дана грамматика.

I ® T

I ® I + T

I ®I - T

T ® M

T ® T*M

T ® T/M

M ® (I)

M ® K

K ® a

K ® b

K ® c

Построим дерево вывода.

Для предложения a * b + c дерево вывода будет:

I

I T

T M

T * M K

M K c

a b

Этот же результат можно получить и другим способом:

I ® I + I

I ® I - I I

I ® I*I

I ® I/I I + I

I ® (I)

I ® a I * I c
I ® b

I ® c a b