Лексический анализ. Регулярное выражение для множества идентификаторов. Алгоритм разбора

Лексический анализ Лексический анализ Лексический анализ Лексический анализ Лексический анализ Регулярные выражения ∅ – регулярное выражение, обозначающее множество ∅; e – регулярное выражение, обозначающее множество {e}; a – регулярное выражение, обозначающее множество {a}; если p и q – регулярные выражения, обозначающие регулярные множества P и Q соответственно, то (а) (p|q) – регулярное выражение, обозначающее регулярное множество P ∪Q, (б) (pq) – регулярное выражение, обозначающее регулярное мно- жество P Q, (в) (p∗) – регулярное выражение, обозначающее регулярное множество P ∗; Лемма. Пусть p, q и r - регулярные выражения. Тогда справедливы следующие соотношения: p|q = q|p ; ● {*}∅* = e ; ● p|(q|r) = (p|q)|r ; ● p(qr) = (pq)r ; ● p(q|r) = pq|pr ; ● (p|q)r = pr|qr ; ● pe = ep = p ; ● ∅p = p∅ = ∅ ; ● p* = p|p* ; ● (p*)* = p* ; ● p|p = p ; ● p|∅ = p ; ● Регулярное выражение для множества идентификаторов. Letter = a|и|c|...|x|y|z Digit = 0|1|...|9 Identifier = Letter(Letter|Digit)* Регулярное выражение для множества чисел в десятичной записи. Digit = 0|1|...|9 Integer = Digit+ Fraction = .Integer|e Exponent = (E(+|-|e)Integer)|e Number = Integer Fraction Exponent Регулярные выражения Алгоритм разбора 1) Первый символ исходной цепочки α1,α2,... αn┴ заменяется нетерминалом A, для которого в грамматике есть правило вывода A →a1 (другими словами, производим «свёртку» терминала a1 к нетерминалу A); 2) затем многократно (до тех пор, пока не считаем признак конца цепочки) выполняем следующие шаги: полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа от него очередной терминал ai исходной цепочки заменяем нетерминалом B G ({a, b, ⊥}, {S, A, B, C}, P, S) P: S→ C b ┴ A B S A – C – B C – – S – – – a C→ Ab | Ba A →a | Ca B→ b | Cb C a b C A B S A – C – B C – – S – – – Диаграмма свертки При работе этого алгоритма возможны следующие ситуации 1) прочитана вся цепочка; на каждом шаге находилась единственная нужная «свёртка»; на последнем шаге «свёртка» произошла к символу S. Это означает, что исходная цепочка a1a2...an⊥ϵ L (G); 2) прочитана вся цепочка; на каждом шаге находилась единственная нужная «свёртка»; на последнем шаге «свёртка» произошла к символу, отличному от S. Это означает, что исходная цепочка a1a2...an⊥не принадлежит L (G); 3) на некотором шаге не нашлось нужной «свёртки», т.е. для полученно-го на предыдущем шаге нетерминала A и расположенного непосред-ственно справа от него очередного терминала ai исходной цепочки не нашлось нетерминала B, для которого в грамматике было бы правило вывода B → Aai. Это означает, что исходная цепочка a1a2...an⊥не принадлежит L (G); 4) на некотором шаге работы алгоритма оказалось, что есть более одной подходящей «свёртки», т.е. в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями, и поэтому непонят-но, к какому из них производить «свёртку». Это говорит о недетерми-нированности разбора. Пример Пример Взаимодействие лексического анализатора и синтаксического Конечные автоматы Недетерменированный конечный автомат M = (Q, T, D, q0, F), где Q - конечное множество состояний, T - конечное множество допустимых входных символов (входной алфавит), D - функция переходов (отображающая множество во множество подмножеств множества Q), определяющая поведение управляющего устройства, q0 ϵ Q - начальное состояние управляющего устройства; F Q - множество заключительных состояний. Определения Конфигурацией M = (Q, T, D, q0, F) (q, w) QxT*, Конфигурация (q0, w) называется начальной, конфигурация (q, e), где q ϵ F - заключительной (или допускающей). Тактом автомата М определяется├ : если p ϵ D(q, a), где a ϵ T U{e}, то (q, aw) ├ (p, w) для всех w ϵT*. ├+ и (├*) Определения Автомат M допускает цепочку w, если (q0, w)├*(q, e) для некоторого q ϵ F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество входных цепочек, допускаемых автоматом M. Т.е. НКА (a|b)*abb Таблица переходов для НКА НКА принимающий аа*|bb* Детерминированный конечный автомат ДКА ● Пусть M = (Q, T, D, q0, F) - НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие два условия: 1.D(q, e) = ∅ для любого qϵ Q, и 2.D(q, a) содержит не более одного элемента для любых q ϵ Q и a ϵ T. L = L(r), где r = (a|b)*a(a|b)(a|b). ● НКА M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}}, ● где функция переходов D определяется так: ● D(1, a) = {1, 2}, ● D(3, a) = {4}, ● D(2, a) = {3}, ● D(3, b) = {4}, ● D(2, b) = {3}. M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b},D,1, {3, 5, 6, 8}}, ● где функция переходов D определяется так: ● D(5, b) = 6, ● D(5, a) = 8, ● D(1, a) = 2, ● D(1, b) = 1, ● D(6, a) = 2 ● D(2, a) = 4 ● D(6, b) = 1, ● D(2, b) = 7, ● D(7, a) = 8, ● D(3, a) = 3, ● ● D(3, b) = 5, D(7, b) = 6, ● D(8, a) = 4, ● D(8, b) = 7. ● ● D(4, a) = 3, D(4, b) = 5, НКА и ДКА Диаграмма автомата, допускающего множество чисел в десятичной записи Алгоритмы построения КА ● 1. для выражения ε ● ● ● ● Для выражения ● a ϵТ ● s|t ● st s* Построение детерминированного конечного автомата по недетерминированному ● Вход. НКА M = (Q, T, D, q0, F). ● Выход. ДКА M' = (Q', T, D', q0', F'), такой что L(M) = L(M'). ● ● Метод. Каждое состояние результирующего ДКА - это некоторое множество состояний исходного НКА. В алгоритме будут использоваться следующие функции: 1.e-closure(R) (R Q) - множество состояний НКА, достижимых из состояний, входящих в R, посредством только переходов по e, т.е. множество ● ● ● move(R, a) (R Q) - множество состояний НКА, в которые есть переход на входе a для состояний из R, т.е. множество Построение ДКА по регулярным выражениям