Алгоритм нисходящего разбора. Нисходящие распознаватели

Алгоритм нисходящего разбора. Нисходящие распознаватели Разбор сентенциальной формы означает построение вывода и, возможно синтаксического дерева для нее. Программу разбора называют также рас- познавателем, так как она распознает только предложения рассматривае- мой грамматики. Именно это и является нашей задачей в данный момент. Все алгоритмы разбора, которые бутут здесь описаны называются алгори- тмами слева направо ввиду того, что они обрабатывают сначала самые ле- вые символы обрабатываемой цепочки и продвигаются по цепочке только тогда, когда это необходимо. Можно подобным способом определить разбор справа налево, но он менее естественен. Инструкции в программе выполня- ются слева направо, да и мы читаем слева направо. Различают две категории алгоритмов разбора: нисходящий (сверху вниз) и восходящий (снизу вверх). Их называют также разверткой и сверткой. ( В данном реферате будет рассмотрен процесс только нисходящего раз- бора. ) Соотетственно, эти термины соответствуют и способу построения синтаксического дерева. При нисходящем разборе дерево строится от корня состоит в том, что отправляясь от заданной цепочки, пытаются привести ее к начальному символу. В качестве примера нисходящего разбора рассмотрим предложение (1) в следующей грамматике целых чисел ( последовательностей, N ::= D ND D ::= 0 1 2 3 4 5 6 7 8 9 (1) На первом шаге непосредственный вывод N => ND будет строиться так, как показано в первом дереве на рис. 1. На каждом последующем шаге самый левый нетерминал V текущей сентенциальной формы xVy заменяется на правую часть u правила V ::= u, в результате чего получается сле- дующая сентенциальная форма. Этот процесс для предложения (1) предс- надо получить ту сентенциальную форму, которая сопадает с заданной цепочкой. N N N N N *-------* *-------* *-------* *-------* N D N D N D N D D D D 5 3 3 > N D => D D => 3 D => 3 5 Рис. 1. Нисходящий разбор и построение вывода было сказано, начиная с корня, постепенно опускаясь до уровня предло- из-за необходимости вспомогательных операций, которые необходимы гла- вным образом для того, чтобы выполнять возвраты с твердой уверенностью, что все возможные попытки построения дерева были предприняты. Чтобы свести осложнеия к минимуму, давайте опишем этот алгоритм раз- построенной части дерева находится по одному человеку. Люди, которые находятся в терминальных узлах, занимают места соответственно символам предложения. Некоему человеку надлежит провести разбор предложения x. Прежде все- го ему необходимо отыскать вывод Z => +x, где Z - начальный символ; сле- довательно первым непосредственным выводом должен будет быть вывод Z => y где Z ::= y - правило. Пусть для Z существуют правила Z ::= X X.. X Y Y.. Y Z Z.. Z 1 2 n 1 2 m 1 2 1 Сначала человек пытается определить правило Z ::= X X.. X. Если 1 2 n 1 2 m следующему правилу и т. д. Как ему определить, правильно он выбрал непосредственный вывод Z => X X.. X ? Заметим, что если вывод правилен, то для некоторых 1 2 n цепочек x будет иметь место x=x x.. x , где X => *x для i=1,...,n. i 1 2 n i i Прежде всего человек, выполняющий разбор, возьмет себе приемного сына M , который должен будет найти вывод X =>*x для любого x , такого, что x = x... Если сыну M удастся найти такой вывод, он (и любой из 1 1 1 ет своему отцу об успехе. Тогда его отец усыновит M , чтобы тот нашел 2 вывод X => *x , где x = x x... и ждет ответа от него и т. д. Как толь- 2 2 1 2 ко сообщил об успехе сын M ,он усыновит еще и M , чтобы тот нашел i-1 i вывод X => *x. Сообщение об успехе, пришедшее от сына M , означает i i n что разбор предложения закончен. >*x ? В этом i i i i дает старшему брату M ,M такое распоряжение: "Ты уже нашел вывод, i i-1 но этот вывод неверен. Найди-ка мне другой". Если M сумеет найти i-1 другой вывод, он вновь сообщит об успехе, и все продолжится по-пре- жнему. Если же M сообщит о неудаче, отец отречется и от него, и i-1 тогда уже старшего брата M , попросят предпринять еще одну попыт- i-2 1 вод Z => X X.. X был неверен, и человек, начинавший разбор, попы- 1 2 n тается воспользоваться другим выводом Z => Y.. Y. 1 m Как же действует каждый из M ? Положим, его целью является тер- 1 минал X. Входная цепочка имеет вид x=x x.. x T.. ,где символы в 1 2 i-1 1 2 i-1 i i закрывает этот символ и сообщает об успехе. Если нет, сообщает об Если цель M - нетерминал X , то M поступает точно так же, как 1 1 и его отец. Он начинает проверять правые части правил, относящихся к нетерминалу, и, если необходимо, тоже усыновляет или отрекается от сыновей. Есливсе его сыновья сообщают об успехе то M в свою очередь i сообщает об успехе отцу. Если отец просит M найти другой вывод, а це- i i другого такого вывода не существует. В противном случае M просит своего i младшего сына найти другой вывод и реагирует на его ответ также, как и Теперь, наверное, понятно, почему этот метод называется прогнозиру- ющим или целенаправленным. Используется и название "нисходящий" из-за способа построения синтаксического дерева. При разборе отправляются от Z *---*-------* F T T F i + i * i Рис. 2. Частичный нисходящий разбор предложения i+i*i. тоит, что каждый человек должен помнить лишь о своей цели, о своем от- це, о своих сыновьях, а также о своем месте в грамматике и выходной це- почке. И никому не нужны точные сведения о том, что происходит в других местах. Это как раз и есть то, к чему мы вообще стремимся в программиро- титься о собственной входной и выходной информации и ни о чем более. Для имитации усыновления и отречения сыновей в программах использу- ют стек типа LIFO (последний вошел - первый вышел), или, как его иногда называют, "магазин". Положим, во-первых, что грамматика задана списком в одномерном мас- U ::= xy... z представлено, как Uxy... z$. То есть каждый символ занимает одну "", а за "$". Таким образом, грамматика Z ::= E# E ::= T+ET T ::= F*TF будет выглядеть как ZE#$ET+ET$TF*TF$F(E)i$ Каждый элемент стека соответствует человеку и состоит из пяти компонент (GOAL,i,FAT,SON,BRO) которые означают следующее: 1. GOAL - цель, т. е. символ, который человек ищет. Таким обра- зом, в незакрытой в данный момент части предложения ему предстоит найти такую голову, которая приводится к GOAL, и закрыть ее. GOAL передается ему отцом. 2. i - индекс в массиве GRAMMAR, указывающий на тот символ в правой части для GOAL, с которым человек работает в данный момент. 3. FAT - имя отца (номер элемента стека, соответствующего от- цу). 4. SON - имя самого последнего (младшего) из сыновей. Нуль в любом из полей означает, что данная величина отсутствует. В программе значение переменной v равно количеству участвующих в имя (номер элемента в стеке) человека, работающего в данный момент. Остальные ожидают конца его работы. Индекс j относитстя к самому ле- вому (незакрытому) символу входной цепочки INPUT(1),...,INPUT(n). *---------*------* 1 Z 4 0 15 0 E # 3 T 20 2 4 0 4 F 28 3 5 0 *--*------* 5 i 0 4 0 0 6 + 0 2 0 3 + 8 T 18 7 12 0 F T 9 F 28 8 10 0 10 i 0 9 0 0 i *---*---* 11 * 0 8 0 9 F * T 13 F 28 12 14 0 i F 15 # 0 1 0 2 i Рис 3. Стек после нисходящего разбора i+i*i а) - синтаксическое дерево б) - стек после разбора Поле SON используется для хранения ссылки на последнего (младше- го) сына. Тогда поле BRO элемента, соответствующего этому сыну, укажет на старшего брата. В качестве иллюстрации расмотрим изображенное на рис. 3 а) синтаксическое дерево для предложения i+i*i вышеописанной Теперь у человека 2(S (2)) есть цель E; предполагается, что он в соотве- тствии с синтаксическим деревом использует правило E ::= T+E. Таким номером 7, цель которого E. Имя среднего сына - число 6, определяется значением поля S(7). BRO; - цель этого сына - символ +. Имя старшего сына находится в поле BRO человека 6 и равно 3. Очевидно, что у нас имеется список сыновей каждого человека и окончательном виде представляет собой внутреннюю форму синтаксического дерева. Рассмотрим теперь сам алгоритм нисходящего разбора. Для удобства чтения разделим его на шесть поименованных частей. 1. НАЧАЛЬНАЯ УСТАНОВКА S(1) := (Z,0,0,0,0); c:=1; v:=1; j:=1; переход на НОВЫЙ ЧЕЛОВЕК 2. НОВЫЙ ЧЕЛОВЕК IF GOAL терминал THEN Новый человек изучает свою цель. IF INPUT (j)=GOAL THEN Цель - терминал. BEGIN j:=j+1; Если GOAL совпадает с символом из GO TO УСПЕХ; предложения, человек закрывает этот части для GOAL; Цель нового человека - нетерминал. GO TO ЦИКЛ Подготовка к просмотру правых частей в правилах для GOAL 3. ЦИКЛ IF GRAMMAR(i)="" Просмотр правой части THEN IF FAT=/=0 Достигли конца правой части, поэтому THEN GO TO УСПЕХ сообщаем об успехе. Если нет отца, ELSE STOP - предложение; то останов - окончен разбор IF GRAMMAR(i )="$" Нет больше правых частей, которые THEN IF FAT=/=0 можно было бы попробовать, поэтому ELSE STOP - не остановка, не распознав предложения предложение; v:=v+1; GRAMMAR(i) - другая цель, которую SON); Тогда старший брат - тот, кто был до Переключить внимание на младшего сына SON:=v; c:=v; и ждать от него ответа GO TO НОВЫЙ ЧЕЛОВЕК 4. УСПЕХ c:=FAT; Сообщить об успехе своему отцу. Он i:=i+1; GO TO ЦИКЛ предпримет следующий шаг. 5. НЕУДАЧА c:=FAT; Сообщить о неудаче своему отцу. Он v:=v-1; отречется от сына и попросит его GO TO ЕЩЕ РАЗ попытку. 6. ЕЩЕ РАЗ IF SON=0 THEN Есть ли еще сын, который может пред- BEGIN WHILE GRAMMAR(i) принять еще одну попытку? Нет. =/="" Тогда пропускается правая часть - DO i:=i+1; Это не та, которая нужна - переход к i:=i+1 GO TO ЦИКЛследующей. END; i:=i-1; c:=SON; Естьсын. Его просят повторить попытку IF GOAL нетерминал Его цель - нетерминал, так что он по- THEN GO TO ЕЩЕ РАЗ пытается еще раз добиться успеха. j=j-1 Его цель терминал. Попытка не приведет GO TO НЕУДАЧА к успеху. Поэтому он открывает свой символ и сообщает о неудаче. *---------* 1 *----*----* *----------------------------> *------* > <------* Нет / \ *-----------< 2 > * *----------< 4 > * *-------< 9 > \ / \ / * * Да Да Нет * *---*---* *---* Н / \ 10 6 --< 5 > * *---*---* *---* \ / / \ * *-< 3 > * Да \ / / \ Да *-* * <1 1>-----* *-7 *-----* \ / *-* Нет * *---------------* Нет <--------* *-- 1 2 *---*---* *-------* 8 -------* *-------* Рис 4. Блок-схема алоритма нисходящего разбора 2. GOAL - терминал ? 3. j:=j+1; INPUT(j)=GOAL ? 4. GRAMMAR(i)="Конец" ? 5. FAT =/= 0 ? 6. STOP - Конецработы; SON := v; c := v; 8. c := FAT; i := i+1; 9. SON = 0 ? 10. Пока GRAMMAR (i) =/= "Конец": j:=j+1; i :=i -1; c := SON; 11. GOAL - нетерминал ? 12. C := FAT ; v := v-1; SON := S (SON) * BRO. 3. Проблемы нисходящего разбора В алгориме, описанном ранее, есть один серьезный недостаток, который проявляется, когда цель определена с использованием левосто- ронней рекурсии. Если X - наша цель, а первое же правило имеет вид X ::= X..., то мы незамедлительно усыновляем того, кто будет искать X. Он в свою очередь немедленно заведет себе сына, чтобы тот искал X. Таким образом, каждый будет сваливать ответственность на своего сы- на, и для решения задачи не хватит населения Китая. По этой причине правила грамматики написаны с применением право- сторонней рекурсии вместо более привычной левосторонней. Лучший способ избавиться от прямой левосторонней рекурсии - записывать правила, ис- пользуя итеративные и факультативные обозначения. Запишем правила (3. 1) E ::= E+T T как E ::= T { +T } и оьразуются в эквивалентные правила, использующие итерацию. U ::= xy xw... xz, то их надо заменить на U ::= x(yw... z), где скобки являются метасимволами Допустима факторизация в более общей форме, такая как в арифметиче- ских выражениях. Например, если в (3. 2) y=y y и w=y w , мы могли бы за- менить U ::= x (yw... z) на U ::= x(y (y w )... z). 1 2 2 Заметим, что исходные правила U ::= xxy мы преобразуем к виду U ::= x(yЛ), где Л - пустая цепочка. Когда бы ни использовалось по- добное преобразование, Л всегда помещается как последняя альтернати- ва, так как мы принимаем условие, что если цель - Л, то эта цель все- Помимо того что факторизация позволяет нам исключить прямую реку- рсию, использование этого приема сокращает размеры грамматики и позво- ляет проводить разбор более эффективно. В этом мы убедимся позже. После факторизации (3. 2) в грамматике останется не более одной пра- вой части с прямой левосторонней рекурсией для каждогоиз нетерминалов. (3. 3) Пусть U ::= xy... zUv - правила, у которых осталась леворе- курсивная правая часть. Эти правила означают, что членом син- таксического класса U является x, y или z, за которыми либо ни- чего не следует, либо следует только v. Тогда преобразуем эти правила к виду U ::= (xy... z) {v}. позволяющее избавиться от ненужных скобок заключающихся в T. В качес- тве другого примера преобразуем A ::= BCBCDAxzAxy а) Z б) Z E + T T + T + T + T E + T *-*-* E + T T Рис 5. Деревья, использующие рекурсию и итерацию Применив правило (3. 2) получим A ::= BC(DЛ)Ax(zy); Применив (3. 3), получим A ::= BC(DЛ){x(zy)}. Можно избавиться от одной па- ры скобок, после чего получим A ::= BC(DЛ){x(zy)}. После таких изменений мы, конечно, должны изменить и наш алгоритм нисходящего разбора. Теперь алгоритм должен уметь обрабатывать альтер- нативы не только в одной правой части, но и в ее подцепочках, должен учитывать в своей работе существование пустой цепочки Л, должен уметь Использование итерации вместо рекурсии отчасти меняет и структуру деревьев. Таким образом, рис 3. а должен был бы походить на рис. 3. б. Но эти два дерева следует рассматривать как эквивалентные; операторы "плюс" должны заменяться слева направо. Мы не решили всей проблемы левосторонней рекурсии: с прямой лево- U ::= Vx и V ::= Uyv дают вывод U => +Uyx. Избавиться от этого не так просто, но обнаружить левосторонней рекурсией. Символ U, получившейся в результате этих пре- образований грамматики, может быть леворекурсивным тогда и только тогда когда U FIRST+ U. Как проверить это отношение, нам уже известно. является представление грамматики в вычислительной машине. Одно из возможных представлений уже использовалось ранее. Очевидно, что оно неудачно из-за обьема работы необходимой для поиска правил, соответст- вующих каждому нетерминалу. Речь пойдет о другом представлении. Прежде который воспринимает грамматику, проводит любые из преобразований, о сивными, и составляет таблицы для грамматики в одной из описываемых да- лее форм довольно легко. зываемая синтаксическим графом. Каждый узел представляет символ S из правой части и состоит из четырех компонент: ИМЯ, ОПРЕДЕЛЕНИЕ (ОПР), АЛЬТЕРНАТИВА (АЛТ) и ПРЕЕМНИК (ПРЕМ), где 2. ОПРЕДЕЛЕНИЕ равно 0, если S - терминал; в противном случае эта компонента указывает на узел соответствующий первому символу в перво правой части для S. 3. АЛЬТЕРНАТИВА указывает на первый символ той альтернативы пра- вой части которая следует за правой частью, содержащей данный узел (0, если такой правой части нет). Это только для символов в правых частях. 4. ПРЕЕМНИК указывает на следующий символ правой части (0, если такого символа нет). ящим из одной компоненты, которая указывает а первый символ в первой правой части, относящейся к этому символу. Примером может служить рис. 4, на котором изображено расположения компонент узла синтаксическо- го графа грамматики: *---------------------------* ИМЯ *--------*---------*--------* ОПР АЛТ ПРЕМ Рис 6. Расположение компонент узла синтаксического графа грамматики Подробно о синтаксических графах см. в книге Д. Гриса "Конструи- " Разбор без возвратов гать к возвратам. Мы должны иметь уверенность в том, что каждая пред- полагаемая цель верна. Это нреобходимо потому, чтонам предстоит связать семантику с синтаксисом, и по мере того, как мы будем прогнозировать и находить цели, эти символы будут обрабатываться семантически. Вот неко- торые примеры "обработки": 1) при обработке описаний переменных иденти- выражений проверяют, совместимы ли типы операндов. придется уничтожить результаты семантической обработки, сделанной во время поисков этой цели. Сделать это не так -то просто, поэтому постара- емся провести грамматический разбор без возвратов. контекста обычно используется следующий "незакрытый" символ исходной про- граммы. Тогда на грамматику налагается следующее требование: если есть альтернативы xy... z, то множества символов, которыми могут начинаться выводимые из x,y,..,z слова, должны быть попарно различны. То есть если x => *Au и y => *Bv то A =/= B. если это требование выполнено, можно довольно просто определить, какая из альтернатив x,y или z - наша цель. Заметим, что факторизация оказывает здесь большую помощь. Если есть пра- вило U ::= xyxz, ео преобразование этого правила к виду U ::= x(yz) помогает сделать множесва первых символов для разных альтернатив непе- ресекающимися. 4. Заключение В данном реферате рассматривались нисходящие распознаватели, разбором. Одна из первых статей, рассматривающих фиксированный ал- горитм нисходящего разбора, принадлежит Айронсу. Но его метод не являлся нисходящим разбором в чистом виде, а являлся смешением нис- ходящих и восходящих разборов. Алгоритм, приведенный в данном рефе- рате, впервые был предложен в обзоре Флойда. Он же ввел и понятия "отец - сын - брат". Способы избавления от возвратов описаны Унге- ром. 5. Список литературы 1. Грисс. Конструирование компиляторов для цифровых вы- числительных машин. М., Мир, 1975г. 2. Ахо А., Ульман Дж. Теория синтаксического анализа, пере- вода и компиляции. М. Мир 1978г. 3. Ф. Льюис, Д. Розенкранц, Р. Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979г. 4. Фельдман Дж., Грис Д. Системы построения трансляторов. Сб. Алгоритмы и алгоритмические языки, вып. 5, ВЦ АН СССР, 1971г. _