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