Карпов - Основы построения трансляторов (2005) (943926), страница 31
Текст из файла (страница 31)
Пара <Я, аЬ определяет по таблице на рис. 5.31, что верхний символ магазина 5 должен быть заменен цепочкой АОС'. Далее, пара <А, а"- требует заменить А в верхушке магазина на цепочку СЯ вЂ” правую часть правила А — +СЯ. На следующем шаге анализа пара <С, а=' приводит к замене верхнего символа магазина С на цепочку аС.
Поскольку теперь в верхушке магазина терминал, и он совпадает с очередным входным терминалом, то он из магазина выталкивается, а анализатор сдвигается к следующему входному символу о, имея в магазине остаток сен- Глава 5 Для грамматики б5.4 ° БРЕХТ(Я вЂ” +АВС) = ~а, о, с, д, е,Я; БРЕХТ(А — +а) = (а~, БРЕХТ(А — +СоВ) = ~е, ~; Ь~, БРЕХТ(А — +с) = ~с, с/~ '„ БРЕХТ(В-+с) = ~с~, 1ЧЕХТ(В-+ИСа) = ф~; БРЕХТ(С вЂ” +еВа) = (е~, БРЕХТ(С-+~АВ) = ф, МЕХТ(С вЂ” +~) = (а, К ~~ Поскольку множества 1ЧЕХТ(М вЂ” +а,) не пересекаются для различных ~' у всех нетерминалов грамматики 05 ~, то это грамматика класса 1.1 (1). На основе этой таблицы решений, представленной на рис. 5.33, восстановление вывода цепочки Я ==>? ==> свисс в этой грамматике осуществляется однозначно (рис.
5.34). Справа цепочка ограничивается конечным маркером 3. Рис. 5.33. Таблица решений для грамматики 654 Входная цепочка: с Г о с с 3 Рис. 5.34. Последовательность состояний магазина МП-автомата при синтаксическом анализе цепочки сйсс в грамматике 65~ Алгоритмы построения функций Г1В5Т, 1=ОП 0% и 1ЧЕХТ по правилам грамматики достаточно очевидны, они остаются в качестве упражнения. 200 Глава 5 На рис. 5.35 представлена последовательность состояний магазина при трансляции цепочки свисс, причем, в отличие от рис.
5.34, в магазин записываются и семантические операции. Легко видеть, что последовательность верхних символов магазина как раз определяет скобочную запись дерева вывода этой цепочки в грамматике Сг~ ~. Рис. 5.35. Состояния магазина при трансляции цепочки с~Ьсс в грамматике 8~4 Действительно, все символы, выталкиваемые из магазина„должны, в соот- ветствии с нашей семантикой, просто выдаваться иа печать. Цепочка: Я(А () Л( с) Г(~А ( С" () Ь Л(с)) Л(с))) Рис.
5.36. Представление цепочки Я(А()В(с)С(ГА(С()ЬВ(с))В(с)) в виде дерева Если дерево вывода желательно представить списочной структурой данных, то таку1о структуру нужно также специально генерировать в процессе анали- которую можно прочесть в верхушке магазина рис. 5.35 в последовательных состояниях магазина. как раз и оиределяег выдаваемую на печать информа- цию. Эта цепочка — скобочиое представление дерева рис.
5.36, которое есть дерево вывода цепочки асс в нашей грамматике. Нисходящие методы синтаксического анализа за. Таким образом, трансляция при нисходящем синтаксическом анализе проводится семантическими процедурами, которые вставляются непосредственно в правые части правил грамматики. При синтаксическом анализе правые части грамматики заталкиваются в магазин вместе с семантическими процедурами на основании таблицы решений. Семантические процедуры выполняются при их выталкивании из магазина. Фактически входная цепочка просто управляет последовательностью выполнения этих семантических процедур в синтаксическом анализаторе, и для каждой входной цепочки такая последовательность будет своей.
5.10. Пример транслятора рекурсивного спуска В этом разделе приводится полная программа на языке С, выполняющая трансляцию операторов присваивания с арифметическими выражениями в правой части в код на языке ассемблера. Читателю предлагается самостоятельно разобраться в этой программе и проверить ее работу на примерах арифметических выражений. Компилятор рекурсивного спуска $ 1пс1ыс(е <Б~сйо.Ь> $1пс1ыбе <стуре. Ь> $ 1пс1ыс(е <в~г1пд.Ь> $ 1пс1ыс(е <БЫ11Ь.Ь> Г11.Е *ореп(), *йЫ; /* сЬат ~оКеп; с?~аг Ыпе (128) ="", *р Ыпе=1,1пе; Синтаксический анализатор чоЫ ЯСАЛ (чоз.с$) ыМ1е ( саврасе (~оКеп=аде~с (~1п) ) ) (~окреп== '~п') ( Ыпе(0)="~0'; р 1Ые=Ыпе; ) е1зе р Ыпе+=зргз п~Й (р Ыпе, "%с", ~оКеп); /* /* Грамматика АЯЯ аИМЕИТ ЕХРВЕЯЯ1ОИ : теВм РР1МАВУ ИЖ1АВ1.Е 1ЭЕКТ1Г1ЕР, СОИЯТА?~Т Идентификатор — это */ = Иж1АВ1,Е '=' ЕХРКЕЯЯ1ОИ ($' — 1) терм ((Ф+' 3 ' †') теРМ) * — Рк1МАю (( * ~ / ) Рапи~* = СОКЯТАИТ ~ ЧАВ1АВ1 Е ~ '(' ЕХРРЕЯЯ10И ')' — 1ВЕИТ1Г1ЕР, ю ~! ~ ю)ою ~ ~ в~1 ~ еА! ~ ~Ре ~ ~ вУ~ 'О' ! '1' ! ...
! '9' буква латинского алфавита, константа — любая цифра Нисходящие методы синтаксического анализа 203 Нетерминал РК1МАКУ вЂ” — — — --------* /' чол.с( РЮ"1АР.У (стол.с2) очаг аа.к "о)сеп; 1Й ( 1аЖд1~ (~окреп) ) ( ЕМ1Т ( "1 ОИЭ1 " ); ЕМ1Т! ~о).еп); БСАК (); е1зе ( ( ~о)сеп=-= '(') БСХЛ (); ЕХРРЕББ103 ( ); .о)сеп==- ' ) ' ) БСРЛ (); е1яе ЕР,Р,ОК() р е18е за~ ~о)~еп=~оЫп; ~ДЫ17Я1,Е ( ); ЕМ1Т (" ОАг") р ЕМ1Т (зач ~о)сеп); Нетерминал ЧАВ1М31.Е- — — — — --- — — — — *// '/о1с( ЧАГ~1АВ1.Е (чоЫ) ( ( 1за1р)1а (~. о)сеп) ) БСРЛ (); е15е ЕРРОР,(); 1п, талип( 1п~ атас, спаг" агу'"() ) ~1п=+ореп1"~.пп.1", "г~"); 1Г (Г1п== К~Л 1,) ЕМ1Т("~пСап'~ ореп 1пры~ ~: 1е "); Бслы (); мБ1акмеит (); ему~ (1); 5.11.
Заключение Все алгоритмы нисходящего распознавания работают по следующей схеме: восстановление (распознавание) правой части продукции для конкретного нетерминала производится по первым Ь-терминальным символам той подстроки„которая порождается из этой правой части. Обычно используется 1 = 1. Ограничения, которым должна удовлетворять КС-грамматика для возможности применения нисходящего распознавания, весьма существенны— в частности, грамматики даже простых конструкций распространенных языков программирования таким ограничениям зачастую не удовлетворяют.
Применение операций факторизации, эквивалентная замена левой рекурсии Нисходящие методы синтаксического анализа 205 11. Пусть в число операторов языка Милан введен оператор цикла языка С вида: Гог(ехрг1; ехрг2; ехргЗ) ламп~ Первое выражение ехрг1 выполняется до цикла (это инициализация цикла), второе — это проверка, выполняемая перед каждой итерацией цикла. Когда это выражение равно О, происходит выход из цикла. Третье выражение ехргЗ выполняется в каждой итерации цикла после тела цикла зйп1, оно служит для увеличения параметра цикла.
Построить семантические действия для генерации команд стековой машины по синтаксической диаграмме. 12. Пусть в число операторов языка Милан введен оператор цикла вида: $0г1:= ехрг1 Мер ехрг2 пиЯ ехрг3 до Мпй Три разных варианта семантики существует для этого оператора.
В языке Р1/1 вычисление шага (ехрг2) и предела (ехргЗ) выполняется один раз до входа в цикл. Второй вариант — вычисление шага и предела выполняется при каждом прохождении цикла. В третьем варианте (именно он используется в языке Алгол) при отрицательном шаге выход из цикла производится при значении параметра цикла, меньшем предела. Построить семантические действия для генерации команд стековой машины по синтаксической диаграмме для всех трех вариантов семантики. 13. Объясните, почему грамматика с леворекурсивными правилами не может быть 1.1.(1с)-грамматикой при любых 1 > 1.
ГЛАВА 6 Восходящие алгоритмы синтаксического анализа Восходящие алгоритмы синтаксического анализа работают по одной и той же схеме. На входе они имеют произвольную цепочку из терминальных и нетерминальных символов заданной грамматики, составляющих сентенциальную форму, порождаемую этой грамматикой. Напомним, что сентенциальной формой называется любая промежуточная цепочка вывода в данной грамматике. Цепочка эта просматривается слева направо с целью поиска в ней подцепочки, являющейся "связкой" (Ьапд!е) — правой частью продукции грамматики, которую нужно заменить нетерминалом — левой частью этой продукции — с получением предыдущей сентенциальной формы при выводе ее из начального символа. Многократное выполнение этой операции до тех пор, пока в качестве предыдущей сентенциальной формы получится начальный символ грамматики, позволяет восстановить правый канонический вывод данной цепочки из начального символа и, если необходимо, восстановить дерево вывода цепочки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
