Лабораторные работы 1-7(старые) / Отчет по ТЯП5
.docСанкт-Петербургский государственный электротехнический университет
КАФЕДРА МО ЭВМ
ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ N5
по дисциплине "Теория языков программирования"
“Алгоритм разбора для LL(1) – грамматик.”
Преподаватель: Самойленко В.П.
студенты гр. 0341 Юбрин А.Н.
Шин Е.Д.
Санкт-Петербург
2002
5.1 Построить управляющую таблицу (вручную) и промоделировать работу LL(1) – анализатора для КС– грамматики G = (T,N,S,R).
T= {a,b,c,d}
N= {S,A,B}
R= {S BA (1), A BS (2), A d (3), B aA (4), B bS (5), B c (6)}
V={S,A,B,a,b,c,d}
VT={a,b,c,d}
-
Построим управляющую таблицу.
Таблица должна содержать 8 строк, помеченных символами из множества V{} и 5 столбцов, помеченных символами из множества VТ{}.
Построим строку таблицы для нетерминала S. Этому нетерминалу соответствует правило (1),
ПЕРВ(ВА)={a, b, c}, следовательно M(S,a)=M(S,b)=M(S,c)=(BA,1).
Для нетерминала A имеется 2 правила вывода (2) и (3). По правилу (2) ПЕРВ(BS)={a, b, c}, следовательно M(A,a)=M(A,b)=M(A,c)=(BS,2), по правилу (3) Ad следовательно M(A,d)=(d,3).
Для нетерминала B имеется 3 правила вывода (4), (5) и (6).
(4) M(B,a)=(aA,4)
(5) M(B,b)=(bS,5)
(6) M(B,c)=(c,6)
Далее всем элементам таблицы, находящимся на пересечении строки и столбца отмеченных одним и тем же терминалом, присвоим значение ВЫБРОС, а элементу таблицы M(, ) присвоим значение ДОПУСК.
Остальным элементам присвоим значение ОШИБКА.
Управляющая таблица (Пустые ячейки - ОШИБКА)
|
a |
b |
с |
d |
|
S |
BA,1 |
BA,1 |
BA,1 |
|
|
A |
BS,2 |
BS,2 |
BS,2 |
d,3 |
|
B |
aA,4 |
bS,5 |
c,6 |
|
|
a |
выб |
|
|
|
|
b |
|
выб |
|
|
|
c |
|
|
выб |
|
|
d |
|
|
|
выб |
|
|
|
|
|
|
доп |
ПРИМЕР работы анализатора
Входная цепочка – bcdadcd
Конфигурации алгоритма
------------------------------------------------
# ¦ Магазин ¦ Вх. цепочка ¦ Вых. цепочка
---+-------------+----------------+--------------
0¦ S - ¦ b c d ¦
1¦ B A - ¦ b c d ¦ 1
2¦ b S A ¦ b c d ¦ 1 5
3¦ S A - ¦ c d a ¦ 1 5
4¦ B A A ¦ c d a ¦ 1 5 1
5¦ c A A ¦ c d a ¦ 1 5 1 6
6¦ A A - ¦ d a d ¦ 1 5 1 6
7¦ d A - ¦ d a d ¦ 1 5 1 6 3
8¦ A - ¦ a d c ¦ 1 5 1 6 3
9¦ B S - ¦ a d c ¦ 1 5 1 6 3 2
10¦ a A S ¦ a d c ¦ 1 5 1 6 3 2 4
11¦ A S - ¦ d c d ¦ 1 5 1 6 3 2 4
12¦ d S - ¦ d c d ¦ 1 5 1 6 3 2 4 3
13¦ S - ¦ c d Eps ¦ 1 5 1 6 3 2 4 3
14¦ B A - ¦ c d Eps ¦ 1 5 1 6 3 2 4 3 1
15¦ c A - ¦ c d Eps ¦ 1 5 1 6 3 2 3 1 6
16¦ A - ¦ d Eps ¦ 1 5 1 6 3 2 3 1 6
17¦ d - ¦ d Eps ¦ 1 5 1 6 3 2 3 1 6 3
18¦ - ¦ Eps ¦ 1 5 1 6 3 2 3 1 6 3
19¦ - ¦ Eps ¦ 1 5 1 6 3 2 3 1 6 3
-----------------------------------------------
Разбор входной цепочки завершен успешно !
Выходная цепочка - 1 5 1 6 3 2 3 1 6 3