Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3)

Нажмите для полного просмотра!

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №2

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №3

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №4

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №5

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №6

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №7

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №8

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №9

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №10

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №11

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №12

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №13

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №14

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №15

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №16

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №17

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №18

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №19

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №20

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №21

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №22

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №23

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №24

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №25

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №26

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №27

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №28

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №29

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №30

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №31

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №32

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №33

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №34

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №35

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №36

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №37

Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3), слайд №38

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3). Доклад-сообщение содержит 38 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ГЛАВА 3 3.1 Назначение и необходимость фазы лексического анализа 3.2 Транслитератор 3.3 Регулярные языки и грамматики 3.4 Конечные автоматы 3.4.1 Определение КА. 3.4.2 Диаграмма переходов (состояний) 3.5 Матрица переходов КА 3.6 Детерминированный и недерминированный автомат 3.7 Лексический анализатор 3.8 Связь регулярных грамматик КА 3.8.1 Построение КА на основе леволинейной грамматики 3.8.2 Построение леволинейной грамматики на основе КА

Слайд 2

Описание слайда:

3.1 Назначение и необходимость фазы лексического анализа Лексический анализ – первая фаза процесса трансляции, предназначенная для группировки символов входной цепочки в более крупные конструкции, называемые лексемами. Лексемы – минимальные несущие смысл объединения символов. С каждой лексемой связано два понятия: класс лексемы, определяющий общее название для категории элементов, обладающих общими свойствами значение лексемы, определяющее подстроку символов входной цепочки, соответствующих распознанному классу лексемы. В зависимости от класса, значение лексемы может быть преобразовано во внутреннее представление уже на этапе лексического анализа.

Слайд 3

Описание слайда:

3.1 Назначение и необходимость фазы лексического анализа Задачи, решаемые сканером (преимущества сканера): представление элементарных конструкций языка в более удобной внутренней форме уменьшение длины программы, за счет устранения из нее несущественных для дальнейшего анализа пробелов, комментариев, игнорируемых символов. один и тот же язык программирования может иметь различные внешние представления элементарных конструкций.

Слайд 4

Описание слайда:

3.2 Транслитератор Устройство, осуществляющее сопоставление класс с каждым отдельным символом, называется транслитератором. Наиболее типичными классами символов являются: буква; цифра; разделитель; игнорируемый; запрещенный; прочие.

Слайд 5

Описание слайда:

3.3 Регулярные языки и грамматики Пример. Классы лексем: идентификаторы; служебные слова (множество идентификаторов); целые числа, вещественные, строки (литералы); однолитерные разделители ('+', '-', '(', ')'...); двухлитерные разделители ('//', '/*', '*/', ':=') комментарии.

Слайд 6

Описание слайда:

3.3 Регулярные языки и грамматики

Слайд 7

Описание слайда:

3.3 Регулярные языки и грамматики Доказано, что класс регулярной и автоматной грамматики почти эквиваленты. Любую регулярную грамматику можно привести к автоматному виду. Домашнее задание: Алгоритм преобразования регулярной грамматики к автоматному виду

Слайд 8

Описание слайда:

3.4 Конечные автоматы ГЛАВА 3. Лексический анализ

Слайд 9

Описание слайда:

3.4.1 Определение КА Конечный автомат (КА) – это пятерка (Q, V, δ, q0, F), где: Q – конечное множество состояний; V – конечное множество допустимых входных символов (алфавит); δ – отображение множества Q  VT -> Q, определяющее поведение автомата; отображение δ часто называют функцией переходов; q0  Q – начальное состояние; F  Q – непустое множество конечных состояний.

Слайд 10

Описание слайда:

3.4.1 Определение КА Конечный автомат называется полностью определенным, если в каждом его состоянии определена функция перехода для каждого входного символа. Для a є V и q  Q определена δ (a, q)= R, R

Слайд 11

Описание слайда:

3.4.2 Диаграмма переходов (состояний) Граф переходов (дерево, диаграмма) – направленный помеченный граф с символами состояний конечного автомата в вершинах, в котором есть дуга (p,q) , помеченная символом a є V (p,q  Q), если в КА определена функция δ (a,p) и q  δ (a,p).

Слайд 12

Описание слайда:

3.5 Матрица переходов КА Каждая строка этой матрицы представляет состояние автомата, а каждый столбец соответствует возможному входному элементу. В ячейках матрицы указывается структура из трех полей: состояние функция которая выполняется при переходе из одного состояния в другое сообщение об ошибке

Слайд 13

Описание слайда:

3.5 Матрица переходов КА ::= | < десятичное целое с фиксированной точкой > ::= ::= | | ::= . ::= + | - ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Слайд 14

Описание слайда:

3.5 Матрица переходов КА

Слайд 15

Описание слайда:

3.5 Матрица переходов КА

Слайд 16

Описание слайда:

3.5 Матрица переходов КА

Слайд 17

Описание слайда:

3.6 Детерминированный и недерминированный автомат Конечный автомат (Q, V, δ, q0, F) называется детерминированным конечным автоматом (ДКА), если в каждом из его состояний для любого входного символа функция переходов содержит не более одного состояний. Для a є V, q  Q, r  Q, определена δ (a, q)= {r} В недетерминированном КА δ (a,q) = {r1,r2,...,rn} – означает, что из состояния q по входному символу a можно осуществить переход в любое из состояний ri, i = 1, 2, ... ,n. Доказано, что для любого КА можно построить ДКА. Домашнее задание: Алгоритм преобразования произвольного КА к детерминированному виду.

Слайд 18

Описание слайда:

3.7 Лексический анализатор Лексический анализатор – программа, которая используя набор сканеров, преобразует исходный текст программы во внутреннее представление и помещает определённую информацию в специальные таблицы. Типы лексем (сканеров): идентификаторы, служебные слова, литералы (или константы) и разделители. Каждой лексеме сопоставляется пара: (тип лексемы, указатель на инф. о ней)

Слайд 19

Описание слайда:

3.7 Лексический анализатор ::= PROGRAM VAR BEGIN END. ::= id ::= ; | ; ::= : ::= INTEGER ::= | , ::= | ; ::= | | | ::= := | + | - ::= | * | DIV ::= | | () ::= READ() ::= WRITE() ::= FOR DO ::= := TO ::= | BEGIN END ::= ::= | | ::= | ::= A | В | С|... | Z ::= 0 | 1 | 2 |...| 9

Слайд 20

Описание слайда:

3.7 Лексический анализатор PROGRAM STATS VAR SUM, SUMSQ, I, VALUE, MEAN, VARIANCE: INTEGER; BEGIN SUM := 0; SUMSQ := 0; FOR I 1 TO 100 DO BEGIN READ( VALUE ); SUM := SUM + VALUE; SUMSQ := SUMSQ + VALUE * VALUE; END; MEAN := SUM DIV 100; VARIANCE := SUMSQ DIV 100 - MEAN * MEAN; WRITE( MEAN, VARIANCE); END.

Слайд 21

Описание слайда:

3.7 Лексический анализатор

Слайд 22

Описание слайда:

3.7 Лексический анализатор

Слайд 23

Описание слайда:

3.7 Лексический анализатор Переменные: buf – буфер для накопления символов лексем; с – очередной входной символ; d – переменная для формирования числового значения константы; TW – таблица служебных слов ; TD – таблица ограничителей; TID – таблица идентификаторов; TNUM – таблица констант; tabl – имя типа таблиц; ptable – указатель на tabl.

Слайд 24

Описание слайда:

3.7 Лексический анализатор Функции: void clear (void) – очистить буффер buf, void add (void) – добавление символа с в конец буфера buf; int look (ptabl T) – поиск в таблице Т лексемы из буфера buf; результат – номер строки таблицы с информацией о лексеме либо 0, если лексемы нет в таблице; int putl (ptabl Т) – запись в таблицу Т лексемы из buf; результат – номер строки с информацией о лексеме; int puntnum(void) – запись в TNUM константы из d если ее там не было; результат – номер строки в таблице TNUM с информацией о константе-лексеме; void makelex (int k, int i) – формирование и вывод внутреннего представления лексемы; к – номер класса, i – номер в классе; void gc (void) – чтение из входного потока очередного символа и занесение его в с

Слайд 25

Описание слайда:

3.7 Лексический анализатор

Слайд 26

Описание слайда:

3.7 Лексический анализатор КА пользуясь набором сканера формирует набор лексем.

Слайд 27

Описание слайда:

3.7 Лексический анализатор

Слайд 28

Описание слайда:

3.7 Лексический анализатор

Слайд 29

Описание слайда:

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

Слайд 30

Описание слайда:

3.8.1 Построение КА на основе леволинейной грамматики Необходимо построить КА M(Q, V, δ, q0, F), по леволинейной грамматике G(VT, VN, P, S). 1) Множество входных символов строится на основании терминальных символов V=VT 2) Множество состояний автомата строится на основании множества нетерминальных символов. Каждому нетерминалу ставится в соответствие состояние автомата и добавляется еще одно начальное состояние. Q = VN U {H}

Слайд 31

Описание слайда:

3.8.1 Построение КА на основе леволинейной грамматики 3) Просматриваем все множество правил грамматики G. Если встречается правило вида A -> t, A єVN, t є VT, то функцию перехода добавляем состояние A. A є δ(H,t). Если A -> Bt, A,B є VN, t є VT, то A є δ(B,t). 4) Начальное состояние автомата q0=H. 5) Множество конечных состояний включает одно состояние, соответствующее начальному символу грамматики S. F={S}

Слайд 32

Описание слайда:

3.8.1 Построение КА на основе леволинейной грамматики Построить автомат M(Q, V, δ, q0, F) на основе имеющейся автоматной грамматики: G = ( {0,1}, {S,A,B}, P, S) P: S -> A0 | B1 A -> S1|1 B -> S0|0 L(G) = { (10 | 01)n, n>0} S => A0 => 10 S => A0 => S10 => B110 => 0110 S => B1 => 01 S => B1 => S01 =>A001 => 1001

Слайд 33

Описание слайда:

3.8.1 Построение КА на основе леволинейной грамматики Шаг 1. V = {0, 1} Шаг 2. Q = {S, A, B, H} Шаг 3. δ(A,0) = {S} δ(B,1) = {S} δ(S,1) = {A} δ(H,1) = {A} δ(S,0) = {B} δ(H,0) = {B} Шаг 4. q0 = H Шаг 5. F= {S}

Слайд 34

Описание слайда:

3.8.1 Построение КА на основе леволинейной грамматики

Слайд 35

Описание слайда:

3.8.2 Построение леволинейной грамматики на основе КА 1) Множество терминальных символов строится на основании входных символов VT=V 2) Множество нетерминалов грамматики G строится на основании множества состояний Q автомата за исключением начального состояния автомата VN = Q / {q0}

Слайд 36

Описание слайда:

3.8.2 Построение леволинейной грамматики на основе КА 3) Просматриваем функции переходов автомата M для всех возможных состояний из Q для всех входных символов из V. Если δ(A,t)={B1,B2, … Bn}, A,B є Q, t є V, 1A t 4) Если множество конечных состояний F автомата M содержит только одно состояние F={f0}, то начальным символом грамматики принимается нетерминал, соответствующий этому состоянию. Если множество заключительных состояний F={f1,f2,…,fn}, то S -> F1 | F2 | … | Fn VN = VN U {S}