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

T ::= T*P

P ::= (E)

P ::= I

ЛЕКЦИЯ 3

АНАЛИЗ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ

С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ

Будем рассматривать каноническое свертывание контекстно-сво-

бодных (КС) языков. Нахождение эффективных методов свертывания -

одна из важнейших задач в теории построения трансляторов. В рас-

сматриваемых алгоритмах анализа входного текста, написанного на

КС-языке, используются отношения предшествования между каждой па-

рой соседних символов строки.

Рассмотрим подробнее отношения предшествования: пусть Si и

Sj - символы языка L (Si,Sj С V). Если в некоторой строке языка

они могут быть записаны рядом (...SiSj...), то между ними могут

существовать только три отношения.

1. В строке ...SiSj... свертываемая часть строки начинается

└──┘

с символа Sj, то есть Sj - самый левый символ свертываемой под-

строки. Если при этом Si не является последним символом другой

строки свертываемой подстроки, то будем говорить, что Si предшес-

твует Sj. Запишем это условие в виде Si < Sj.

2. В строке ...SiSj... символы Si и Sj входят в одну и ту

└────┘

же свертываемую часть строки.Этот факт запишем в виде Si = Sj и

будем говорить, что Si и Sj входят в одно и то же свертывание.

3. В строке ...SiSj... свертываемая часть строки кончается

└──┘

символом Si, то есть Si - самый правый символ свертываемой части