- •1. Грамматики
- •Пример.
- •2. Лексический анализ
- •3. Синтаксический анализ
- •4. Генератор кода
- •Алгоритм.
- •5. Оптимизация кода
- •6. Регулярные множества, их распознавание
- •7. Компиляторы и интерпретаторы.
- •8. Эквивалентность мп-автоматов и кс-грамматик
- •9. Разбор снизу вверх
- •10. Lr(1) - таблица разбора
- •10. Lr(1) - таблица разбора
- •11. Построение lr – таблицы разбора
- •12. Сравнение ll – и lr – методов разбора
- •13. Нормальная форма Хомского
- •14. Нормальная формула Грейбах
- •15. Ll(1)-грамматики
- •16. Ll(1)-таблица разбора
- •17. Контекстно-свободные языки
- •18. Циклы
10. Lr(1) - таблица разбора
Выше мы рассмотрели технологию разбора «снизу вверх». Однако при этом не обсуждался вопрос, как решить, следует ли выполнять конкретное приведение, когда правая часть правила появляется в вершине стека. Механизмом, который регулирует вопрос принятия правильного решения, является таблица разбора.
Таблица представляет собой матрицу. Она состоит из столбцов для каждого терминала и нетерминала грамматики плюс знак окончания и строк, соответствующих каждому состоянию, в котором может находиться анализатор. Каждое состояние соответствует той позиции в порождающем правиле, которой достиг анализатор. Таблица разбора для грамматики
S real IDLIST
IDLIST IDLIST, ID
IDLIST ID
ID A B C D
приведена в табл. 5.1. Драйвер анализатора использует еще и два стека – стек символов и стек состояний. Таблица разбора включает элементы четырех типов.
Элементы сдвига. Эти элементы имеют вид S7 и означают: поместить в стек символ, соответствующий столбцу; поместить в стек состояний 7 и перейти к состоянию 7; если входной символ – терминал, принять его.
Элемент приведения. Он имеет вид R4 и означает: выполнить приведение с помощью правила 4), т.е., допустив, что n есть число символов в правой части правила 4), удалить n элементов из стека символов и n элементов из стека состояний и перейти к состоянию, указанному в верхней части стека состояний. Нетерминал в левой части правила (4) нужно считать следующим входным символом.
Элемент ошибок. Эти элементы являются пробелами в таблице и соответствуют синтаксическим ошибкам.
Элемент остановки. Им завершается разбор.
Таблица 5.1.
Состояние |
S |
IDLIST |
ID |
real |
«,» |
A B C D |
|
1 2 3 4 5 6 7 |
HALT |
S5 |
S4 |
S2 |
R4 R3 S6
R2 |
S3
S3
|
R4 R3 R1
R2 |
Рассмотрим, как с помощью вышеописанной таблицы разбирается строка:
real A, B, C
|
Стек символов |
|
Стек состояний |
real A, B, C |
|
|
1 |
входной символ real – из элемента таблицы (1, real), сдвиг в состояние 2;
real A, B, C |
real |
|
2 1 |
входной символ А – сдвиг в состояние 3;
real A, B, C |
А real |
|
3 2 1 |
входной символ – «,», приведение по правилу (4);
real A, B, C |
real |
|
2 1 |
входной символ – ID, сдвиг в состояние 4;
real A, B, C |
ID real |
|
4 2 1 |
входной символ – «,», приведение по правилу (3);
real A, B, C |
real |
|
2 1 |
входной символ – IDLIST, сдвиг в состояние 5;
real A, B, C |
IDLIST real |
|
5 2 1 |
входной символ – «,», сдвиг в состояние 6;
real A, B, C |
, IDLIST real |
|
6 5 2 1 |
входной символ – В, сдвиг в состояние 3;
real A, B, C |
В , IDLIST real |
|
3 6 5 2 1 |
входной символ – «,», приведение по правилу (4);
real A, B, C |
, IDLIST real |
|
6 5 2 1 |
входной символ – ID, сдвиг в состояние 7;
real A, B, C |
ID , IDLIST real |
|
7 6 5 2 1 |
входной символ – «,», приведение по правилу (2);
real A, B, C |
real |
|
2 1 |
входной символ – IDLIST, сдвиг в состояние 5;
real A, B, C |
IDLIST real |
|
5 2 1 |
входной символ – «,», сдвиг в состояние 6;
real A, B, C |
, IDLIST real |
|
6 5 2 1 |
входной символ – С, сдвиг в состояние 3;
real A, B, C |
С , IDLIST real |
|
3 6 5 2 1 |
входной символ – «», приведение по правилу (4);
real A, B, C |
, IDLIST real |
|
6 5 2 1 |
входной символ – ID, сдвиг в состояние 7;
real A, B, C |
ID , IDLIST real |
|
7 6 5 2 1 |
входной символ – «», приведение по правилу (2);
real A, B, C |
real |
|
2 1 |
входной символ – IDLIST, сдвиг в состояние 5;
real A, B, C |
IDLIST real |
|
5 2 1 |
входной символ – «», приведение по правилу (1);
real A, B, C |
|
|
1 |
входной символ – S, поэтому HALT (ОСТАНОВ).
Разбор завершен успешно.
Заметим, что после сдвига входным символом является следующий символ, а после приведения – символ, к которому только что привело действие.