Информатика и выч. техника \ Информационно-безопасные системы

Информационно-безопасные системы. Анализ проблемы: Учебное пособие, страница 35

4.  ВЬ1БОР(<А>®a) = ПЕРВ(а) U СЛЕД(<А>), где а аннулирующая.

Определение 8.5: КС-грамматика называется LL(1)-грамматикой тогда и только тогда, когда множества выбора правил с одинаковой левой частью не пересекаются.

Первым шагом при построении синтаксического блока является определение мно­жеств выбора для каждого правила грамматики.

Для грамматики (см. рис. 8.6) множества выбора для каждого правила показаны на рис.8.7.

ВЫБОР(1) = ВЬ1БОР(<P>®...) - { BEGIN }

ВЫБОР(2) = ВЫБОР(<L>®...) = ПEPB(<S>;<L>) = { ИДЕНТ, IF, WHILE }

ВЫБОР(З) = ВЫБОР(<L>®...) = СЛЕД( <L> ) = { END, ENDIF, ENDWHILE )

ВЫБОР(4) = BЫБOP(<S>®...) - ( ИДЕНТ }

ВЫБОР(5) = ВЫБОР(<S>®...) - { IF }

ВЫБОР(б) = BЫБOP(<S>®...) - { WHILE }

ВЫБОР(7) = ВЫБОР(<E>®...) = ПЕРВ(<Т>;<E-list>)={ИДЕНТ, КОНСТ, (  }

ВЬ1БОР(8) = BЫБOP(<E-list>®...) = { + }

ВЫБОР(9) = BЫБОP(<E-list>®...) = СЛЕД(<E-list>) =

= { ОТНОШЕНИЕ, ;, THEN, ENDIF, DO, ENDWHILE, END }

ВЫБОР(10) = ВЫБОР(<Т>®...) = ПEPB(<F>;<T-list>) - {ИДЕНТ, КОНСТ, ( }

ВЬ1БОР(11) = BЫБOP(<T-list>®...) = { * }

ВЫБОР(12) = BЫБOP(<T-list>®...) = СЛЕД(<T-list>) =

= { ОТНОШЕНИЕ, ; , THEN, ENDIF, DO, ENDWHILE, END, + (  }

ВЫБОР(13) = ВЬ1БОР(<F>®...) = { ( }

ВЫБОР(14) = BЫБOP(<F>®…) = { ИДЕНТ }

ВЫБОР(15) = ВЫБОР(<F>®...) = { КОНСТ }

ВЫБОР(16) = BЫБOP(<R>®...) = ( ОТНОШЕНИЕ }

Рис.8.7.Множества выбора для грамматики (рис.8.6).

Из рис.8.7 видно, что множества выбора правил с одинаковой левой частью не пересекаются, т.е. данная грамматика является Ц-(1)-грамматикой. Так как некоторые нетерминалы снабжены атрибутами, то эта грамматика является атрибутной.

Атрибутная транслирующая грамматика - это транслирующая грамматика, к кото­рой добавляются следующие определения:

1.  Каждый входной символ, символ действия или нетерминальный символ имеет конечное множество атрибутов.

2.  Все атрибуты нетерминальных символов и символов действия делятся на синте­зируемые и наследуемые.

3.  Правила вычисления наследуемых атрибутов определяются следующим образом:

а) каждому вхождению наследуемого атрибута в правую часть данной продукции сопоставляется правило вычисления этого атрибута как функции некоторых других атрибутов символов, входящих в правую или левую часть данной продукции;

б) задается начальное значение каждого наследуемого атрибута начального символа.

4. Правила вычисления синтезируемых атрибутов определяются так:

а) каждому вхождению синтезируемого нетерминального атрибута в левую часть данной продукции сопоставляется правило вычисления этого атрибута как  функции некоторых других атрибутов символов, входящих в  правую или левую часть данной продукции;

б) каждому синтезируемому атрибуту символа действия сопоставляется правило вычисления этого атрибута как   функции некоторых других   атрибутов этого символа действия.

В нашей грамматике (см. рис. 8.7) все атрибуты   нетерминалов СИНТЕЗИРУЕМЫЕ, кроме следующих:

<E-list>pl, t2

<T-list>p1, t2      p1 - наследуемый t2 - синтезируемый

Все атрибуты символов действия НАСЛЕДУЕМЫЕ.

Литература к разделу 8

1.  Карпов Ю.Г. Основы построения компиляторов (уч.пособие). - Ленинград, 1982.

2.  Серебряков В.А. Лекции по конструированию компиляторов.-ВЦ РАН Москва, 1994.

3.  ЛьюисФ., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов.-М Мир, 1979.

4.  Рейуорд- Смит В.Дж. Теория формальных языков. Вводный курс.-М., 1988.

5.  Хантер Р. Проектирование и конструирование компиляторов.-М.; финансы и статистика, 1984.

9. ОБНАРУЖЕНИЕ НЕСАНКЦИОНИРОВАННЫХ ЗАПИСЕЙ В ПАМЯТИ ЭВМ

В данном разделе рассматривается один из важных вопросов, связанных с защитой информации - обнаружение несанкционированных записей и искажений в памяти ЭВМ. Своевременное обнаружение таких записей и искажений в программах управле­ния техническими системами позволит избежать аварийных ситуаций, которые могут иметь катастрофические последствия не только для обслуживающего персонала, но и для окружающей среды.

Скачать файл