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