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, h0;A:=)
2) f(S, i, A)=(S, h0C)
3) f(S, (, A)=(S, h0C)А)
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, $, h0)=(S, $)
6. Далі відповідно до побудованих правил розпізнаємо заданий ланцюжок:
(s, i:=i+(i+i); , h0I) – 1
(s, :=i+(i+i);, h0;A:=) – 7
(s, i+(i+i);, h0;A) - 2
(s, +(i+i);, h0;C) – 4
(s, (i+i);, h0;A) – 3
(s, i+i);, h0;C)A) – 2
(s, +i);, h0;C)С) - 4
(s, i);, h0;C)А) – 2
(s, );, h0;C)C) – 6
(s, );, h0;С)) – 8
(s, ;, h0;C) -5
(s, ;, h0;) -9
(s, $, h0) -10
(s,$,$)
Ланцюжк розпізнано.