Теория языков программирования методов трансляции (стр. 19 )

Таблица 4.6 – Таблица разбора

	terminals	jump	accept	stack	return	Error
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22	{begin} {begin} {d} {semi} {s} {end} {d} {d} {comma, semi} {comma} {semi} {comma} {d} {semi} {s} {s} {comma, end} {comma} {end} {comma} {s} {end}	2 3 7 5 15 0 8 9 10 12 14 13 7 0 16 17 18 20 22 21 15 0	false true false true false true false true false false false true false false false true false false false true false false	false false true false true false false false false false false false false false false true false false false false false false	false false false false false true false false false false false false false true false false false false false false false true	True True True True True true true true true false true true true true true true true false true true true true

Рассмотрим разбор предложения

begin d comma d semi s semi end

i	Действия	Стек разбора
1.	begin считывается и проверяется; перейти к 2	0
2.	begin считывается и принимается; перейти к 3	0
3.	d считывается и проверяется; 4 помещается в стек; перейти к 7	4 0
7.	d принимается; перейти к 8	4 0
8.	d проверяется и принимается; перейти к 9	4 0
9.	comma считывается и проверяется; перейти к 10	4 0
10.	comma проверяется; перейти к 12	4 0
12.	comma проверяется и принимается; перейти к 13	4 0
13.	d считывается и проверяется; перейти к 7	4 0
7.	d проверяется; перейти к 8	4 0
8.	d проверяется и принимается; перейти к 9	4 0
9.	comma считывается и проверяется; перейти к 10	4 0
10.	semi не совпадает с comma; ошибка ложь – перейти к 11	4 0
11.	comma проверяется; перейти к 14	4 0
14.	semi проверяется; возврат истина – удаляется 4; перейти к 4	0
4.	semi проверяется и принимается; перейти к 5	0
5.	s считывается и проверяется; 6 помещается в стек; перейти к 15	6 0
15.	s проверяется; перейти к 16	6 0
16.	s проверяется и принимается; перейти к 17	6 0
17.	comma считывается и проверяется; перейти к 18	6 0
18.	comma проверяется; перейти к 20	6 0
20.	comma проверяется и принимается; перейти к 21	6 0
21.	s считывается и проверяется; перейти к 15	6 0
15.	s проверяется; перейти к 16	6 0
16.	s проверяется и принимается; перейти к 17	6 0
17.	end считывается и проверяется; перейти к 18	6 0
18.	end не совпадает с comma; ошибка ложь; перейти к 19	6 0
19.	end проверяется; перейти к 22	6 0
22.	end проверяется; возврат истина – удалить 6; перейти к 6	0
6.	end проверяется и принимается; возврат истина – удалить 0; i:=0
0.	Разбор заканчивается

LL(1) – метод разбора имеет ряд преимуществ.

1)  Никогда не требует возврата, поскольку этот метод детерминирован.

2)  Время разбора пропорционально длине программы.

3)  Имеются хорошие диагностические характеристики, и существует возможность исправления ошибок, т. к. синтаксические ошибки распознаются по первому неприемлемому символу, а в таблице разбора есть список возможных символов предложения.

4)  Таблица разбора меньше, чем соответствующие таблицы в других методах разбора.

5)  LL(1) –разбор применим к широкому классу современных языков.

Контрольные вопросы

1.  Эквивалентность МП-автоматов и КС-грамматик.

2.  LR(k)-грамматики.

3.  S-грамматика.

4.  LL(1)-грамматика.

5.  Алгоритм определения принадлежности данной грамматики к LL(1)-грамматике.

6.  LL(1) – таблица разбора.

5.  Синтаксический анализ снизу вверх

5.1.  Разбор снизу вверх

Мы рассмотрели проблему левостороннего разбора как частный случай синтаксического анализа. Обобщая выводы, можно констатировать, что методы разбора могут быть нисходящими, т. е. идущими от стартового символа к предложению, и восходящими - от предложения к стартовому символу. Предложения, читаемые слева направо, норма для большинства естественных языков, хотя проблема разбора в них не всегда тривиальна. Однако ряд естественных языков и языков программирования имеют другую структуру. В этом случае удобнее использовать правосторонний вывод и соответствующие грамматики. Эти грамматики называются LR-грамматиками и в синтаксическом разборе используют технологию снизу вверх.

Синтаксические анализаторы, работающие по этому принципу, сводят предложения языка к начальному символу путем последовательного применения правил грамматики.

Рассмотрим, например, язык, генерируемый правилами

1)  S ® real IDLIST

2)  IDLIST ® IDLIST, ID

3)  IDLIST ® ID

4)  ID ® A | B | C |D.

Предложение real A, B, C принадлежит этому языку и может быть разобрано по следующей схеме. Каждый символ, считанный анализатором, немедленно помещается в стек анализатора.

real ­ A, B, C real

real A­, B, C A

real

Стрелка ставится непосредственно после последнего считанного символа. Затем анализатор заменяет А с помощью правила 4). Это действие называется приведение. Правые части правил заменяются их соответствующими левыми частями.

 

real A­, B, C ID

real

Далее применяется правило (3) для выполнения другого приведения.

real A­, B, C IDLIST

real

Теперь анализатор считывает следующий символ

,

real A, ­B, C IDLIST

real

и другой

В

,

real A, B­, C IDLIST

real

Очередные два действия – приведение с использованием правил 4) и 2)