Page 34 - 4625

Означення. Лівостороннім аналізом  ланцюжка 
 L(G) будемо називати послідовність номерів правил, які
були використані при лівосторонньому виведенні  в G.
Приклад: Для граматики G  N , , P, S зі схемою Р
S  S  T (1)
S T (2)
T  T * F (3)
T  T (4)
F  (S ) (5)
F  a (6)
для ланцюжка   a (a  a) побудуємо лівосторонній аналіз
*
:
S  T  T F  F F  a F  a (S )  a (S  T ) 
*
*
*
*
*
a (T  T ) a (F  T )  a (a  T )  a (a  F )  a (a  a)
*
*
*
*
*
З наведеного вище виведення ланцюжка   L(G)
лівосторонній аналіз  буде: 2,3,4,6,5,1,2,4,6,4,6, а
синтаксичне дерево виведення   a (a  a) зображено на
*
(рис. 11).
Нехай  лівосторонній аналіз ланцюжка   L(G).
Знаючи  досить легко побудувати (відтворити) синтаксичне
дерево. Відтворення (синтез) синтаксичного дерева можна
виконати, скориставшись однією зі стратегій синтаксичного
аналізу:
 стратегія "зверху донизу";
 стратегія "знизу вгору".

33