Грамматики для условных операторов и операторов цикла

Грамматики для условных операторов и операторов цикла

Допустим, что рассматриваются условные операторы, аналогичные используемым в языке Паскаль, с разделителями 'if', 'then', 'else'. В качестве условия в таких операторах разрешается использовать отношения, состоящие из двух идентификаторов, соединенных знаками = и <. Структура такого оператора определяется двумя видами последовательностей фиксированной длины, для описания которых можно воспользоваться простым перечислением компонентов. Первая последовательность определяет полный и сокращенный условные операторы, а вторая - конструкцию "отношение". Схема грамматики, задающая эти последовательности, может быть изображена так:

V> ® .if. R4 C2

C2 ® .then. S C3

C3 ® .else. S | l

R4 ® I R3

R3 ® < I | = I

В этой грамматике S определяется схемой предыдущей грамматики. Рассмотрим описание операторов цикла, подобных используемым в языке Паскаль, с разделителями 'while', 'do', 'repeat', 'until'. Каждый оператор может быть описан в виде простой последовательности ограниченной длины, в которой используются построенные ранее грамматики для определения понятий R4 и S. На практике часто встречаются ситуации, когда удобнее работать с грамматикой, правая часть правил которой начинается терминальным символом. Построение подобных грамматик сводится к тому, что для каждого терминального символа заданной конструкции языка строится отдельное правило. Для рассматриваемых операторов цикла такие схемы грамматик с использованием определенных ранее нетерминальных символов имеют вид:

W ® .while. R4 C4

C4 ® .do. S

W1 ® .repeat. S C5

C5 ® .until. R4

Разбор цепочек

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

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

С практической точки зрения наибольший интерес представляет разбор по контекстно-свободным (КС и УКС) грамматикам. Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования. Для различных подклассов КС-грамматик имеются хорошо разработанные практически приемлемые способы решения задачи разбора.

Рассмотрим основные понятия и определения, связанные с разбором по КС-грамматике.

Определение: вывод цепочки b Î (VT)^* из S Î VN в КС-грамматике G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.

Определение: вывод цепочки b Î (VT)^* из S Î VN в КС-грамматике G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.

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

Например, для цепочки a+b+a в грамматике

G = ({a,b}, {S,T}, {S ® T | T+S; T ® a|b}, S)

можно построить выводы:

(1)  S®T+S®T+T+S®T+T+T®a+T+T®a+b+T®a+b+a

(2)  S®T+S®a+S®a+T+S®a+b+S®a+b+T®a+b+a

(3)  S®T+S®T+T+S®T+T+T®T+T+a®T+b+a®a+b+a

Здесь (2) - левосторонний вывод, (3) - правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.

Для КС-грамматик можно ввести удобное графическое представление вывода, называемое деревом вывода, причем для всех эквивалентных выводов деревья вывода совпадают.

Определение: дерево называется деревом вывода (или деревом разбора) в КС-грамматике G = {VT, VN, P, S), если выполнены следующие условия:

(1)  каждая вершина дерева помечена символом из множества (VN È VT È l), при этом корень дерева помечен символом S; листья - символами из (VT È l);

(2)  если вершина дерева помечена символом A Î VN, а ее непосредственные потомки - символами a₁, a₂, ... , a_n, где каждое a_i Î (VT È VN), то A ® a₁a₂...a_n - правило вывода в этой грамматике;

(3)  если вершина дерева помечена символом A Î VN, а ее единственный непосредственный потомок помечен символом l, то A ® l - правило вывода в этой грамматике.

Пример дерева вывода для цепочки a+b+a в грамматике G на рис.2.1:

Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка a Î L(G), для которой может быть построено два или более различных деревьев вывода. В противном случае грамматика называется однозначной.

Это утверждение эквивалентно тому, что цепочка a имеет два или более разных левосторонних (или правосторонних) выводов.

Рис.2.1. Дерево вывода для цепочки a+b+a

Определение: язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.

Пример неоднозначной грамматики:

G = ({if, then, else, a, b}, {S}, P, S),

где P = {S ® if b then S else S | if b then S | a}.

В этой грамматике для цепочки if b then if b then a else a можно построить два дерева вывода.

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

S ® if b then S | if b then S’ else S | a

S’ ® if b then S’ else S’ | a

Проблема, порождает ли данная КС-грамматика однозначный язык (т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой.

Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности:

(1)A ® AA | a

(2)A ® AaA | b

(3)A ® aA | Ab | g

(4)A ® aA | aAbA | g

Пример неоднозначного КС-языка:

L = {aⁱ b^j c^k | i = j или j = k}.

Интуитивно это объясняется тем, что цепочки с i=j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j=k. Но тогда, по крайней мере, некоторые из цепочек с i=j=k будут порождаться обеими группами правил  и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, что КС-язык L неоднозначный, приведен в [3, стр. 235-236]. Одна из грамматик, порождающих L, такова:

S ® AB | DC

A ® aA | l

B ® bBc | l

C ® cC | l

D ® aDb | l

Очевидно, что она неоднозначна.

Дерево вывода можно строить нисходящим либо восходящим способом.

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

Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.

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

Еще раз вернемся к неоднозначным грамматикам.

Рассмотрим некоторую грамматику G({+,-,*,/,(,),a,b},{S},P,S):

Р: S ® S+S | S-S | S*S | S/S | (S) | а | b

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

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

S Þ S+S Þ S*S+S Þ a*S+S Þ a*b+S Þ a*b+a

S Þ S*S Þ a*S Þ a*S+S Þ a*b+S Þ a*b+a

Каждому из этих вариантов будет соответствовать свое дерево вывода. Два варианта дерева вывода для цепочки «а*b+а» приведены на рис. 2.2.

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

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

Дадим более точное определение неоднозначной грамматики.

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

Рис. 2.2. Два варианта дерева цепочки «а*b+а» вывода для неоднозначной грамматики арифметических выражений

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

Проблема преобразования и эквивалентности грамматик.

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

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

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

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

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

Если грамматика все же является неоднозначной, то необходимо преобразовать ее в однозначный вид. Как правило, это возможно. Например, для рассмотренной выше неоднозначной грамматики арифметических выражений над операндами а и b существует эквивалентная ей однозначная грамматика следующего вида

G'({+,-,*./,(,),a,b},{S,Т,E},P',S);

Р':

S ® S+T | S-T | Т

Т ® Т*Е | Т/Е | Е

Е ® (S) | а | b

В этой грамматике для рассмотренной выше цепочки символов языка а*b+а возможен только один левосторонний вывод:

S Þ S+T Þ Т+Т Þ Т*Е+Т Þ Е*Е+Т Þ а*Е+Т Þ a*b+T Þ a*b+E Þ a*b+a

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

Т.о. нам необходимо решить две проблемы:

·                   во-первых, доказать, что две имеющиеся грамматики эквивалентны (задают один и тот же язык);

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

Рис. 2.3. Дерево вывода для однозначной грамматики арифметических выражений

Проблема эквивалентности грамматик в общем виде формулируется следующим образом: имеются две грамматики G и G', необходимо построить алгоритм, который бы позволял проверить, являются ли эти две грамматики эквивалентными.

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

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

В общем случае вопрос об алгоритмической неразрешимости проблем однозначности и эквивалентности грамматик сводится к вопросу об алгоритмической неразрешимости проблемы, известной как «проблема соответствий Поста». Проблема соответствий Поста формулируется следующим образом: имеется заданное множество пар непустых цепочек над алфавитом V: {(a1,b1), (a2,b2),..., (an,bn)}, n > 0, "n > i > 0: ai,bi Î V^*; необходимо проверить, существует ли среди них такая последовательность пар цепочек: (a1,b1), (a2,b2),..., (am,bm), m > 0 (необязательно различных), что a1a2…am = b1b2…bm. Доказано, что не существует алгоритма, который бы за конечное число шагов мог дать ответ на этот вопрос, хотя на первый взгляд постановка задачи кажется совсем несложной.

То, что проблема не решается в общем виде, совсем не значит, что ее нельзя решить в каждом конкретном случае. Например, для алфавита V = {а,b} можно построить множество пар цепочек {(abbb,b),(a,aab),(ba,b)} и найти одно из решений: (a,aab),(a,aab),(ba,b),(abbb,b) — видно, что (a)(a)(ba)(abbb) = (aab)(aab)(b)(b). А для множества пар цепочек {(ab,aba),(aba,baa),(baa,aa)} очевидно, что решения не существует.

Точно так же неразрешимость проблем эквивалентности и однозначности грамматик в общем случае совсем не означает, что они не разрешимы вообще. Для некоторых частных случаев — например, для определенных типов и классов грамматик (в частности, для регулярных грамматик) — эти проблемы решены. Также их иногда удается решить полностью или частично в каждом конкретном случае, и для конкретной заданной грамматики доказать, является ли она однозначной или нет. Например, приведенная выше грамматика G' для арифметических выражений над операндами а и Ь относится к классу грамматик операторного предшествования из типа КС-грамматик. На основе этой грамматики возможно построить распознаватель в виде детерминированного расширенного МП-автомата, а потому можно утверждать, что она является однозначной.

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

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

1. А ® АА | a,

2. А ® АaА | b,

3. А ® aА | Аb | g,

4. А ® aА | aАbА | g,

здесь AÎVN; a, b, g Î (VN È VT)*.

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

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

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