Приклад 1. 1. Побудувати спадний розпізнавач для оператору присвоювання арифметичного виразу

1. Побудувати спадний розпізнавач для оператору присвоювання арифметичного виразу. Арифметичний вираз містить: ідентифікатори і,:=, (,),;. Кількість вкладених дужок не обмежена.

1. Будуємо правила граматики

1. I® i = A;

2. A® i C

3. A® (А) C

4. C® + A

5. C® $

2.Визначимо чи містить наша граматика невиробляючі символи:

відшукуємо правило в правій частині, якого розташовано термінал чи $. {C} – продуктивний симвіл. Відшукуємо правила, праві символи яких вже занесені в список чи лівий символ вже занесений у список. Якщо є, то додаємо в список нетерміналів:

{C}

{CA}

{CAI}

У список потрапили всі нетермінали, отже, непродуктивних символів немає.

3. Шукаємо недосяжні символи.

Заносимо в список початковий символ граматики {I}

Шукаємо правила, ліва частина якого вже занесена в список. Додаємо нетермінали правої частини:

{I}

{IA}

{IAC}

У список потрапили всі нетермінали, отже, недосяжних символів немає.

4. Дана граматика містить анулюючі правила та правила, права частина котрих починається з нетермінала, отже вона не може бути розділеною та слаборозділеною граматикою. Визначимо належність даної граматики до LL(1) - граматики.

Аналізуючи складені нами правила, дійдемо висновку, що ліворекурсивних правил немає.

Побудуємо функцію ВИБІР:

1. ВИБІР(I®і:=A;)={і}

2. ВИБІР(A®iC)={і}

3. ВИБІР(A®(А)C)={(}

4. ВИБІР(C®+A)={+}

5. ВИБІР(C®$)=СЛІД(А)={;,)}

Дана граматика є LL(1) – граматикою, так як множина ВИБІР для правил, що починаються з однакових терміналів не містить однакових символів.

5. Будуємо команди розпізнавача:

1) f(S, i, I)=(S, h₀;A:=)

2) f(S, i, A)=(S, h₀C)

3) f(S, (, A)=(S, h₀C)А)

4) f(S, +, C)=(S, A)

5) f*(S,;, C)=(S, $)

6) f*(S,), C)=(S, $)

7) f(S,:=,:=)=(S, $)

8) f(S,),))=(S, $)

9) f(S,;,;)=(S, $)

10) f(S, $, h₀)=(S, $)

6. Далі відповідно до побудованих правил розпізнаємо заданий ланцюжок:

(s, i:=i+(i+i);, h₀I) – 1

(s,:=i+(i+i);, h₀;A:=) – 7

(s, i+(i+i);, h₀;A) - 2

(s, +(i+i);, h₀;C) – 4

(s, (i+i);, h₀;A) – 3

(s, i+i);, h₀;C)A) – 2

(s, +i);, h₀;C)С) - 4

(s, i);, h₀;C)А) – 2

(s,);, h₀;C)C) – 6

(s,);, h₀;С)) – 8

(s,;, h₀;C) -5

(s,;, h₀;) -9

(s, $, h₀) -10

(s,$,$)

Ланцюжк розпізнано.