Алгоритм построения преобразователя.

Задана цепочка G= <V_T,V_N,I,R>

T = {P , S , s₀ , W , φ , ψ}

P,S,W– алфавит входных состояний и выходов.

s₀– начальное состояние.

φ , ψ – функции переходов и выходов.

P = W_T / e

S = V_N

s₀ = I

φ , ψ  R

1. По заданной грамматике мтроится распознаватель.

2. В качестве выходного алфавита берем множество номеров правил грамматики.

3. Строится множество функций выходов преобразователя. Для каждого правила с номером mвидаAbC

A , C € V_N

b € V_T

в автомате будут соответственно выходная функция.

Пример:

G :

V_T = {a , b , c

V_N = {I , A , B}

I

R = {I aA , A  aA , A bB , B  bB , Bc , (B cZ , Z  e)}

Построим распознаватель

W = {1 , 2 , 3 , 4 , 5}

Построим цепочку aabbbc.

Если подать на вход aabbbc, то получим синтаксический разбор [1 , 2 , 3 , 4 , 5].