Переход от праволинейной грамматики к автоматной

Детерминированному

Переход от недетерминированного распознающего автомата к

Лексический анализ

Основные функции компилятора.

1. Лексический анализ - приведение к некоторому стандартному виду ;

2. Синтаксический анализ - грамматический разбор ;

3. Семантический анализ - смысловой анализ;

4. Генерация выходного текста.

Лексический анализ выявляет лексемы - словарные единицы.

Основные функции лексического анализа:

1. выделение служебных слов языка (begin, while, for, …);

2. обработка численных констант;

3. выделение идентификаторов;

4. выделение сложных символов ( := <=);

5. внесение исправлений;

6. устранение различий устройств ввода;

7. устранение особенностей использования алфавитов, кодов.

Состояния автомата и совокупности состояний, в который автомат переходит, объявляются множествами. Каждое из этих множеств становится состоянием нового детерминированного автомата. Переход из состояния, содержащего множество элементов, будет в состояние-множесто, составленное из всех состояний, в которые в исходном автомате осуществлялись переходы. Заметим, что пустые клеточки дают состояние - пустое множество.

A ® aB | bB | aC

B ® bC | b

C ® a

B

a,b b

A b F

a a

C

Праволинейная грамматика - грамматика с правилами вида:

A ® a

A ® aВ

где A, B Î V_N , aÎ V^*_T

То есть это такая КС-грамматика, где вначале идет любое количество терминальных символов, а в конце возможен один нетерминальный символ

Пример:

Дана праволинейная грамматика:

1. S®aA

2. S®bc

3. S®A

4. A®abbS

5. A®cA

6. A®E

Правила 2, 3, 4 – нарушают требования к автоматным грамматикам.

Их можно последовательно заменить совокупностями автоматных правил.

2a S ® b<cE>

2b <cE> ® cE правило 2.

2c E ® e .

3b S ® cA правило 3

3c S ® e