В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 4
Текст из файла (страница 4)
Сначала выделяется отдельная лексема (возможно, используя символыразделители). Ключевые слова распознаются либо явным выделениемнепосредственно из текста, либо сначала выделяется идентификатор, азатем делается проверка на принадлежность его множеству ключевых21ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ22слов.Если выделенная лексема является ограничителем, то он (точнее, некоторый его признак) выдается как результат лексического анализа. Есливыделенная лексема является ключевым словом, то выдается признаксоответствующего ключевого слова.
Если выделенная лексема является идентификатором – выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексемапринадлежит какому-либо из других классов лексем (например, лексема представляет собой число, строку и т.д.), то выдается признак соответствующего класса, а значение лексемы сохраняется отдельно.Лексический анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу “дай лексему”.В первом случае (рис.
3.1, а) выходом анализатора является файл лексем, во втором (рис. 3.1, б) лексема выдается при каждом обращении канализатору (при этом, как правило, признак класса лексемы возвращается как результат функции “лексический анализатор”, а значениелексемы передается через глобальную переменную). С точки зрения обработки значений лексем, анализатор может либо просто выдавать значение каждой лексемы, и в этом случае построение таблиц объектов (идентификаторов, строк, чисел и т.д.) переносится на более поздние фазы,либо он может самостоятельно строить таблицы объектов.
В этом случаев качестве значения лексемы выдается указатель на вход в соответствующую таблицу.LbiAgZq_gb_KbglZgZebaZlhjLbie_dk_fuLZ[ebpZZAgZq_gb_E_dkZgZebaZlhj[Рис. 3.1:Работа лексического анализатора задается некоторым конечным автоматом. Однако, непосредственное описание конечного автомата неудобно с практической точки зрения. Поэтому для задания лексического анализатора, как правило, используется либо регулярное выражение, либоправолинейная грамматика.
Все три формализма (конечных автоматов,3.1. РЕГУЛЯРНЫЕ МНОЖЕСТВА И ВЫРАЖЕНИЯ23регулярных выражений и праволинейных грамматик) имеют одинаковую выразительную мощность. В частности, по регулярному выражению или праволинейной грамматике можно сконструировать конечныйавтомат, распознающий тот же язык.3.1Регулярные множества и выраженияВведем понятие регулярного множества, играющего важную роль в теории формальных языков.Регулярное множество в алфавите T определяется рекурсивно следующим образом:(1) ∅ (пустое множество) – регулярное множество в алфавите T ;(2) {e} – регулярное множество в алфавите T (e – пустая цепочка);(3) {a} – регулярное множество в алфавите T для каждого a ∈ T ;(4) если P и Q – регулярные множества в алфавите T , то регулярнымиявляются и множества(а) P ∪ Q (объединение),(б) P Q (конкатенация, т.е.
множество {pq|p ∈ P, q ∈ Q}),∞S(в) P ∗ (итерация: P ∗ =P n );n=0(5) ничто другое не является регулярным множеством в алфавите T .Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо ∅, либо {e}, либо {a} для некоторого a ∈ T , либо его можно получить из этих множеств применением конечного числа операцийобъединения, конкатенации и итерации.Приведенное выше определение регулярного множества позволяетввести следующую удобную форму его записи, называемую регулярнымвыражением.Регулярное выражение в алфавите T и обозначаемое им регулярноемножество в алфавите T определяются рекурсивно следующим образом:(1) ∅ – регулярное выражение, обозначающее множество ∅;(2) e – регулярное выражение, обозначающее множество {e};(3) a – регулярное выражение, обозначающее множество {a};(4) если p и q – регулярные выражения, обозначающие регулярныемножества P и Q соответственно, то(а) (p|q) – регулярное выражение, обозначающее регулярноемножество P ∪ Q,24ГЛАВА 3.
ЛЕКСИЧЕСКИЙ АНАЛИЗ(б) (pq) – регулярное выражение, обозначающее регулярное множество P Q,(в) (p∗ ) – регулярное выражение, обозначающее регулярное множество P ∗ ;(5) ничто другое не является регулярным выражением в алфавите T .Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет.Кроме того, мы будем пользоваться записью 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.Ясно, что для каждого регулярного множества можно найти регулярное выражение, обозначающее это множество, и наоборот. Более того, для каждого регулярного множества существует бесконечно многообозначающих его регулярных выражений.Будем говорить, что регулярные выражения равны или эквивалентны (=), если они обозначают одно и то же регулярное множество.Существует ряд алгебраических законов, позволяющих осуществлятьэквивалентное преобразование регулярных выражений.Лемма. Пусть p, q и r – регулярные выражения.
Тогда справедливыследующие соотношения:(1) p|q = q|p;(7)pe = ep = p;(2) ∅∗ = e;(8)∅p = p∅ = ∅;(3) p|(q|r) = (p|q)|r;(9)p∗ = p|p∗ ;(4) p(qr) = (pq)r;(10) (p∗ )∗ = p∗ ;(5) p(q|r) = pq|pr;(11) p|p = p;(6) (p|q)r = pr|qr;(12) p|∅ = p.Следствие. Для любого регулярного выражения существует эквивалентное регулярное выражение, которое либо есть ∅, либо не содержит в своей записи ∅.3.2. КОНЕЧНЫЕ АВТОМАТЫ25В дальнейшем будем рассматривать только регулярные выражения,не содержащие в своей записи ∅.При практическом описании лексических структур бывает полезносопоставлять регулярным выражениям некоторые имена, и ссылатьсяна них по этим именам.
Для определения таких имен мы будем использовать запись видаd1 = r1d2 = r2...dn = rnгде di – различные имена, а каждое ri – регулярное выражение над символами T ∪ {d1 , d2 , ... , di−1 }, т.е. символами основного алфавита и ранее определенными символами (именами). Таким образом, для любого ri можно построить регулярное выражение над T , повторно заменяяимена регулярных выражений на обозначаемые ими регулярные выражения.Пример 3.2. Использование имен для регулярных выражений.а) Регулярное выражение для множества идентификаторов.Letter = a|b|c| ... |x|y|zDigit = 0|1| ... |9Identif ier = Letter(Letter|Digit)∗б) Регулярное выражение для множества чисел в десятичной записи.Digit = 0|1| ...
|9Integer = Digit+F raction = .Integer|eExponent = (E(+| − |e)Integer)|eN umber = Integer F raction Exponent3.2Конечные автоматыРегулярные выражения, введенные ранее, служат для описания регулярных множеств. Для распознавания регулярных множеств служатконечные автоматы.Недетерминированный конечный автомат (НКА) – это пятерка M =(Q, T, D, q0 , F ), где(1) Q – конечное множество состояний;(2) T – конечное множество допустимых входных символов (входнойалфавит);(3) D – функция переходов (отображающая множество Q × (T ∪ {e}) вомножество подмножеств множества Q), определяющая поведениеуправляющего устройства;(4) q0 ∈ Q – начальное состояние управляющего устройства;ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ26(5) F ⊆ Q – множество заключительных состояний.Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов.
Такт определяется текущим состояниемуправляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис. 3.2).Khklhygb_IjhqblZggZyqZklv\oh^ghcp_ihqdbDL_dmsbc\oh^ghckbf\heG_ijhqblZggZyqZklv\oh^ghcp_ihqdbРис.
3.2:Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e.Пусть M = (Q, T, D, q0 , F ) – НКА. Конфигурацией автомата M называется пара (q, w) ∈ Q × T ∗ , где q – текущее состояние управляющегоустройства, а w – цепочка символов на входной ленте, состоящая из символа под головкой и всех символов справа от него. Конфигурация (q0 , w)называется начальной, а конфигурация (q, e), где q ∈ F – заключительной (или допускающей).Пусть M = (Q, T, D, q0 , 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 }.3.2.
КОНЕЧНЫЕ АВТОМАТЫ27Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e.Пусть M = (Q, T, D, q0 , F ) – НКА. Будем называть M детерминированным конечным автоматом (ДКА), если выполнены следующие дваусловия:(1) D(q, e) = ∅ для любого q ∈ Q, и(2) D(q, a) содержит не более одного элемента для любых q ∈ Q и a ∈ T .Так как функция переходов ДКА содержит не более одного элементадля любой пары аргументов, для ДКА мы будем пользоваться записьюD(q, a) = p вместо D(q, a) = {p}.Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина, а дуга, помеченная символомa ∈ T ∪ {e}, соединяет две вершины p и q, если p ∈ D(q, a).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
