Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 41 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

43
таточно полно описать синтаксическую структуру реальных языков програм-
мирования; с другой стороны, для разных подклассов УКС-грамматик сущест-
вуют достаточно эффективные алгоритмы разбора. Один из таких подклассов –
грамматики предшествования, распознаватели для которых строятся на основе
алгоритма «сдвиг-свертка».
Грамматики предшествования
Принцип организации распознавателя входных цепочек языка, заданного
грамматикой предшествования, основывается на том, что для каждой упорядо-
ченной пары символов в грамматике устанавливается некоторое отношение, на-
зываемое отношением предшествования. В процессе разбора входной цепочки
сравнивается текущий символ входной цепочки с одним из символов, находя-
щихся на верхушке стека. В процессе сравнения проверяется, какое из возмож-
ных отношений предшествования существует между этими двумя символами.
В зависимости от найденного отношения выполняется либо сдвиг (перенос),
либо свертка. При отсутствии отношения предшествования между символами
алгоритм сигнализирует об ошибке.
Задача заключается в том, чтобы иметь возможность непротиворечивым
образом определить отношения предшествования между символами граммати-
ки. Если это возможно, то грамматика может быть отнесена к одному из клас-
сов грамматик предшествования.
Существует несколько видов грамматик предшествования. Они различа-
ются по тому, какие отношения предшествования в них определены и между
какими типами символов (терминальными или нетерминальными) могут быть
установлены эти отношения. Кроме того, возможны незначительные модифи-
кации функционирования самого алгоритма «сдвиг-свертка» в распознавателях
для таких грамматик (в основном на этапе выбора правила для выполнения
свертки, когда возможны неоднозначности).
Выделяют следующие виды грамматик предшествования:
1. простого предшествования;
2. расширенного предшествования;
3. слабого предшествования;
4. смешанной стратегии предшествования;
5. операторного предшествования.
Рассмотрим два наиболее простых и распространенных типа – грамматики
простого и операторного предшествования.
Грамматики простого предшествования
Грамматикой простого предшествования называют такую приведенную
(без циклов, бесплодных и недостижимых символов и λ-правил) КС-
грамматику G(VN,VT,P,S), V = VT∪VN, в которой:
1. Для каждой упорядоченной пары терминальных и нетерминальных симво-
лов выполняется не более, чем одно из трех отношений предшествования:
− В
i
=• В
j
(∀ B
i
, B
j
∈ V), если и только если ∃ правило A→xB
i
B
j
y ∈ P, где
A∈VN, x,y∈V*;

Страницы