Реферат: Проектирование трансляторов

Sj следует за Si.

Отношения <, =, > назовем отношениями предшествования. Отно-

шения предшествования обычно записываются в виде матрицы, стол-

бцы и строки которой соответствуют символам словаря V. На пересе-

чении i-ой строки и j-го столбца записывается отношение предшес-

твования между символами Si и Sj. Элементами матрицы являются

знаки <, =, > или пусто. Последний случай означает, что символы

Si и Sj ни в одной строке языка не могут стоять рядом.

В дальнейшем будет введено формальное определение отношений

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

Сейчас же мы рассмотрим алгоритм анализа программы, разрабо-

танный Виртом и Вебером.

Достоинство этого алгоритма заключается в том, что он сни-

мает дополнительное ограничение на грамматику языка, и допускает,

чтобы в правилах грамматики два нетерминальных символа стояли ря-

дом. Но и в этом алгоритме требуется, чтобы между каждой парой

символов языка существовало не более одного отношения предшество-

вания и в множестве синтаксических правил не было двух одинако-

вых правых частей, т.е. правил, у которых правые части одинаковы,

а левые - разные.

Алгоритм основан на каноническом свертывании, т.е. на выде-

лении самой левой свертываемой части строки. Блок-схема алгорит-

ма показана на рис. 1 (@ - символ начального (конечного) ограни-

чителя входного анализируемого текста; не входит в алфавит языка).

┌────────────────────────────────┐

│ ^

┌─────┴───┬─┐ │

┌───────┬─┐ │ i:=i+1 │2│ │

│ i:=1 │1│ │ └─┤ │