Презентация Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 38 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3)
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:38 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:501.40 kB
- Просмотров:94
- Скачиваний:1
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
![ГЛАВА . Назначение и](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img0.jpg)
Содержание слайда: ГЛАВА 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 слайд
![. Назначение и необходимость](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img1.jpg)
Содержание слайда: 3.1 Назначение и необходимость фазы лексического анализа
Лексический анализ – первая фаза процесса трансляции, предназначенная для группировки символов входной цепочки в более крупные конструкции, называемые лексемами.
Лексемы – минимальные несущие смысл объединения символов. С каждой лексемой связано два понятия:
класс лексемы, определяющий общее название для категории элементов, обладающих общими свойствами
значение лексемы, определяющее подстроку символов входной цепочки, соответствующих распознанному классу лексемы. В зависимости от класса, значение лексемы может быть преобразовано во внутреннее представление уже на этапе лексического анализа.
№3 слайд
![. Назначение и необходимость](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img2.jpg)
Содержание слайда: 3.1 Назначение и необходимость фазы лексического анализа
Задачи, решаемые сканером (преимущества сканера):
представление элементарных конструкций языка в более удобной внутренней форме
уменьшение длины программы, за счет устранения из нее несущественных для дальнейшего анализа пробелов, комментариев, игнорируемых символов.
один и тот же язык программирования может иметь различные внешние представления элементарных конструкций.
№5 слайд
![. Регулярные языки и](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img4.jpg)
Содержание слайда: 3.3 Регулярные языки и грамматики
Пример. Классы лексем:
идентификаторы;
служебные слова (множество идентификаторов);
целые числа, вещественные, строки (литералы);
однолитерные разделители ('+', '-', '(', ')'...);
двухлитерные разделители ('//', '/*', '*/', ':=')
комментарии.
№9 слайд
![. . Определение КА Конечный](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img8.jpg)
Содержание слайда: 3.4.1 Определение КА
Конечный автомат (КА) – это пятерка (Q, V, δ, q0, F), где:
Q – конечное множество состояний;
V – конечное множество допустимых входных символов (алфавит);
δ – отображение множества Q VT -> Q, определяющее поведение автомата; отображение δ часто называют функцией переходов;
q0 Q – начальное состояние;
F Q – непустое множество конечных состояний.
№10 слайд
![. . Определение КА Конечный](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img9.jpg)
Содержание слайда: 3.4.1 Определение КА
Конечный автомат называется полностью определенным, если в каждом его состоянии определена функция перехода для каждого входного символа.
Для a є V и q Q определена δ (a, q)= R, R <= Q
Множество цепочек, допускаемых конечным автоматом, составляет определяемый им язык.
Два конечных автомата называются эквивалентными, если они определяют один и тот же язык.
№11 слайд
![. . Диаграмма переходов](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img10.jpg)
Содержание слайда: 3.4.2 Диаграмма переходов (состояний)
Граф переходов (дерево, диаграмма) – направленный помеченный граф с символами состояний конечного автомата в вершинах, в котором есть дуга (p,q) , помеченная символом a є V (p,q Q), если в КА определена функция δ (a,p) и q δ (a,p).
№12 слайд
![. Матрица переходов КА Каждая](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img11.jpg)
Содержание слайда: 3.5 Матрица переходов КА
Каждая строка этой матрицы представляет состояние автомата, а каждый столбец соответствует возможному входному элементу.
В ячейках матрицы указывается структура из трех полей:
состояние
функция которая выполняется при переходе из одного состояния в другое
сообщение об ошибке
№13 слайд
![. Матрица переходов КА lt](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img12.jpg)
Содержание слайда: 3.5 Матрица переходов КА
<десятичное целое с фиксированной точкой> ::=
<число с точкой> <цифра> |
< десятичное целое с
фиксированной точкой > <цифра>
<число с точкой> ::= <целое>
<десятичная точка>
<целое> ::= <знак> <целое> |
<цифра> | <целое> <цифра>
<десятичная точка> ::= .
<знак> ::= + | -
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
№17 слайд
![. Детерминированный и](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img16.jpg)
Содержание слайда: 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 слайд
![. Лексический анализатор](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img17.jpg)
Содержание слайда: 3.7 Лексический анализатор
Лексический анализатор – программа, которая используя набор сканеров, преобразует исходный текст программы во внутреннее представление и помещает определённую информацию в специальные таблицы.
Типы лексем (сканеров): идентификаторы, служебные слова, литералы (или константы) и разделители.
Каждой лексеме сопоставляется пара:
(тип лексемы, указатель на инф. о ней)
№19 слайд
![. Лексический анализатор lt](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img18.jpg)
Содержание слайда: 3.7 Лексический анализатор
<рrоg> ::= PROGRAM <prog_name> VAR <dec_list> BEGIN <stmt_ list> END.
<prog_name> ::= id
<dec_list> ::= <dec>; | <dec_list>; <dec>
<dec> ::= <id_list>:<type>
<type> ::= INTEGER
<id_list> ::= <id> | <id_list>, <id>
<stmt_list> ::= <stmt> | <stmt_list>; <stmt>
<stmt> ::= <assign> | <read> | <write> | <for>
<assign> ::= <id>:=<exp>
<exp> <term> | <exp>+<term> | <exp>-<term>
<term> ::= <factor> | <term>*<factor> | <term> DIV <factor>
<factor> ::= <id> | <int> | (<exp>)
<read> ::= READ(<id_list>)
<write>::= WRITE(<id_ list>)
<for> ::= FOR <index_ exp> DO <body>
<index_exp> ::= <id>:=<exp> TO <exp>
<body> ::= <stmt> | BEGIN <stmt_list> END
<id> ::= <id_name>
<id name> ::= <letter> | <id_name> <letter> | <id_name><digit>
<int> ::= <digit> | <int><digit>
<letter> ::= A | В | С|... | Z
<digit>::= 0 | 1 | 2 |...| 9
№20 слайд
![. Лексический анализатор](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img19.jpg)
Содержание слайда: 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.
№23 слайд
![. Лексический анализатор](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img22.jpg)
Содержание слайда: 3.7 Лексический анализатор
Переменные:
buf – буфер для накопления символов лексем;
с – очередной входной символ;
d – переменная для формирования числового значения константы;
TW – таблица служебных слов ;
TD – таблица ограничителей;
TID – таблица идентификаторов;
TNUM – таблица констант;
tabl – имя типа таблиц;
ptable – указатель на tabl.
№24 слайд
![. Лексический анализатор](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img23.jpg)
Содержание слайда: 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) – чтение из входного потока очередного символа и занесение его в с
№29 слайд
![. Связь регулярных грамматик](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img28.jpg)
Содержание слайда: 3.8 Связь регулярных грамматик КА
На основании имеющейся регулярной грамматики можно построить эквивалентный ей КА, и наоборот на основе КА можно построить эквивалентную ему грамматику.
Поскольку КА являются распознавателями регулярных языков, таким образом, построив по регулярной грамматике КА, решаем задачу разбора.
№30 слайд
![. . Построение КА на основе](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img29.jpg)
Содержание слайда: 3.8.1 Построение КА на основе леволинейной грамматики
Необходимо построить КА M(Q, V, δ, q0, F), по леволинейной грамматике G(VT, VN, P, S).
1) Множество входных символов строится на основании терминальных символов V=VT
2) Множество состояний автомата строится на основании множества нетерминальных символов. Каждому нетерминалу ставится в соответствие состояние автомата и добавляется еще одно начальное состояние.
Q = VN U {H}
№31 слайд
![. . Построение КА на основе](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img30.jpg)
Содержание слайда: 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 слайд
![. . Построение КА на основе](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img31.jpg)
Содержание слайда: 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
№35 слайд
![. . Построение леволинейной](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img34.jpg)
Содержание слайда: 3.8.2 Построение леволинейной грамматики на основе КА
1) Множество терминальных символов строится на основании входных символов
VT=V
2) Множество нетерминалов грамматики G строится на основании множества состояний Q автомата за исключением начального состояния автомата
VN = Q / {q0}
№36 слайд
![. . Построение леволинейной](/documents_6/c100a2790f86d9f7b29b01fba114e0b2/img35.jpg)
Содержание слайда: 3.8.2 Построение леволинейной грамматики на основе КА
3) Просматриваем функции переходов автомата M для всех возможных состояний из Q для всех входных символов из V.
Если δ(A,t)={B1,B2, … Bn}, A,B є Q, t є V, 1<i<=n,
то для всех состояний Bi выполняем следующее:
Если A= q0, то множество Bi -> t
Если A≠ q0, то множество Bi ->A t
4)
Если множество конечных состояний F автомата M содержит только одно состояние F={f0}, то начальным символом грамматики принимается нетерминал, соответствующий этому состоянию.
Если множество заключительных состояний F={f1,f2,…,fn},
то S -> F1 | F2 | … | Fn
VN = VN U {S}
Скачать все slide презентации Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3) одним архивом:
Похожие презентации
-
Генератор лексического анализатора и генератор синтаксического анализатора языков программирования. (Глава 6)
-
Синтаксический анализ языков программирования. Распознаватели. Задача разбора. (Глава 4)
-
Языковое дерево. Языки программирования машинного обучения
-
История развития языков программирования. Языки программирования
-
Генерация кода языков программирования. (Глава 5)
-
Теория формальных языков и грамматик. (Глава 2)
-
Проектирование трансляторов языков программирования. Схема работы компилятора. (Глава 1)
-
Этапы разработки программного обеспечения и языки программирования. (Глава 3)
-
Языки программирования QBasic и Turbo Pascal 7. 0
-
Базовые типы данных языков программирования высокого уровня