Курсовая Лексический анализатор. Краткий курс лекций. Курс лекций по спецкурсу Методы трансляции

• Название: Курс лекций по спецкурсу Методы трансляции
• Анкор: Курсовая Лексический анализатор
• Дата: 29.12.2019
• Размер: 0.64 Mb.
• Имя файла: Краткий курс лекций.doc
• Тип: Курс лекций; #102547
• страница: 7 из 19

Вывод отношений в грамматиках с простым предшествованием

Отношения предшествования можно найти, непосредственно пользуясь определениями. Однако для сложных грамматик это сделать достаточно трудно (нужно не только найти отношения, но и показать отсутствие других отношений). Поэтому используют специальные методы определения отношений.

Для определения отношений предшествования предварительно для каждого нетерминального символа U находятся два множества:

L(U) – множество самых левых символов в разложениях U, т.е. множество таких символов q, что существует вывод Uqz;

R(U) – множество самых правых символов в разложениях U, т.е. множество таких символов p, что существует вывод Uzp.

Построение множеств L(U), R(U) состоит из следующих шагов:

1. 
   для каждого правила вида U → z в L(U) заносится самый левый символ правой части, в R(U) – самый правый символ;
   
2. 
   если L(U) содержит нетерминальные символы U₁, U₂, ..., то L(U) дополняется символами, входящими в L(U₁), L(U₂) ... и не входящими в L(U). Аналогично дополняется R(U);
   
3. 
   шаг 2 повторяется, пока L(U), R(U) не перестанут изменяться.
   

Пример:

Z → bMb Грамматика определяет цепочки символов

M → (N | a bab, b(aa)b, b((aa)a)b, b(((aa)a)a)b и т.д.

N → Ma)

Построение множеств левых и правых символов для нетерминалов:

L(U), R(U) после первого шага окончательно

U	L(U)	R(U)		U	L(U)	R(U)
Z	b	b		Z	b	b
M	(, a	N, a		M	(, a	N, a, )
N	M	)		N	M, (, a	)