Реферат: Проектирование трансляторов
существовать только три отношения.
1. В строке ...SiSj... свертываемая часть строки начинается
└──┘
с символа Sj, то есть Sj - самый левый символ свертываемой под-
строки. Если при этом Si не является последним символом другой
строки свертываемой подстроки, то будем говорить, что Si предшес-
твует Sj. Запишем это условие в виде Si < Sj.
2. В строке ...SiSj... символы Si и Sj входят в одну и ту
└────┘
же свертываемую часть строки.Этот факт запишем в виде Si = Sj и
будем говорить, что Si и Sj входят в одно и то же свертывание.
3. В строке ...SiSj... свертываемая часть строки кончается
└──┘
символом Si, то есть Si - самый правый символ свертываемой части
строки. Это условие запишем в виде Si > Sj и будем говорить, что
Sj следует за Si.
Отношения <, =, > назовем отношениями предшествования. Отно-
шения предшествования обычно записываются в виде матрицы, стол-
бцы и строки которой соответствуют символам словаря V. На пересе-
чении i-ой строки и j-го столбца записывается отношение предшес-
твования между символами Si и Sj. Элементами матрицы являются
знаки <, =, > или пусто. Последний случай означает, что символы
Si и Sj ни в одной строке языка не могут стоять рядом.
В дальнейшем будет введено формальное определение отношений
предшествования и дан алгоритм их определения.
Сейчас же мы рассмотрим алгоритм анализа программы, разрабо-
танный Виртом и Вебером.
Достоинство этого алгоритма заключается в том, что он сни-
мает дополнительное ограничение на грамматику языка, и допускает,
чтобы в правилах грамматики два нетерминальных символа стояли ря-
дом. Но и в этом алгоритме требуется, чтобы между каждой парой
символов языка существовало не более одного отношения предшество-
вания и в множестве синтаксических правил не было двух одинако-
вых правых частей, т.е. правил, у которых правые части одинаковы,
а левые - разные.
Алгоритм основан на каноническом свертывании, т.е. на выде-
лении самой левой свертываемой части строки. Блок-схема алгорит-
ма показана на рис. 1 (@ - символ начального (конечного) ограни-
чителя входного анализируемого текста; не входит в алфавит языка).
┌────────────────────────────────┐
│ ^
┌─────┴───┬─┐ │
┌───────┬─┐ │ i:=i+1 │2│ │
│ i:=1 │1│ │ └─┤ │
│ └─┤ │ j:=i │ │
│ k:=2 │ │ │ │
│ │ │ R :=L │ │
│ R :=@ │ │ i k │ │
│ i │ │ │ │
└────┬────┘ │ k:=k+1 │ │
│ └────┬──────┘ │
│ │ │
│ ___│___ │
│ / │3\ ┌─────────┬──┐ │
│ / └──\ Да │ Конец │10│ │
│ / R равно @ \─────>┤ работы └──┤ │
│ \ i / │ алгорита │ │
│ \ / └────────────┘ │
│ \_______/ │
│ │ │
│ │ │
└───────────────────>─┤ │
┌───────────────────>─┤ Нет │
│ ___│____ │
│ / │4\ │
│ / └──\ Нет │
│ / R > L \__________________________│
│ \ i k /
│ \ ? /
│ \________/
│ Да│
│ ├<────────────────────┐
│ ____│______ │
│ / │5\ │
│ / └──\ ┌─────┴───┬─┐
│ / R = R \______│ │6│
│ \ j-1 j / Да │ j:=j-1 └─┤
│ \ / │ │
│ \___________/ └───────────┘
│ │Нет
│ ┌────────┴─────┬─┐
│ │ │7│
│ │ U < R ... R└─┤
│ │ j i │
│ └────────┬───────┘
│ │
│ │
│ ┌───────┴─────┬─┐
│ │ │8│
│ │ Переход на └─┤
│ │ семантические │
│ │ подпрограммы │
│ │ │
│ └───────┬───────┘
│ │
│ ┌───────┴────┬─┐
│ │ i:=j │9│
└───────────────┤ R :=u └─┤
│ i │
└──────────────┘
Рис. 1. Блок-схема алгоритма свертывания
В начале анализа строки в верхнюю ячейку магазина записы-
вается первый символ программы, т.е. символ "@" (блок 1).
Затем находится самый правый символ самой левой свертывае-
мой части строки (блок 4). Для этого по матрице предшествования,
которая составляется заранее, проверяют отношения предшествова-
ния между символом, находящимся в верхней ячейке магазина Ri, и
очередным входным символом строки Lk. Если условие Ri > Lk не вы-
полняется, то очередной входной символ записывается в верхушку
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
