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

В приводимом ниже примере будем считать, что в качестве идентификатора в языке, порожденном грамматикой G₁, может использоваться любая строчная буква латинского алфавита. Каждая такая буква воспринимается распознавателем как идентификатор (И).

ПримерИспользуя распознаватель для грамматики с операторным предшествованием, таблицу порождающих правил и семантических подпрограмм (табл. 4), а также матрицу операторного предшествования (табл. 3), перевести в обратную польскую запись выражение

Решение показано в табл. 5. В соответствии с алгоритмом распознавателя для грамматики с операторным предшествованием, описанным в предыдущем пункте, символы входной строки переписываются в стек распознавателя до тех пор, пока между верхним терминальным символом в стеке и очередным терминальным символом входной строки не появится отношение •>. В этот момент в стеке выделяется первичная фраза, заключенная между отношениями  <• и •>, по таблице порождающих правил отыскивается  правило,  правая часть которого совпадает с первичной фразой с точностью до нетерминальных символов, затем выполняется редукция и, если нужно, семантическая подпрограмма.

Требуемая обратная польская запись исходного выражения получается, если прочитать записи в выходную строку сверху вниз:

Таблица 5:

Перевод в обратную польскую запись

методом операторного предшествования

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

                     (9)

П

Заметим, что «сокращенный» разбор содержит 7 элементов, считая исходное выражение и начальный символ грамматики П, в то время как полный разбор содержал бы еще три дополнительных элемента за счет применения правил вида TM и BT.

Обратная польская запись в этом примере получается за 10 шагов, но, если исключить 3 шага, которые служат только для выделения идентификаторов, останется лишь 7 шагов. Напомним, что метод предшествования решает эту задачу за 12 шагов (если не считать шагов, выделяющих идентификаторы), а метод стека с приоритетами — за 6 шагов, следовательно, по числу шагов метод операторного  предшествования  эффективнее  общего метода предшествования и почти столь же эффективен, как и метод, основанный на стеке с приоритетами.