Побудувати спадний розпізнавач для оператору виводу write або writeln. Оператор може містити в дужках список операторів і і коментарів ‘t ‘.
1. Будуємо правила граматики
1. I®write A;|writelnA;
2. A®(B)
3. A®$
4. B®’t’C
5. B®iC
6. C®, B
7. C®$
2. Дана граматика не містить марних символів і не містить ліворекурсивні правила.
3. Дана граматика містить анулюючі правила та правила, права частина котрих починається з нетермінала, отже вона не може бути розділеною та слаборозділеною граматикою. Визначимо належність даної граматики до LL(1) - граматики.
1. ВИБІР(I®write A;|writelnA; )={write, writeln }
2. ВИБІР (A®(B))={ (}
3. ВИБІР(A®$)=Слід(А)={$,; }
4. ВИБІР(B®’t’C )={ ‘}
5. ВИБІР(B®iC )={i }
6. ВИБІР( C®, B)={, }
7. ВИБІР(C®$)=Слід(С)=Слід(В)={),$ }
Дана граматика є LL(1) – граматикою, так як множина ВИБІР для правил, що починаються з однакових терміналів не містить однакових символів.
4. Будуємо команди розпізнавача:
1. f(s, write, I)=(s, h0;A)
2. f(s, writeln, I)=(s, h0;A)
3. f(s, (, A)=(s, h0)B)
4. f*(s, ; , A)=(s, $)
5. f*(s, $, A)=(s, $)
6. f(s, ‘, B)=(s, C’t)
7. f(s, i, B)=(s, C)
8. f(s, , , C)=(s, B)
9. f*(s, ),C)=(s, $)
10. f*(s, $, C)=(s, $)
11. f(s, ; , ;)=(s, $)
12. f(s, ) , ))=(s, $)
13. f(s, ’, ‘)=(s, $)
14. f(s, t, t)=(s, $)
15. f(s, $, h 0)=($, $)
5. Розпізнаємо заданий ланцюжок:
(s, writeln(‘t’,I,I); h0I ) – 1
(s, (‘t’,I,I); h0;A ) – 3
(s, ‘t’,I,I); h0;)B ) – 6
(s, t’,I,I); h0;)C’t ) – 14
(s, ’,I,I); h0;)C’) – 13
(s, ,I,I); h0;)C ) – 8
(s, I,I); h0;)B ) –7
(s, ,I); h0;)C ) – 8
(s, I); , h0;)B) – 7
(s, ); , h0;)C) – 9
(-(s, ); , h0;)) – 12
(s, ; , h0;) – 11
(s, $, h0) – 15
($,$)
Ланцюжок розпізнано.
9. Література.
1. Альфред Ахо, Рави Сети Джеффри Ульман . Компиляторы. Принципы , технологии, инструменты.:Москва-Санкт-Петербург-Киев:Вильямс, 2001 г.-767 с.
2. Гордеев А.В. Молчанов А.Ю. Системное программное обеспечение. Учебник.- Санк-Петербург, 2002 г.- 734 с.
3. А. Ахо, Дж.Ульман. Теория синтаксического анализа перевода и компиляции М.:Мир,1978.-612с
4. Р. Хантер. «Проектирование и конструирование компиляторов».-М.: Финансы и статистика, 1984.