И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 8
Текст из файла (страница 8)
Иными словами, существуют i, j, 1 ≤ i < j ≤ k, такие что⎯→ L ⎯⎯→ p j пути T является циклом. Пусть длинаpi = pj. Таким образом, участок pi ⎯aaэтого цикла равна m (m > 0, так как цикл — это непустой путь). Рассмотрим успешный путьaa⎯→L⎯⎯→p j присутствуетT ′, который отличается от T тем, что циклический участок pi ⎯в нем дважды:aaaaaabp1 ⎯⎯→L pi ⎯⎯→L⎯⎯→( pi = p j ) ⎯⎯→L⎯⎯→pj ⎯⎯→L pk +1 ⎯⎯→L p2 k +1 .33Элементы теории трансляции / Разбор по регулярным грамматикамПометкой пути T ′ является цепочкаak +m kвуb ∈ L(A) . Так как aa k +mb k .Поскольку T ′ — успешный путь,k +m kb ∉ L , получаем, что L ≠ L ( A) . Это противоречит равенстL = L ( A ) .
Следовательно, предположение о том, что L регулярен, неверноРегулярные выраженияКроме регулярных грамматик и конечных автоматов, существует еще один широкоиспользуемый в математических теориях и приложениях формализм, задающий регулярныеязыки. Это регулярные выражения. Они позволяют описать любой регулярный язык над заданным алфавитом, используя три вида операций: + (объединение),(итерация). 15)⋅ (конкатенация),∗Определение. Пусть L, L1, L2 — языки над алфавитом Σ.
Тогда будем называть языкL1 ∪ L2 объединением языков L1 и L2 ; язык L1⋅L2 = {ϕ⋅ψ| ϕ ∈ L1, ψ ∈ L2} — конкатенацией (сцеплением) языков L1 и L2 (содержит всевозможные цепочки, полученные сцеплениiем цепочек из L1 с цепочками из L2); i-ой степенью языка L назовем язык L = L*для i > 0, L0 = {ε}. Язык L =U∞n =0⋅Li−1L n назовем итерацией языка L.Определение. Пусть Σ — алфавит, не содержащий символов ∗, +, ε, ∅, (, ).
Определим рекурсивно регулярное выражение γ над алфавитом Σ и регулярный язык L(γ), задаваемый этим выражением:1) a ∈ Σ ∪ {ε, ∅} есть регулярное выражение; L(a) = {a} для a ∈ Σ ∪ {ε}; L(∅) = ∅;2) если α и β — регулярные выражения, то:а) (α) + (β) — регулярное выражение;L ( (α) + (β) ) = L (α) ∪ L (β);б) (α)(β) — регулярное выражение;L ( (α)(β) ) = L (α) L (β);*в) (β) — регулярное выражение;**L ( (β) ) = ( L (β) ) ;3) все регулярные выражения конструируются только с помощью пунктов 1 и 2.Если считать, что операция «+» имеет самый низкий приоритет, а операция «∗» —наивысший, то в регулярных выражениях можно опускать лишние скобки.Примеры регулярных выражений над алфавитом {a, b}:a + b,*(a + b) ,**(aa (ab) bb) .Соответствующие языки:L( a + b ) = {a} ∪ {b} = {a, b},15)Операцию итерации называют также звездочкой Клини, в честь ученого, предложившего регулярные выражения для описания регулярных языков.
«Регулярность» в названии этого класса языков означает повторяемость некоторых фрагментов цепочек. На примере диаграмм конечных автоматов видно, что повторяемость фрагментов обусловлена наличием циклов в диаграмме.34Элементы теории трансляции / Задачи лексического анализа**L( (a + b) ) = {a, b} ,**nL( (aa (ab) bb) ) = {ε}∪{ aa x1bb aa x2bb... xkbb | k ≥ 1, xi ∈ {(ab) | n ≥ 0} для i = 1, ..., k }.Существуют алгоритмы построения регулярного выражения по регулярной грамматике или конечному автомату и обратные алгоритмы, позволяющие преобразовать выражение в эквивалентную грамматику или автомат [3].Регулярные выражения используются для описания лексем языков программирования, в задачах редактирования и обработки текстов; подходят для многих задач сравненияизображений и автоматического преобразования.
Расширенные их спецификации (эквивалентные по описательной силе, но более удобные для практики) входят в промышленныйстандарт открытых операционных систем POSIX и в состав базовых средств языка программирования Perl.Задачи лексического анализаЛексический анализ (ЛА) — это первый этап процесса компиляции. На этом этапе литеры, составляющие исходную программу, группируются в отдельные лексические элементы, называемые лексемами.Лексический анализ важен для процесса компиляции по нескольким причинам:а) замена в программе идентификаторов, констант, ограничителей и служебных словлексемами делает представление программы более удобным для дальнейшей обработки;б) лексический анализ уменьшает длину программы, устраняя из ее исходного представления несущественные пробельные символы и комментарии;в) если будет изменена кодировка в исходном представлении программы, то это отразится только на лексическом анализаторе.Выбор конструкций, которые будут выделяться как отдельные лексемы, зависит отязыка и от точки зрения разработчиков компилятора.
Обычно принято выделять следующиетипы лексем: идентификаторы, служебные слова, константы и ограничители. Каждой лексеме сопоставляется пара:〈 тип_лексемы, указатель_на_информацию_о_ней 〉.Соглашение: эту пару тоже будем называть лексемой, если это не будет вызывать недоразумений.Таким образом, лексический анализатор — это транслятор, входом которого служитцепочка символов, представляющих исходную программу, а выходом — последовательностьлексем.Очевидно, что лексемы перечисленных выше типов можно описать с помощью регулярных грамматик. Поскольку лексемы не пусты, для описания лексического состава любогоязыка программирования достаточно автоматных грамматик без ε-правил.Например, идентификатор (I ) описывается так:35Элементы теории трансляции / Задачи лексического анализаI → a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9Целое без знака (N):N → 0 | 1 |...| 9 | N0 | N1 |...| N9и т.
д.Для грамматик этого класса, как мы уже видели, существует простой и эффективныйалгоритм анализа того, принадлежит ли заданная цепочка языку, порождаемому этой грамматикой. Однако перед лексическим анализатором стоит более сложная задача: он должен сам выделить в исходном тексте цепочку символов, представляющуюлексему, и проверить правильность ее записи; зафиксировать в специальных таблицах для хранения разных типов лексем фактпоявления соответствующих лексем в анализируемом тексте; преобразовать цепочку символов, представляющих лексему, в пару 〈 тип_лексемы,указатель_на_информацию_о_ней 〉; удалить пробельные литеры и комментарии.Для того чтобы решить эту задачу, опираясь на способ анализа с помощью диаграммысостояний, введем на дугах дополнительный вид пометок — пометки-действия.
Теперь каждая дуга в ДС может выглядеть так:t1, t2,…, tnABD1; D2;…;DmСмысл ti прежний: если в состоянии A очередной анализируемый символ совпадает с tiдля какого-либо i = 1, 2, …, n, то осуществляется переход в состояние B, при этом необходимо выполнить действия D1, D2, ..., Dm.Задача. По заданной регулярной грамматке, описывющей целое число без знака, построить диаграмму с действиями по нахождению и печати квадрата данного числа.S → N⊥N → 0 | 1 |...| 9 | N0 | N1 |...| N9РешениеПеревод числа во внутренне представление (переменная n типа int) будем осуществлять по схеме Горнера: распознав очередную цифру числа, умножаем текущее значениие nна 10 и добавляем числовое значение текущей цифры (текущий символ хранится в переменной c типа char).
Встретив маркер конца, печатаем квадрат числа n.0, 1,…, 9Hn = c–’0’;N⊥cout << n*n;0, 1,…, 9n = n∗10 + c –’0’;36SЭлементы теории трансляции / Задачи лексического анализаЛексический анализатор для М-языкаОписание модельного языкаPD1DBSEE1TFLINCR→→→→→→→→→→→→→→program D1; B⊥var D {,D}I {, I}: [ int | bool ]begin S {;S} endI := E | if E then S else S | while E do S | B | read (I) | write (E)E1 [ = | < | > | != ] E1 | E1T {[ + | − | or ] T}F {[ ∗ | / | and ] F}I | N | L | not F | (E)true | falseC | IC | IRR | NRa | b | ... | z | A | B | ...
| Z0 | 1 | 2 | ... | 9Замечания к грамматике модельного языка:а) запись вида {α} означает итерацию цепочки α, т. е. в порождаемой цепочке вэтом месте может находиться либо ε, либо α, либо αα, либо ααα и т. д.;б) запись вида [α | β] означает, что в порождаемой цепочке в этом месте может находиться либо α, либо β;в) P — цель грамматики; символ ⊥ — маркер конца текста программы.Контекстные условия:1.
Любое имя, используемое в программе, должно быть описано и только один раз.2. В операторе присваивания типы переменной и выражения должны совпадать.3. В условном операторе и в операторе цикла в качестве условия возможно толькологическое выражение.4.
Операнды операции отношения должны быть целочисленными.5. Тип выражения и совместимость типов операндов в выражении определяются пообычным правилам; старшинство операций задано синтаксисом.В любом месте программы, кроме идентификаторов, служебных слов и чисел, можетнаходиться произвольное число пробелов и комментариев в фигурных скобках вида {〈 любые символы, кроме «}» и «⊥» 〉 }.true, false, read и write — служебные слова (их нельзя переопределять, также какстандартные идентификаторы в Паскале).Разделители между идентификаторами, числами и служебными словами употребляются так же, как в Паскале.37Элементы теории трансляции / Задачи лексического анализаПерейдем к построению лексического анализатора.Вход лексического анализатора — символы исходной программы на М-языке; результат работы — исходная программа в виде последовательности лексем (их внутреннего представления).
В нашем случае лексический анализатор будет вызываться, когда потребуетсяочередная лексема исходной программы, поэтому результатом работы лексического анализатора будет очередная лексема анализируемой программы на М-языке.Лексический анализатор для модельного языка будем создавать поэтапно: сначалаопишем на языке Си + + классы объектов, которые будут использоваться при ЛА, затем построим ДС с действиями для распознавания и формирования внутреннего представлениялексем, а затем по ДС напишем программу ЛА. Отметим, что мы будем рассматривать одиниз возможных способов проектирования и реализации программы ЛА на Си + +, быть может, не самый лучший.Проектирование классовой структуры лексического анализатораПредставление лексем: выделим следующие типы лексем, введя следующий перечислимый тип данных:enum type_of_lex{LEX_NULL,LEX_AND, LEX_BEGIN, … LEX_WRITE,LEX_FIN,LEX_SEMICOLON, LEX_COMMA, … LEX_GEQ,LEX_NUM,LEX_ID,POLIZ_LABEL,POLIZ_ADDRESS,POLIZ_GO,POLIZ_FGO};////////////////////0181935363738394041Содержательно внутреннее представление лексем — это пара (тип_лексемы, значение_лексемы).
Значение лексемы — это номер строки в таблице лексем соответствующегокласса, содержащей информацию о лексеме, или непосредственное значение, например, вслучае целых чисел.Соглашение об используемых таблицах лексем:TW — таблица служебных слов М-языка;TD — таблица ограничителей М-языка;TID — таблица идентификаторов анализируемой программы;Таблицы TW и TD заполняются заранее, т. к. их содержимое не зависит от исходнойпрограммы; TID формируется в процессе анализа.Необходимые таблицы можно представить в виде объектов, конкретный вид которыхмы рассмотрим чуть позже, или в виде массивов строк, например, для служебных слов.Класс Lex:38Элементы теории трансляции / Задачи лексического анализаclass Lex{type_of_lex t_lex;intv_lex;public:Lex ( type_of_lex t = LEX_NULL, int v = 0){t_lex = t; v_lex = v;}type_of_lex get_type () { return t_lex; }int get_value () { return v_lex; }friend ostream& operator << ( ostream &s, Lex l ){s << '(' << l.t_lex << ',' << l.v_lex << ");";return s;}};Класс Ident:class Ident{char*booltype_of_lexboolintpublic:Ident (){declareassign}name;declare;type;assign;value;= false;= false;char *get_name (){return name;}void put_name (const char *n){name = new char [ strlen(n) + 1 ];strcpy ( name, n );}bool get_declare (){return declare;}void put_declare (){declare = true;}39Элементы теории трансляции / Задачи лексического анализаtype_of_lex get_type (){return type;}void put_type ( kind_of_lex t ){type = t;}bool get_assign (){return assign;}void put_assign (){assign = true;}int get_value (){return value;}void put_value (int v){value = v;}};Класс tabl_ident :class tabl_ident{ident*p;intsize;inttop;public:tabl_ident ( int max_size ){p= new ident[size=max_size];top = 1;}~tabl_ident (){delete []p;}ident& operator[] ( int k ){return p[k];}int put ( const char *buf );};int tabl_ident::put ( const char *buf ){40Элементы теории трансляции / Задачи лексического анализаfor ( int j=1; j<top; ++j )if ( !strcmp(buf, p[j].get_name()) )return j;p[top].put_name(buf);++top;return top-1;}Класс Scanner :class Scanner{enumstate { H, IDENT, NUMB, COM, ALE, DELIM, NEQ };static char* TW[];static type_of_lexwords[];static char* TD[];static type_of_lexdlms[];stateCS;FILE* fp;charc;charbuf[80];intbuf_top;void clear (){buf_top = 0;for ( int j = 0; j < 80; ++j )buf[j] = '\0';}void add (){buf [ buf_top ++ ] = c;}int look ( const char *buf, char **list ){int i = 0;while ( list[i] ){if ( !strcmp(buf, list[i]) )return i;++i;}return 0;}void gc (){c = fgetc (fp);}public:41Элементы теории трансляции / Задачи лексического анализаLex get_lex ();Scanner ( const char * program ){fp = fopen ( program, "r" );CS = H;clear();gc();}};Таблицы лексем М-языка можно описать на Си + +, например, таким образом:char * Scanner::TW[] ={""// 0 позиция 0 не используется"and",// 1"begin",// 2"bool",// 3"do",// 4"else",// 5"end",// 6"if",// 7"false",// 8"int",// 9"not",// 10"or",// 11"program",// 12"read",// 13"then",// 14"true",// 15"var",// 16"while",// 17"write",// 18NULL};char * Scanner::{""";","@",",",":",":=","(",")","=","<",">","+","-","*","/","<=",42TD[] =////////////////////////////////0 позиция 0 не используется123456789101112131415Элементы теории трансляции / Задачи лексического анализа"!=",">=",NULL// 16// 17};tabl_ident TID(100);type_of_lex Scanner::words[] ={LEX_NULL,LEX_AND,LEX_BEGIN,LEX_BOOL,LEX_DO,LEX_ELSE,LEX_END,LEX_IF,LEX_FALSE,LEX_INT,LEX_NOT,LEX_OR,LEX_PROGRAM,LEX_READ,LEX_THEN,LEX_TRUE,LEX_VAR,LEX_WHILE,LEX_WRITE,LEX_NULL};type_of_lex Scanner::dlms[] ={LEX_NULL,LEX_FIN,LEX_SEMICOLON,LEX_COMMA,LEX_COLON,LEX_ASSIGN,LEX_LPAREN,LEX_RPAREN,LEX_EQ,LEX_LSS,LEX_GTR,LEX_PLUS,LEX_MINUS,LEX_TIMES,LEX_SLASH,LEX_LEQ,LEX_NEQ,LEX_GEQ,LEX_NULL};43Элементы теории трансляции / Задачи лексического анализаgc();’_’Hadd(); gc();буква,цифрабукваIDENTj = look(buf, TW); Lex(words[j], j);или j = TID.put(buf); Lex(LEX_ID, j);clear(); add(); gc();d = d*10 + ( c –´0´); gc( );буква,цифрацифраd = c−´0´; gc();NUMBLex(LEX_NUM, d);gc( );{}COMgc();gc();⊥:,<,>ALEclear(); add(); gc();j=look(buf, TD); Lex(dlms[j], j);=add( ); gc( ); j=look(buf, TD); Lex(dlms[j], j);⊥!gc();ERLex(LEX_FIN);NEQgc() ; Lex(LEX_NEQ);⊥DELIMER+,−,∗,/,,,;,(,),=clear( ); add( ); gc( );j=look(buf, TD); Lex(dlms[j], j);Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
