А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 46

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 46)

1. Значение ни11аЫе (и) для узла и синтаксического дерева равно ггне тогда и только тогда, когда подвыражение, представленное и, содержит в своем языке с. Иначе говоря, подвыражение может быть "сделано нулевым" или пустой строкой, хотя оно может представлять и другие, непустые строки. 2.

йгз~роз(п) представляет собой множество позиций в поддереве с корнем и, которые соответствуют первому символу как минимум одной строки в языке подвыражения с корнем и. 3. 1нз~роз(п) представляет собой множество позиций в поддереве с корнем п, которые соответствуют последнему символу как минимум одной строки в языке подвыражения с корнем п. 232 Глава 3. Лексический анализ 4.

!оПоироз (р) для позиции р представляет собой множество позиций д в синтаксическом дереве в целом, для которых существует строка х = и~ аз, ., а„ языка т",((г) ф), обладающая тем свойством, что для некоторого ! в, соответствует позиции р, а а,чч — позиции д. Пример 3.33. Рассмотрим санузел и на рис.

3.56, который соответствует выражению (а ~ Ь)* а. Мы утверждаем, что лилаЫе (и) равно Га!яе, поскольку этот узел генерирует все строки из а и Ь, оканчивающиеся на о; он не может генерировать е. С другой стороны, у в1аг-узла ниже него значение функции лилаЫе равно ггце, поскольку наряду со строками из а и Ь он генерирует и пустую строку с. Пгзгроз (и) = (1,2,3). В типичной сгенерированной строке наподобие ии первая позиция строки соответствует позиции 1 дерева, а первая позиция строки Ьа соответствует второй позиции дерева. Однако если сгенерированная строка представляет собой просто а, то это а соответствует третьей позиции в дереве. !аз!роз (и) = (3).

Не имеет значения, какая именно строка генерируется из выражения для узла п, — последняя позиция в строке представляет собой в, получающееся из третьей позиции дерева. Вычислить значение !ЬПоироз несколько сложнее, но вскоре мы позналомимся с правилами, которые облегчают решение этой задачи. Здесь же мы просто приведем пример рассуждений для вычисления !ЬПоиргм (1) = (1, 2, 3), Рассмотрим строку ас, где с — либо а, либо Ь, причем первое и получается из позиции 1 в дереве, т.е. это а является одним из символов, генерируемых а в выражении (а ~ Ь)'. За этим а может следовать другое а или Ь из того же подвыражения, т.е.

в этом случае с получается из позиций 1 или 2 дерева. Может также оказаться, что это а — последнее в строке, сгенерированной выражением (а ~ Ь)', и в этом случае символ с должен представлять собой а, получающееся из позиции 3 дерева. Следовательно, за позицией 1 могут следовать позиции 1, 2 и 3. 3.9.3 Вычисление ннПаЫе, йг81ро8 и 1а81ро8 Вычислить пи!1аЫе,Яз!Роз и !аз!роз можно при помощи простой рекурсии по высоте дерева.

Базисные и индуктивные правила для лилаЫе и Пгя!ро5 приведены на рис. 3.58. Правила для вычисления !аз!роз, по сути, те же, что и для вычисления Пгзгрог, но в правиле для санузла роли дочерних узлов с~ и ся должны поменяться. Пример 3.34. Из всех узлов на рис. 3.56 значение функции лилаЫе равно ггне только для вГаг-узла. Из рис. 3.58 видно, что ни один лист не имеет значение функции пилаЫе, равное ггце, так как все они соответствуют операндам, не являющимся е. Ог-узел также не может давать значение лилаЫе, равное ггце, поскольку этого не делает ни один из его дочерних узлов.

Бгаг-узел имеет значение ггне„ поскольку это свойство любого вгаг-узла. Наконец, в санузле функция пилаЫе гзз 3.9, Оптимизация распознавателей на основе ДКА Рис. 3.58. Правила для вычисления ииПаЫе и йгз1роа принимает значение 2а!яе, если таково значение функции хотя бы в одном из его дочерних узлов. Вычисления функций йгягроя и 1ахгроя для каждого из узлов показаны на рис. 3.59 (значениет5гз1роя (п) показано слева от узла п, а значение 1аяГроя (и)— справа). Каждый лист в качестве значений функций 22гягроя и 1аягроя имеет сам себя в соответствии с правилом для не-е-листьев на рис, 3.58.

Значения функций для ог-узлов представляют собой объединения значений функций в дочерних узлах. Правило для з2аг-узла гласит, что значения функций 22гягроя и 1ая2роя в нем те же, что и в его единственном дочернем узле. 11,21 ' 11,21 13~ а 131 ! ( П а 111 (21 а 121 Рис. 3.59. Значения функций йгагроя и!аагроз в узлах синтаксического дерева для 1а ~ Ь) аЬЬЗР 234 Глава 3. Лексический анализ Теперь перейдем к самому нижнему саьузлу, который назовем и. Вычисление Пгзгроз (и) начнем с проверки значения функции пилаЫе в его левом дочернем узле. В нашем случае оно равно ггпе, а значит, Пгзгроз в узле и представляет собой объединение значений Пгз!роз в дочерних узлах, т.е.

равно (1, 2) 0 (3) = = (1, 2, 3). Правила для !аз!роз в явном виде на рис. 3.58 не показаны, но, как уже говорилось, они такие же, как и для Пге!роз, но с взаимообменом дочерних узлов, т.е. вычисление !аз!роз мы должны начать с проверки значения функции пиПаЫе в правом дочернем узле (узел с позицией 3 в нашем случае). Поскольку оно равно Ызе, значение 1аз!роз (и) то же, что и значение 1азфоз в правом дочернем узле, т.е. (3). п 3.9.4 Вычиелеиие $оПоюрой Наконец, мы должны выяснить, как же вычислять значения функции 1олои рож Имеется два пути следования одной позиции регулярного выражения за другой. 1. Если и — саг-узел с левым потомком с1 и правым сз, то для каждой из позиций 1 из !аз!роз (с1 ) все позиции из Пгз!роз (сз ) содержатся в 1олои роз (!).

2. Если и — з!аг-узел и 1 — позиция в 1ах!роз (и), то все позиции из Пгя!рох (и) содержатся в )плон роз (1). Пример 3.35. Продолжим наш пример, для которого на рис. 3.59 были вычислены значения функций Пгхгрое и!аз!рож Правило ! для 1олоироз требует от нас, чтобы мы просмотрели каждый са1-узел и поместили каждую позицию из Пгжроз его правого дочернего узла в 1оПонроз для каждой позиции из !аз!роз его левого дочернего узла. Для самого нижнего саг-узла на рис.

3.59 это правило гласит, что позиция 3 находится в 1оПовроз (1) и 1оловроз(2). Рассмотрение следуюшего, находящегося выше, самуэла позволяет сделать вывод, что позиция 4 находится в 1олонроз (3), а двух оставшихся сас-узлов — что 5 входит в !олоироз (4), а 6— в 1олоироз (5). Мы должны также применить правило 2 к згаг-узлу. Это правило гласит, что позиции 1 и 2 находятся как в 1олонрое(1), так и в 1олонрое(2), поскольку для этого узла и Пгзгроз, и !аз!роз равны (1, 2).

Полностью множества 1оПоироз показаны на рис. 3.60. П Функцию 1оПоюроз можно представить в виде ориентированного графа с узлами для каждой позиции и дугами, идущими из позиции ! в позицию з тогда и только тогда, когда ! Е ~олоироз (1). На рис. 361 показан такой ориентированный граф для функции 1олоироз с рис. 3.60. Не должно удивлять то, что ориентированный граф для 1оПовроз практически является НКА без е-переходов для исходного регулярного выражения, и будет полностью таковым, если 235 3.9.

Оптимизация распознавателей на основе ДКА Рис. 3.60. Значения функции 1о1!онроз Рнс. З.б! . Ориентированный граф для функции 1оПоюрох 1) сделать все позиции из Дгз1роз корня начальными состояниями; 2) пометить каждую дугу из 1 в 1 символом из позиции 1; 3) сделать позицию, связанную с ограничителем Ф, единственным принимаю- щим состоянием. 3.9.5 Преобразование регулярного выражения непосредственно в ДКА Алгоритм 3.36.

Построение ДКА из регулярного выражения т ВХОД: регулярное выражение г. Выход: ДКА .О, распознающий язык Ь 1г). МЕТОД: 1. Построить синтаксическое дерево Т из расширенного регулярного выра- жения (г) ф. 2. Вычислить для дерева Т функции лиПайе, 1згз~роз, 1аз~роз и 1о11он роз с ис- пользованием методов из разделов 3.9.3 и 3.9.4. 236 Глава 3, Лексический анализ 3. Построить Ря1агез — множество состояний ДКА Р и функцию переходов ДКА Рггап в соответствии с процедурой, приведенной на рис. 3.62. Состояния Р представляют собой множества позиций Т.

Изначально все состояния "непомечены*', "помеченным" состояние становится непосредственно перед тем, как мы рассматриваем его исходящие переходы. Начальным состоянием Р является без!роз (по), где узел по — корень Т. Принимающими являются состояния, которые содержат позицию для символа ограничителя !!. д Инициализируем Рз1агея единственным непомеченным состоянием !!ге!роз(по), где по — корень синтаксического дерева Т для (г) Ф., зтЬйе ( в Рк1агез имеется непомеченное состояние В ) ( Пометить Я; !ог ( каждый входной символ а ) ( Пусть (! — объединение !оИовроя (р) для всех р из Я, которые соответствуют а; !Г ( Ь! ф Рз1а1ея ) Добавить с! в качестве непомеченного состояния в Рк1а1ея; Р1гап [о',а] = с1; ) ) Рнс.

Характеристики

Список файлов книги