Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 57
Текст из файла (страница 57)
Описание соответствующего типа данных приведено в (5.9), а гра. фнчески узел можно изобразить как В.Ю. Построение габли«но-уара ела»май аргер«мам 337 Выясняется, что еще нужен элемент, представляющий пустую последовательность, символ «пусто». Мы обозначим его с по- мощью терминального элемента, называемого етр1у (5.9). турероЫег = (нвае; иове == гесогй гис,ай: ро!п1ег; саяе 1егттай Ьаогеан ет ггие: (геут: сйаг); Ха)ее: (лгут: йро!и!ег) евй (5.9) Правила преобразования графов в структуре данных аналогичны правилам В! — Ву. Правила преобразования графов в структурах банных С).
Свести систему графов к как можно меньшему числу отдельных графов с помощью соответствующих подстаиовок. С2. Преобразовать каждый граф в структуру данных согласно правилам СЗ вЂ” С5, приведенным ниже. СЗ. Последовательность элементов (см. рисунок к правилу ВЗ) преобразуется в следующий список узлов: С4. Список альтернатив (см. рисунок к правилу В4) преобразуется в такую структуру данных: 333 6. Структура яаыкав и трансляторы Сб. Цикл (см.
рисунок к правилу В5) преобразуется в еле. дующую структуру: В качестве примера на рис. 5.3 показана структура, полу» ченная из графа, соответствующего синтаксису примера 5 (рис. 5.2),(т.',труктурз данных идентифицируется узлом-заго- Ряс. 3.3. Структура даяяых, ярсдставляюшая граф ряс. з.х. ловком, который содержит имя нетерминального символа (цели), к которому относится структура,:-Пока в заголовке необходимости нет, так как можно вместо поля цели указывать непосредственно на «вход» в соответствующую структуру.
Однако заголовок можно использовать для хранения выводимого на печать имени структуры: туре Яро(лает = (адепт(ег; Ьеастег = гестй еяггу: ро(пгег; (5.10)' зутн: айаг евй '-: Программа, производящая грамматический разбор предложения, представленного в виде последовательности символов входного файла, состоит из повторяющегося оператора, в.в.
Построение гиблинно-унравлнвмос нровриммм 339 описывающего переход от одного узла к следующему узлу. Она оформлена как процедура, задающая интерпретацию графа; если встречается узел, представляющий нетерминальный символ, то интерпретация графа„на который он ссылается предшествует завершению интерпретации текущего графа.
Следовательно, процедура интерпретации вызывается рекурсионо. Если текущий символ (зут) входного файла сов падает с символом в текущем узле структуры данных, то процедура переходит к узлу, на который указывает пола зис, иначе — к узлу, на который указывает поле а(г: ргесейвте рагве(аоай йроьпГег', тат та!сй! Ьоо!сап)в тат е: ро!пгвг; Ъей!а с: = лоаЦ,ептгу; гереаФ К а)легт!па! йеи Фей!н К г('.гвупг ° еулг 9йеи Ьерв та!ой:= !гне, 'ае!аут евй еЬе гни: !с(',йВпг ° етр!у) евй е1аерагре(с('.плут, та!сй); !х та!ой !)ген е:= а !ляс е!ее х:= е!.ай ин!!1 е н!! епй (5.11) Программа грамматического разбора (5.11) «стремится» к новой подцели 6, как только она появляется, не проверяя даже, содержится ли текущий символ входного файла в множестве начальных символов соответствующего графа Дгзг(Сг), Это предполагает, что в синтаксическом графе не должно существовать выбора между несколькими альтернативными не- терминальными элементами.
В частности, если какой-либо нетерминальный символ может порождать пустую последовательность, то ни одна из правых частей соответствующих ему порождающих правил не должна начинаться с нетерминального символа. На основе (5.11) можно построить более сложные таблично-управляемые программы грамматического разбора, которые могут работать с более широкими классами грамматик. Небольшая модификация позволяет также осуществлять и возвраты, но зто будет сопровождаться значительной потерей эффективности.
Представление синтаксиса с помощью графа имеет один существснный недостаток: вычислительные машины не могут читать графы, Но перед началом грамматического разбора 340 5. Структура явыков и трансляторы нужно каким-то образом строить структуру данных, управляющих программой. В этом смысле представление грамматик в БНФ оказывается идеальным в качестве исходных данных для универсальной программы грамматического разбора. Поэтому следующий раздел посвящен разработке программы, которая читает правила БНФ и по правилам В1 — Вб преобразует их во внутреннюю структуру данных, с которой может работать программа грамматического разбора (5.11) (5.8~Д ТЗХ ПРЕОЬРАЗОВАНИЕ ЬНФ В СТРУКТУРЫ ДАННЫХ, УПРАВЛЯЮЩИЕ ГРАММАТИЧЕСКИМ РАЗЬОРОМ Пусть метаязык, т.
е. язык, на котором пишутся синтаксические правила, описан следующими порождающими правилами: (правнло) п=(символ) = (выражение) (выражение) н= (терм) (, (терм)) (терм) п=(фактор) ( (фактор)) (фактор) н=. (символ) ~ [(терм)] (5.12) Заметим, что в порождающих правилах входного языка используются иные мстасимволы, чем в БНФ. Это делается по двум причинам: 1. В (512) нужно отличать символы языка от метасимиолов. Транслятор, распознающий порождающие правила БНФ и преобразующий их в какое-то другое представление, как раз служит примером программы, входные данные которой можно рассматривать как предложения, принадлежащие некоторому языку.
Действительно, саму БНФ можно считать некоторым языком, имеющим свой собственный синтаксис, который, разумеется, также можно описать с помощью порождающих правил БНФ. Следовательно, его транслятор может служить примером распознавателя, который помимо этого преобразует входные данные, т. е., вообще говоря, является процессором. Поэтому мы будем действовать следующим образом: Шог !. Определим синтаксис метаязыка, называемого РБНФ (расширенной БНФ). Шаг 2.
Построим распознающую программу для РБНФ в соответствии с правилами, приведенными в равд. 5.4. Шаг 3. Расширив эту программу, превратим ее в транслятор и объединим с таблично-управляемой программой грамматического разбора. б.б. Преобразование БИФ в структура данных ЗЯ! 2. Желательно использовать более привычные символы печатающего устройства, в частности использовать одик знак (=) вместо (::=).
Соответствие между обычной БНФ и нашей входной версией показано в табл. 5.), Кроме того, каждое наше порождающее Таблица бн. Метзсимволы и символы языка БНФ РБНФ ( ! ) правило должно заканчиваться точкой:: При использовании этого входного языка для описания синтаксиса примера 5 (5.7) мы получаем А =х, (В).
В =АС. С = !+А). (5.!3) ') Напомним, что символы языка суть множество терминальных и нетсрмпнзльных символов, «построенных» нз обычно вводимых символов систсмы. — Прим. ред. Чтобы упростить построение транслятора, мы будем считать, что терминальные символы — это отдельные буквы и каждое порождающее правило пишется в отдельной строке. Это позволяет использовать во входном тексте пробелы (чтобы его было удобнее читать), которые транслятор нгнорируег. Но тогда оператор гент!(сй) в правиле В7 нужно заменить вызовом процедуры, которая определяет очередной учитываемый символ.
Эта процедура — простейшая разновидность лексического сканера, или просто сканера. Задача сканера— выделить из входной последовательности обычных символов очередной ср ивол языка *).'.Это не всегда бывает так легко, как в нашем примере, поскпяьку мы до сих пор предполагали, что символы языка †э отдельные буквы, а на самом деле — это особый и на практике редко встречающийся случай. Наконец, мы постулируем, что в нашем входном языке БНФ нетерминальные символы представляются буквамн А — Н, а терминальные символы — буквамн 1 — Е Это чистая условность, не связанная ни с какими серьезными причинами, но она избавляет от необходимости задавать словари терминальных и нетерминальных символов перед списком порождающих правил, 342 Ю.
Структура явыков и трансляторы Убедившись, что (5.12) удовлетворяет ограничениям 1 и 2, и действуя строго по правилам В1 — В7, мы получаем про. грамму 5.2, которая распознает язык, определенный в (5.12), Заметим, что сканер называется по>зупг. На третьем шаге разработки транслятора нужно прочитанные порождающие правила БНФ преобразовать в структуру данных, которая может интерпретироваться процедурой грам.
матического разбора (5.11). К сожалению, этот этап не под. дается формализации в отличие от этапа, связанного с настроением программы распознавания. Поэтому мы просто на. рисуем структуры, соответствующие каждой конструкции ааиожитеяиг Р 5'г' ги 1. Ьугиеог> 2. )1гегиг1> Слагаемые> Часгог-1> ... Оасгог-гз Р— — ч- Гае-! Ч т. р — -в- Гас.1 гас-2 гас-и и ) игг ° ° г ин Ваграисеиияг Ггегиг-и> (гегиг-2) авпи-1> 4г гагиг-1 угоегяга рагяег(Ьри1, отри1); 2аЪе! 99; сопя! евряу = 'е", тяг яув: сЬа«;. уяосе4пяе гегяут; Ъеп!п аеуея! геа4!яут); згг11етяут) вве!! яув Ф ' ' ев4 (уеяяут); угосе4пге еггог; Ъеу!п»тйей; мт11е1п ( тсопяест !нр!1т); 4о2о 99 «в4 !еггог) ", угоее4пге гегт; уяосе4ояе/асгог; Ъеу!в и яут !п ГА', .
'2', етряу) йеп уе1яут еье !2яут = 'Г йеп Ъеу!п 8егяув; гегв; И'яув = ')' йев уейут еЬе еггог еп4 еЬе еггог еп4 !уасяог); Ъеу!в Уасяог; згЫ!е яув !в ГА' .. 'Х', '~', етр1у) 4оуасгог ет$ !1егт); уяоее4пяе ехргеяя!оп; Ъеу!в 1егт; зкЫ!еяут = ','4о Ьеп!в яе1яув; гегт еп4 ия4 1гехргеяя1оп); Ъе4!п ! основная програлима) пЬ!!е — ~еоД ~!прая') 4о Ъеу!п аегяув; И' яут !п ['А' .. '2') йеи уегяут еЬе еггог; !2 аут = '=' !Ьеп уетув еЬе еггог; ехргеяя!о и; !Гяут Ф '.' йев еггог; мтуей; геа41и; еп4; 99: еп4 Программа 5.2. Граммагячесаяе разбор для языка !5.!2!. а. Структура яямяав и трансляторы языка. Формируемые структуры выдаются как параметры-результаты соответствующих процедур распознавания языковых конструкций; таким образом, эти процедуры превращаются в процедуры трансляции.
Естественно, в качестве результатов передаются не сами структуры, а ссылки на них р, д, г (см. рис. на с. 342). Ясно, что процедура 1ае1ог формирует новые элементы структуры данных; остальные же две процедуры связывают их в линейные списки, при этом 1егт использует для связывания поле зис, а ехргезз1оп — поле а)й Подробности показаны в программе 5.3. Метод обработки нетерминальных символов нуждается в некотором пояснении. Нетерминальный символ может встретиться в качестве фактора раньше, чем появится в левой части порождающего правила. Процедура 1(пд(зут, й) ищет заданный символ зугп в линейном списке, где собраны все заголовки нетерминальных символов. Если символ найден, ссылка на него присваивается 6, а если он еще не содержится в этом списке, то добавляется к нему.
В процедуре 11пд применяется метод барьера, подробно обсуждавшийся в гл. 4. Программа 5.3 состоит из трех частей, каждая обрабаты. вает определенный раздел входного файла. Часть 1 читает порождающие правила и преобразует их в соответствующие структуры данных, Часть 2 читает и идентифицирует один символ — это начальный символ, с которого начинается порождение предложения языка. (Ему предшествует знак й, разграничивающий части 1 и 2 входных данных.) Часть 3 есть программа грамматического разбора (5.11), читающая входные предложения и анализирующая их в соответствии со структурами данных, сформированными в части 1. Примечательно, что программа 5.3 получена просто с по. мощью включения добавочных операторов в неизмененну.о программу 5.2. Старая программа только распознавала правильно сформированные предложения, на ее основе можно построить новую, расширенную программу, которая не только распознает, но н транслирует предложения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
