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

Содержание

• 
  Слайд 1

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

• 
  Слайд 2
  

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

• 
  Слайд 3
  

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

• 
  Слайд 4
  

  4 В зависимости от ситуации одна и та же последовательность символов может быть и частью лексемы, и частью разделителя. if (a>b)/* if */ лексема разделитель

• 
  Слайд 5
  

  5 В некоторых случаях разделители между лексемами могут отсутствовать. if (a>b)a -= b ;else b -= a ; if(a>b)a-=b;else b-=a;

• 
  Слайд 6
  

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

• 
  Слайд 7
  

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

• 
  Слайд 8
  

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

• 
  Слайд 9
  

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

• 
  Слайд 10
  

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

• 
  Слайд 11
  

  11 Формальное определение регулярного множества Регулярное множество в алфавите 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
  

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

• 
  Слайд 13
  

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

• 
  Слайд 14
  

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

• 
  Слайд 15
  

  15 Для краткости записи регулярных выражений используются следующие соглашения: – лишние скобки в регулярных выражениях опускаются с учетом приоритета операций: 1. операция итерации (наивысший приоритет) 2. операция конкатенации 3. операция объединения (наименьший приоритет). – запись p+ обозначает выражение pp* Например: (a | ((ba)(a*))) a | ba+

• 
  Слайд 16
  

  16 Примеры регулярных выражений: a ( | a) | 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
  

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

• 
  Слайд 18
  

  18 При записи регулярных выражений оказывается удобно дать им индивидуальное обозначение. Пример 1. Регулярное выражение для множества идентификаторов. Letter = a | b | c | ... | x | y | z Digit = 0 | 1 | ... | 9 Identifier = Letter(Letter | Digit)*

• 
  Слайд 19
  

  19 Пример 2. Регулярное выражение для множества вещественный чисел с плавающей запятой. Digit = 0 | 1 | ... | 9 Integer = Digit+ Fraction = .Integer |  Exponent = (E(+ | – | )Integer) |  Number = IntegerFractionExponent

• 
  Слайд 20
  

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

• 
  Слайд 21
  

  21 Формальное определение конечного автомата Конечным автоматом (КА) называют пятерку(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
  

  22 Работа конечного автомата представляется в виде последовательности шагов. На каждом шаге автомат находится в одном из своих состояний qQ, называемым текущим состоянием. В начале работы автомат всегда находится в начальном состоянии q0. На следующем шаге он может перейти в другое состояние или остаться в текущем. То, в какое состояние автомат перейдет на следующем шаге работы, определяет функция переходов f.

• 
  Слайд 23
  

  23 Функция переходов зависит не только от текущего состояния, но и от того, какой символ из алфавита V был подан на вход автомата. Значением функции переходов fявляется некоторое множество следующих состояний автомата. Конечный автомат может перейти в любое из этих состояний.

• 
  Слайд 24
  

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

• 
  Слайд 25
  

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

• 
  Слайд 26
  

  26 Неформальное определение конечного автомата

• 
  Слайд 27
  

  27

• 
  Слайд 28
  

  28 Конечный автомат называют полностью определенным (всюду определенным), если в каждом его возможном состоянии функция перехода определена для всех возможных входных символов: aV qQ  f(a, q)=R, RQ.

• 
  Слайд 29
  

  29 Конечный автомат называют детерминированным, если для любой допустимой комбинации входного символа и текущего состояния значение функции переходов содержит не более одного следующего состояния. aV qQ |f(a, q)|1 В противном случае конечный автомат называют недетерминированным.  aV  qQ |f(a, q)|>1

• 
  Слайд 30
  

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

• 
  Слайд 31
  

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

• 
  Слайд 32
  

  32 Доказательство (конструктивное). Дополним множество 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
  

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

• 
  Слайд 34
  

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

• 
  Слайд 35
  

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

• 
  Слайд 36
  

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

• 
  Слайд 37
  

  37 Состояниям этого конечного автомата соответствуют: 1 – Начало числа 2 – Целая часть 3 – Начало дробной части 4 – Дробная часть 5 – Начало экспоненциальной части 6 – Начало модуля показателя 7 – Показатель

• 
  Слайд 38
  

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

• 
  Слайд 39
  

  39 Способы программной реализации конечного автомата 1-й способ. С помощью подпрограммы Все состояния КА рекомендуется описать в виде перечисления: enum StateType { STATE_START, STATE_1, STATE_2, … };

• 
  Слайд 40
  

  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
  

  41 Для проверки входной последовательности символов достаточно нужное число раз вызвать функцию переходов: StateType State=START_STATE; for(int i=0;i

• 
  Слайд 42
  

  42 Затемследует определить (например, с помощью отдельной логической функции), является ли состояние конечного автомата заключительным, если да, то каким именно: if ( isFinalState(State) ) { // Ok! switch(State) { ... } } else { // Error! }

• 
  Слайд 43
  

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

• 
  Слайд 44
  

  44 Иерархию классов удобно начать с абстрактного класса: abstract class AbstractState{ abstract AbstractState getNextState (char c); abstract boolean isFinalState(); }

• 
  Слайд 45
  

  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
  

  46 Процедура анализа последовательности символов будет иметь вид: AbstractStatestate = new StartState(); for(int i=0;i

• 
  Слайд 47
  

  47 Использование объектно-ориентированного программирования при реализации конечного автомата имеет ряд преимуществ. Основное из них: значительно упрощается процесс добавления нового состояния КА (достаточно описать новый класс-состояние и внести изменение в те классы, из которых появляются новые переходы).

• 
  Слайд 48
  

  48 Таблично управляемый конечный автомат Один из способов построения конечного автомата заключается в использовании таблично заданной функции переходов. Основная идея программной реализации таблично управляемого конечного автомата заключается в следующей схеме: состояние' = таблица[состояние][символ]

• 
  Слайд 49
  

  49 Минимизация конечного автомата Полная таблица переходов КА может быть очень большой, поэтому обычно используют различные алгоритмы минимизации. Все алгоритмы минимизации основаны на объединении нескольких различных состояний КА в одно.

• 
  Слайд 50
  

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

• 
  Слайд 51
  

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

• 
  Слайд 52
  

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

• 
  Слайд 53
  

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

• 
  Слайд 54
  

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

• 
  Слайд 55
  

  55 Шаг 1. Начальное разбиениемножества состояний будет таким: G1 = { 1 }G2 = { 2, 3, 4, 5 } Шаг 2. Множество G2нужно разбить на две подгруппы: { 2, 3 } и { 4, 5 } Шаг 3. Новое разбиение будет таким: G1 = { 1 }G2 = { 2, 3 }G3 = { 4, 5 } Выполнение еще одной итерации не приведет к изменению разбиения.

• 
  Слайд 56
  

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

• 
  Слайд 57
  

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

• 
  Слайд 58
  

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