- •4.Восходящие методы обработки языков
- •41. Неформальное описание восходящего анализа
- •4.2.1.Определение lr(к)-грамматики
- •4.2.2. Алгоритм разбора для lr(k)-грамматики
- •4.2.3.Алгоритм построения управляющей таблицы для lr(0)-грамматики без -правил
- •4.2.4.Алгоритм построения управляющей таблицы для slr(1)-грамматики без -правил
- •4.2.5.Включение -правилв lr(0)-иSlr (1)-грамматики
4.Восходящие методы обработки языков
41. Неформальное описание восходящего анализа
П
S
(AS)
S
b
A
(SaA)
A
a Рис.4.1
Рассмотрим КС-грамматику G1, правила вывода которой приведены на рис 4.1. Это однозначная грамматика, поэтому каждая выводимая цепочка имеет единственное дерево вывода и единственный правый вывод.
Например, правый вывод цепочки ((baa)b) имеет вид:
S r (AS) r (Ab) r ((SaA)b) r ((Saa)b) r ((baa)b)
Заметим, что на каждом шаге вывода подчеркнутый нетерминал заменяется правой частью правила, номер которого записан над знаком отношения непосредственного вывода.
Для получения разбора этой цепочки восходящим способом будем просматривать входную цепочку слева направо, отыскивая самую левую подцепочку, совпадающую с правой частью какого-либо правила вывода грамматики, после чего свернем найденную подцепочку к нетерминалу из левой части соответствующего правила. Эти действия будем повторять до тех пор, пока входная цепочка не свернется к начальному символу грамматики. Обозначив отношение непосредственной свертки через , получим следующую последовательность сверток для цепочки ((baa)b):
((baa)b) ((Saa)b ((SaA)b) (Ab) S ,
в которой каждое вхождение правой части используемого правила подчеркнуто. Очевидно, что получился правый разбор цепочки, являющийся обращением ее правого вывода.
В терминах деревьев восходящий анализ заключается в последовательном построении частичных деревьев из листьев и частичных деревьев, построенных на более ранних шагах. На рис. 4.2 приведена последовательность частичных деревьев, которые получаются при восходящем анализецепочки ((baa)b).
Заметим, что свертку не всегда можно выполнить единственным cпособом. Например, в грамматике G2 (рис. 4.3) при восходящем анализе цепочки acbb символ c можно свернуть к символу S (правило (2)) или к символу В (правило (6)).
a)
б)
S
S A
(
( b a a ) b ) ( ( b a a
) b )
д)
S
в)
г)
A
A S A S
S
A S A
S A
( ( b a a ) b )
( ( b a a ) b ) ( ( b a
a ) b )
Рис. 4.2
Для того чтобы восходящий анализ был детерминированным, грамматика, порождающая входной язык, должна удовлетворять определенным требованиям.
Б
S
aAb
S
c
A
bS
A
Bb
B
aA
B
c Рис. 4.3
Определение.
Пусть S r* Aw r w r* xw – правый вывод в КС-грамматике G = < T, N, S, R >. Тогда вхождение в цепочку w называется основой цепочки w, а правило A – основывающим правилом этой цепочки:.
Таким образом, основывающее правило цепочки - это последнее правило, примененное в правом выводе цепочки, а основа цепочки - вхождение правой части этого правила в цепочку. Если грамматика однозначна, у цепочки может быть не более одного правого вывода, а следовательно, не более одной основы и одного основывающего правила.
Детерминированный восходящий анализ, базирующийся на поиске основы, можно реализовать с помощью расширенного ДМП-преобразователя, входная лента которого имеет концевой маркер.
При построении расширенного ДМП-преобразователя реализующего восходящий метод синтаксического анализа, возникает проблема получения преобразователем дополнительной информации для выделения основы. Существующие алгоритмы восходящего анализа по-разному решают эту задачу. Алгоритм синтаксического анализа для LR(k)-грамматик использует специальный магазинный алфавит и k первых символов непросмотренной части входной цепочки, а алгоритм анализа типа “перенос – свертка”, предназначенный для грамматик предшествования, использует символы, расположенные ниже символа из верхушки магазина.
4.2. LR (К)-грамматики