Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Контекстно-свободные языки и грамматики

Контекстно-свободные языки и грамматики


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


Определение КС-грамматик и КС-языков было дано ранее. Напомним, что порождающую грамматику [math]G=(V,N,S,P)[/math] называют контекстно-свободной (или КС-грамматикой), если каждое правило вывода из множества [math]P[/math] имеет вид [math]A\to\gamma[/math], где [math]A\in N[/math] — нетерминал, а [math]\gamma\in(V\cup N)^{\ast}[/math] — цепочка в объединенном алфавите грамматики. Таким образом, неформально каждое правило вывода в КС-грамматике есть правило замены нетерминального символа цепочкой (возможно, пустой) в объединенном алфавите.


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


Пример 8.1. Рассмотрим КС-грамматику [math]G_0=(\{a,b\},\{S,A,B,C\},S,P_0)[/math], где множество правил вывода [math]P_0[/math] имеет вид:


[math]\begin{array}{lrlr}S\to ABC,&\quad (1)&\qquad B\to a,&\quad (5)\\ A\to BB,&\quad (2)&\qquad C\to AA,&\quad (6)\\ A\to\lambda,&\quad (3)&\qquad C\to b.&\quad (7)\\ B\to CC,&\quad (4)&\qquad & \end{array}[/math]

В этой грамматике рассмотрим такой вывод:


[math]\begin{aligned}&S\vdash_{(1)} ABC\vdash_{(2)} BBBC\vdash_{(6)} BBBAA\vdash_{(3)} BBB\lambda A\vdash_{(4)} CCBBA\vdash_{(7)}^2\\ &\vdash_{(7)}^2 bbBBA\vdash_{(5)}^2 bbaaA\vdash_{(2)} bbaaBB\vdash_{(5)}^2 bbaaaa.\end{aligned}[/math]

Первый шаг процесса построения дерева вывода

По шагам этого вывода проследим процесс построения дерева вывода. Первому шагу соответствует дерево, изображенное на рис. 8.1.


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


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


Второй шаг процесса построения дерева вывода

На втором шаге применяется правило (2) и производится замена вхождения (единственного в данном случае) символа [math]A[/math] цепочкой [math]BB[/math]. Поэтому вершину дерева на рис. 8.1 с меткой [math]A[/math] заменим кустом, Рис. 8.2 как показано на рис. 8.2.


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


Дерево после третьего шага процесса построения дерева вывода

Четвёртый шаг процесса построения дерева вывода

Четвертый шаг требует более подробного комментария. Здесь в кроне дерева имеется несколько вхождений символа [math]A[/math]. На четвертом шаге первое вхождение символа [math]A[/math] в цепочку [math]BBAA[/math] заменяется пустой цепочкой. Поэтому очередной шаг в построении дерева будет состоять в том, что первый лист с меткой [math]A[/math] кроне дерева должен быть заменен кустом с корнем [math]A[/math] и единственным листом с меткой [math]\lambda[/math]. Тогда получим дерево, изображенное на рис. 8.5.


Крона вновь полученного дерева — это цепочка [math]BBB\lambda A[/math], выведенная из аксиомы за четыре шага. Она, как элемент свободного моноида [math](V\cup N)^{\ast}[/math], равна (в силу известных свойств пустой цепочки ) цепочке [math]BBBA[/math]. Обратим здесь внимание на то, что, хотя пустая цепочка и не является символом ни одного из алфавитов грамматики, она, как было уже сказано, может быть меткой вершины дерева вывода. Тем самым в дереве вывода фиксируются все вхождения выбрасываемых, т.е. заменяемых в процессе вывода пустой цепочкой, нетерминалов. Это равносильно выделению в выводимой цепочке некоторых вхождений в нее пустой цепочки.


Пятый шаг процесса построения дерева вывода

На пятом шаге первое вхождение символа [math]B[/math] в цепочку [math]BBBA[/math] заменяется цепочкой [math]CC[/math]. Этому отвечает новое построение на очередном дереве, состоящее в замене первого листа кроны с меткой [math]B[/math] кустом, изображенным на рис. 8.6, после чего получим дерево, показанное на рис. 8.7.


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


Дерево вывода

Из разобранного примера следует, что шаги построения дерева вывода в точности соответствуют шагам самого вывода, причем после каждого шага получаем некоторое дерево (назовем его частичным деревом вывода, полученным после данного шага). Начинаем построение с корня, и его меткой служит тот нетерминал, с которого начинается вывод (в частности, это может быть аксиома грамматики). Если на очередном шаге вывода применяется правило [math]B\to X_1X_2\ldots X_m[/math], где [math]X_i\,(1\leqslant i\leqslant m)[/math] — либо символ объединенного алфавита, либо пустая цепочка, то тот лист частичного дерева вывода, полученного перед этим шагом, который имеет метку [math]B[/math] и соответствует заменяемому вхождению символа [math]B[/math], заменяется кустом с корнем [math]B[/math] и листьями [math]X_1,X_2,\ldots,X_m[/math].


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


Дерево вывода цепочки CCa для нетерминала A

2. Совершенно необязательно рассматривать только деревья выводов терминальных цепочек а из аксиомы. Дерево вывода может быть построено по выводу любой цепочки в объединенном алфавите из любого нетерминала грамматики. Так, мы могли бы на базе разобранного выше примера нарисовать дерево вывода цепочки [math]CCa[/math] из нетерминала [math]A[/math], показанное на рис. 8.9.


3. Можно заметить, что разные выводы одной и той же цепочки из заданного нетерминала могут дать одно и то же дерево вывода. Так, дерево, изображенное на рис. 8.9, можно построить по двум различным выводам:


[math]A\vdash BB\vdash CCB\vdash CCa[/math] и [math]A\vdash BB\vdash Ba\vdash CCa[/math].

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


*Здесь, в рамках сугубо неформального изложения, мы не даем строгого определения эквивалентных выводов.


Теперь дадим формальное определение дерева вывода. Рассмотрим множество (ориентированных) деревьев, вершины которых помечены символами некоторого алфавита [math]W[/math]. Ориентированное дерево, каждая вершина которого помечена символом некоторого алфавита, будем называть помеченным деревом. Если, кроме того, задано определенное правило перечисления меток вершин дерева, образующих некоторое подмножество вершин всего дерева, в частности листьев дерева, то такое помеченное дерево называют упорядоченным деревом. Всюду в дальнейшем, изображая деревья выводов, условимся понимать их как упорядоченные деревья, метки листьев которых перечисляются всегда слева направо. Слева направо будем также перечислять и сыновей каждой вершины. Будем считать, что в машинном представлении деревьев выводов порядок "слева направо" при изображении дерева на плоскости соответствует порядку от первого элемента списка смежности вершины к последнему. Дерево, корень которого помечен символом [math]A[/math], а листья имеют метки [math]X_1,X_2,\ldots,X_m[/math], договоримся записывать в виде цепочки


[math]A\downdownarrows X_1X_2\ldots X_m[/math] (с двумя стрелками).

Если рассматриваемое дерево является кустом, то условимся писать


[math]A\downarrow X_1X_2\ldots X_m[/math] (с одной стрелкой).

Листья дерева, обозначенного таким образом, отождествим с символами цепочки [math]X_1,X_2,\ldots,X_m[/math]. Это значит, что, говоря о листе [math]X_i[/math], мы имеем в виду лист помеченного дерева, меткой которого является символ [math]X_i[/math] и который в перечислении листьев слева направо получает номер [math]i[/math]. Тем самым устанавливается взаимно однозначное соответствие между листьями помеченного дерева и вхождениями символов алфавита [math]W[/math] в цепочку [math]X_1,X_2,\ldots,X_m[/math]. Например, записывая дерево в виде [math]A\downdownarrows BBCBC[/math], мы можем говорить о листе [math]B[/math], соответствующем первому вхождению символа [math]B[/math] в цепочку [math]BBCBC[/math], или же, обозначив [math]BBCBC[/math] через [math]\alpha[/math], о листе [math]\alpha(1)[/math]. Тогда листья [math]\alpha(1),\, \alpha(2)[/math] и [math]\alpha(4)[/math] — это разные листья дерева, хотя их меткой является один и тот же символ алфавита [math]W[/math].


Расширим множество помеченных деревьев, допуская в качестве меток их вершин и пустую цепочку. В этом случае, в записи [math]A\downdownarrows X_1X_2\ldots X_m[/math], представляющей дерево корнем [math]A[/math] и листьями [math]X_1,X_2,\ldots,X_m[/math], среди меток листьев, т.е. элементов [math]X_i,~i=\overline{1,m}[/math] могут быть и пустые цепочки. Тогда, говоря о листе с меткой [math]\lambda[/math], нужно указывать, какое вхождение пустой цепочки [math]\lambda[/math] в цепочку [math]X_1X_2\ldots X_m[/math] имеется в виду.


Дерево вывода грамматики

Пример 8.2. а. Дерево вывода, изображенное на рис. 8.8, может быть обозначено так: [math]S\downdownarrows bbaa\lambda aa[/math]. В нем лист с меткой [math]\lambda[/math] ответствует вхождению [math](bbaa,\lambda,aa)[/math] пустой цепочки в цепочку [math]bbaaaa[/math].


б. Для грамматики из примера 8.1 вывод


[math]\begin{aligned}S&\vdash ABC\vdash BBBC\vdash aBBC\vdash aCCBC\vdash aAACBC\vdash a\lambda ACBC\vdash a\lambda\lambda CBC\vdash\\ &\vdash a\lambda\lambda AABC\vdash a\lambda\lambda\lambda ABC\vdash a\lambda\lambda\lambda\lambda BC\vdash a\lambda\lambda\lambda\lambda aC\vdash a\lambda\lambda\lambda\lambda ab=aab\end{aligned}[/math]

имеет дерево, показанное на рис. 8.10. В этом дереве любой его лист с меткой [math]\lambda[/math] соответствует одному и тому же вхождению пустой цепочки в выводимую цепочку [math]aab[/math], а именно вхождению [math](a,\lambda,ab)[/math], так как для любого натурального [math]n[/math] выполняется равенство [math]\lambda^n=\lambda[/math].


в. Представленное на рис. 8.11 дерево вывода цепочки [math]aabaa[/math] может быть задано записью [math]S\downdownarrows aa\lambda\lambda b\lambda aa[/math]. Оно имеет три листа с меткой [math]\lambda[/math].


Первые два соответствуют вхождению [math](aa,\lambda,baa)[/math], а третье — вхождению [math](aab,\lambda,aa)[/math] пустой цепочки в выводимую цепочку.


Дерево вывода цепочки aabaa



Помеченное дерево [math]A\downdownarrows X_1X_2\ldots X_m[/math] называют λ-свободным, если среди меток [math]X_1,X_2,\ldots,X_m[/math] его листьев нет пустой цепочки. Из предыдущих примеров можно заключить, что не всякая цепочка, выводимая в КС-грамматике из какого-либо нетерминала, имеет λ-свободное дерево вывода.


Помеченное дерево, полученное из дерева


[math]A\downdownarrows X_1\ldots X_{i-1}X_iX_{i+1}\ldots X_m[/math]

заменой листа [math]X_i\ne\lambda[/math] деревом [math]X\downdownarrows Y_1\ldots Y_k[/math], будем записывать в виде цепочки


[math]A\downdownarrows X_1\ldots X_{i-1}[X\downdownarrows Y_1\ldots Y_k]X_{i+1}\ldots X_m\,.[/math]

Это дерево, поскольку в нем вместо листа [math]X_i[/math], возникают листья с метками [math]Y_1\ldots Y_k[/math], можно представить также в виде


[math]A\downdownarrows X_1\ldots X_{i-1}Y_1\ldots Y_kX_{i+1}\ldots X_m\,.[/math]

Дерево вывода цепочки [math]\beta[/math] в объединенном алфавите из нетерминала [math]A[/math] в КС-грамматике [math]G=(V,N,S,P)[/math] — это помеченное дерево, метками вершин которого являются символы объединенного алфавита [math]V\cup N[/math] или пустая цепочка [math]\lambda[/math] и которое строится по следующим правилам:


1) дерево любого вывода длины 0 состоит из единственной вершины, помеченной нетерминалом [math]A[/math] (в данном случае цепочка [math]\beta=A[/math]);

2) дерево вывода [math]A\vdash\lambda[/math] — это дерево [math]A\downarrow\lambda[/math] (в данном случае цепочка [math]\beta=\lambda[/math]);

3) дерево вывода [math]A\vdash\alpha[/math], где [math]\alpha[/math] — непустая цепочка, есть дерево [math]A\downarrow\alpha[/math];

4) если [math]\alpha[/math] — цепочка в объединенном алфавите и [math]A\downdownarrows X_1X_2\ldots X_m[/math] дерево некоторого вывода [math]\mathbf{D}[/math] этой цепочки из нетерминала [math]A[/math], где [math]\alpha=X_1X_2\ldots X_m[/math] и для каждого [math]i=\overline{1,m}[/math] имеем [math]X_i\in V\cup N\cup\{\lambda\}[/math], а для некоторого [math]i\in[1,m][/math] есть [math]X_i=B\in N[/math] — нетерминальный символ грамматики [math]G[/math], и в множестве правил вывода [math]P[/math] грамматики [math]B[/math] есть правило [math]B\to Y_1\ldots Y_k[/math], то дерево


[math]A\downdownarrows X_1\ldots X_{i-1}[X_i\downarrow Y_1\ldots Y_k]Y_{i+1}\ldots Y_m[/math]

есть дерево такого вывода цепочки [math]\beta= X_1\ldots X_{i-1} Y_1\ldots Y_kX_{i+1}\ldots X_m[/math] из нетерминала [math]A[/math], что его последний шаг имеет вид


[math]X_1\ldots X_{i-1}BX_{i+1}\ldots X_m\vdash_{B\to Y_1\ldots Y_k} X_1\ldots X_{i-1} Y_1\ldots Y_kX_{i+1}\ldots X_m\,,[/math]

а вывод цепочки [math]\alpha=X_1\ldots X_{i-1}BX_{i+1}\ldots X_m[/math] из [math]A[/math] совпадает с [math]\mathbf{D}[/math].


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


Это значит, что при построении дерева вывода по левому выводу данной цепочки [math]\alpha[/math] из данного нетерминала [math]A[/math] каждый раз "развертывается" в куст самый левый лист кроны частичного дерева вывода, помеченный нетерминальным символом, а при построении дерева вывода по правому выводу то же совершается с самым правым листом кроны.


Для построенного выше в примере 8.2.а дерева вывода левый вывод имеет вид


[math]\begin{aligned}S&\vdash \boldsymbol{A}BC\vdash \boldsymbol{B}BBC\vdash \boldsymbol{C}CBBC\vdash b\boldsymbol{C}BBC\vdash bb\boldsymbol{B}BC\vdash bba\boldsymbol{B}C\vdash bbaa\boldsymbol{C}\vdash\\ &\vdash bbaa\boldsymbol{A}A\vdash bbaa\lambda\boldsymbol{A}\vdash bbaa\boldsymbol{B}B\vdash bbaaa\boldsymbol{B}\vdash bbaaaa\,.\end{aligned}[/math]

Правый вывод той же цепочки имеет вид


[math]\begin{aligned}S&\vdash AB\boldsymbol{C}\vdash ABA\boldsymbol{A}\vdash ABAB\boldsymbol{B}\vdash ABA\boldsymbol{B}a\vdash ABAaa\vdash A\boldsymbol{B}\lambda aa\vdash\\ &\vdash \boldsymbol{A}aaa\vdash B\boldsymbol{B}aaa\vdash \boldsymbol{B}aaaa\vdash C\boldsymbol{C}aaaa\vdash \boldsymbol{C}baaaa\vdash bbaaaa\,.\end{aligned}[/math]

В обоих выводах полужирным шрифтом выделены заменяемые вхождения нетерминалов, а также удалено возникающее после применения правила [math]A\to\lambda[/math] вхождение пустой цепочки [math]\lambda[/math]. Можно показать, что эквивалентные выводы различаются между собой только порядком применения правил. Сами же применяемые правила и вхождения заменяемых нетерминалов у эквивалентных выводов одинаковы.


Мы часто будем использовать условное графическое обозначение дерева вывода [math]A\downdownarrows X_1X_2\ldots X_m[/math] в виде "треугольника", одна из вершин которого помечена нетерминалом [math]A[/math], а противолежащая этой вершине сторона символизирует всю цепочку [math]\alpha= X_1X_2\ldots X_m[/math]. Иногда будем точками (или штрихами) отмечать отдельные символы цепочки [math]\alpha[/math] или листья с меткой [math]\lambda[/math] (рис. 8.12). Кроме того, по традиции деревья выводов изображаются без стрелок на дугах (хотя понимаются как ориентированные деревья).


Отдельные символы цепочки или листья с меткой

Из определения дерева вывода понятно, что в нем дуга из вершины с меткой [math]X[/math] ведет в вершину с меткой [math]Y[/math] тогда и только тогда, когда на некотором шаге вывода применяется правило вывода [math]X\to\gamma_1 Y\gamma_2[/math], где [math]\gamma_1[/math] и [math]\gamma_2[/math] — цепочки в объединенном алфавите (возможно, пустые). Следовательно, число дуг любого пути ненулевой длины дерева вывода, т.е. длина этого пути, есть не что иное, как число применений правил вывода заданной КС-грамматики в некотором фрагменте вывода. А так как в КС-грамматике каждое применение правила вывода есть замена вхождения нетерминала некоторой цепочкой в объединенном алфавите, то длина пути в дереве вывода равна числу замен нетерминалов в соответствующем фрагменте вывода. Например, для дерева, показанного на рис. 8.8, пути [math]S\to A\to B\to a[/math] отвечает фрагмент вывода [math]S\vdash ABC\vdash BBBC\vdash BaBC[/math]. Обратим внимание на то, что приведенный фрагмент есть фрагмент одного из множества эквивалентных выводов, имеющих данное дерево.


Таким образом, по заданному пути в дереве вывода однозначно восстанавливается фрагмент одного из множества эквивалентных выводов. Более того, по дереву вывода, построенному по одному из множества эквивалентных выводов, можно восстановить все выводы этого множества, в частности левый и правый. Можно показать, что для этого необходимо задать определенный порядок посещения вершин дерева при поиске в глубину от корня. Левый (соответственно правый) вывод будет восстановлен, если каждый раз при поиске в глубину от очередной вершины задавать продолжение поиска от самого левого (соответственно самого правого) сына этой вершины.


Замечание 8.2. Длина вывода в общем случае не меньше, чем высота дерева этого вывода. Можно доказать, что для фиксированной КС-грамматики [math]G[/math] существует такая константа [math]C_G[/math], зависящая от [math]G[/math], что для любого вывода [math]\mathbf{D}[/math] (начинающегося каким-либо нетерминалом) и дерева [math]\mathbf{T}[/math] этого вывода разность между длиной [math]l_{\mathbf{D}}[/math] вывода [math]\mathbf{D}[/math] и высотой [math]h_{\mathbf{T}}[/math] дерева [math]\mathbf{T}[/math] не превышает [math]C_G\colon l_{\mathbf{D}}- h_{\mathbf{T}}\leqslant C_G[/math]. Другими словами, разность между длиной вывода и высотой дерева вывода для фиксированной грамматики ограничена сверху. Это обусловлено тем, что указанная разность определяется числом нетерминалов в правых частях правил вывода, которое в пределах заданной грамматики всегда ограничено. Это число, говоря неформально, определяет, как сильно "ветвится" дерево вывода в процессе его "роста". Для линейной грамматики, как нетрудно сообразить, высота дерева вывода равна длине вывода. Однако если не фиксировать грамматику, то разность между длиной вывода и высотой дерева вывода может быть сколь угодно большой. Это можно подтвердить таким простым примером.


Рассмотрим семейство КС-грамматик [math]G_m=(V_m,N_m,S,P_m)[/math], где [math]m\geqslant1,~ V_m=\{a_1,\ldots,a_m\},~ N_m=\{S,B_1,\ldots,B_m\}[/math], а множество правил вывода [math]P_m[/math] имеет вид


[math]S\to B_1\ldots B_m,\qquad B_1\to a_1,\ldots, B_m\to a_m.[/math]

Высота дерева вывода

Грамматика [math]G_m[/math] порождает единственную терминальную цепочку [math]a_1,\ldots,a_m[/math]. Высота дерева вывода этой цепочки равна 2 и не зависит от [math]m[/math] (рис. 8.13), тогда как длина вывода определяется числом [math]m+1[/math].


Пусть фиксировано ориентированное дерево [math]\mathbf{T}[/math] с корнем [math]R[/math]. Выделим в нем произвольно вершину [math]Q[/math], не являющуюся ни листом, ни корнем, называемую внутренней вершиной дерева. Образуем поддерево дерева [math]\mathbf{T}[/math] , объявив его корнем вершину. Такое поддерево назовем символьным поддеревом, если оно содержит все вершины исходного дерева [math]\mathbf{T}[/math], достижимые из вершины [math]Q[/math]. Ясно, что высота любого максимального поддерева больше нуля и меньше высоты дерева [math]\mathbf{T}[/math]. Для помеченного дерева [math]\mathbf{T}[/math] нетрудно проверить справедливость следующей теоремы.




Дерево языка с листьями

Теорема 8.1. Крона любого максимального поддерева помеченного дерева есть подцепочка кроны всего дерева.


Замечание 8.3. Сформулированное утверждение достаточно прозрачно и означает, что если в помеченном дереве [math]\mathbf{T}[/math] фиксировать произвольно внутреннюю вершину [math]Q[/math] и рассмотреть крону максимального поддерева с корнем [math]Q[/math], то все листья кроны этого поддерева, расположенные между самым левым [math](L)[/math] и самым правым [math](L')[/math] листьями, достижимыми из [math]Q[/math], также достижимы из [math]Q[/math] (рис. 8.14).


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


Дерево вывода цепочки bAAa из нетерминала A в грамматике

Следствие 8.1. Если в дереве вывода некоторой цепочки [math]\alpha[/math] из нетерминала [math]A[/math] фиксировать произвольно внутреннюю вершину, помеченную нетерминалом [math]B[/math], то максимальное поддерево с корнем в фиксированной вершине (с меткой [math]B[/math]) является деревом вывода некоторой подцепочки [math]\beta[/math] цепочки [math]\alpha[/math] из нетерминала [math]B[/math], т.е. существуют такие цепочки [math]\gamma_1[/math] и [math]\gamma_2[/math], что [math]\alpha=\gamma_1\beta\gamma_2[/math] и [math]A\vdash^{\ast}\gamma_1B\gamma_2\vdash^{\ast}\gamma_1\beta\gamma_2[/math] (рис. 8.15).


Так, для дерева вывода цепочки [math]bAAa[/math] из нетерминала [math]A[/math] в грамматике [math]G_0[/math] из примера 8.1 (рис. 8.16), фиксируя максимальное поддерево с корневой вершиной [math]C[/math]С (вторая вершина слева на первом уровне, выделена полужирным шрифтом), получим [math]\gamma_1=b,~\beta=AA,~ \gamma_2=a[/math], Соответствующее этому максимальному поддереву разбиение вывода на два фрагмента, может быть, например, таким: [math]A\vdash BB\vdash CCB\vdash bCB\vdash bCa[/math] (первый фрагмент) и [math]C\vdash AA[/math] (второй фрагмент).


Дерево вывода цепочки bAAa из нетерминала A в грамматике 2

Описанная в следствии 8.1 "декомпозиция" дерева вывода и соответственно вывода, по которому построено это дерево, может быть интерпретирована так: выводя цепочку [math]\alpha[/math] из нетерминала [math]A[/math], мы, получив на некотором шаге цепочку, содержащую выделенное вхождение нетерминала [math]B[/math], "замораживаем" этот нетерминал и продолжаем замены нетерминалов слева и справа от [math]B[/math], выводя начало (подцепочку [math]\gamma_1[/math]) и конец (подцепочку [math]\gamma_2[/math]) цепочки [math]\alpha[/math]. После этого мы "размораживаем" нетерминал [math]B[/math] и "довыводим" из него середину цепочки [math]\alpha[/math] — подцепочку [math]\beta[/math].




Однозначности КС-грамматики


Понятие дерева вывода связано с понятием однозначности КС-грамматики.


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


Поскольку по дереву вывода цепочки [math]\alpha[/math] из нетерминала [math]A[/math] однозначно строится как левый, так и правый вывод данной цепочки, то определение 8.1 можно сформулировать иначе: КС-грамматика однозначна, если каждая цепочка порождаемого ею языка имеет единственный левый и единственный правый вывод.


Рассмотрим один хрестоматийный пример неоднозначной грамматики.


Пример 8.3. Зададим грамматику [math]GE[/math] следующим образом:


[math]GE= \bigl(\{a,b,\mathbf{if},\mathbf{then},\mathbf{else}\}, \{S\},S, S\to\mathbf{if}~b~ \mathbf{then}~ S~\mathbf{else}~S\mid \mathbf{if}~b~\mathbf{then}~S\mid a\bigr).[/math]

Эта грамматика описывает "абстрактный синтаксис" операторов условного перехода в некотором "паскалеобразном" языке программирования. Термин "абстрактный синтаксис" в данном случае означает, что мы отвлекаемся от структуры как операторов языка, так и логических условий.


Терминальный символ [math]a[/math] означает произвольный оператор (или последовательность операторов), а терминальный символ [math]b[/math] — произвольное логическое условие. Кроме того, терминалами грамматики являются также лексемы [math]\mathbf{if},\,\mathbf{then}[/math] и [math]\mathbf{else}[/math], формирующие "скелет" любого оператора условного перехода.


Определенная таким образом грамматика неоднозначна, что усматривается из такого примера: цепочка [math]\mathbf{if}~b~ \mathbf{then~if}~b~ \mathbf{then}~a~ \mathbf{else}~a[/math] имеет два дерева вывода (рис. 8.17 и 8.18).


Два дерева вывода неоднозначной грамматики

Заметим (неформально), что наличие нескольких деревьев вывода одной и той же цепочки имеет отношение к семантике рассматриваемого языка. В данном конкретном примере понятно, что каждому дереву вывода приведенной выше цепочки отвечает свое смысловое прочтение этой цепочки: в первом случае [math]\mathbf{else}[/math] мы относим к первому [math]\mathbf{then}[/math], а во втором — ко второму. В итоге получаем две совершенно разные интерпретации оператора условного перехода. Данный пример неоднозначности известен поэтому под названием "кочующее [math]\mathbf{else}[/math]".


Исходную грамматику, однако, можно "исправить", построив эквивалентную ей однозначную грамматику:


[math]\begin{aligned}GE_1= \big(& \{a,b, \mathbf{if},\mathbf{then},\mathbf{else}\}, \{S_1,S_2\}, S_1,\\ &S_1\to \mathbf{if}~b~ \mathbf{then}~S_2~\mathbf{else}~ S_1\mid \mathbf{if}~b~ \mathbf{then}~ S_1\mid a,\\ &S_2\to\mathbf{if}~b~\mathbf{then}~S_2~ \mathbf{else}~S_2\mid a\big). \end{aligned}[/math]

В общем случае алгоритма преобразования произвольной неоднозначной КС-грамматики к эквивалентной однозначной не существует.




Пример неоднозначности в естественном языке


Рассмотрим в заключение интересный пример неоднозначности в естественном языке (точнее, в художественном тексте). В известном стихотворении А.С. Пушкина "К вельможе", адресованном князю Юсупову, владельцу Архангельского, есть такая строка:


Посланник молодой увенчанной жены...

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

Процитированную строчку можно прочитать двояко:


1) посланник (молодой увенчанной жены),
2) (посланник молодой) увенчанной жены,

т.е. в первом случае эпитет "молодой" отнесен к "жене", а во втором — к "посланнику". Чисто синтаксически эта коллизия неразрешима, но внеязыковый контекст данной фразы, учитывающий совершенно определенные биографические обстоятельства персонажей, позволяет с высокой долей вероятности предположить, что правильным будет второе прочтение.

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


Сдавайте мусор дворнику, который накопился.

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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved