Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 51
Текст из файла (страница 51)
(1) Индукцией по числу внутренних вершин дерева Е докажем, что (3.1.1) если Š— дерево вывода в 6( с кроной х и корнем, помеченным А, и применение к Е шага (2) дает дерево Е' с кроной у, то (А, А) =ь'(х„у). Базис (дерево, содержащее одну внутреиню1о вершину) — тривиален. Все прямые потомки являются листьями, н в )с должно быть правило А- х, у.
Для доказательства шага индукции допустим, что утверждение (3.!.1) верно для деревьев с меньшим числом внутренних вершин и корень дерева Е имеет прямых потомков с метками Х„..., Хь. Тогда х — — 'х,. хю где Х, =ьо ху для 1 ~1(й. Пусть прямые потомки корня дерева Е' помечены 1'„...,1,. Тогда у.=у,...уо где 1 =ьо,у~ для 1 ='! ~1, Кроме того, в )с есть правйло А Х,...Х„, 1;...1;. Если Х~ — нетермииал, то ему соответствует некоторый символ К =Х . По предположению индукции (Хеч Хр ) =Ь'('хр,ур ). I Так как шаг (26) приводит к перестановке вершин„ то (А, А)=> (х„... х„, У;...1.)) =О'(х~ха ..ХА сс((сс) а(с)) =Ф* (х ...х )х~'ч сс'")) где ум если )Р~ Е)ч( и соответствует одному из Х„., „Х, сс(пч у; в противном случае. Таким образом, утверждение (3.1.1) справедливо. Часть (2) теоремы — зто частный случай следующего утверждения: (3.1.2) если (А, А)=Ор(х, у), то существучот дерево вывода 0 в б, с корнем, помеченным А, и кроной х н такая последовательность выборов при обращении к еиагу (2б), что применение шага (2) к дереву 1) дает дерево с кроной у.
Доказательство этого утверждения индукцией по 1 оставляем в качестве упражнения. [) Заметим, что порядок применений шага (2) алгоритма 3 1 к вершинам дерева не важен. Можно было бы выбрать любой порядок, при котором каждая внутренняя вершина рассматри- вается точно один раз. Проверку этого утверждения тоже остав- ляем в качестве упражнения. Определение. СУ-схема Т=()ч1, л', с), Е, 5) называется про- стой, если для каждого правила А- сс, р из )( соответствую- щие друг другу вхождения нетерминалов встречаются в (х и р в одном н том же порядке, Перевод, определяемый простой Су-схемой, называется простым синтаксически управляемым пе- реводом (простым СУ-переводом).
Все СУ-схемы в примерах 3.3 — 3.5 простые, а в примере 3,6 — нет. Соответствие нетерми палов в выводимой паре простой СУ-схемы самое простое, оио определяется порядком, в каком эти нетер- миналы появляются в цепочках, Простые СУ-переводы образуют важный класс переводов, потому что для каждого из них легко построить транслятор, представляющий собой преобразователь с магазинной памятью. Зто построение будет проведено в разд. 3.1.4.
Многие, но не все, полезные переводы можно описать как простые СУ-пере- воды. В гл. 9 мы дадим несколько обобщений схемы синтакси- чески управляемого перевода, которые можно использовать для определения более широких классов переводов КС-языков. В за- ключение этого раздела приведем еще один пример простого СУ-перевода. Пример 3.7. Следующая простая СУ-схема отображает ариф- метические выражения из языка Е(6,) в арифметические выра- жения, не содержащие избыточных скобок: (1) Е- (Е), Е (2) Š— Е+Е, Е+Е (3) Е- Т, Т (4) Т- (Т), Т (5) Т А»А, А»А (6) Т вЂ” а, а (7) А (Е+Е), (Е+Е) (8) А-»Т, Т Например, для выражения ((а+(а»а))»а) эта СУ-схема дает ') лг( -)- ° » ) ').
О ) в -, .*..* ° °,) ...* ° ...,......~.й ....) ЕЕ»очес соответствует точно одне вьподная, Гл. 3, теогия певвводА ЗЛ.З. Конечные преобразователи Введсм наш простейший транслятор — конечный преобразователь. Преобразователь — зто просто распознаватель, выдающий на каждом такте выходную цепочку (она может быть и пустой). Конечный преобразователь получится, если конечному автомату (распознавателю) позволить выдавать на каждом такте цепочку выходных символов (рис.
З.З). В равд. 3.3 мы будем пользо- вькваевлеем (еаеьее,азеееп Рнс. 3.3. навечный преабрззавзтель. ваться конечным преобразователем как моделью лексического анализатора, Для большей общности рассмотрим в качестве основы конечного преобразователя недетерминированный конечный автомат, способный делать е-такты. Определение. Конечным пргобразсваазв ем называется шестерка М =(1г, 2', Л, 6, 4е, Р), где (1) Я вЂ” конечное множество состояний, (2) Х вЂ” конечный вхпднсй алфавит, (3) Л вЂ” конечный выходной алфавит, (4) 6 — отображение множества Ях(г () (в)) в множество конечных подмножеств множества ЯмЛ', (5) д, ЕЯ вЂ” начальное состояние, (Б) г" ~ Я вЂ” множество заключительных состояний. Определим кснфигураиию преобразователя М как тройку (д, х, у), где (1) 4~1г — текущее состояние управляющего устройства, (2) х б Х' — оставшаяся непрочитанной часть входной цепочки, причем самый левый символ цепочки х расположен под входной головкой, (3) у б Л" †час выходной цепочки, выданная вплоть до текущего момента.
254 зл.е ь еовмллизмы,используемые для опгедалания пегеводл Определим бинарное отношение ) — м (или ) †, когда ясно, о каком М идет речь) на конфигурациях, соответствующее одному такту работы преобразователя М: для всех 4 Е 9, а Е Х () (е), хп гь и уЕЛ', таких, что 6(д, а) содержит (г, г), будем писать (4, ах, у) ) — (г, х, уг) Обычным образом далее определяются ) — ', ) — ' и 1 — +. цепочку у назовем выходом для цепочки х, если (4, х, е) ',— ' (4, с, у) для некоторого д Е г".
Переводом, спределясмьыз преобразователем М (обозначается т (М)), назовем множество ((х, у) ( (д„х, е) 1 — '(ц, е, у) для некоторого д Е г). Перевод, определяемыи конечным преобразователем, будем называть регулярным переводом или конечным преобразованием. Заметим, что для того, чтобы выходную цепочку у можно было считать переводом входной цепочки х, цепочка х должна перевести преобразователь М из начального состояния в заключительяое, Пример 3.8. Построим конечный преобразователь, который распознает арифметические выражения, порождаемые правилами 3- а+Я)а — 3)+Я! — 31а и устраняет из этих выражений избыточные унарные операции. Например, выражение — а+ — а — + — а он переведет в — а — а 1-а. Во входном языке символ а представляет идентификатор и перед идентификатором допускается произвольная последовательность знаков унарных операций + и —.
Заметим, что входной язык является регулярным множеством. Пусть М=Я,Х,Л,6 д Р) где ( ) 9 = И, 4„4., 4., 44), (2) Х = (а, +, — ) „ (3) Л=-Х, (4) 6 определяется диаграммой, изображенной на рис. 3.4; метка АУ на дУге, ведУщей из веРшины, помеченной аи в веР- шивУ, помеченнУю дэ Указывает, что 6(йо х) содеРжит (дг, У), (5) р= (4,).
ПРеобРазователь М начинает РаботУ в состоЯнии дз и, чеРедуя состояния д, и дз на входном символе —, определяет, четное или нечетное число знаков - предшествует первому символу а. Ко~да появляется а, преобразователь М переходит в состояуз, допуская вход, и выдает а или — а в зависимости от того четко или нечетно число появившихся минусов. Для сле"ующих символов а он подсчитывает, четно или нечетно число "РедшествУющих минУсов, с помощью состозний дз и 4з.
Един- гл, а. ТЕОРИЯ ПРРРВОДА ал оом РМАЛИЭМЫ, ИСПОЛЬЗУЕМЫЕ Для ОПРЕДЕЛЕНИЯ ПЕРЕВОДЛ -(в Рис. З.4. Граф переходов. ственное различие между парами у„у, и д„у, состоит в том, что если символу а предшествует четное число минусов, то первая из них выдает +а, а не только а, Для входа — а+ — а — + — а последовательность тактов превбраэователя М такова: (уа> — а+ — а — + — а, Е) )-(д„а+ — а — -~- — а, е) )-(д„+ — а — + — а, — а) г — (д„— а — + — а, — а) )-(Ч„а — + — а, — а) 1 — (до — + — а, — а — а) ) — («„+ — а, — а — а) )-(«а.
— а, — а — а) ) — («„а, — а — а) )-(д„в, — а — аи а) Отсюда ясно, что М отображает цепочку — а+ — а — + — а в — а — а+а, поскольку д,— заключительное состояние. Г) Конечный преобразователь М назовем детерминированным, если для всех уЕЯ (1) либо 6 (д, а) содержит не более одного элемента для каждого ач Х и 6(д, в) пусто, либо (2) 6(у, в) содержит один элемент и 6(у, а) пусто для всех або.
В п имере 3 8 конечныи преобразователь детерминированиыи Заметим, что детерминированный конечный преобразователь может да давать несколько переводов для одного входа. ПРимеР3.9. ПУсть М ((У„У,), (а), (Ь), 6, д„(дх)) и 6(д„а)= ((у, Ь)), 6(у„е) — ((у„Ь)). Тогда (д„а, е))- (д„е, Ь) ) — '(ум е, Ь'~х) допустимая последовательность тактов для всех 1)О. Таким образом, т(М)=((а Ь')11)~1) П Известно несколько простых модификаций определения детерминизма для конечных преобразователей, гарантирующих единственность выхода.
Мы предлагаем потребовать, чтобы в заключительном состоянии были невозможны е-такты. Для нскотовых классов языков можно получить ряд свойств замкнутости, если рассматривать преобразователи как операторы, определенные на языках. Например, если М вЂ конечн преобразователь и язык (. содержится в области определения отношения т(М), то полагаем М (6)= (ухай и (х, у) Ет(М)) Можно также определить обратное коне«нов преобразование, а именно, если М- — конечный преобразователь, положим М х(Е)=— = (х~у~(. и (х, у) ~т(М)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
