'

Организация лексического анализа

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

tltLetter A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z tltDigit 0 1 2 3 4 5 6 7 8 9 tltSkip пробел табуляция перевод строки перевод формата Диаграммы Вирта, задающие некоторые из классов символов, порождаемых 24 Трансляторы


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

IsBinary { 0 2 } 1 lexInt lexError _ tltLetter 2 3 4 5 6 7 8 9 32 Трансляторы


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

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


Слайд 36

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 Трансляторы


Слайд 37

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 lexInt lexError lexInt lexError lexInt lexError lexComment lexError lexSlash lexStar lexSemicolon lexComma 38 Трансляторы


Слайд 38

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 Трансляторы


Слайд 39

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


Слайд 40

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 Трансляторы


Слайд 41

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


Слайд 42

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


Слайд 43

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


Слайд 44

IsPrefNumber { 0 2 } lexError 1 lexInt lexError _ tltLetter 2 3 4 5 6 7 8 9 8 } lexError 0 1 0 } lexError 1 2 3 4 5 lexInt tltDigit lexError _ tltLetter 6 7 _ tltLetter 8 9 lexInt lexError 6 } a lexError tltDigit b c d e f A B C D E F lexInt lexError G...Z |_ g…Z 45 Трансляторы


Слайд 45

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


×

HTML:





Ссылка: