Значение слова
<<  Слово и его лексическое значение Лексическое значение слова  >>
Организация лексического анализа
Организация лексического анализа
Назначение фазы лексического анализа
Назначение фазы лексического анализа
Необходимость фазы лексического анализа
Необходимость фазы лексического анализа
Транслитератор
Транслитератор
Праволинейные грамматики - конечный автомат
Праволинейные грамматики - конечный автомат
Построение конечного автомата, по диаграмме Вирта, без нетерминалов:
Построение конечного автомата, по диаграмме Вирта, без нетерминалов:
Буква
Буква
Цифра
Цифра
=> x
=> x
=> Бц
=> Бц
Замена правой рекурсии на итерацию в диаграммах Вирта:
Замена правой рекурсии на итерацию в диаграммах Вирта:
=>
=>
=> Бц
=> Бц
Преобразования в итерацию для правил, содержащих левую рекурсию:
Преобразования в итерацию для правил, содержащих левую рекурсию:
=> x =>
=> x =>
=>
=>
Методы лексического анализа
Методы лексического анализа
…
К достоинствам непрямого лексического анализатора следует отнести:
К достоинствам непрямого лексического анализатора следует отнести:
…
…
Лексический анализатор демонстрационного языка программирования
Лексический анализатор демонстрационного языка программирования
Общая организация транслитератора
Общая организация транслитератора
Трансляторы
Трансляторы
Разработка непрямого лексического
Разработка непрямого лексического
…
…
…
_
_
_
_
_
_
_
_
IsOctal
IsOctal
_
_
_
_
7. Под остальными понимаются
7. Под остальными понимаются
8. Лексемы, определяющие разделительные символы,
8. Лексемы, определяющие разделительные символы,
kwAbort le …
kwAbort le …
IsStar
IsStar
Разработка прямого лексического
Разработка прямого лексического
IsContinueIdOrKw …
IsContinueIdOrKw …
+
+
…
2
2
IsPrefNumber
IsPrefNumber
. lexError
. lexError

Презентация на тему: «Организация лексического анализа». Автор: Шестаков Александр Петрович. Файл: «Организация лексического анализа.ppt». Размер zip-архива: 1796 КБ.

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

содержание презентации «Организация лексического анализа.ppt»
СлайдТекст
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

Буква

Буква

Прочие

1

end

Цифра

Идентификатор

1

end

Диаграмма Вирта

Преобразование диаграммы Вирта в эквивалентный конечный автомат.

0

Конечный автомат,

эквивалентный представленной диаграмме Вирта

Трансляторы

7

8 Цифра

Цифра

Буква

0

1

Идентификатор

end

Минимизированная диаграмма Вирта, задающая идентификатор.

Трансляторы

8

9 => x

=> x

A

A ? x A ? yA

y A

Связь между диаграммами Вирта и праволинейными грамматиками.

Преобразование правой рекурсии в итерацию

Непосредственное преобразование простой грамматики

Трансляторы

9

10 => Бц

=> Бц

Непосредственное преобразование идентификатора

Буква бц

$ Идентификатор = буква бц . $ бц = буква бц | цифра бц | .

Буква бц цифра

Идентификатор

Трансляторы

10

11 Замена правой рекурсии на итерацию в диаграммах Вирта:

Замена правой рекурсии на итерацию в диаграммах Вирта:

·Дуга, входящая в рекурсивно

Определяемый нетерминал, замыкается своим выходом на самое начало правила, образуя, таким образом, цикл;

·Сам нетерминал, оказавшийся в подвешенном состоянии

Вычеркивается, а выходившая из него дуга убирается.

Трансляторы

11

12 =>

=>

x => A

=> x

y A

A

A

A

x y

y

A ? x A ? yA

Преобразование праволинейной грамматики в итеративную диаграмму Вирта.

Трансляторы

12

13 => Бц

=> Бц

=>

=>

Преобразование праволинейной грамматики

идентификатора в итеративную диаграмму Вирта.

Идентификатор

Буква бц

$ Идентификатор = буква бц . $ бц = буква бц | цифра бц | .

Буква бц цифра

Идентификатор

Буква бц

Бц

Буква буква

Буква

Идентификатор

Буква

Цифра

Трансляторы

13

14 Преобразования в итерацию для правил, содержащих левую рекурсию:

Преобразования в итерацию для правил, содержащих левую рекурсию:

·Дуга, выходящая из рекурсивно

Определяемого нетерминала, замыкается своим входом на самый конец правила, образуя, таким образом, цикл;

·Сам нетерминал, оказавшийся без адресата, вычеркивается, а входившая в него дуга убирается.

Связь между диаграммами Вирта и

Грамматиками с левой рекурсией.

Преобразование левой рекурсии в итерацию

Трансляторы

14

15 => x =>

=> x =>

=> A x

A

A ? x A ? Ay

A y

A

x A

y y

Преобразование грамматики с левой рекурсией в итеративную диаграмму Вирта

Трансляторы

15

16 =>

=>

=>

$ Идентификатор = буква | идентификатор буква | =>

Идентификатор

Буква цифра

Идентификатор

Идентификатор цифра.

Идентификатор

Буква цифра

Буква

Идентификатор

Буква

Цифра

Преобразование грамматики идентификатора с левой рекурсией в итеративную диаграмму Вирта.

Трансляторы

16

17 Методы лексического анализа

Методы лексического анализа

Непрямой лексический анализ, или

Лексический анализ с возвратами,

заключается в последовательной проверке версий о классах лексем. Если проверка текущей версии не подтверждается, то происходит откат назад по цепочке символов и осуществляется проверка следующей версии.

Прямой лексический анализ позволяет определить значение лексемы без откатов назад по цепочке символов.

Трансляторы

17

18 …

Обобщенная структура непрямого лексического анализатора

Трансляторы

18

Входная лента

a0

a1

ai

an

Старт

Символ

Лексема 1

Распознаватель 1

Блок управления

Входной

Откат

Отказ

Головкой

Следующий

Лексема 2

Распознаватель 2

Откат

Отказ

Следующий

Откат

Отказ

Следующий

Лексема n

Распознаватель n

Откат

Отказ

Следующий

Нейтрализация

Лексема

Ошибки

“Ошибка”

Обработчик

Ошибки

Стоп

19 К достоинствам непрямого лексического анализатора следует отнести:

К достоинствам непрямого лексического анализатора следует отнести:

·Прозрачность общей регулярной структуры,

Которая легко может изменяться и наращиваться;

·Простота каждого отдельно автомата,

Распознающего одну достаточно элементарную конструкцию;

·Практическая применимость подхода в самых

Разнообразных языках, независимо от сложности выделения в нем тех или иных лексем.

Пример: DOI=3,10,3

DO I = 3, 10, 3 или DOI=3 ?

К недостаткам непрямого лексического анализатора следует отнести низкую скорость распознавания правильных лексем. Это связано с постоянными возвратами входной головки к исходному состоянию, если версия о лексеме не подтверждается.

Трансляторы

19

20 …

Структура лексического анализатора с параллельной работой распознавателей

Трансляторы

20

Входная лента

ai

aj

an

Старт

Символ

Распознаватель 1

Арбитр

Лексема 1

Отказ

Символ

Распознаватель 2

Лексема 2

Отказ

Лексема или

Ошибка

Следующий

Символ

Распознаватель n

Лексема n

Отказ

Блок выравнивания

Головок

Арбитраж

Проведен

Стоп

21 …

Не та …

… Лексема t Фрагмент nm

Обобщенная структура прямого лексического анализатора

Трансляторы

21

Входная лента

a0 …

ai …

an

Передача управления

Старт

Лексема 1

Группа

Частному блоку

Символов 1

Фрагмент 1

Фрагмент 11

Ошибка

Не та группа

Лексема i

Группа символов 2

Фрагмент 1k

Фрагмент 2

Ошибка

Группа

Лексема j Фрагмент n1

Группа символов n

Фрагмент n Ошибка

Ошибка

Лексема “ошибка”

Обработчик лексических ошибок

22 Лексический анализатор демонстрационного языка программирования

Лексический анализатор демонстрационного языка программирования

Содержание

Транслитератор DPL.

Непрямой лексический анализатор DPL. Прямой лексический анализатор DPL.

Трансляторы

22

23 Общая организация транслитератора

Общая организация транслитератора

1. Класс букв: прописные и строчные буквы латинского алфавита

2. Класс цифр: объединяет арабские цифры от 0 до 9.

3. Класс пропусков: состоит из пробела,

Перевода строки, табуляции, перевода формата (разделяющего текст на отдельные страницы).

4. Класс игнорируемых символов: включает все символы, которые, как предполагается, не отображаются в окне текстового редактора.

5. Класс прочих символов: включает все оставшиеся символы.

Трансляторы

23

24 Трансляторы

Трансляторы

24

tltLetter

tltDigit

tltSkip

Пробел

Табуляция

Перевод строки перевод формата

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

0

1

2

3

4

5

6

7

8

9

Диаграммы Вирта, задающие некоторые из классов символов, порождаемых

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

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

Анализатора

Трансляторы

25

26 …

a

b o r t

b

e g i n

w

r i t e

kwAbort

kwBegin

kwWrite

IsKwAbort

IsKwBegin

IsKwWrite

а) Непосредственный анализ ключевых слов.

Трансляторы

26

27 …

=>ndKw

_

_

kwAbort

kwBegin

tltLetter

IsIdOrKw

tltLetter

kwWrite lexId

tltDiggit

б) Семантическое выделение ключевых слов из анализа идентификатора

Трансляторы

27

28 …

tltEOF

tltLetter

tltLetter

IsEof

Примечание

1. Лексема, порождаемая при достижении конца

Обрабатываемого текста.

=>ndKw

_

_

Примечание 2. Идентификатор и ключевые слова описываются правилом с семантической вставкой. Осуществляется также анализ на недопустимость возможного слияния идентификатора с действительным числом, начинающимся с точки.

lexEof

kwAbort

kwBegin

IsIdOrKw

kwWrite lexId

tltDiggit

lexError

Трансляторы

28

29 _

_

_

IsFloat1

Е +

lexFloat

tltDiggit

tltDiggit

lexError

Е -

tltLetter

IsFloat2

Е +

lexFloat

tltDiggit

tltDiggit

lexError

Е -

tltLetter

Трансляторы

29

30 _

_

_

IsFloat3

tltDiggit

lexFloat

tltDiggit

lexError

tltLetter

IsFloat4

lexFloat lexError

Е

+

tltDiggit

tltDiggit

Е

-

tltLetter

Трансляторы

30

31 _

_

IsFloat5

lexFloat

tltDiggit

lexError

tltLetter

Примечание 3 . Пять вариантов правил для распознавания действительного числа приводятся только для демонстрации арбитража при непрямом лексическом анализе. На практике легко можно обойтись одним правилом. Выдача ошибки происходит, если действительное число не отделяется разделителем от

Идентификатора

Или

Другого

Действительного

Числа,

Начинающегося с десятичной точки

Трансляторы

31

32 _

_

IsBinary

lexInt

tltLetter

0

{

2 }

lexError

1

2

3

4

5

6

7

8

9

Трансляторы

32

33 IsOctal

IsOctal

_

lexError

tltLetter

{

8

}

0

1

2

3

4

5

6

7

lexInt

8

9

Примечание 4 . Для двоичных и десятичных целых чисел необходима проверка того, что оно не сливается с теми цифрами, которые в них не содержатся.

Трансляторы

33

34 _

_

IsPrefDecimal

lexInt

tltDigit

tltLetter

lexInt

_

{ 1 0 }

lexError

IsDecimal

tltDigit

lexError

tltLetter

Примечание 5. Для целого десятичного числа без префикса анализ на недопустимость точки излишен, так как похожая ситуация должна была быть проанализирована раньше для действительного числа.

Трансляторы

34

35 _

_

IsHex

tltDigit

lexInt

Примечание 6. Для целого шестнадцатеричного проверка на недопустимость должна исключать прописные и строчные буквы, используемые в самом числе. На представленных диаграммах это показано сокращенной записью путем задания диапазона. Это сделано для того, чтобы не загромождать диаграмму деталями.

{

1

6

}

a

b

c

d e

f

A B C D E F

lexError

G...Z | g…Z

Трансляторы

35

36 7. Под остальными понимаются

7. Под остальными понимаются

символы не рассматриваемые непосредственно в текущей точке. В точке 1 - это не “*” и не конец файла; в точке 2 - это не “*”, не конец файла и не “/”

Примечание

IsComment

tltEOF

2

/ *

* /

1

Остальные

lexComment

lexError

Трансляторы

36

37 8. Лексемы, определяющие разделительные символы,

8. Лексемы, определяющие разделительные символы,

Расположены в соответствии с их приоритетом при анализе сверху вниз и слева направо.

Примечание

lexSlash

lexArrow

lexMinus

* lexStar

lexSemicolon

lexGE

lexGT

, lexComma

lexLftndBr

lexLE

lexRghRndBr

lexLT

lexLftSqBr

lexNE

lexEQ lexIgnore

lexRghSqBr

lexPercent

+ lexPlus

lexAssign

: lexColon

IsSlash IsStar

IsArrow

IsMinus -

IsSemicolon IsComma IsLftRndBr IsRghRndBr IsLftSqBr IsRghSqBr IsPercent

IsGE

IsGT >

IsLE

IsLT

IsNE

IsEQ

IsIgnore

IsPlus

IsAssign IsColon

Трансляторы

37

/

-

>

;

>

=

(

<

=

)

<

[

!

=

]

=

% tltIgnore

: =

38 kwAbort le …

kwAbort le …

NextLexema

IsEof

IsIdOrKw

lexError lexFloat lexError lexFloat lexError lexInt

IsFloat1

IsFloat5 IsBinary

lexError lexInt

IsOctal

lexError lexInt

IsPrefDecimal IsDecimal

lexError lexInt

lexError lexInt

IsHex

lexComment lexError

IsComment

lexSlash lexStar

IsSlash IsStar

lexSemicolon lexComma

IsSemicolon IsComma

lexEof

lexError

Трансляторы

38

39 IsStar

IsStar

lexSemicolon lexComma lexLftRndBr lexRghRndBr lexLftSqBr lexRghSqBr lexPercent

IsSemicolon IsComma IsLftRndBr IsRghRndBr

IsLftSqBr IsRghSqBr

IsPercent IsPlus

lexAssign lexColon lexArrow lexMinus lexGE

IsAssign IsColon IsArrow IsMinus

IsGE IsGT IsLE IsLT IsNE IsEQ IsIgnore

lexGT lexLE lexLT lexNE lexEQ

lexIgnore lexError

lexStar

lexPlus

Трансляторы

39

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

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

Анализатора

Трансляторы

40

41 IsContinueIdOrKw …

IsContinueIdOrKw …

/

{

; ,

* (

) [ ] %

Трансляторы

41

NextLexema

lexEof

tltEOF tltLetter

kwAbort

lexId

_

lexError lexSkip lexInt

tltSkip

lexFloat

tltDiggit

IsNumber

lexError lexIgnore lexSlash

tltIgnore

lexComment

IsSlashComment

lexError

lexInt

IsPrefNumber

lexError

lexFloat

IsFloatNumber

lexError

lexSemicolon lexComma lexStar

lexLftRndBr lexRghRndBr

lexLftSqBr lexRghSqBr lexPercent

42 +

+

:

=

-

>

>

=

<

=

=

!

=

lexPlus

lexColon

lexAssign

lexMinus

lexArrow

lexGT

lexGE

lexLE

lexEQ

lexError

lexNE

lexError

lexLT

Трансляторы

42

43 …

=>ndKw

_

kwAbort

kwBegin

tltLetter

IsContinueIdOrKw

kwWrite lexId

tltDiggit

lexError

IsNumber

lexInt

_ lexError

tltDiggit

tltLetter

Е +

lexFloat lexError

tltDiggit

tltDiggit

Е -

_

tltLetter

Трансляторы

43

44 2

2

*

* /

1

IsSlashComment

lexSlash

lexError

tltEOF

Остальные

lexComment

Трансляторы

44

45 IsPrefNumber

IsPrefNumber

lexInt

_

tltLetter

lexInt

lexInt

tltDigit

_

tltLetter

_

tltLetter

tltDigit

A B C D E F lexInt

g…Z

G...Z |_

2 } lexError

lexError

lexError 0

lexError

lexError

lexError

lexError

lexError

0

{

1

2

3

4

5

6

7

8

9

8 }

1 2 3 4 5

6 7

1 0 }

8

9

6 }

a

b c d e f

Трансляторы

45

46 . lexError

. lexError

_

IsFloatNumber

+

lexFloat

tltDiggit

tltDiggit

-

lexError

tltLetter

Е

Е

Трансляторы

46

«Организация лексического анализа»
http://900igr.net/prezentacija/russkij-jazyk/organizatsija-leksicheskogo-analiza-173282.html
cсылка на страницу
Урок

Русский язык

100 тем
Слайды
900igr.net > Презентации по русскому языку > Значение слова > Организация лексического анализа