Правила, задающие неоднозначность в грамматиках

Вывод. Цепочки вывода

Цепочки вывода. Сентенциальная форма

Выводом называется процесс порождения предложения языка на основе правил определяющей язык грамматики. Чтобы дать формальное определение процессу вывода, необходимо ввести еще несколько дополнительных понятий.

Цепочка р = 5jy5₂ называется непосредственно выводимой из цепочки а = 8i(n8₂ в грамматике G(VT,VN,P,S), V = VTuVN, 8₁₍ у, 6₂ е V, со е V⁺, если в граммати­ке G существует правило: со-»у е Р. Непосредственная выводимость цепочки р из цепочки а обозначается так: а=>р. Иными словами, цепочка р выводима из цепочки а в том случае, если можно взять несколько символов в цепочке а, заме­нить их на другие символы согласно некоторому правилу грамматики и полу­чить цепочку р. В формальном определении непосредственной выводимости любая из цепочек 5_t или 5₂ (а равно и обе эти цепочки) может быть пустой. В предельном случае вся цепочка а может быть заменена на цепочку р, тогда в грамматике G должно существовать правило: а-»р е Р.

Цепочка р называется выводимой из цепочки а (обозначается а=>*Р) в том слу­чае, если выполняется одно из двух условий:

□ р непосредственно выводима из а (а=>Р);

Q 3 у, такая, что: у выводима из аи р непосредственно выводима из у (а=>*у и т=>Р).

Это рекурсивное определение выводимости цепочки. Суть его заключается в том, что цепочка р выводима из цепочки а, если а=>р или же если можно построить последовательность непосредственно выводимых цепочек от а к р следующего

В общем виде невозможно проверить, является ли заданная грамматика одно­значной или нет. Однако для КС-грамматик существуют определенного вида правила, по наличию которых в множестве правил грамматики G(VT,VN,P,S) можно утверждать, что она является неоднозначной. Эти правила имеют сле­дующий вид:

1. А -» АА | а,

2. А -> АаА | р,

3. А -» аА | Ар | у,

4. А -> аА | аАрА | у,

здесь AeVN; a,p,ye(VNuVT)*.

Если в заданной грамматике встречается хотя бы одно правило подобного вида (любого из приведенных вариантов), то доказано, что такая грамматика точно будет неоднозначной. Однако если подобных правил во всем множестве правил грамматики нет, это совсем не означает, что грамматика является однозначной. Такая грамматика может быть однозначной, а может и не быть. То есть отсутст­вие правил указанного вида (всех вариантов) — это необходимое, но не достаточ­ное условие однозначности грамматики.

С другой стороны, установлены условия, при удовлетворении которым грамма­тика заведомо является однозначной. Они справедливы для всех регулярных и многих классов контекстно-свободных грамматик. Однако известно, что эти ус­ловия, напротив, являются достаточными, но не необходимыми для однозначно­сти грамматик.

В рассмотренном выше примере грамматики арифметических выражений с опе­рандами а и b — G({+,-,*,/,(,),а,b},{S},P,S) — во множестве правил Р: S -» S+S | S-S | S*S | S/S | (S) | а | b встречаются правила 2 типа. Поэтому данная грам­матика является неоднозначной, что и было показано выше.

Распознаватели. Задача разбора

Общая схема распознавателя

Для каждого языка программирования (как, наверное, и для многих других язы­ков) важно не только уметь построить текст программы на этом языке, но и оп­ределить принадлежность имеющегося текста к данному языку. Именно эту задачу решают компиляторы в числе прочих задач (компилятор должен не толь­ко распознать исходную программу, но и построить эквивалентную ей результи­рующую программу). В отношении исходной программы компилятор выступает как распознаватель, а человек, создавший программу на некотором языке, высту­пает в роли генератора цепочек этого языка.

распознавании, оадача разоора

Распознаватель (или разборщик) — это специальный алгоритм, который позво­ляет определить принадлежность цепочки символов некоторому языку. Задача распознавателя заключается в том, чтобы на основании исходной цепочки дать ответ, принадлежит ли она заданному языку или нет. Распознаватели, как было сказано выше, представляют собой один из способов определения языка.

В общем виде распознаватель можно отобразить в виде условной схемы, пред­ставленной на рис. 9.5.

Входная цепочка символов

' Считывающая головка

УУ К-

Рабочая

(внешняя)

память

Рис. 9.5. Условная схема распознавателя

Следует подчеркнуть, что представленный рисунок — всего лишь условная схе­ма, отображающая работу алгоритма распознавателя. Ни в коем случае не стоит искать подобного устройства в составе компьютера. Распознаватель, являющийся частью компилятора, представляет собой часть программного обеспечения ком­пьютера.

Как видно из рисунка, распознаватель состоит из следующих основных компо­нентов:

□ ленты, содержащей исходную цепочку входных символов, и считывающей го­
ловки, обозревающей очередной символ в этой цепочке;

□ устройства управления (УУ), которое координирует работу распознавателя,
имеет некоторый набор состояний и конечную память (для хранения своего
состояния и некоторой промежуточной информации);

□ внешней (рабочей) памяти, которая может хранить некоторую информацию в
процессе работы распознавателя и в отличие от памяти УУ может иметь не­
ограниченный объем.

Распознаватель работает с символами своего алфавита — алфавита распознава­теля. Алфавит распознавателя конечен. Он включает в себя все допустимые сим­волы входных цепочек, а также некоторый дополнительный алфавит символов, которые могут обрабатываться УУ и храниться в рабочей памяти распознава­теля.

В процессе своей работы распознаватель может выполнять некоторые элемен­тарные операции, такие как чтение очередного символа из входной цепочки, сдвиг входной цепочки на заданное количество символов (вправо или влево), Доступ к рабочей памяти для чтения или записи информации, преобразование информации в памяти, изменение состояния УУ. То, какие конкретно операции Должны выполняться в процессе работы распознавателя, определяется в УУ.

ЗТ8 Глава 9. Формальные языки и грамматики

Распознаватель работает по шагам или тактам. В начале такта, как правило, счи-тывается очередной символ из входной цепочки, и в зависимости от этого симво­ла УУ определяет, какие действия необходимо выполнить. Вся работа распозна­вателя состоит из последовательности тактов. В начале каждого такта состояние распознавателя определяется его конфигурацией. В процессе работы конфигура­ция распознавателя меняется.

Конфигурация распознавателя определяется следующими параметрами:

□ содержимое входной цепочки символов и положение считывающей головки
в ней;

□ состояние УУ;

□ содержимое внешней памяти.

Для распознавателя всегда задается определенная конфигурация, которая счи­тается начальной конфигурацией. В начальной конфигурации считывающая головка обозревает первый символ входной цепочки, УУ находится в заданном начальном состоянии, а внешняя память либо пуста, либо содержит строго опре­деленную информацию.

Кроме начального состояния для распознавателя задается одна или несколько конечных конфигураций. В конечной конфигурации считывающая головка, как правило, находится за концом исходной цепочки (часто для распознавателей вводят специальный символ, обозначающий конец входной цепочки).

Распознаватель допускает входную цепочку символов а, если, находясь в началь­ной конфигурации и получив на вход эту цепочку, он может проделать последо­вательность шагов, заканчивающуюся одной из его конечных конфигураций.

Формулировка «может проделать последовательность шагов» более точна, чем прямое указание «проделает последовательность шагов», так как для многих распознавателей при одной и той же входной цепочке символов из начальной конфигурации могут быть допустимы различные последовательности шагов, не все из которых ведут к конечной конфигурации.

Язык, определяемый распознавателем, — это множество всех цепочек, которые допускает распознаватель.

Далее в главах этого пособия рассмотрены конкретные типы распознавателей для различных типов языков. Но все, что было сказано здесь, относится ко всем без исключения типам распознавателей для всех типов языков.

Дата добавления: 2015-06-27