- •Предисловие
- •Глава 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.5. Преобразование синтаксической диаграммы в конечный автомат
КА распознающий лексемы определенных типов (идентификаторы, константы и др.), можно получить используя соответствия между регулярными выражениями (регулярными определениями ) , синтаксическими диаграммами, регулярными грамматиками и КА . Для этого надо использовать соответствующии цепочки преобразований. Рассмотрим правила этих преобразований на конкретном примере .
Пример 4.8. Пусть задано регулярное определение , описывающее вещественные константы, приведенное в примере 4.6, п.5. Синтаксис , задаваемый этим определением, можно задать и при помощи синтаксической диаграммы , показанной на рис.4.3, где Ц - терминальный символ ЦÎ{0,1,...,9}.
Рис .4.3
Легко проверить , что и регулярное определение и синтаксическая диаграмма задают один и тот же язык - множество цепочек , соответствующих различным формам записи вещественных констант.
Рассмотрим теперь следующие преобразования .
Преобразование : синтаксическая диаграмма ® регулярная грамматика.
Для выполнения такого преобразования надо разметить синтаксическую диаграмму нетерминальными символами , используя следующие правила :
вершина синтаксической диаграммы помечается начальным символом грамматики S ;
между двумя подряд идущими терминальными символами вставляется нетерминальный символ AÎ N ;
перед альтернативой (разветвлением на несколько ветвей) ставиться только один нетерминальный символ AÎN ;
перед выходящими ветвями итерации (цикла ) ставится один нетерминальный символ .
В данном примере размеченная по этим правилам синтаксическая диаграмма будет иметь следующий вид, показанный на рис.4.4 .
Далее следует записать правила грамматики для каждого нетерминального символа. Все правила должны иметь вид : A® aB или A® a, где A , B Î N , a Î S È {e} (регулярная грамматика ) . При задании условий следует пользоваться следующими правилами :
1. Если два нетерминала А и В связаны одной ветвью направленной от А к В и содержащей терминал а, то правило имеет вид А ® аВ.
Рис. 4.4
2. Если два нетерминала А и В связаны несколькими ветвями, направленными от А к В и содержащими терминалы a,b,..c, то правило имеет вид А® аВ½bB½...½cB.
3. Если среди ветвей, связывающих нетерминалы А и В, содержится пустая (не содержащая терминалов) ветвь и имеется ветвь, связывающая В и С, содержащая терминал а , тогда правило имеет вид А® аС , то есть нетерминал В пропускается .
Применяя эти приемы к размеченной синтаксической диаграмме, показанной на рис. 4.4, получим следующую регулярную грамматику G:
-
S ® +A ½ . A ½цC
A ® .B ½öC
B ® цD
C ® цC ½. D ½ EF
D ® цD ½ EF ½ e
F ® +I ½ -I ½ цJ
I ® цJ
J ® цJ ½ e
Преобразование : регулярная грамматика ® КА
Преобразуем множество правил Р грамматики G в КА по следующим правилам :
множество нетерминалов грамматики G становится множеством символов состояний автомата M, т.е. Q = N;
начальный символ S грамматики G становится символом начального состояния автомата М ;
для каждого правила (А® аВ)ÎР грамматики G будем писать d(А,а)=В , где d - функция переходов автомата М ;
символами заключительных состояний автомата М становятся нетерминалы А , входящие в правила вида А® е , т.е.
F = {A / (A®e) Î P}.
В нашем примере Q = {S , A , B , C , D , F , I , J} , запишем функцию переходов автомата М :
d (S , +) = {A} , d (C , . ) = {D} , d (J , ц) = {J} ,
d (S , - ) = {A} , d (C , E) = {F} ,
d (S , . ) = {B} , d (D , ц) = {D} ,
d (S , ц) = {C} , d (D , E) = {F} ,
d (A , . ) = {B} , d (F , +) = {I} ,
d (A , ц) = {C} , d (F , - ) = {I} ,
d (B , ц) = {D} , d (F , ц) = {J} ,
d (C , ц) = {C} , d (I , ц) = {J} ,
Множеством заключительных состояний является множество {D , J} ( так как (D® e), (J® e)ÎP).
Функция переходов автомата М представлена в виде графа переходов, (рис.4.2)
Рис. 4.2
Таким образом , мы получим тот же самый автомат М , что и в примере 4.6 .
Замечание : Если в множестве правил Р содержатся правила вида В® b , BÎN , bÎS , то :
Q = N È {выход};
d (B , b) = {выход} для всех BÎN и bÎS ;
F ={A / (A® e)ÎP} È {выход}.
Другими словами, к множеству состояний автомата М добавляется еще одно состояние - заключительное «выход» (придумайте соответствующую этому случаю синтаксическую диаграмму и преобразуйте ее в автомат в качестве упражнения ). ¨