🗊Презентация Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 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}