- •Предисловие
- •Глава 1 введение в проблематику конструирования компиляторов
- •1.1. Понятие компилятора и его структура
- •1.2. Применение компиляторов и задачи их разработки
- •Глава 2 способы задания формальных языков
- •2.1. Математический аппарат теории
- •Формальных языков, перевода и компиляции
- •1) AR*a для всех aÎa;
- •2.2 Цепочки и языки
- •2.3 Грамматики
- •2.4. Распознаватели
- •2.5 Регулярные выражения и синтаксические диаграммы
- •2.6. Автоматы с магазинной памятью (мп - автоматы )
- •2.7. Соответствия между способами описания языков
- •Глава 3 основы теории перевода
- •3.1. Определение перевода
- •3.2. Модели простейших трансляторов
- •3.2.1. Конечные преобразователи
- •3.2.2. Преобразователи с магазинной памятью
- •Глава 4 конструирование сканеров
- •4.1. Общая характеристика процесса сканирования
- •4.2. Описание лексем в языке расширенных регулярных выражений
- •4.3. Построение недетерминированного конечного автомата по расширенному регулярному выражению
- •4.4. Преобразование недетерминированного конечного автомата в детерминированный
- •Замечание. Среди состояний могут оказаться недостижимые состояния . Состояние р называется достижимым , если существует такая цепочка w , что (q0, w) *(p , e ). ¨
- •4.5. Преобразование синтаксической диаграммы в конечный автомат
- •4.6. Представление результатов сканирования
- •4.7. Методики конструирования сканеров
- •Глава 5 конструирование однопроходных нисходящих анализаторов
- •5.1. Определение синтаксического разбора
- •5.2. Нисходящий и восходящий разборы
- •5.3. Ll(k) - грамматики
- •5.4. Предсказывающие алгоритмы разбора
- •5.5. Алгоритмы построения управляющих таблиц для левых анализаторов
- •5.6. Приведение грамматик к ll - форме
- •Глава 6 основы генерации кода
- •6.1. Перевод и генерация кода
- •6.2. Представления промежуточной программы
- •6.3. Преобразование промежуточной программы в ассемблерный код
4.4. Преобразование недетерминированного конечного автомата в детерминированный
В примерах, рассмотренных в предыдущем разделе , мы везде получали детерминированные КА, распознающие соответствующие лексемы, заданные расширенными регулярными выражениями. Работу детерминированного КА легко моделировать программно. Однако для многих реальных лексем соответствующие КА оказываются недетерминированными (НКА), что вызывает затруднение при программной реализации НКА. Выход из этой ситуации подсказывает сама теория автоматов, в которой доказывается, что для НКА М, распознающего язык L=L(M), существует КА распознающий тот же самый язык L=L(M), т.е. L(M)=L( ).
В практическом смысле наиболее важным является сам метод преобразования НКА в КА. Приведём его описание.
Пусть M= (Q , å ,d , q0 , F) . Преобразуем его в
=( ,å , , , ) следующим образом :
1. =Â(Q) - это означает , что состояниями автомата являются множества состояний автомата М ;
2. = {q0};
3. – состоит из всех таких подмножеств s множества Q , что sÇF¹Æ ;
4. (S,a)= для всех SÍQ, где ={P|d(q,a) содержит Р для некоторого qÎS }.
Замечание. Среди состояний могут оказаться недостижимые состояния . Состояние р называется достижимым , если существует такая цепочка w , что (q0, w) *(p , e ). ¨
Для автомата, заданного графом, это означает, что для достижимого состояния р существует путь, ведущий из q0 в р, а для недостижимого не существует. Недостижимые состояния можно исключить из множества состояний автомата .
Пример.4.7. Пусть НКА М задана таблицей переходов и множество F={qf}.
Таблица 4.1
Состояние |
|
Вход |
|
|
1 |
2 |
3 |
q0 |
{q0 , q1} |
{q0 , q2} |
{q0 , q3} |
q1 |
{q1 , qf} |
{q1} |
{q1} |
q2 |
{q2 } |
{q2 , qf } |
{q2} |
q3 |
{q3} |
{q3} |
{q3 , qf} |
qf |
Æ |
Æ |
Æ |
1. Построим КА =( , {1 , 2 , 3} , , {q0} , ) , допускающий язык L(M) . Так как М имеет 5 состояний , то по п.1 должен иметь 32 состояния . Однако не все они достижимы . Мы будем включать в таблицу переходов автомата только достижимые состояния .
2. По п.2 .= {q0}, обозначим его через А={q0}= .
3. По п.4 для состояния А={q0} имеем :
({q0},1)={q0 , q1}= B
({q0},2)={q0 , q2}= C
({q0},3)={q0 , q3}= D
4. Вновь применяем п.4 к полученным состояниям В , С , D и получаем :
({q0 , q1 },1)={q0 , q1 , qf }= E
({q0 , q1 },2)={q0 , q1 , q2 }= F
({q0 , q1 },3)={q0 , q1 , q3 }= G
({q0 , q2},1)={q0 , q1 , q2 }=F
({q0 , q2},2)={q0 , q2 , qf }=H
({q0 , q2},3)={q0 , q2 , q3 }=I
({q0 , q3},1)={q0 , q1 , q3 }=G
({q0 , q3},2)={q0 , q2 , q3 }=I
({q0 , q3},3)={q0 , q3 , qf }=J
Продолжая эту процедуру, получим таблицу переходов автомата (табл. 4.2) .
На основании п.3 можно сделать вывод , что в входят те состояния из которые содержат qf , поэтому
={E , H , J , K , M , N , P }.
Примерами недостижимых состояний , которые не вошли в , являются состояния : X={q1 , q2 } и Y={q1 , q2 , qf } .
Таблица 4.2
Состояния |
|
Вход |
|
||
|
1 |
2 |
3 |
||
A={q0} |
B |
C |
D |
||
B={q0 , q1} |
E |
F |
G |
||
C={q0 , q2 } |
F |
H |
I |
||
D={q0 , q3 } |
G |
I |
J |
||
E={q0 , q1 , qf } |
E |
F |
G |
||
F={q0 , q1 , q2 } |
K |
K |
L |
||
G={q0 , q1 , q3 } |
M |
L |
M |
||
H={q0 , q2 , qf } |
F |
H |
I |
||
I={q0 , q2 , q3 } |
L |
N |
N |
||
J={q0 , q3 , qf } |
G |
I |
J |
||
K={q0 , q1 , q2 ,qf } |
K |
K |
L |
||
L={q0 , q1 , q2 ,q3 } |
P |
P |
P |
||
M={q0 , q1 , q3 ,qf} |
M |
L |
M |
||
N={q0 , q2 , q3 ,qf } |
L |
N |
N |
||
P={q0 , q1 , q2 ,q3 ,qf } |
P |
P |
P |