1.4.5. Проблема однозначности грамматик

Возьмем грамматику G4<T4, N4, P4, S>

T4 = {+, –, , /, (, ), a, b}

N4 = {S}

P4:

S  S + SS – SS  SS / Sab(S).

Представленная грамматика определяет язык арифметических выражений с четырьмя основными операциями и скобками над операндами a и b. Примерами предложений этого языка могут быть:

a  b + a; a  (a + b); a  b + a / b и т. д.

Вопрос для слушателей. Каким образом на основе данных правил может быть получена цепочка a  (a + b)?

Возьмем цепочку a  b + a и построим для нее левосторонний вывод:

1) S  S + S  S  S + S  a  S + S  a  b + S  a  b + a.

Возможен и второй вариант левостороннего вывода:

2) S  S  S  a  S  a  S + S  a  b + S  a  b + a.

Каждому из этих вариантов будет соответствовать свое дерево вывода, рис. 1.3.

а) б)

Рис. 1.3. Два варианта дерева вывода для цепочки a  b + a а) вариант 1; б) вариант 2

С точки зрения формального языка – эти два дерева вывода равноправны.

Но в данной грамматике G4 не учтены семантические особенности (умножение имеет более высокий приоритет, чем сложение).

Поэтому с точки зрения арифметических операций эта грамматика имеет неверную семантику, в ней нет приоритета операций и для равноправных операций не определен порядок выполнения (в арифметике – порядок действий слева направо). Хотя синтаксически структура выражений будет правильной.

Такая ситуация называется неоднозначностью в грамматике. Грамматики, допускающие неоднозначность нельзя использовать для построения компиляторов и языков программирования.

Грамматика называется однозначной, если для каждой цепочки символов языка, заданной этой грамматикой, можно построить единственный левосторонний (и единственный правосторонний) вывод, т. е. существует для каждой цепочки единственное дерево вывода. Иначе грамматика называется неоднозначной. Рассмотренная грамматика G4 является неоднозначной.

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

Первый вопрос – является ли данная грамматика однозначной?

Второй вопрос – если заданная грамматика неоднозначна, то как преобразовать ее к однозначному виду?

Однозначность – это свойство грамматики, а не языка. Для некоторых языков, заданных неоднозначными грамматиками, иногда удается построить эквивалентную однозначную грамматику, задающую тот же язык.

Для ответа на первый вопрос достаточно найти в заданном грамматикой языке хотя бы одну цепочку символов, которая допускала бы более чем один левосторонний (или правосторонний) вывод, как в рассмотренном примере. Однако не всегда удается обнаружить такую цепочку, поскольку перебрать все цепочки языка невозможно – как правило, их бесконечное число. Но, если такая цепочка не найдена, нельзя утверждать, что грамматика однозначна. Поэтому нужны другие способы проверки.

При ответе на второй вопрос тоже нет общих подходов и алгоритмов. Проблема решается методом проб и ошибок.

Например, для рассмотренной грамматики G4 существует эквивалентная ей однозначная грамматика G4, в которой:

T4 = T4 P4:

N4 = {S, T, E} S  S + TS – TT

T  T  ET / EE

E  (S)ab.

Утверждается, что в этой грамматике для неоднозначной цепочки a  b + a в грамматике G4 возможен только один левосторонний вывод.

S  S + T  T + T  T  E + T  a  E + T  a  b + E  a  b + a.

Этому выводу соответствует одно единственное дерево вывода, рис. 1.4.

Вопрос слушателям. Возможен ли правосторонний вывод той же цепочки a  b + a и в скольких вариантах?

Рис. 1.4. Дерево левостороннего вывода для цепочки a  b + a в грамматике G4

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

При решении второго вопроса необходимо решить две проблемы: во-первых, доказать, что две имеющиеся грамматики G и G эквивалентны, т. е. надо проверить утверждение, что L(G) = L(G); во-вторых, иметь возможность проверить, что вновь построенная грамматика является однозначной.

Доказано, к сожалению, что проблема эквивалентности грамматик в общем случае алгоритмически неразрешима. Это значит, что не только до сих пор не существует алгоритма, позволяющего проверить эквивалентность грамматик, но и доказано, что такой алгоритм в принципе не существует, а значит он никогда не будет создан. (Но «никогда не говори никогда»).

В общем виде неразрешима и проблема однозначности грамматик. Это значит, что не существует (и никогда не будет существовать) алгоритм, который позволял бы для произвольно заданной грамматики G проверить, является ли она однозначной. Аналогично, не существует алгоритма, который бы позволял преобразовать заведомо неоднозначную грамматику G в эквивалентную ей однозначную грамматику G.

Но для многих частных случаев, например для определенных типов и классов грамматик эти проблемы решены. К таким типам относятся регулярные грамматики. Грамматика G4 для которой найден эквивалент однозначности G4 относится к классу грамматик операторного предшествования из типа КС-грамматик. На основе этой грамматики возможно построить распознаватель в виде детерминированного расширенного МП-автомата, а потому можно утверждать, что она является однозначной.

Приведенные ниже 4 строчки правил, определяющих неоднозначность, относятся к КС-грамматикам. По наличию этих правил во всем множестве правил P грамматики, можно утверждать, что грамматика является неоднозначной.

Эти правила имеют следующий вид.

1. A  AA A  N.

2. A  AA , ,   V*.

3. A  AA.

4. A  AAA.

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

Например, в рассмотренной грамматике G4 во множестве правил P: S  S + SS – SS  SS/S(S)ab встречаются правила второго варианта: S  S + S и S  a, поэтому данная грамматика является неоднозначной.

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

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

Так что не все так безнадежно!

Лекция 7

2. Принципы построения трансляторов

2.1. Основные определения

2.1.1. Формальное определение транслятора

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

Трансляторы подразделяются на Ассемблеры и Компиляторы – в зависимости от исходного языка программы, которую они обрабатывают. Ассемблеры работают с Автокодами (Мнемокодами) или языками Ассемблера. Компиляторы – с языками высокого уровня (ЯВУ).

В определении Т трижды встречается слово программа.

Во-первых, сам транслятор является программой, входящей в программное обеспечение (ПО) и выполняемой в рамках операционной системы (ОС). Все составные части транслятора представляют собой динамические загружаемые библиотеки или модули этой программы со своими входными и выходными данными. Однако не исключается и реализация Т с помощью аппаратных средств, особенно при современном уровне технологий. То есть, распознаватели могут быть аппаратной частью компьютера!

Во-вторых, исходными данными для работы транслятора служит программа на исходном языке программирования (исходный модуль), понимаемая как единое целое для проведения трансляции. Обычно – это символьный файл, удовлетворяющий синтаксическим и семантическим требованиям входного языка. Для некоторых входных языков сложной структуры исходная программа обрабатывается Макропроцессором (или Препроцессором) и на выходе его получается новая редакция, которая является исходной для трансляции. Так, если Макропроцессор заменил в программе некоторый текст А на текст В, то транслятор уже видит только текст В, и «не знает» был ли этот текст написан рукой программиста или подставлен Макропроцессором.

В-третьих, выходными данными Т является программа на результирующем языке, которая так и называется результирующей программой. Она строится по синтаксическим правилам выходного языка Т, а ее смысл определяется семантикой выходного языка.

Равносильность (эквивалентность) исходной и результирующей программ означает совпадение их смысла с точки зрения семантики входного языка для одной и семантики выходного языка для другой программы. Без выполнения этого требования транслятор теряет смысл.

Если исходная программа правильная (синтаксически и семантически), то результат работы Т – результирующая программа. Если же исходная программа неправильная (содержит хотя бы одну ошибку), то результатом работы Т будет оперативное сообщение об ошибке с указанием места ошибки.