- •2 Канонических случая грамматического разбора:
- •Недетерминированный конечный автомат (разбор сверху-вниз)
- •Нормальная форма Грейбах
- •Ll(1) анализ
- •Построение детерминированных анализаторов (разбор снизу-вверх) Грамматики простого предшествования (гпп)
- •Операторное предшествование оп
- •Lr(k)-грамматики
Операторное предшествование оп
A →…UV.. по аналогии с НФГ.
Отношение предшествования
Задается только для 2х терминальных символов
< о , = о , о >
_|_ < о a
a о > _|_
Мы не можем воспроизвести здесь цепочные сворачивания. Чтобы ликвидировать эту проблему, придумано, что все нетерминальные символы, помещаемые в стек являются неразличимыми. Поэтому не нужно делать цепочных сворачиваний. Явные сворачивания будем применять к тем правым частям, которые содержат хотя бы один терминальный символ.
a= о b V→…ab… или V→…aWb…
a< о b V→…aU… U=>+b… или U=>+Wb… (first*)(firstterm)
a о > b V→…Ub… U=>+…a или U=>+…aW (last*)(lastterm)
Пример
S→S+T|T
T→T*F|F
F→(S)|a
|
+ |
* |
( |
) |
a |
+ |
о > |
< о |
< о |
о > |
< о |
* |
о > |
c |
< о |
о > |
< о |
( |
< о |
< о |
< о |
= о |
< о |
) |
о > |
о > |
|
о > |
|
a |
о > |
о > |
|
о > |
|
Преимущества: трудоемкость не превышает 2n, более компактное дерево; недостатки: охват класса грамматик менее мощный, чем у других методов. Из-за обезличивания нетерминальных символов. Мы в итоге используем более широкий язык, чем заданный.
Lr(k)-грамматики
Будут производиться перенос и свертка.
На каждом шаге анализируется не более чем k терминальных символов. И столько верхних символов, сколько необходимо для обеспечения однозначности действия анализатора. Минимальное разумное значение k=1.
Простейший анализатор такого типа: LR(1).
Этот метод наиболее мощный из всех рассмотренных.
Метод очень громоздок, так что рассмотрим на примере простейшей грамматики:
Пример
S→S+T|T
T→T*F|F
F→(S)|a
_|_, выход: _|_
← - перенос
Иногда необходимо будет анализировать по 2 верхних символа (обычно это бывает, если верхний символ - нетерминальный, если терминальный – достаточно одного).
|
+ |
* |
( |
) |
a |
_|_ |
_|_S |
← |
|
|
|
|
допуск |
( S |
← |
|
|
← |
|
|
_|_ T |
S→T |
← |
|
|
|
S→T |
( T |
S→T |
← |
|
S→T |
|
|
+ T |
S→S+T |
← |
|
S→S+T |
|
S→S+T |
_|_ F |
T→F |
T→F |
|
|
|
T→F |
( F |
T→F |
T→F |
|
T→F |
|
|
+ F |
T→F |
T→F |
|
T→F |
|
T→F |
* F |
T→T*F |
T→T*F |
|
T→T*F |
|
T→T*F |
+ |
|
|
← |
|
← |
|
* |
|
|
← |
|
← |
|
( |
|
|
← |
|
← |
|
) |
F→(S) |
F→(S) |
|
F→(S) |
|
F→(S) |
a |
F→a |
F→a |
|
F→a |
|
F→a |
_|_ |
|
|
← |
|
← |
|
Трудоемкость в худшем случае mn (число нетерминальных символов * длину входной цепочки)