Организация лексического анализа Назначение и необходимость фазы лексического анализа. Транслитератор. Грамматики и распознаватели для лексического анализа. - презентация

1 Организация лексического анализа Назначение и необходимость фазы лексического анализа. Транслитератор. Грамматики и распознаватели для лексического анализа. Методы лексического анализа. 1Трансляторы

2 Назначение фазы лексического анализа Лексический анализ - разбиение входного потока на лексемы. класс лексемы, определяющий общее название для группы элементов, обладающих общими свойствами значение лексемы, определяющее подстроку символов входной цепочки, соответствующих распознанному классу лексемы. В зависимости от класса, значение лексемы может быть преобразовано во внутреннее представление уже на этапе лексического анализа. Так, например, поступают с числами, преобразуя их в машинное представление. Это обеспечивает их более компактное хранение и позволяет проверить правильность диапазона чисел на ранней стадии анализа. 2Трансляторы

3 Необходимость фазы лексического анализа 1. Замена, цепочек символов, представляющих элементарные конструкции языка, делает внутренне представление программы более удобным для дальнейшего анализа распознавателем. 2. Уменьшается длина программы за счет устранения из нее несущественных для дальнейшего анализа пробелов, комментариев, игнорируемых символов. 3. Один и тот же язык программирования может иметь различные внешние представления элементарных конструкций. 4. Лексический анализатор использует более простые, по сравнению с синтаксическим анализатором, методы разбора. 5. Блок лексического анализа естественным образом вписывается в иерархическую структуру компилятора. 3Трансляторы

4 Транслитератор Устройство, осуществляющее сопоставление класса с каждым отдельным символом, называется транслитератором. Наиболее типичными классами символов являются: буква - класс, с которым сопоставляется множество букв, причем необязательно только одного алфавита; цифра - множество символов, относящихся к цифрам, чаще всего от 0 до 9; разделители - пробел, перевод строки, возврат каретки перевод формата; игнорируемые - могут встречаться во входном потоке, но игнорируются и поэтому просто выбрасываются из него (например, невидимый код звукового сигнала и другие аналогичные коды); запрещенные - те символы, которые не относятся к алфавиту языка, но встречаются во входной цепочке; остальные - символы, не вошедшие ни в одну из определенных категорий. 4Трансляторы

5 Грамматики и распознаватели для лексического анализа Праволинейные грамматики - конечный автомат Построение конечного автомата можно осуществить с использованием и некоторых грамматик с левой рекурсией, а также диаграмм Вирта. Диаграммы Вирта намного нагляднее при описании правил. Между диаграммами Вирта, не содержащими нетерминалов, и конечными автоматами существует однозначное соответствие. 5Трансляторы

6 Построение конечного автомата, по диаграмме Вирта, без нетерминалов: 1. Вход входной дуги диаграммы преобразуется в начальное состояние конечного автомата. 2. Выход выходной дуги диаграммы образует заключительное состояние конечного автомата. 3. Выходы отдельных дуг, соединяющих символы, и точки ветвления остальных дуг диаграммы образуют множество остальных состояний конечного автомата. 4. Конечные состояния диаграммы являются допускающими состояниями конечного автомата. 5. Терминальные символы диаграммы Вирта расположенные между соответствующими дугами, преобразуются в связи между соответствующими состояниями, с входным символом, соответствующим указанному терминалу. 6. Связи, обеспечивающие переход в допускающие состояния, помечаются множеством оставшихся символов. Это множество не пересекается с множеством символов, обеспечивающих переходы из текущего в другие состояния (обозначены как прочие). 6Трансляторы

7 идентификатор 0 0 буква Диаграмма Вирта буква 1 цифра буква 1 цифра прочие end Конечный автомат, эквивалентный представленной диаграмме Вирта Преобразование диаграммы Вирта в эквивалентный конечный автомат. 7Трансляторы

8 идентификатор буква цифра 0 1 end Минимизированная диаграмма Вирта, задающая идентификатор. 8Трансляторы

9 Связь между диаграммами Вирта и праволинейными грамматиками. Преобразование правой рекурсии в итерацию A x A yA A x yAyA Непосредственное преобразование простой грамматики 9Трансляторы

10 идентификатор $ идентификатор = буква бц. $ бц = буква бц | цифра бц |. буквабц бц буквабц цифра Непосредственное преобразование идентификатора 10Трансляторы

11 Замена правой рекурсии на итерацию в диаграммах Вирта: дуга, входящая в рекурсивно определяемый нетерминал, замыкается своим выходом на самое начало правила, образуя, таким образом, цикл; сам нетерминал, оказавшийся в подвешенном состоянии вычеркивается, а выходившая из него дуга убирается. 11Трансляторы

12 A x A yA A y A x yAyA x A A xyxy Преобразование праволинейной грамматики в итеративную диаграмму Вирта. 12Трансляторы

13 идентификатор $ идентификатор = буква бц. $ бц = буква бц | цифра бц |. идентификатор буквабц бц буква идентификатор буква бц буква цифра буквабц буквабц цифра Преобразование праволинейной грамматики идентификатора в итеративную диаграмму Вирта. 13Трансляторы

14 Связь между диаграммами Вирта и грамматиками с левой рекурсией. Преобразование левой рекурсии в итерацию Преобразования в итерацию для правил, содержащих левую рекурсию: дуга, выходящая из рекурсивно определяемого нетерминала, замыкается своим входом на самый конец правила, образуя, таким образом, цикл; сам нетерминал, оказавшийся без адресата, вычеркивается, а входившая в него дуга убирается. 14Трансляторы

15 A x A Ay A xAxA A x A y A x y Преобразование грамматики с левой рекурсией в итеративную диаграмму Вирта 15Трансляторы

16 идентификатор $ идентификатор = буква | идентификатор буква | идентификатор цифра. идентификатор буква цифра идентификатор буква идентификатор буква цифра буква цифра Преобразование грамматики идентификатора с левой рекурсией в итеративную диаграмму Вирта. 16Трансляторы

17 Методы лексического анализа Непрямой лексический анализ, или лексический анализ с возвратами, заключается в последовательной проверке версий о классах лексем. Если проверка текущей версии не подтверждается, то происходит откат назад по цепочке символов и осуществляется проверка следующей версии. Прямой лексический анализ позволяет определить значение лексемы без откатов назад по цепочке символов. 17Трансляторы

18 Входная лента a0a0 a1a1 …aiai …anan Старт СимволЛексема 1 Блок управления Распознаватель 1 входной головкой ОткатОтказ Следующий Лексема 2 Распознаватель 2 ОткатОтказ Следующий … ОткатОтказ Следующий Лексема n Распознаватель n ОткатОтказ Нейтрализация Следующий Лексема ошибкиошибка Обработчик ошибки Стоп Обобщенная структура непрямого лексического анализатора 18Трансляторы

19 К достоинствам непрямого лексического анализатора следует отнести: прозрачность общей регулярной структуры, которая легко может изменяться и наращиваться; простота каждого отдельно автомата, распознающего одну достаточно элементарную конструкцию; практическая применимость подхода в самых разнообразных языках, независимо от сложности выделения в нем тех или иных лексем. Пример: DOI=3,10,3 DO I = 3, 10, 3 или DOI=3 ? К недостаткам непрямого лексического анализатора следует отнести низкую скорость распознавания правильных лексем. Это связано с постоянными возвратами входной головки к исходному состоянию, если версия о лексеме не подтверждается. 19Трансляторы

20 Входная лента aiai …ajaj …anan Старт Символ Распознаватель 1 Арбитр Лексема 1 Отказ Символ Распознаватель 2 Лексема 2 Отказ … Лексема или ошибка Следующий Символ Распознаватель n Лексема n Отказ Блок выравнивания головок Арбитраж проведен Стоп Структура лексического анализатора с параллельной работой распознавателей 20Трансляторы

21 Входная лента a0…a0… Группа символов 1 Группа символов 2 ai…ai… Старт Фрагмент 1 Не та группа Фрагмент 2 anan Передача управления частному блоку Ошибка Фрагмент 11 … Фрагмент 1k Лексема 1 Лексема i Группа символов n Не та … группа … Фрагмент n Ошибка Ошибка Обработчик лексических ошибок Лексема j Фрагмент n1 … Лексема t Фрагмент nm Лексема ошибка Обобщенная структура прямого лексического анализатора 21Трансляторы

22 Лексический анализатор демонстрационного языка программирования Содержание Транслитератор DPL. Непрямой лексический анализатор DPL. Прямой лексический анализатор DPL. 22Трансляторы

23 Общая организация транслитератора 1. Класс букв : прописные и строчные буквы латинского алфавита 2. Класс цифр : объединяет арабские цифры от 0 до Класс пропусков : состоит из пробела, перевода строки, табуляции, перевода формата (разделяющего текст на отдельные страницы). 4. Класс игнорируемых символов : включает все символы, которые, как предполагается, не отображаются в окне текстового редактора. 5. Класс прочих символов : включает все оставшиеся символы. 23Трансляторы

24 tltLetter A B C D E F G H I JK L M N O P Q R S T U V W X Y Z abcdefghijklm nopqrstuvw x yz tltDigit tltSkip пробел табуляция перевод строки перевод формата Диаграммы Вирта, задающие некоторые из классов символов, порождаемых 24Трансляторы

25 Разработка непрямого лексического анализатора 25Трансляторы

26 IsKwAbort a IsKwBegin b IsKwWrite w kwAbort b o r t kwBegin e g i n … kwWrite r ite а) Непосредственный анализ ключевых слов. 26Трансляторы

27 kwAbort IsIdOrKw tltLetter _ =>ndKw tltDiggit _ kwBegin … kwWrite lexId б) Семантическое выделение ключевых слов из анализа идентификатора 27Трансляторы

28 IsEof lexEof tltEOF Примечание1. Лексема, порождаемая при достижении конца обрабатываемого текста. kwAbort IsIdOrKw tltLetter _ =>ndKw tltDiggit _ kwBegin … kwWrite lexId lexError Примечание 2. Идентификатор и ключевые слова описываются правилом с семантической вставкой. Осуществляется также анализ на недопустимость возможного слияния идентификатора с действительным числом, начинающимся с точки. 28Трансляторы

29 IsFloat1 tltDiggit IsFloat2 tltDiggit Е+Е+ е-е- Е+Е+ е-е- lexFloat tltDiggit lexError _ tltLetter lexFloat tltDiggit lexError _ tltLetter 29Трансляторы

30 IsFloat3 tltDiggit lexFloat tltDiggit lexError _ tltLetter IsFloat4 Е tltDiggit е + - lexFloat lexError _ tltLetter 30Трансляторы

31 IsFloat5 lexFloat tltDiggit lexError _ tltLetter Примечание3. Пять вариантов правил для распознавания действительного числа приводятся только для демонстрации арбитража при непрямом лексическом анализе. На практике легко можно обойтись одним правилом. Выдача ошибки происходит, если действительное число не отделяется разделителем от идентификатораилидругогодействительногочисла, начинающегося с десятичной точки 31Трансляторы

32 IsBinary { 0 2}2} 1 lexInt lexError _ tltLetter Трансляторы

33 IsOctal { 8} lexInt lexError _ tltLetter 8 9 Примечание4. Для двоичных и десятичных целых чисел необходима проверка того, что оно не сливается с теми цифрами, которые в них не содержатся. 33Трансляторы

34 IsPrefDecimal lexInt {10}{10} IsDecimal tltDigit lexInt lexError _ tltLetter _ Примечание 5. Для целого десятичного числа без префикса анализ на недопустимость точки излишен, так как похожая ситуация должна была быть проанализирована раньше для действительного числа. 34Трансляторы

35 IsHex { 16} a bcd ef tltDigit A B C D E F lexInt lexError _ G...Z | g…Z Примечание 6. Для целого шестнадцатеричного проверка на недопустимость должна исключать прописные и строчные буквы, используемые в самом числе. На представленных диаграммах это показано сокращенной записью путем задания диапазона. Это сделано для того, чтобы не загромождать диаграмму деталями. 35Трансляторы

36 IsComment /*/* 1 Примечание 2 остальные lexComment */*/ lexError tltEOF 7. Под остальными понимаются символы не рассматриваемые непосредственно в текущей точке. В точке 1 - это не * и не конец файла; в точке 2 - это не *, не конец файла и не / 36Трансляторы

37 IsSlash IsStar IsSemicolon IsComma IsLftRndBr IsRghRndBr IsLftSqBr IsRghSqBr IsPercent lexSlash / * lexStar lexSemicolon ;, lexComma lexLftndBr ( lexRghRndBr ) lexLftSqBr [ lexRghSqBr ] lexPercent IsArrow - IsMinus - IsGE > IsGT > IsLE < IsLT < IsNE ! IsEQ = IsIgnore lexArrow > lexMinus lexGE = lexGT lexLE = lexLT lexNE = lexEQ lexIgnore IsPlus IsAssign IsColon Примечание % tltIgnore + lexPlus lexAssign :=:= : lexColon 8.Лексемы, определяющие разделительные символы, расположены в соответствии с их приоритетом при анализе сверху вниз и слева направо. 37Трансляторы

38 NextLexema IsEof IsIdOrKw IsFloat1 … IsFloat5 IsBinary IsOctal IsPrefDecimal IsDecimal IsHex IsComment IsSlash IsStar IsSemicolon IsComma lexEof kwAbort le … lexError lexFloat lexError lexFloat lexError lexInt lexError lexInt lexError lexComment lexError lexSlash lexStar lexSemicolon lexComma 38Трансляторы

39 IsStar IsSemicolon IsComma IsLftRndBr IsRghRndBr IsLftSqBr IsRghSqBr IsPercent IsPlus IsAssign IsColon IsArrow IsMinus IsGE IsGT IsLE IsLT IsNE IsEQ IsIgnore lexStar lexSemicolon lexComma lexLftRndBr lexRghRndBr lexLftSqBr lexRghSqBr lexPercent lexPlus lexAssign lexColon lexArrow lexMinus lexGE lexGT lexLE lexLT lexNE lexEQ lexIgnore lexError 39Трансляторы

40 Разработка прямого лексического анализатора 40Трансляторы

41 NextLexema tltEOF tltLetter _ tltSkip tltDiggit tltIgnore / { ;,;, *(*( )[]%)[]% lexEof kwAbort IsContinueIdOrKw … lexId lexError lexSkip lexInt lexFloat IsNumber lexError lexIgnore lexSlash lexComment IsSlashComment lexError lexInt IsPrefNumber lexError lexFloat IsFloatNumber lexError lexSemicolon lexComma lexStar lexLftRndBr lexRghRndBr lexLftSqBr lexRghSqBr lexPercent 41Трансляторы

42 lexPlus + lexColon : lexAssign = lexMinus - lexArrow > lexGT > lexGE = lexLT < lexLE = lexEQ = lexError ! lexNE = lexError 42Трансляторы

43 kwAbort IsContinueIdOrKw tltLetter =>ndKw tltDiggit _ kwBegin … kwWrite lexId lexError IsNumber lexInt tltDiggit Е+Е+ е-е- _ lexError tltLetter lexFloat lexError _ tltLetter 43Трансляторы

44 IsSlashComment * 1 lexSlash 2 остальные lexComment */*/ lexError tltEOF 44Трансляторы

45 IsPrefNumber { 0 2} lexError 1 lexInt lexError _ tltLetter }8} lexError 0 10}10} lexError lexInt tltDigit lexError _ tltLetter 6767 _ 8 9 lexInt lexError 6}6} a tltDigit bcdefbcdef A B C D E F lexInt lexError G...Z | _ g…Z 45Трансляторы

46 IsFloatNumber Е + lexFloat tltDiggit е -. lexError _ lexError tltLetter 46Трансляторы