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

Содержание слайда: ГЛАВА 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 Построение леволинейной грамматики на основе КА

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

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

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

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

Содержание слайда: 3.3 Регулярные языки и грамматики

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

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

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

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

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

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

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

Содержание слайда: 3.5 Матрица переходов КА

Содержание слайда: 3.5 Матрица переходов КА

Содержание слайда: 3.5 Матрица переходов КА

Содержание слайда: 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. Доказано, что для любого КА можно построить ДКА. Домашнее задание: Алгоритм преобразования произвольного КА к детерминированному виду.

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

Содержание слайда: 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

Содержание слайда: 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.

Содержание слайда: 3.7 Лексический анализатор

Содержание слайда: 3.7 Лексический анализатор

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

Содержание слайда: 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) – чтение из входного потока очередного символа и занесение его в с

Содержание слайда: 3.7 Лексический анализатор

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

Содержание слайда: 3.7 Лексический анализатор

Содержание слайда: 3.7 Лексический анализатор

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

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

Содержание слайда: 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}

Содержание слайда: 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

Содержание слайда: 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}

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

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

Содержание слайда: 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}

Содержание слайда: 3.8.2 Построение леволинейной грамматики на основе КА

Содержание слайда: 3.8.2 Построение леволинейной грамматики на основе КА V= {0,1,+,-, } Q = {S, A, B, H} q0 = H F= {S}