ЯЗЫКИ И ГРАММАТИКИ ПРОСТОГО ПРЕДШЕСТВОВАНИЯ

Одна из центральных проблем детерминированного восходящего синтаксического анализа состоит в однозначном определении основы – самой левой подцепочки сентенциальной формы, которую требуется редуцировать на данном этапе разбора. Хотелось бы, “перемещаясь” по цепочке слева направо и рассматривая одновременно только два соседних символа, суметь определить, нашли ли мы хвост основы (конец редуцируемой части). А затем, продвигаясь назад к левому концу найти голову основы, опять таки анализируя лишь два соседних символа. То есть мы сталкиваемся с такой задачей: если задана сентенциальная форма ... x y... (где x, y Î N È S), то всегда ли x – хвост основы, или x и y принадлежат основе, или возможны другие варианты? Для решения этой задачи требуется еще до начала разбора исследовать грамматику языка и принять решения относительно каждой пары символов x и y.

Пусть x, y Î N È S грамматики G. Предположим, что в языке, определяемом G, при выводе цепочки языка существует сентенциальная форма ... x y.... На некотором этапе разбора либо x, либо y, либо оба символа одновременно должны войти в основу. При этом возникают три различных варианта:

1). x – часть основы, а точнее ее хвост, а y в основу не входит. Эту ситуацию мы будем обозначать x ·> y и говорить, что x больше, а, более строго, x предшествует y, так как x редуцируется раньше, чем y. Заметим, что x в этом случае должен быть последним, хвостовым, самым правым символом в правой части некоторого правила грамматики U ®... x (рис. 5.5). Отметим также, что основа располагается слева от y, и следовательно y должен быть терминалом, так как имеет место канонический разбор.

Рис. 5.6

2). Оба символа входят в основу. При этом говорят, что x и y имеют одинаковое отношение предшествования, они редуцируются одновременно и изображают это отношение: x y. Очевидно, что в грамматике при этом имеет место правило U ®... x y... (рис. 5.6).

3). y – часть основы, а точнее ее голова, а x в основу не входит. Эта ситуация обозначается x <· y и можно говорить, что x меньше y или x следует за y. При этом символ y должен быть первым, самым левым в правой части некоторого правила
U ® y... (рис. 5.7).

Если сентенциальной формы ... x y... при выводе цепочек в грамматике G не существует, то мы будем считать что между упорядоченной парой символов (x, y) не определено отношение предшествования (обозначим этот факт как x y).

Заметим, что ни одно из определенных выше отношений не является симметричным: из x y вовсе не следует, что y x, и уж тем более x <· y не свидетельствует о том, что y ·> x.

Поиск по сайту: