Методы трансляции.Грамматика.Распознаватель, страница 2

Если нужно, вызывается семантическая подпрограмма, соответствующая правилу (1), которая обрабатывает строку х, переводя ее на выходной язык. Семантическая подпрограмма учитывает как терминальные, так и нетерминальные символы первичной фразы, поэтому в ней можно предусмотреть возможность устранения неоднозначности разбора.

Затем в стеке строка х заменяется символом , и описанный выше процесс продолжается. Состояние стека и входной строки может быть, например, таким, как показано на рис.2. Буквами S обозначены нетерминальные символы, а буквами t терминальные.

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

Описанный алгоритм реализуется в трансляторе почти так же, как общий алгоритм метода предшествования, но матрица предшествования получается гораздо меньших размеров.

Матрица и функции операторного предшествования

Для отыскания отношений операторного предшествования удобно ввести множество самых левых терминальных символов L_t(U) и множество самых правых терминальных символов R_t(U) относительно нетерминального символа U.

Пусть t - терминальный символ, x, y и z - любые строки, быть может, пустые, С — нетерминальный символ, L(U') - множество самых левых, а K(U') - множество самых правых символов относительно нетерминального символа U', тогда

 (2)

или

. (3)

 (4)

или

 (5)

Формулы (2) и (3) являются определениями множеств L_t и R_t, а эквивалентные формулы (4) и (5) фактически определяют алгоритм отыскания множеств L_t и R_t.

Определения отношений операторного предшествования можно записать так:

1.  (6)

2.  (7)

3.  (8)

Эти формулы удобнее для практического применения.

ПримерНайти матрицу и функции операторного предшествования для грамматики G₁:

ПВ

ВT 

BBT

TTM

МИ

М(В)

Решение Нетерминальные символы грамматики G₁:

П, В, Т, М, а терминальные – , , , И, (,).

Матрицу операторного предшествования можно наши в следующем порядке.

1 Для каждого нетерминального символа U грамматики G₁ отыскиваются множества L_t(U) и R_t(U). Для этого:

1.1. Отыскиваются множества L(U) и R(U)

1.2. Для каждого нетерминального символа U:

а) отыскиваются правила грамматики G₁ с правыми частями вида tzи Ctz. Терминальные символы t фиксируются в качестве элементов множества L_t(U);

б) отыскиваются правила с правыми частями вида zt и ztC. Терминальные символы tфиксируются в качестве элементов множества R_t(U).

В результате получается таблица:

Таблица 1:

Множества L_t(U) и R_t(U) после выполнения

первого шага алгоритма

1.3. Для каждого нетерминального символа U:

а) просматривается множество L(U) и отыскиваются входящие в него нетерминальные символы  Затем множество L_t(U) дополняется символами, входящими в  и не входящими в L_t(U);

б) просматривается множество R(U) и отыскиваются входящие в него нетерминальные символы  Затем множество R_t(U) дополняется символами, входящими в  и не входящими в R_t(U);

В результате получается табл. 2:

Таблица 2:

Множества L_t(U) и R_t(U) (окончательная таблица)

2. Составляется матрица операторного предшествования. Для этого просматриваются правые части порождающих правил грамматики G₁.

2.1. По правилу (6) определяются отношения

2.2. По правилу (7) с использованием табл. 2 определяются отношения <·.