В.А. Серебряков - Теория и реализация языков программирования (1114953), страница 8
Текст из файла (страница 8)
п.).Таким образом, общая схема работы лексического анализатора такова.Сначала выделяется отдельная лексема (при этом, возможно, используются символы-разделители). Ключевые слова распознаются явным выделениемнепосредственно из текста, либо сначала выделяется идентификатор, а затемделается проверка на принадлежность его множеству ключевых слов.Если выделенная лексема является ограничителем, то этот ограничитель (точнее, некоторый его признак) выдается как результат лексического2 В.А. Серебряков34Глава 3. Лексический анализанализа.
Если выделенная лексема является ключевым словом, то выдаетсяпризнак соответствующего ключевого слова. Если выделенная лексема является идентификатором — выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексема принадлежиткакому-либо из других классов лексем (например, лексема представляет собой число, строку и т. п.), то выдается признак соответствующего класса,а значение лексемы сохраняется отдельно.Лексический анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу «дай лексему». В первомслучае (рис. 3.1, а) выходом анализатора является файл лексем, во втором— (рис.
3.1, б) лексема выдается при каждом обращении к анализатору (приэтом, как правило, признак класса лексемы возвращается как результат функции «лексический анализатор», а значение лексемы передается через глобальную переменную). С точки зрения обработки значений лексем, анализаторможет либо просто выдавать значение каждой лексемы, при этом построениетаблиц объектов (идентификаторов, строк, чисел и т.
п.) переносится на болеепоздние фазы, либо он может самостоятельно строить таблицы объектов.В этом случае в качестве значения лексемы выдается указатель на входв соответствующую таблицу.Рис. 3.1Работа лексического анализатора задается некоторым конечным автоматом. Однако непосредственное описание конечного автомата неудобно с практической точки зрения. Поэтому для задания лексического анализатора,как правило, используется либо регулярное выражение, либо праволинейнаяграмматика. Все три формализма (конечных автоматов, регулярных выражений и праволинейных грамматик) имеют одинаковую выразительную мощность.
В частности, по регулярному выражению или праволинейной грамматике можно сконструировать конечный автомат, распознающий тот же язык.3.1. Регулярные множества и выражения353.1. Регулярные множества и выраженияВведем понятие регулярного множества, играющее важную роль в теорииформальных языков.Регулярное множество в алфавите T определяется рекурсивно следующим образом.1.2.3.4.∅ (пустое множество) — регулярное множество в алфавите T .{e} — регулярное множество в алфавите T (e — пустая цепочка).{a} — регулярное множество в алфавите T для каждого a ∈ T .Если P и Q — регулярные множества в алфавите T , то регулярнымиявляются и множества:а) P ∪ Q (объединение),б) P Q (конкатенация, т.
е. множество {pq|p ∈ P , q ∈ Q}),∞SP n ).в) P ∗ (итерация: P ∗ =n=05. Ничто другое не является регулярным множеством в алфавите T .Итак, множество в алфавите T регулярно тогда и только тогда, когда онолибо ∅, либо {e}, либо {a} для некоторого a ∈ T , либо его можно получитьиз этих множеств применением конечного числа операций объединения, конкатенации и итерации.Приведенное выше определение регулярного множества позволяет ввестиследующую удобную форму его записи, называемую регулярным выражением.Регулярное выражение в алфавите T и обозначаемое им регулярноемножество в алфавите T определяются рекурсивно следующим образом.1.2.3.4.∅ — регулярное выражение, обозначающее регулярное множество ∅.e — регулярное выражение, обозначающее регулярное множество {e}.a — регулярное выражение, обозначающее регулярное множество {a}.Если p и q — регулярные выражения, обозначающие регулярные множества P и Q соответственно, то:а) (p|q) — регулярное выражение, обозначающее регулярное множество P ∪ Q,б) (pq) — регулярное выражение, обозначающее регулярное множество P Q,в) (p∗ ) — регулярное выражение, обозначающее регулярное множество P ∗ .5.
ничто другое не является регулярным выражением в алфавите T .2*36Глава 3. Лексический анализМы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идетоперации конкатенации, наконец, операция объединения имеет наименьшийприоритет.Кроме того, мы будем пользоваться записью p+ для обозначения pp∗ .Таким образом, запись (a|((ba)(a∗ ))) эквивалентна a|ba+ .Мы также будем использовать запись L(r) для регулярного множества,обозначаемого регулярным выражением r.Пример 3.1. Несколько регулярных выражений и обозначаемых ими регулярныхмножеств:а) a(e|a)|b обозначает множество {a, b, aa};б) a(a|b)∗ обозначает множество всевозможных цепочек, состоящих из a и b,начинающихся с a;в) (a|b)∗ (a|b)(a|b)∗ обозначает множество всех непустых цепочек, состоящих из aи b, т.
е. множество {a, b}+ ;г) ((0|1)(0|1)(0|1))∗ обозначает множество всех цепочек, состоящих из нулейи единиц, длины которых делятся на 3.Ясно, что для каждого регулярного множества можно найти регулярноевыражение, обозначающее это множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно много обозначающих егорегулярных выражений.Будем говорить, что регулярные выражения равны, или эквивалентны(=), если они обозначают одно и то же регулярное множество.Существуют алгебраические законы, позволяющие осуществлять эквивалентные преобразования регулярных выражений.Лемма 3.1. Пусть p, q и r — регулярные выражения.
Тогда справедливыследующие соотношения:1)2)3)4)p|q = q|p;∅∗ = e;p|(q|r) = (p|q)|r;p(qr) = (pq)r;5)6)7)8)p(q|r) = pq|pr; 9)(p|q)r = pr|qr; 10)pe = ep = p;11)∅p = p∅ = ∅; 12)p∗ = p|p∗ ;(p∗ )∗ = p∗ ;p|p = p;p|∅ = p.Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть ∅, либо не содержитв своей записи ∅.В дальнейшем будем рассматривать только регулярные выражения, не содержащие в своей записи ∅.При практическом описании лексических структур бывает полезно сопоставлять регулярным выражениям некоторые имена и ссылаться на них3.2. Конечные автоматы37по этим именам. Для определения таких имен мы будем использовать записьвидаd 1 = r1 ,d 2 = r2 ,...
,d n = rn ,где di — различные имена, а каждое ri — регулярное выражение над символами T ∪ {d1 , d2 , . . . , di−1 }, т. е. символами основного алфавита и ранееопределенными символами (именами). Таким образом, для любого ri можнопостроить регулярное выражение над T , повторно заменяя имена регулярныхвыражений на обозначаемые ими регулярные выражения.Пример 3.2. Использование имен для обозначения регулярных выражений.а) Регулярные выражения для множества идентификаторов:Letter = a|b|c| .
. . |x|y|z ,Digit = 0|1| . . . |9,Identif ier = Letter(Letter|Digit)∗ .б) Регулярные выражения для множества чисел в десятичной записи:Digit = 0|1| . . . |9,Integer = Digit+ ,F raction = .Integer|e,Exponent = (E(+| − |e)Integer)|e,N umber = Integer F raction Exponent.3.2. Конечные автоматыРегулярные выражения, введенные ранее, служат для описания регулярных множеств. Для распознавания регулярных множеств служат конечныеавтоматы.Недетерминированный конечный автомат (НКА) — это пятерка M == (Q, T , D, q0 , F ), где:1) Q — конечное множество состояний;2) T — конечное множество допустимых входных символов (входной алфавит);3) D — функция переходов (отображающая множество Q × (T ∪ {e})во множество подмножеств Q), определяющая поведение управляющегоустройства;4) q0 ∈ Q — начальное состояние управляющего устройства;5) F ⊆ Q — множество заключительных состояний.38Глава 3.
Лексический анализРабота конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный моментвходной головкой. Сам шаг состоит из изменения состояния и, возможно,сдвига входной головки на одну ячейку вправо (рис. 3.2).Рис. 3.2Недетерминизм автомата заключается в том, что, во-первых, находясьв некотором состоянии и обозревая текущий символ, автомат может перейтив одно из, вообще говоря, нескольких возможных состояний и, во-вторых,автомат может делать переходы по e.Пусть M = (Q, T , D, q0 , F ) — НКА. Конфигурацией автомата M называется пара (q , w) ∈ Q × T ∗ , где q — текущее состояние управляющегоустройства, а w — цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него.
Конфигурация (q0 , w)называется начальной, а конфигурация (q , e), где q ∈ F , — заключительной(или допускающей). Тактом автомата M называется бинарное отношение ⊢,определенное на конфигурациях M следующим образом: если p ∈ D(q , a), гдеa ∈ T ∪ {e}, то (q , aw) ⊢ (p, w) для всех w ∈ T ∗ .Будем обозначать символом ⊢+ (⊢∗ ) транзитивное (рефлексивно-транзитивное) замыкание отношения ⊢.Будем говорить, что автомат M допускает цепочку w, если(q0 , w) ⊢∗ (q , e) для некоторого q ∈ F . Языком, допускаемым (распознаваемым, определяемым) автоматом M (обозначается L(M )), называетсямножество входных цепочек, допускаемых автоматом M :L(M ) = {w|w ∈ T ∗ и (q0 , w) ⊢∗ (q , e) для некоторого q ∈ F }.Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом тактеработы имеет возможность перейти не более чем в одно состояние и не можетделать переходы по e.3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
