Курсовая ТЯП. КР. Теория автоматов и формальных языков
 Скачать 0.99 Mb.
|
|
А read блок 4) 5) блок 12 read write for to while do true false if then else or and not as Ключевое слово Разделитель >= <= <> ) ( , ; : % # $ - * / + > < = ] [ } { /* */ Программа { } описание оператор ; Описание тип идентификатор , Тип % # $ буква цифра Идентификатор буква Оператор составной присвоения условный фиксированного цикла условного цикла ввода вывода Составной оператор : [ ] идентификатор Присваивания as выражение Рисунок 2.2 – Синтаксические правила модельного языка М, лист 2 13 Условный if выражение then оператор else оператор Фиксированного цикла for присваивания to выражение do оператор Условного цикла выражение do оператор while Ввода read ( идентификатор , ) Вывода write ( выражение , ) сумма Выражение < > <> = <= >= Произведение * / and множитель + - or произведение Сумма идентификатор число логическая константа not множитель ( выражение ) Множитель Рисунок 2.2 – Синтаксические правила модельного языка М, лист 3 14 true false Логическая константа действительное целое Число Числовая строка цифра Двоичное 0 1 B b двоичное Целое восьмеричное десятичное шестнадцатиричное Восьмеричное 0 1 О о 2 3 4 5 6 7 D Десятичное цифра d Шестнадцатеричное цифра A B C D E F b c d e f H h цифра a Действительное числовая строка порядок числовая строка числовая строка порядок Порядок E e + - числовая строка Рисунок 2.2 – Синтаксические правила модельного языка М, лист 4 15 Пример 2.4. Программа на модельном языке М, вычисляющая среднее ариф- метическое чисел, введенных с клавиатуры. {% i, k, n, sum; read(n); sum as 0; i as 1; while i<=n do [read(k) : sum as sum + k]; write(sum/n)} 2.2 Общая схема работы распознавателя Определение 2.2. Распознаватель – это специальный алгоритм, который поз- воляет определить принадлежность цепочки символов некоторому языку. Распознаватель схематично можно представить в виде совокупности входной ленты, управляющего устройства и вспомогательной памяти (рисунок 2.3). Входная лента представляет собой последовательность ячеек, каждая из кото- рых содержит один символ некоторого конечного алфавита. Входная головка в каждый момент обозревает одну ячейку. За один шаг рабо- ты распознавателя головка сдвигается на одну ячейку влево (вправо) или остается неподвижной. Распознаватель, не перемещающий входную головку влево, называ- ется односторонним. Управляющее устройство – это программа управления распознавателем. Она задает конечное множество состояний распознавателя и определяет переходы из со- стояния в состояние в зависимости от прочитанного символа входной ленты и со- держимого вспомогательной памяти. Вспомогательная память служит для хранения информации, которая зависит от состояния распознавателя. У некоторых типов распознавателей она может отсут- ствовать. Поведение распознавателя можно представить с помощью его конфигураций. Определение 2.3. Конфигурация распознавателя есть совокупность трех эле- ментов: 16 - состояния управляющего устройства; - содержимого входной ленты и положения входной головки; - содержимого вспомогательной памяти. а 1 а 2 … а n Входная лента Рисунок 2.3 – Схема распознавателя Определение 2.4. Управляющее устройство называется детерминированным, если для каждой конфигурации распознавателя существует не более одного воз- можного следующего шага, в противном случае управляющее устройство называет- ся недетерминированным. Определение 2.5. Конфигурация распознавателя называется начальной, если управляющее устройство находится в заданном начальном состоянии, входная го- ловка обозревает самый левый символ на входной ленте и вспомогательная память имеет заранее установленное начальное содержимое. Определение 2.6. Конфигурация распознавателя называется заключительной, если управляющее устройство находится в одном из заранее выделенных заключи- тельных состояний, а входная головка сошла с правого конца входной ленты. Со- держимое вспомогательной памяти удовлетворяет некоторому заранее установлен- ному условию. Определение 2.7. Входная строка допускается распознавателем, если от начальной конфигурации, в которой цепочка записана на входной ленте, распо- знаватель может выполнить последовательность шагов, заканчивающуюся заключи- тельной конфигурацией. Входная головка Вспомогательная память Управляющее устройство 17 Определение 2.8. Множество всех строк, допускаемых распознавателем, называется языком распознавателя. Классификация распознавателей Для каждого класса грамматик из иерархии Хомского существует класс распо- знавателей, определяющих тот же класс языков. Чем шире класс грамматик, тем сложнее класс соответствующих распознавателей. Для языков типа 0 распознавателями являются машины Тьюринга. Распознаватели КЗ-языков называются линейными ограниченными автомата- ми (машины Тьюринга с конечным объемом ленты). Распознавателями для КС-языков являются автоматы с магазинной памятью (МП-автоматы). Для регулярных языков распознавателями служат конечные автоматы (КА). 2.3 Лексический анализатор программы Определение 2.9. Лексический анализатор (ЛА) – это распознаватель, который группируют символы, составляющие исходную программу, в отдельные минималь- ные единицы текста, несущие смысловую нагрузку – лексемы. Задача лексического анализа - выделить лексемы и преобразовать их к виду, удобному для последующей обработки. ЛА использует регулярные грамматики. ЛА является необязательным этапом трансляции, но желательным по следую- щим причинам: 1) замена идентификаторов, констант, ограничителей и служебных слов лек- семами делает программу более удобной для дальнейшей обработки; 2) ЛА уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии; 3) если будет изменена кодировка в исходном представлении программы, то это отразится только на ЛА. В языках программирования лексемы обычно делятся на классы: 1) служебные слова; 18 2) ограничители; 3) числа; 4) идентификаторы. Каждая лексема представляет собой пару чисел вида (n, k), где n – номер таб- лицы лексем, k - номер лексемы в таблице. Входные данные ЛА - текст транслируемой программы на входном языке. Выходные данные ЛА - файл лексем в числовом представлении. Пример 2.5. Для модельного языка М таблица служебных слов будет иметь вид: 1) read; 2) write; 3) if; 4) then; 5) else; 6) for; 7) to; 8) while; 9) do; 10) true; 11) false; 12) or; 13) and; 14) not; 15) as. Таблица ограничителей содержит: 1) { ; 2) } ; 3) % ; 4) ! ; 5) $ ; 6) , ; 7) ; ; 8) [ ; 9) ] ; 10) : ; 11) ( ; 12) ) ; 13) +; 14) - ; 15) * ; 16) / ; 17) = ; 18) <> ; 19) > ; 20) < ; 21) <= ; 22) >= ; 23) /* ; 24) /* . Таблицы идентификаторов и чисел формируются в ходе лексического анализа. Пример 2.6. Описать результаты работы лексического анализатора для мо- дельного языка М. Входные данные ЛА: { % k, sum; k as 0;… Выходные данные ЛА: (2,1) (2,3) (4,1) (2,6) (4,2) (2,7) (4,1) (1,15) (3,1) (2,7) … Анализ текста проводится путем разбора по регулярным грамматикам и опи- рается на способ разбора по диаграмме состояний, снабженной дополнительными пометками-действиями. В диаграмме состояний с действиями каждая дуга имеет вид, представленный на рисунке 2.4. Смысл этой конструкции: если текущим явля- ется состояние А и очередной входной символ совпадает с i t для какого либо i, то осуществляется переход в новое состояние В, при этом выполняются действия D 1 , D 2 ,…, D m Рисунок 2.4 – Дуга ДС с действиями D 1 , D 2 ,…, D m t 1 , t 2 , …, t n В А 19 Для удобства разбора вводится дополнительное состояние диаграммы ER, по- падание в которое соответствует появлению ошибки в алгоритме разбора. Переход по дуге, не помеченной ни одним символом, осуществляется по любому другому символу, кроме тех, которыми помечены все другие дуги, выходящие из данного со- стояния. Алгоритм 2.1. Разбор цепочек символов по ДС с действиями Шаг 1. Объявляем текущим начальное состояние ДС H. Шаг 2. До тех пор, пока не будет достигнуто состояние ER или конечное со- стояние ДС, считываем очередной символ анализируемой строки и переходим из те- кущего состояния ДС в другое по дуге, помеченной этим символом, выполняя при этом соответствующие действия. Состояние, в которое попадаем, становится теку- щим. ЛА строится в два этапа: 1) построить ДС с действиями для распознавания и формирования внутреннего представления лексем; 2) по ДС с действиями написать программу сканирования текста исходной программы. Пример 2.7. Составим ЛА для модельного языка М. Предварительно введем обозначения для переменных, процедур и функций. Шаг 1. Построим ДС с действиями для распознавания и формирования внут- реннего представления лексем модельного языка М (рисунок 2.5). В диаграмме использованы следующие обозначения. Переменные: 1) СН – очередной входной символ; 2) S - буфер для накапливания символов лексемы; 3) B – переменная для формирования числового значения константы; 4) CS - текущее состояние буфера накопления лексем с возможными значени- ями: Н – начало; I – идентификатор; N2 – двоичное число; N8 – восьмеричное число; N10 – десятичное число; N16 – шестнадцатеричное число; С1, C2, C3 – комментарий; 20 M1 – меньше, меньше или равно, не равно; M2 – больше, больше или равно; P1 – точка; P2 – дробная часть числа; B – символ «B» или «b»; O – символ «O» или «o»; D – символ «D» или «d»; HX – символ «H» или «h»; E11 - символ «E» или «e»; E12, E13, E22 – порядок числа в экспоненциальной форме; ZN, E21 – знак порядка числа в экспоненциальной форме; ОG – ограничитель; V – выход; ER –ошибка; 5) t - таблица лексем анализируемой программы с возможными значениями: TW - таблица служебных слов М-языка, TL – таблица ограничителей М-языка, TI - таблица идентификаторов программы, TN – таблица чисел, используемых в про- грамме; 6) z - номер лексемы в таблице t (если лексемы в таблице нет, то z=0). H ‘ ’ or Перевод строки gc V } out(2,2) I let nill,add,gc let or digit add,gc look(TW) z≠0 + - out(1,z) put(TI),out(4,z) C1 / gc C2 gc * gc C3 * gc / gc out(2,16) M1 < gc > gc,out(2,18) = gc,out(2,21) out(2,20) M2 > gc gc,out(2,22) = out(2,19) ER } AA BB Рисунок 2.5 – Диаграмма состояний с действиями для модельного языка М 21 N2 0..1 add,gc 0..1 B or b add,gc B translate(2), put(TN),out(3,z) N8 add,gc 0..7 O or o gc O N10 add,gc 0..9 2..7 nill, add,gc 8..9 nill, add,gc D or d add,gc N16 add,gc 0..9 or A..F or a..f H or h gc HX digit nill, add, gc let or digit D A..C or F or a..c or f add,gc ER ER E or e add,gc H or h gc H or h gc + or - add,gc add,gc add,gc A..F or a..f nill, add,gc 2..7 8..9 O or o H or h translate(8), put(TN),out(3,z) ER a..f or A..F ER put(TN),out(3,z) let or digit translate(16), put(TN),out(3,z) ZN E12 add,gc digit digit add,gc E13 add,gc digit H or h gc add,gc A..F or a..f ER let or . P1 P2 digit add,gc digit E21 nill,add, gc add,gc let or . E or e add,gc + or - add,gc E22 add,gc digit ER let or . digit convert,put(TN), out(3,z) convert, put(TN), out(3,z) convert, put(TN), out(3,z) add,gc add,gc add,gc D or d z≠0 + nill,add ER - OG gc,out(2,z) look(TL) D or d H or h A or C or F or a or c or f let\AFH,O,o let\AFH let\AFH,O,o let\ AFH let\AFH AA E11 BB Рисунок 2.5 – Диаграмма состояний с действиями для модельного языка М, лист 2 22 Процедуры и функции: 1) gc – процедура считывания очередного символа текста в переменную СН; 2) let – логическая функция, проверяющая, является ли переменная СН буквой; 3) digit - логическая функция, проверяющая, является ли переменная СН циф- рой; 4) nill – процедура очистки буфера S; 5) add – процедура добавления очередного символа в конец буфера S; 6) look(t) – функция поиска лексемы из буфера S в таблице t с возвращением номера лексемы в таблице; 7) put(t) – процедура записи лексемы из буфера S в таблицу t, если там не было этой лексемы; возвращает номер данной лексемы в таблице; 8) out(n, k) – процедура записи пары чисел (n, k) в файл лексем; 9) check_hex – логическая функция, проверяющая, является ли переменная CH цифрой или буквой из диапазона A..F или a..f; 10) AFH – логическая функция, проверяющая является ли переменная CH бук- вой из диапазона A..F и a..f или буквой H, h; 11) translate(base) – процедура перевода числа в буфере из системы счисления по основанию base в десятичную систему счисления; 12) convert – процедура преобразования действительного числа в буфере из строковой формы записи в десятичную форму. Шаг 2. Составляем функцию scanner для анализа текста исходной программы: bool scanner(){ sost CS; gc(); CS=H; do{switch(CS){ case H:{while(CH==' ' || CH=='\n' && !fcin.eof() ) gc(); if(fcin.eof() ) CS=ER; if(let() ){nill(); add(); 23 gc(); CS=I;} else if(CH=='0' || CH=='1'){nill(); CS=N2; add(); gc();} else if(CH>='2' && CH<='7') {nill(); CS=N8; add(); gc();} else if(CH>='8' && CH<='9'){nill(); CS=N10; add(); gc();} else if(CH=='.'){nill(); add(); gc(); CS=P1;} else if(CH=='/'){gc(); CS=C1;} else if(CH=='<'){gc(); CS=M1;} else if(CH=='>'){gc(); CS=M2;} else if(CH=='}'){out(2, 2); CS=V;} else CS=OG; break;} case I:{while(let() || digit()){add(); gc();} look(TW); if(z!=0){out(1, z); CS=H;} else{put(TI); out(4, z); CS=H;} break;} case N2:{while(CH=='0' || CH=='1'){ add(); gc();} if(CH>='2' && CH<='7') CS=N8; else if(CH=='8' || CH=='9') CS=N10; else if(CH=='A' || CH=='a' || CH=='C' || CH=='c' || CH=='F' || CH=='f') CS=N16; else if(CH=='E' || CH=='e'){add(); gc(); CS=E11;} else if(CH=='D' || CH=='d'){add; gc(); CS=D;} else if(CH=='O' || CH=='o') CS=O; else if(CH=='H' || CH=='h'){gc(); CS=HX;} 24 else if(CH=='.'){add(); gc(); CS=P1;} else if(CH=='B' || CH=='b') {add(); gc();CS=B;} else if(let() ) CS=ER; else CS=N10; break;} case N8:{while(CH>='2' && CH<='7'){add(); gc();} if(CH=='8' || CH=='9') CS=N10; else if(CH=='A' || CH=='a' || CH=='B' || CH=='b' || CH=='C' || CH=='c' ||CH=='F' || CH=='f') CS=N16; else if(CH=='E' || CH=='e'){add(); gc(); CS=E11;} else if(CH=='D' || CH=='d'){add(); gc(); CS=D;} else if(CH=='H' || CH=='h'){gc(); CS=HX;} else if(CH=='.'){add(); gc(); CS=P1;} else if(CH=='O' || CH=='o'){gc();CS=O;} else if(let() ) CS=ER; else CS=N10; break;} case N10:{ while(CH=='8' || CH=='9'){add(); gc();} if(CH=='A' || CH=='a' || CH=='B' || CH=='b' || CH=='C' || CH=='c' || CH=='F' || CH=='f') CS=N16; else if(CH=='E' || CH=='e'){add(); gc(); CS=E11;} else if(CH=='H' || CH=='h'){gc(); CS=HX;} else if(CH=='.'){add(); gc(); CS=P1;} 25 else if(CH=='D' || CH=='d'){add();gc();CS=D;} else if(let() ) CS=ER; else { put(TN); out(3,z); CS=H;} break;} case N16:{while(check_hex() ){add(); gc();} if(CH=='H' || CH=='h'){gc(); CS=HX;} else CS=ER; break;} case B:{if( check_hex() ) CS=N16; else if( CH=='H' || CH=='h'){gc(); CS=HX;} else if(let() ) CS=ER; else{translate(2); put(TN); out(3,z); CS=H;} break;} case O:{if( let() || digit()) CS=ER; else {translate(8); put(TN);out(3,z);CS=H;} break;} case D:{if(CH=='H' || CH=='h'){gc(); CS=HX;} else if(check_hex() ) CS=N16; else if(let() ) CS=ER; else{put(TN); out(3,z); CS=H;} break;} case HX:{if(let() || digit() ) CS=ER; else{translate(16); put(TN);out(3,z); CS=H;} 26 break;} case E11:{if(digit() ){add(); gc(); CS=E12;} else if(CH=='+' || CH=='-'){add(); gc(); CS=ZN;} else if(CH=='H' || CH=='h'){gc(); CS=HX;} else if(check_hex() ){add(); gc(); CS=N16;} else CS=ER; break;} case ZN:{if(digit() ){add(); gc(); CS=E13;} else CS=ER; break;} case E12:{while(digit() ){add(); gc();} if(check_hex() ) CS=N16; else if(CH=='H' || CH=='h'){gc(); CS=HX;} else if(let() ) CS=ER; else{convert(); put(TN); out(3,z); CS=H;} break;} case E13:{while(digit() ){add(); gc();} if (let() || CH=='.') CS=ER; else {convert(); put(TN); out(3,z); CS=H;} break;} case P1:{if(digit() ) CS=P2; else CS=ER; break;} case P2:{while(digit() ){add(); gc();} if (CH=='E' || CH=='e'){add(); gc(); CS=E21;} else if (let() || CH=='.' ) CS=ER; else {convert();put(TN); out(3,z); CS=H;} break;} 27 case E21:{if (CH=='+' || CH=='-') {add(); gc(); CS=ZN;} else if (digit() ) CS=E22; else CS=ER; break;} case E22:{while(digit() ){add(); gc();} if (let() || CH=='.') CS=ER; else {convert(); put(TN); out(3,z); CS=H;} break;} case C1:{if (CH=='*'){gc(); CS=C2;} else{out(2,16); CS=H;} break;} case C2:{int flag=0; while(CH!='*' && !flag && CH!='}'){flag=gc();} if (CH=='}' || flag) CS=ER; else {gc(); CS=C3;} break;} case C3:{if (CH=='/'){gc(); CS=H;} else CS=C2; break;} case M1:{if (CH=='>') {gc(); out(2, 18); CS=H;} else if (CH=='=') {gc(); out(2, 21); CS=H;} else {out(2, 20); CS=H;} break;} case M2:{if (CH=='='){gc(); out(2, 22); CS=H;} else {out(2,19); CS=H;} break;} case OG:{nill(); add(); look(TL); |