Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Лексический анализ

Содержание

Лексический анализОсновная задача лексического анализа разбить входной текст, состоящий из последовательности отдельных литер (символов), на последовательность лексем (слов)
Лексический анализ Лексический анализОсновная задача лексического анализа разбить входной текст, состоящий из последовательности отдельных Лексический анализ Любой символ входной последовательности может– принадлежать к какой-либо лексеме– принадлежать к разделителю (разделять лексемы) Лексический анализ В зависимости от ситуации одна и та же последовательность символов может Лексический анализ В некоторых случаях разделители между лексемами могут отсутствовать. if ( a > Лексический анализ Кроме определения границ лексем, при работе лексического анализатора требуется определить их Лексический анализ Лексический анализатор выдает последующим фазам компиляции информацию в зависимости от типа Лексический анализдля семантического анализа– пользовательские идентификаторы – значение лексемы;– числа – значение лексемы;– строки – значение лексемы; и т.д. Лексический анализдля всех последующих фаз– расположение лексемы в исходном тексте программы (имя файла, Лексический анализРегулярные множества На этапе лексического анализа удобно считать, что лексемы каждого типа Лексический анализФормальное определение регулярного множества Регулярное множество в алфавите V определяется рекурсивно следующим Лексический анализНеформальное определение регулярного множества Множество в алфавите V регулярно тогда и только Лексический анализРегулярные выражения Средством записи регулярных множеств являются регулярные выражения. Лексический анализФормальное определение регулярного выражения Регулярное выражение в алфавите V определяется рекурсивно следующим Лексический анализ Для краткости записи регулярных выражений используются следующие соглашения:– лишние скобки в регулярных Лексический анализПримеры регулярных выражений:a ( | a) | b обозначает множество {a, Лексический анализ Для каждого регулярного множества можно найти регулярное выражение, обозначающее это множество, Лексический анализ При записи регулярных выражений оказывается удобно дать им индивидуальное обозначение. Пример 1. Лексический анализ Пример 2. Регулярное выражение для множества вещественный чисел с плавающей запятой. Digit Лексический анализ Для определения принадлежности последовательности символов регулярному множеству (т.е. для реализации процедуры Лексический анализФормальное определение конечного автомата Конечным автоматом (КА) называют пятерку (Q, V, f, Лексический анализ Работа конечного автомата представляется в виде последовательности шагов. На каждом шаге автомат Лексический анализ Функция переходов зависит не только от текущего состояния, но и от Лексический анализ Работа конечного автомата продолжается до тех пор, пока на его вход Лексический анализ Множество цепочек, принимаемых (допускаемых) конечным автоматом, называют языком, распознаваемым (допускаемым) конечным автоматом. Лексический анализНеформальное определение конечного автомата Лексический анализ Лексический анализ Конечный автомат называют полностью определенным (всюду определенным), если в каждом его Лексический анализ Конечный автомат называют детерминированным, если для любой допустимой комбинации входного символа Лексический анализ Особенностью недетерминированных конечных автоматов (НКА) является то, что находясь в некотором Лексический анализ Большое практическое значение имеет следующая Теорема. Пусть М = (Q, V, f, Лексический анализ Доказательство (конструктивное). Дополним множество Q состояний ДКА новым состоянием: Q' = Q{q'}, Лексический анализ Новое состояние конечного автомата соответствует ошибочной ситуации (т.е. на вход автомата Лексический анализДиаграмма переходов конечного автомата Графически конечные автоматы принято изображать с помощью диаграмм Лексический анализ Пример 1. Диаграмма всюду определенного детерминированного конечного автомата Q = {A,B,C} V = {0,1} q0 = A Лексический анализ Пример 2. Диаграмма конечного автомата, принимающего множество положительных действительных чисел Различными цветами Лексический анализ Состояниям этого конечного автомата соответствуют: 1 – Начало числа 2 – Целая часть 3 Лексический анализ Функция переходов этого конечного автомата определяется следующим образом: Лексический анализ Способы программной реализации конечного автомата 1-й способ. С помощью подпрограммы Все состояния КА Лексический анализ Подпрограмма, реализующая функцию переходов конечного автомата, будет иметь следующую структуру: Лексический анализ Для проверки входной последовательности символов достаточно нужное число раз вызвать функцию Лексический анализ Затем следует определить (например, с помощью отдельной логической функции), является ли Лексический анализ 2-й способ. С помощью набора объектов Все состояния КА могут быть описаны Лексический анализ Иерархию классов удобно начать с абстрактного класса: abstract class AbstractState { Лексический анализ Для каждого состояния или группы состояний КА следует описать конкретные классы, Лексический анализ Процедура анализа последовательности символов будет иметь вид: AbstractState state = new StartState(); for(int i=0;i Лексический анализ Использование объектно-ориентированного программирования при реализации конечного автомата имеет ряд преимуществ. Основное из Лексический анализТаблично управляемый конечный автомат Один из способов построения конечного автомата заключается в Лексический анализМинимизация конечного автомата Полная таблица переходов КА может быть очень большой, поэтому Лексический анализ1 шаг Множество состояний КА делится на две группы: – множество заключительных состояний; – множество всех остальных состояний. Лексический анализ2 шаг Каждая группа из получившего разбиения делится на подгруппы по следующему Лексический анализ3 шаг Заменить исходное разбиение на новое. Шаги 2–3 должны повторяться до тех Лексический анализ4 шаг Новый конечный автомат формируется следующим образом:– каждая группа получившегося разбиения становится Лексический анализ Рассмотрим реализацию описанного алгоритма на примере следующего конечного автомата. Лексический анализ Шаг 1. Начальное разбиение множества состояний будет таким: G1 = { 1 Лексический анализ Шаг 4. В результате получим КА с 3 состояниями Лексический анализ Построение конечного автомата по регулярному выражению Другой способ автоматизации построения лексических анализаторов Лексический анализ На каждом шаге построения строящийся автомат имеет в точности одно заключительное
Слайды презентации

Слайд 2 Лексический анализ
Основная задача лексического анализа
разбить входной текст, состоящий

Лексический анализОсновная задача лексического анализа разбить входной текст, состоящий из последовательности

из последовательности отдельных литер (символов), на последовательность лексем (слов)

Слайд 3 Лексический анализ
Любой символ входной последовательности может

– принадлежать к какой-либо

Лексический анализ Любой символ входной последовательности может– принадлежать к какой-либо лексеме– принадлежать к разделителю (разделять лексемы)

лексеме
– принадлежать к разделителю (разделять лексемы)


Слайд 4 Лексический анализ
В зависимости от ситуации одна и та

Лексический анализ В зависимости от ситуации одна и та же последовательность символов

же последовательность символов может быть и частью лексемы, и

частью разделителя.

if (a>b) /* if */

лексема разделитель

Слайд 5 Лексический анализ
В некоторых случаях разделители между лексемами могут

Лексический анализ В некоторых случаях разделители между лексемами могут отсутствовать. if ( a

отсутствовать.

if ( a > b ) a -= b

; else b -= a ;
if(a>b)a-=b;else b-=a;

Слайд 6 Лексический анализ
Кроме определения границ лексем, при работе лексического

Лексический анализ Кроме определения границ лексем, при работе лексического анализатора требуется определить

анализатора требуется определить их тип:

– идентификаторы, в т.ч.
– ключевые слова; –

пользовательские идентификаторы;
– пунктуаторы;
– числа;
– строки;
и т.д.

Слайд 7 Лексический анализ
Лексический анализатор выдает последующим фазам компиляции информацию

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

в зависимости от типа лексемы:

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

– ключевые слова –

значение лексемы;
– пользовательские идентификаторы – тип лексемы;
– пунктуаторы – значение лексемы;
– числа – тип лексемы;
– строки – тип лексемы;
и т.д.

Слайд 8 Лексический анализ
для семантического анализа

– пользовательские идентификаторы – значение лексемы;
– числа

Лексический анализдля семантического анализа– пользовательские идентификаторы – значение лексемы;– числа – значение лексемы;– строки – значение лексемы; и т.д.

– значение лексемы;
– строки – значение лексемы;
и т.д.

Слайд 9 Лексический анализ
для всех последующих фаз

– расположение лексемы в исходном

Лексический анализдля всех последующих фаз– расположение лексемы в исходном тексте программы (имя

тексте программы (имя файла, номер строки, позиция в строке)

(для

локализации синтаксических ошибок и ошибок времени выполнения)

Слайд 10 Лексический анализ
Регулярные множества

На этапе лексического анализа удобно считать,

Лексический анализРегулярные множества На этапе лексического анализа удобно считать, что лексемы каждого

что лексемы каждого типа являются элементами отдельных языков, называемым

регулярными множествами.

Слайд 11 Лексический анализ
Формальное определение регулярного множества
Регулярное множество в алфавите

Лексический анализФормальное определение регулярного множества Регулярное множество в алфавите V определяется рекурсивно

V определяется рекурсивно следующим образом:
(1)  (пустое множество) – регулярное

множество в алфавите V;
(2) {} – регулярное множество в алфавите V ( – пустая цепочка);
(3) {a} – регулярное множество в алфавите V для каждого aV;
(4) если P и Q – регулярные множества в алфавите V, то регулярными являются и множества
(а) PQ (объединение),
(б) PQ (конкатенация, т.е. множество {pq | p  P, q  Q}),
(в) P* (итерация: P* = );

(5) ничто другое не является регулярным множеством в алфавите V.

Слайд 12 Лексический анализ
Неформальное определение регулярного множества

Множество в алфавите V

Лексический анализНеформальное определение регулярного множества Множество в алфавите V регулярно тогда и

регулярно тогда и только тогда, когда оно
– ,
– {},
– {a}, где

a  V,
– его можно получить из этих множеств применением конечного числа операций объединения, конкатенации и итерации.

Слайд 13 Лексический анализ
Регулярные выражения

Средством записи регулярных множеств являются регулярные

Лексический анализРегулярные выражения Средством записи регулярных множеств являются регулярные выражения.

выражения.

Слайд 14 Лексический анализ
Формальное определение регулярного выражения
Регулярное выражение в алфавите

Лексический анализФормальное определение регулярного выражения Регулярное выражение в алфавите V определяется рекурсивно

V определяется рекурсивно следующим образом:
(1)  – регулярное выражение, обозначающее

множество ;
(2)  – регулярное выражение, обозначающее множество {};
(3) a – регулярное выражение, обозначающее множество {a};
(4) если p и q – регулярные выражения, обозначающие регулярные множества P и Q соответственно, то
(а) (p|q) – регулярное выражение, обозначающее регулярное множество PQ,
(б) (pq) – регулярное выражение, обозначающее регулярное множество PQ,
(в) (p*) – регулярное выражение, обозначающее регулярное множество P*;
(5) ничто другое не является регулярным выражением в алфавите V.

Слайд 15 Лексический анализ
Для краткости записи регулярных выражений используются следующие

Лексический анализ Для краткости записи регулярных выражений используются следующие соглашения:– лишние скобки в

соглашения:

– лишние скобки в регулярных выражениях опускаются с учетом приоритета

операций: 1. операция итерации (наивысший приоритет) 2. операция конкатенации 3. операция объединения (наименьший приоритет).
– запись p+ обозначает выражение pp*

Например: (a | ((ba)(a*)))  a | ba+

Слайд 16 Лексический анализ
Примеры регулярных выражений:
a ( | a) |

Лексический анализПримеры регулярных выражений:a ( | a) | b обозначает множество

b обозначает множество {a, b, aa};
a (a | b) * обозначает

множество всевозможных цепочек, состоящих из a и b, начинающихся с a;
(a | b)* (a | b) (a | b )* обозначает множество всех непустых цепочек, состоящих из a и b, т.е. множество {a, b}+;
( (0 | 1) (0 | 1) (0 | 1) )* обозначает множество всех цепочек, состоящих из нулей и единиц, длины которых делятся на 3.

Слайд 17 Лексический анализ
Для каждого регулярного множества можно найти регулярное

Лексический анализ Для каждого регулярного множества можно найти регулярное выражение, обозначающее это

выражение, обозначающее это множество, и наоборот.

Для каждого регулярного

множества существует бесконечно много обозначающих его регулярных выражений.

Слайд 18 Лексический анализ
При записи регулярных выражений оказывается удобно дать

Лексический анализ При записи регулярных выражений оказывается удобно дать им индивидуальное обозначение. Пример

им индивидуальное обозначение.

Пример 1. Регулярное выражение для множества идентификаторов.

Letter

= a | b | c | ... | x | y | z
Digit = 0 | 1 | ... | 9
Identifier = Letter ( Letter | Digit )*

Слайд 19 Лексический анализ
Пример 2. Регулярное выражение для множества вещественный

Лексический анализ Пример 2. Регулярное выражение для множества вещественный чисел с плавающей

чисел с плавающей запятой.

Digit = 0 | 1 |

... | 9
Integer = Digit +
Fraction = .Integer | 
Exponent = (E(+ | – | )Integer) | 
Number = Integer Fraction Exponent

Слайд 20 Лексический анализ
Для определения принадлежности последовательности символов регулярному множеству

Лексический анализ Для определения принадлежности последовательности символов регулярному множеству (т.е. для реализации

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

конечные автоматы.

Слайд 21 Лексический анализ
Формальное определение конечного автомата

Конечным автоматом (КА) называют

Лексический анализФормальное определение конечного автомата Конечным автоматом (КА) называют пятерку (Q, V,

пятерку (Q, V, f, q0, F), где
Q – конечное множество

состояний автомата;
V – конечное множество допустимых входных символов (алфавит автомата);
f – функция переходов, отображающая декартово произведение множеств VQ во множество подмножеств Q:
f(a, q)=R, aV, qQ, RQ;
q0 – начальное состояние автомата, q0Q;
F – непустое множество заключительных состояний автомата, FQ, F.

Слайд 22 Лексический анализ
Работа конечного автомата представляется в виде последовательности

Лексический анализ Работа конечного автомата представляется в виде последовательности шагов. На каждом шаге

шагов.

На каждом шаге автомат находится в одном из своих

состояний qQ, называемым текущим состоянием. В начале работы автомат всегда находится в начальном состоянии q0.

На следующем шаге он может перейти в другое состояние или остаться в текущем. То, в какое состояние автомат перейдет на следующем шаге работы, определяет функция переходов f.

Слайд 23 Лексический анализ
Функция переходов зависит не только от текущего

Лексический анализ Функция переходов зависит не только от текущего состояния, но и

состояния, но и от того, какой символ из алфавита

V был подан на вход автомата.

Значением функции переходов f является некоторое множество следующих состояний автомата.

Конечный автомат может перейти в любое из этих состояний.

Слайд 24 Лексический анализ
Работа конечного автомата продолжается до тех пор,

Лексический анализ Работа конечного автомата продолжается до тех пор, пока на его

пока на его вход поступают символы.

Если после окончания работы

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

Слайд 25 Лексический анализ
Множество цепочек, принимаемых (допускаемых) конечным автоматом, называют

Лексический анализ Множество цепочек, принимаемых (допускаемых) конечным автоматом, называют языком, распознаваемым (допускаемым) конечным автоматом.

языком, распознаваемым (допускаемым) конечным автоматом.


Слайд 26 Лексический анализ
Неформальное определение конечного автомата



Лексический анализНеформальное определение конечного автомата

Слайд 27 Лексический анализ

Лексический анализ

Слайд 28 Лексический анализ
Конечный автомат называют полностью определенным (всюду определенным),

Лексический анализ Конечный автомат называют полностью определенным (всюду определенным), если в каждом

если в каждом его возможном состоянии функция перехода определена

для всех возможных входных символов:

aV qQ  f(a, q)=R, RQ.

Слайд 29 Лексический анализ
Конечный автомат называют детерминированным, если для любой

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

допустимой комбинации входного символа и текущего состояния значение функции

переходов содержит не более одного следующего состояния.
aV qQ |f(a, q)|1

В противном случае конечный автомат называют недетерминированным.
 aV  qQ |f(a, q)|>1

Слайд 30 Лексический анализ
Особенностью недетерминированных конечных автоматов (НКА) является то,

Лексический анализ Особенностью недетерминированных конечных автоматов (НКА) является то, что находясь в

что находясь в некотором состоянии и получая на входе

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

Непосредственная практическая реализация НКА затруднительна. Однако можно построить ДКА, распознающий тот же самый язык, что и НКА.

Слайд 31 Лексический анализ
Большое практическое значение имеет следующая

Теорема. Пусть М =

Лексический анализ Большое практическое значение имеет следующая Теорема. Пусть М = (Q, V,

(Q, V, f, q0, F) – детерминированный конечный автомат,

не являющийся всюду определенным.
Тогда существует всюду определенный детерминированный конечный автомат М'=(Q',V, f ',q0, F), такой что L(M) = L'(M').

Слайд 32 Лексический анализ
Доказательство (конструктивное).

Дополним множество Q состояний ДКА новым

Лексический анализ Доказательство (конструктивное). Дополним множество Q состояний ДКА новым состоянием: Q' =

состоянием: Q' = Q{q'}, q'Q.

Определим новую функцию f '

переходов ДКА следующим образом:
– f '(a, q) = f (a, q), если f (a, q)  
– f '(a, q) = {q' }, если f (a, q) = 
– f '(a, q' ) = {q' }

Легко показать, что построенный таким образом автомат допускает тот же самый язык.

Слайд 33 Лексический анализ
Новое состояние конечного автомата соответствует ошибочной ситуации

Лексический анализ Новое состояние конечного автомата соответствует ошибочной ситуации (т.е. на вход

(т.е. на вход автомата поступил недопустимый в данном состоянии

символ).

Слайд 34 Лексический анализ
Диаграмма переходов конечного автомата

Графически конечные автоматы принято

Лексический анализДиаграмма переходов конечного автомата Графически конечные автоматы принято изображать с помощью

изображать с помощью диаграмм переходов.

Диаграмма переходов конечного автомата

– это направленный граф, вершины которого помечены символами состояний конечного автомата, и содержащий помеченные дуги, описывающие допустимые переходы, т.е. на графе изображается дуга (p, q), помеченная символом aV, если q  f(p, a).

Слайд 35 Лексический анализ
Пример 1. Диаграмма всюду определенного детерминированного конечного

Лексический анализ Пример 1. Диаграмма всюду определенного детерминированного конечного автомата Q = {A,B,C} V = {0,1} q0 = A

автомата

Q = {A,B,C}
V = {0,1}
q0 = A

Слайд 36 Лексический анализ
Пример 2. Диаграмма конечного автомата, принимающего множество

Лексический анализ Пример 2. Диаграмма конечного автомата, принимающего множество положительных действительных чисел Различными

положительных действительных чисел







Различными цветами показаны различные состояния конечного автомата:

начальное, промежуточные, заключительные

Слайд 37 Лексический анализ
Состояниям этого конечного автомата соответствуют:

1 – Начало

Лексический анализ Состояниям этого конечного автомата соответствуют: 1 – Начало числа 2 – Целая

числа
2 – Целая часть
3 – Начало дробной части
4 –

Дробная часть
5 – Начало экспоненциальной части
6 – Начало модуля показателя
7 – Показатель

Слайд 38 Лексический анализ
Функция переходов этого конечного автомата определяется следующим

Лексический анализ Функция переходов этого конечного автомата определяется следующим образом:

образом:

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

1-й способ. С

Лексический анализ Способы программной реализации конечного автомата 1-й способ. С помощью подпрограммы Все состояния

помощью подпрограммы

Все состояния КА рекомендуется описать в виде перечисления:

enum

StateType { STATE_START, STATE_1, STATE_2, … };

Слайд 40 Лексический анализ
Подпрограмма, реализующая функцию переходов конечного автомата, будет

Лексический анализ Подпрограмма, реализующая функцию переходов конечного автомата, будет иметь следующую структуру:

иметь следующую структуру:
StateType f(StateType State, char c) {

switch(State) {
case STATE_START:
switch(c) {
case '1': return STATE_1;
case '2': return STATE_2;
...
default: return STATE_ERROR;
}
break;
case STATE_1: switch(c) {
...
}
break;
...
}
}

Слайд 41 Лексический анализ
Для проверки входной последовательности символов достаточно нужное

Лексический анализ Для проверки входной последовательности символов достаточно нужное число раз вызвать

число раз вызвать функцию переходов:

StateType State=START_STATE;
for(int i=0;i

{
State = f(State,stroka[i]);
}

Слайд 42 Лексический анализ
Затем следует определить (например, с помощью отдельной

Лексический анализ Затем следует определить (например, с помощью отдельной логической функции), является

логической функции), является ли состояние конечного автомата заключительным, если

да, то каким именно:

if ( isFinalState(State) ) {
// Ok!
switch(State) {
...
}
} else {
// Error!
}

Слайд 43 Лексический анализ
2-й способ. С помощью набора объектов

Все состояния

Лексический анализ 2-й способ. С помощью набора объектов Все состояния КА могут быть

КА могут быть описаны как отдельные объекты, у которых

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

Слайд 44 Лексический анализ
Иерархию классов удобно начать с абстрактного класса:

Лексический анализ Иерархию классов удобно начать с абстрактного класса: abstract class AbstractState

abstract class AbstractState {
abstract AbstractState getNextState (char c);

abstract boolean isFinalState();
}

Слайд 45 Лексический анализ
Для каждого состояния или группы состояний КА

Лексический анализ Для каждого состояния или группы состояний КА следует описать конкретные

следует описать конкретные классы, например:

class StartState extends AbstractState

{

AbstractState getNextState (char c) {
switch(c) {
case '1': return new StateOne();
case '2': return new StateTwo();
...
default: return new StateError();
}
}

boolean isFinalState() { return false; }

}

Слайд 46 Лексический анализ
Процедура анализа последовательности символов будет иметь вид:

Лексический анализ Процедура анализа последовательности символов будет иметь вид: AbstractState state = new StartState(); for(int i=0;i

AbstractState state = new StartState();

for(int i=0;i

}

if (state.isFinalState()) {
// Ok!
} else {
// Error!
}

Слайд 47 Лексический анализ
Использование объектно-ориентированного программирования при реализации конечного автомата

Лексический анализ Использование объектно-ориентированного программирования при реализации конечного автомата имеет ряд преимуществ. Основное

имеет ряд преимуществ.

Основное из них: значительно упрощается процесс добавления

нового состояния КА (достаточно описать новый класс-состояние и внести изменение в те классы, из которых появляются новые переходы).

Слайд 48 Лексический анализ
Таблично управляемый конечный автомат
Один из способов построения

Лексический анализТаблично управляемый конечный автомат Один из способов построения конечного автомата заключается

конечного автомата заключается в использовании таблично заданной функции переходов.

Основная

идея программной реализации таблично управляемого конечного автомата заключается в следующей схеме:

состояние' = таблица[состояние][символ]

Слайд 49 Лексический анализ
Минимизация конечного автомата
Полная таблица переходов КА может

Лексический анализМинимизация конечного автомата Полная таблица переходов КА может быть очень большой,

быть очень большой, поэтому обычно используют различные алгоритмы минимизации.

Все

алгоритмы минимизации основаны на объединении нескольких различных состояний КА в одно.

Слайд 50 Лексический анализ
1 шаг
Множество состояний КА делится на две

Лексический анализ1 шаг Множество состояний КА делится на две группы: – множество заключительных состояний; – множество всех остальных состояний.

группы:
– множество заключительных состояний;
– множество всех остальных состояний.

Слайд 51 Лексический анализ
2 шаг
Каждая группа из получившего разбиения делится

Лексический анализ2 шаг Каждая группа из получившего разбиения делится на подгруппы по

на подгруппы по следующему правилу

в одну подгруппу включаются такие

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

Слайд 52 Лексический анализ
3 шаг
Заменить исходное разбиение на новое.

Шаги 2–3

Лексический анализ3 шаг Заменить исходное разбиение на новое. Шаги 2–3 должны повторяться до

должны повторяться до тех пор, пока разбиение на подгруппы

не перестанет изменятся.


Слайд 53 Лексический анализ
4 шаг
Новый конечный автомат формируется следующим образом:
– каждая

Лексический анализ4 шаг Новый конечный автомат формируется следующим образом:– каждая группа получившегося разбиения

группа получившегося разбиения становится состоянием нового КА;
– группа, содержащая начальное

состояние исходного КА, становится исходным состоянием нового КА;
– группы, содержащие заключительные состояния исходного КА, становятся заключительными состояниеми нового КА;
– функция переходов определяется очевидным образом.

Слайд 54 Лексический анализ
Рассмотрим реализацию описанного алгоритма на примере следующего

Лексический анализ Рассмотрим реализацию описанного алгоритма на примере следующего конечного автомата.

конечного автомата.

Слайд 55 Лексический анализ
Шаг 1. Начальное разбиение множества состояний будет

Лексический анализ Шаг 1. Начальное разбиение множества состояний будет таким: G1 = {

таким:
G1 = { 1 } G2 = { 2, 3,

4, 5 }

Шаг 2. Множество G2 нужно разбить на две подгруппы: { 2, 3 } и { 4, 5 }

Шаг 3. Новое разбиение будет таким:
G1 = { 1 } G2 = { 2, 3 } G3 = { 4, 5 }

Выполнение еще одной итерации не приведет к изменению разбиения.

Слайд 56 Лексический анализ
Шаг 4. В результате получим КА с

Лексический анализ Шаг 4. В результате получим КА с 3 состояниями

3 состояниями

Слайд 57 Лексический анализ
Построение конечного автомата по регулярному выражению

Другой способ

Лексический анализ Построение конечного автомата по регулярному выражению Другой способ автоматизации построения лексических

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

Основная

идея заключается в построении композиции конечных автоматов, соответствующих подвыражениям исходного регулярного выражения.
  • Имя файла: leksicheskiy-analiz.pptx
  • Количество просмотров: 73
  • Количество скачиваний: 0
- Предыдущая Композиторы - романтики
Следующая - Правильные многогранники и их построение

Похожие презентации

Аилантис от идеи ...Презентация Microsoft PowerPoint Аилантис от идеи ...Презентация Microsoft PowerPoint 72
Внимание заменяем числа словами презентация к уроку (1 класс) Внимание заменяем числа словами презентация к уроку (1 класс) 99
Правила поведения дома Правила поведения дома 107
Adoption. auf jeden fall! Adoption. auf jeden fall! 70
БиографияФранческо Растрелли БиографияФранческо Растрелли 103
Пошаговое изготовление фликера презентация Пошаговое изготовление фликера презентация 102
Советская модель тоталитаризма Советская модель тоталитаризма 105
Посттравматические стрессовые расстройства Посттравматические стрессовые расстройства 94
Презентация к внеклассному мероприятию по профессиям часть 3 презентация к уроку (4 класс) Презентация к внеклассному мероприятию по профессиям часть 3 презентация к уроку (4 класс) 86
Презентация ЛЕГОтехнологии презентация к уроку по конструированию, ручному труду Презентация ЛЕГОтехнологии презентация к уроку по конструированию, ручному труду 77
Основы муниципального управления Основы муниципального управления 121
foto zanyatiya foto zanyatiya 106
Характеристика предприятий общественного питания Орловской области Характеристика предприятий общественного питания Орловской области 125
Студенческая жизнь Студенческая жизнь 80
ПК 4.4. Педагогические разработки методическая разработка ПК 4.4. Педагогические разработки методическая разработка 115
Организация предметно-пространственной развивающей среды в музыкальном зале ДОУ (презентация) презентация по теме Организация предметно-пространственной развивающей среды в музыкальном зале ДОУ (презентация) презентация по теме 114
umk nachalnaya shkola 21 veka umk nachalnaya shkola 21 veka 83
Тема выпускной квалификационной работы Тема выпускной квалификационной работы 72
Балто Балто 107
Презентация Сюжетно - ролевая игра с неоформленным материалом презентация к уроку (средняя, старшая группа) Презентация Сюжетно - ролевая игра с неоформленным материалом презентация к уроку (средняя, старшая группа) 24
Модификации сухожильных швов Модификации сухожильных швов 83
Презентация по правоведению на тему Знай свои права! Презентация по правоведению на тему Знай свои права! 26
Первые проблемы подросткового периода. презентация к уроку (4 класс) Первые проблемы подросткового периода. презентация к уроку (4 класс) 92
День матери День матери 77
Презентация. Итоговая практико-значимая работа Тема: Формирование представлений о домашних животных у младших дошкольников материал Презентация. Итоговая практико-значимая работа Тема: Формирование представлений о домашних животных у младших дошкольников материал 122
Шехтель, Фёдор Осипович Шехтель, Фёдор Осипович 76
Здоровьесберегающие технологии в начальной школе (часть 2) Здоровьесберегающие технологии в начальной школе (часть 2) 89
Презентация Игровые технологии презентация Презентация Игровые технологии презентация 128
Презентация Классификация живых организмов Презентация Классификация живых организмов 163
Супермаркет часть 6 Супермаркет часть 6 74