ВУЗ:
Составители:
Рубрика:
32
Функция свертки зависит от верхней части стека, включающей основу и еще одного символа ниже
нее. Оставшаяся необработанная часть входной цепочки на свертку не влияет.
Грамматика операторного предшествования – это приведенная контекстно-свободная грамматика
без е-правил, в которой правые части правил не содержат смежных нетерминалов. Операторная грамматика
является грамматикой операторного предшествования, если между любыми двумя терминальными символа-
ми выполняется не более одного отношения предшествования. Для грамматик операторного предшествова-
ния отношения задаются на множестве терминалов плюс маркер начала (конца), игнорируя нетерминалы.
Рассмотрим отношения:
a=• b,если есть правило A→…ab… или A→…aBb…
a
<•
b,если есть правило A
→
…aB и B
→
b… или B
→
Cb…
a •> b,если есть правило A→…Bb… и B→…a или B→…aC
$ <• a,если есть правило S→Ca… или S→a…
a
•>
$,если есть правило S
→
…aC или S
→
…a
Пример: рассмотрим грамматику арифметических формул
S
→
S+T|T
T→T*E|E
E→(S) | a
Управляющая таблица имеет следующий вид:
(a*+)$
) •> •> •> •>
a
•> •> •> •>
* <• <• •> •> •> •>
+
<• <• •> •> •> •>
( <• <• <• <• =•
$
<• <• <• <•
Алгоритм разбора цепочки по управляющей таблице аналогичен предыдущему.
Отыскивая самую левую основу, распознаватель для грамматики операторного предшествования не
обращает внимания на нетерминалы приводимой основы. Нетерминалы могут учитываться только семанти-
ческими подпрограммами. Поэтому правила, содержащие только нетерминалы в правых частях, можно не
включать в таблицу правил.
4.3. СОДЕРЖАНИЕ ЗАДАНИЯ
Сначала необходимо составить грамматику для заданного языка и получить управляющую таблицу.
Затем, используя описанные выше алгоритмы разбора, разработать программу синтаксического анализа
предложений заданного языка. Программа – распознаватель должна работать в режиме интерпретации одно-
го предложения. Цель программы – идентификация правильных предложений языка и диагностика ошибок.
