If выражение then if выражение then другой_оператор else другой_оператор

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

Контекстно-свободные грамматики, продукции которых имеют про­стую структуру, называются регулярными грамматиками. Контекстно-сво­бодная грамматика G = (Ф, , P, S) называется регулярной, если все про­дукции имеют вид: А  аВ‚ А  а‚ или S  ε‚ А‚ ВΦ‚ а. Однако про­дукция S  ε может встречаться только тогда, когда S не встречается нигде в правой части продукции. Таким образом, продукции вида А  aS запре­щены.

Формальный язык L  ^ называется регулярным, если существует ре­гулярная грамматика G, такая что L(G) = L. Отсюда сразу следует, что ка­ждый регулярный язык также контекстно-свободный. Однако обратное не­верно: именно {aⁿbⁿ | n1} контекстно-свободный, но не регулярный язык. Позже мы увидим, что множество всех констант в PASCAL – регулярный язык (см. пример 1.11).

Пример 1.5. Контекстно-свободная грамматика.

G = ({E,T}, {+,,a}, P, E), где P = {EΕ+T, ET, TTa, Ta}

порождает язык L(G) = a(a)^(+a(a)^)^. Поэтому возможны следующие продукции:

Е ^ T+T+...+T, T ^ aa...a.

Слова из L(G) могут рассматриваться как арифметические выражения без скобок. Однако возможно указать некоторую регулярную грамматику G’, которая порождает L(G), именно: G^’ = ({S,A}, {+,,a}, P’, S), где P’ = {SаА‚ Sа‚ А+S, AS}. Тогда L(G) регулярный язык. □

Разберем теперь проблему анализа некоторого заданного слова w отно­сительно грамматики G. Под этим понимается следующее.

Пусть G = (Ф, , P, S) и w^. Тогда требуется проверить, является ли w словом из L(G). Эта проблема встречается при трансляции программ. В случае, если L(G) – множество всех синтаксически правильных программ и w – программа, то требуется проверить, является ли w синтаксически пра­вильной программой, то есть лежит ли w в L(G). Мы увидим, что конечные автоматы (соответственно, магазинные автоматы) могут применяться для разрешения проблемы анализа в отношении регулярных (соответственно, контекстно-свободных грамматик).

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

Конечный автомат A над алфавитом есть система A =(Q, , , q₀, F),

1. Q

   где:

   – конечное непустое множество состояний;

2.  – входной алфавит;

3. : Q  P(Q) (степень множества Q) – функция перехода;

4. q₀Q – начальное состояние;

5. F  Q – множество конечных состояний.

Продолжим отображение  до отображения : Q^ P(Q) путем

(q, ) = {q}, (q, aw) = для каждого qQ, w^, a.

Слово w принимается конечным автоматом A тогда и только тогда, ко­гда F  (q₀, w)  . Формальный язык ||A||, принимаемый автоматом A, есть ||A|| = {w | F  (q₀, w)  }.

В случае, если не возникает путаницы, вместо пишут просто .

Функцию перехода  можно также представить так называемой табли­цей переходов.

Пусть A = (Q, , , q₀, F), где Q = {q₀, q₁, …, q_n} и  = {a₁, a₂, …, a_m}, тогда  изображается следующей таблицей:

	a1	a2	…	am
q0	(q0, a1)	(q0, a2)	…	(q0, am)
q1	(q1, a1)	(q1, a2)	…	(q1, am)
.	.	.		.
.	.	.		.
.	.	.		.
qn	(qn, a1)	(qn, a2)	…	(qn, am)

Другая возможность – представление функции перехода ориентирован­ным помеченным графом. Граф имеет n+1 узлов, которые соответствуют состояниям q₀,…, q_n. Если выполняется q(p, a), то ребро, обозначенное символом а, ведет от узла p к узлу q. Узел, соответствующий начальному состоянию, обозначается зачерненным, а узлы, соответствующие конеч­ным состояниям, заключаются в кольцо.

Слово a₁…a_m^ описывает путь от p к q в графе, в случае если сущест­вуют узлы p₁ = p,p₂,…,p_m,p_m+1 = q, так, что для каждого j, 1jm, имеется ребро от p_j к p_j+1, которое обозначается как a_j. Пустое слово  описывает для любого q путь от q к q. Поэтому справедливо, что слово w^ в точно­сти тогда описывает путь в графе от p к q, когда q(p,w). Отсюда ||A|| – множество всех слов, которые описывают путь от начального состояния к одному из конечных состояний.

Пусть G = (Ф, , P, S) – регулярная грамматика. Построим граф конеч­ного автомата, который воспринимает L(G).

Множество узлов графа задается как Ф  {F}. Узел F – конечный узел.

Если S  , то S также конечный узел. Начальный узел задается че­рез S.

Если A  a, то ребро, обозначенное через а, ведет от узла А к ко­неч­ному узлу F.

Если A  aB, то ребро а ведет от узла А к узлу В.

Пример 1.5. (продолжение). Построим граф конечного автомата, вос­принимающего L(G):

Конечный автомат A = (Q, , , q₀, F) – детерминированный, если |(q, x)|1 для всех qQ, x. Вместо (q, x) = {p} пишем тогда (q, x) = p, что оз­начает, что мы рассматриваем  как частичную функцию : Q  Q. Оп­ределение для упрощается тогда до следующего:

(q, ε) = q, (q, aw) =((q, a), w) и ||A|| = {w | (q₀, w)F}.

На графе это означает, что от каждого узла q отходит не более чем одно ребро, обозначаемое х.

Справедлива следующая теорема:

Пусть A = (Q, , , q₀, F) – конечный автомат, тогда имеется детер­минированный конечный автомат A’, такой что ||A|| = ||A’||.

Мы хотим теперь построить автомат A’ с множеством состояний P(Q). Продолжим : Q P(Q) до отображения ’: P(Q)  P(Q) посред­ством

′({q₁, q₂,..., q_k}, x) =(q_j, x), q₁,..., q_kQ, x.

Таким образом, ’({q₁, q₂,..., q_k}, x) есть множество всех тех состояний, которые могут быть достигнуты из одного из состояний q₁, q₂,..., q_k через ребро, обозначенное x. Пусть F’ = {GP(Q) | GF≠ Ø}, что значит множе­ство G как состояние автомата A’ есть конечное состояние тогда и только тогда, когда оно содержит хотя бы одно конечное состояние из F. Пусть A’ = (P(Q), , ’, {q₀}, F’). Тогда выполняется ||A’|| = ||A|| и A’ по по­строению – детерминированный автомат.

Пример 1.5. (продолжение). Построим граф детерминированного ко­нечного автомата, который принимает L(G):

С помощью детерминированных конечных автома­тов можно конечно «быстро» анализировать регуляр­ные языки. Обратно: можно показать, что для каждого конечного автомата A найдется регулярная грамма­тика G, та­кая что L(G) = ||A||.

Предложение 1.1. Пусть L  ^ – формальный язык. Тогда следующие высказывания эквивалентны:

1. существует регулярная грамматика G, такая что L = L(G);

2. существует конечный автомат A, такой что L = ||A||;

3. существует детерминированный конечный автомат, такой что L = ||A||. □

Пример 1.6. Слово v^ называется подсловом слова w^ тогда и только тогда, когда найдутся слова u₁,u₂^, такие, что w = u₁ v u₂. Требу­ется проверить, встречаются ли в слове w^ подслова с определенными свойствами. Для этого строят детерминированный конечный автомат A, который принимает все слова w^, содержащие подслова с определен­ными свойствами. Это есть простейшая проблема распознавания образов («сопоставление с образцом»).

Пусть  = {a, b}. Требуется проверить, обладает ли слово w^ сле­дующими свойствами:

1. ааа должно быть подсловом слова w;

2. аa должно встречаться как подслово на правом конце слова w.

Таким образом, можно построить детерминированный конечный авто­мат, который принимает формальный язык L={a,b}^ааа{a,b}^{a,b}^аа. Укажем две возможных конструкции.

Первый способ построения: конечный автомат вида

принимает L. Чтобы его «детерминировать» представим функцию пере­хода в виде таблицы (без фигурных скобок) и определим функцию пере­хода детерминированного автомата.

	a	b
q0	q0, q1	q0
q1	q2	–
q2	q3	–
q3	–	q4
q4	q4, q5,	q4
q5	q6	–
q6	–	–
q0, q1	q0, q1, q2	q0
q0, q1, q2	q0, q1, q2, q3	q0
q0, q1, q2, q3	q0, q1, q2, q3	q0, q4
q0, q4	q0, q1, q4, q5	q0, q4
q0, q1, q4, q5	q0, q1, q2, q4,q5, q6	q0, q4
q0, q1, q2, q4, q5, q6	q0, q1, q2, q3,q4,q5,q6	q0, q4
q0, q1, q2, q3, q4, q5, q6	q0, q1, q2, q3, q4, q5, q6	q0, q4

Это дает следующий детерминированный конечный автомат:

Относительно состояний p₃, p₆, p₇ видно следующее: три состояния явля­ются конечными состояниями. Символ a переводит автомат из одного из этих трех состояний снова в одно из трех состояний; символ b переводит из всех трех состояний в состояние p₄. Поэтому можно три состояния p₃, p₆, p₇ объединить в одно состояние p, при этом получают следующий де­терминированный автомат:

Второй способ построения. Видно, что слово лежит в L тогда и только то­гда, когда оно заканчивается на aaa или содержит aaa и заканчивается на aa:

Затем дополняют этот «скелет автомата» до вышеописанного автомата.

Обратимся к магазинным автоматам.

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

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

1) читающая головка остается над прочитанным символом или пе­редвигается на один символ вправо;

2) самый верхний символ в магазине стирается;

3) слово над алфавитом магазина записывается на магазинной ленте, и головка чтения-записи устанавливается на новый самый верхний символ магазинной ленты;

4) магазинный автомат переходит в новое состояние.

Итак, пусть дан магазинный автомат, работающий с входным алфави­том . На входной ленте пусть записано слово w^*. Магазинный автомат стар­тует в заданном начальном состоянии, имеет читающую головку над пер­вым символом входного слова и головку чтения-записи над стартовым сим­волом в остальной части пустой магазинной ленты. Далее, автомат действу­ет согласно пунктам 1) – 4). Если магазинному автомату удается попасть в так называемое конечное состояние, причем читающая головка должна сто­ять справа от последнего символа входной ленты, то тогда го­ворят, что ма­газинный автомат принимает w через конечное состояние. Если магазинно­му автомату удается достичь того, что магазинная лента пуста и читающая головка находится справа от последнего символа вход­ной ленты, то говорят, что магазинный автомат принимает w через пустой магазин.

Формализуем теперь магазинные автоматы.

Магазинный автомат P есть семерка P = (Q,    q_0, p_0, F), где

1. Q – непустое конечное множество состояний;

2.  – алфавит, называемый входным алфавитом;

3.  – алфавит, называемый алфавитом магазина;

4. q₀Q – начальное состояние;

5. p₀ – начальный символ на магазинной ленте;

6. FQ – множество конечных состояний;

7.   Q P_fQ Г^* – функция перехода. (Через P_f мы обозначаем множество всех конечных подмножеств.)

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

Интерпретация  следующая:

Пусть (q,a,p)= (q₁, ₁),…,(q_m, _m) , q,q₁,…,q_m Q, a  , p  , ₁, …, _mГ^*.

Если магазинный автомат находится в состоянии q, головка чтения чи­тает символ a, а головка чтения-записи читает самый верхний символ в ма­газине p, то магазинный автомат выбирает недетерминированным образом некоторую пару (q_i, _i). Это означает, что магазинный автомат переходит в состояние q_i, на магазинной ленте p замещается на _i, головка чтения пере­двигается на один символ вправо и головка чтения-записи устанавливается над самым верхним (первым) символом слова _i.

Если выполняется q, p (q₁, ₁),…,(q_m, _m) , то это означает, что головка чтения ничего не читает, а поэтому также и не перемещается вправо. Состояние и содержимое магазина изменяются, как описано выше.

Пусть P = (Q, , , , q₀, p₀, F) – магазинный автомат. Конфигурация (си­туация) магазинного автомата P есть тройка (q, w, ), qQ, w^*, Г^*. Ин­туитивно это означает, что автомат находится в состоянии q, что слово w – еще не прочитанная часть входного слова и что  стоит на магазинной ленте.

Определим далее отношение _P, называемое прямым отношением пе­рехода над конфигурациями P:

(q₁, aw, p) _P (q₂, w, ₁)  (q₂, ₁)(q₁, a, p) для q₁, q₂ Q, a, w^*, p, , ₁ ^*

Отношение _P^* есть рефлексивное и транзитивное замыкание _P. Если выполняется (q₁, w₁, ₁) _P^* (q₂, w₂, ₂), то говорят, что конфигурация (q₁, w₁, ₁) ведет к (q₂, w₂, ₂). В случае, если ясно, какой магазинный автомат имеется в виду, вместо _P и _P^*можно писать  и ^*.

Пусть P = (Q, , , , q₀, p₀, F) – магазинный автомат. Язык T(P), кото­рый принимается автоматом P через конечное состояние, есть

T(P)=w(q₀, w, p₀) ^* (q,, ), qF, ^*.

Язык N(P), который принимается автоматом P через пустой магазин, есть

N(P)=w(q₀, w, p₀ ^* (q, ,), qQ.

Язык , который принимается автоматом P через пустой магазин и конеч­ное состояние, есть

= w q₀, w, p₀ ^* (q, ,), qF.

Конечный автомат P – детерминированный тогда и только тогда, когда для всех qQ, a, p выполнено:

1. q, a, p) 1;

2. если q, , p  , то q, x, p  для всех x.

Магазинный автомат P  Q, , , , q_0, p₀, F может быть представлен бес­конечным ориентированным помеченным графом: множество узлов графа задается как  q) ^*, qQ. От узла (_1, q₁) к узлу (_2, q₂) ведет в точ­ности одно ребро, обозначенное a, если

q_1,a, ₁  (q₂, , ₂)  т. е., если ₁= p, ₂ ₃ и (q₂, ₃)  (q_1,a, p).

Тогда справедливо, что w^* в точности тогда описывает путь от (_1, q₁) к (_2, q₂), когда q_1,w, ₁ ^* (q₂, , ₂).

Отсюда следует непосредственно, что T(P) есть множество всех тех слов, которые описывают путь от (p₀,q₀) к (, q), qF, ^*; что N(P) есть множе­ство всех слов, описывающих путь от (p₀,q₀) к (, q), qQ и что есть мно­жество всех тех слов, которые описывают путь от (p₀,q₀) к ( q), qF.

Пусть G=(S) – контекстно-свободная грамматика, тогда магазин­ный автомат P = (qVqSq принимает язык L(G) через пустой ма­газин (и конечное состояние), причем  определена следующим образом:

(q, B)  q, , A) A B  P, B  ,

(q, )  q, a, A) A a  P, a  ,

(q, )  q, , A) A   P,

(q, x, x) = q,  для всех x.

Пример 1.7. Для контекстно-свободной грамматики G = (SabSaSS, SbS получают P = ({q},,V,,q,S,{q}), где (q,,S)={(q,aSS),(q,b)}, (q,a,a)=(q,b,b)={(q,)}. Имеем: =N(P)=L(G). Автомат P – недетерминированный. 

Конструкция будет проще, если контекстно-свободная грамматика G дана в нормальной форме Грайбах.

Контекстно-свободная грамматика G=(PS) дана в нормальной форме Грайбах, если

из AP следует  или .

Можно показать, что для каждой контекстно-свободной грамматики G, где L(G) ^*, можно построить контекстно-свободную грамматику G₁ в нор­мальной форме Грайбах, такую, что L(G₁)=L(G).

Пусть G = (S) – контекстно-свободная грамматика в нормальной форме Грайбах. Тогда магазинный автомат P = ({q},,,,q,S,{q}) прини­мает язык L(G) через пустой магазин и конечное состояние, причем (q,)q,a,A  AaP и (q,)(q,,A)  A.

Пример 1.8. Пусть контекстно-свободная грамматика G = (S ab SaSS, SbS.

Тогда для P = ({q},,,,q,S,{q}), такого, что q,a,S={(q,SS)}, (q,b,S)={(q,)} выполняется: = N(P) = L(G). Магазинный автомат пред­ставляется сле­дующим графом:

Он является детерминированным. 

Можно доказать следующее предложение.

Предложение 1.2. Пусть L – формальный язык. Тогда следующие вы­сказывания эквивалентны:

1. существует контекстно-свободная грамматика G, такая, что L = L(G);

2. существует магазинный автомат P, такой, что L=T(P);

3. существует магазинный автомат P, такой, что L=N(P);

4. существует магазинный автомат P, такой, что L=. 

Существуют, однако, контекстно-свободные языки, которые не могут быть приняты никаким детерминированным магазинным автоматом. К их числу относится контекстно-свободный язык {ww^R w0,1}^*}, где ^R=, .

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

Пример 1.9. Мы хотим построить магазинный автомат, который при­­нимает все корректно записанные скобочные выражения со скобками x и .

Конструкция первая. Для G = ({S},{x,},{SxSS,S},S) и P = ({q},{x,}, {S,},,q,S,{q}), где q,x,S={(q,SS)}, (q,,S)={(q,)}, (q,,)={(q,)} выполняется, что  L(G) есть множество корректно заданных скобочных выражений со скобками x и .

Конструкция вторая. Слово w над {x,} есть корректное скобочное вы­ражение тогда и только тогда, когда

1. в каждом начальном подслове слова w число скобок не превосхо­дит числа скобок x;

2. число скобок x и в w совпадают.

Отсюда получают магазинный автомат P = ({q},{x,},{ p_0, p₁},,q, p₀,{q}), такой, что (q,x, p₀) = {(q, p₁p₀)}, q,x, p₁) = {(q, p₁p₁)}, q,, p₁ = {(q,}, q,, p₀  ={(q,)}.

Он представляется следующим графом (указаны только существенные узлы):

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

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

Пример 1.10. <F>(<F><O><F>)<vZ> <vZ><Z>{<Z>}

<O> <Z>:01

F,O,vZ и Z обозначают соответственно формулу, оператор, целое число без знака, цифру. Каждой переменной сопоставим синтаксическую диаграмму:

После замещения и в несколько измененной нотации мы получим:

vZ

Блок           в синтаксической диаграмме для <F> мы не можем заме­щать непосредственно, так как конечный узел имеет петлю. Мы должны подставить:

и получим:

Если далее выполним постановку для F, получим магазинный автомат. При этом мы должны обозначить узлы через (,q), где q – состояние,  – слово в магазине. Кроме того, нам потребуются два различных магазинных символа в зависимости от того, какое F мы замещаем.

Это дает магазинный автомат:

P ,

где

Магазинный автомат P производит анализ в основном детерминировано и акцептирует в точности все слова, порожденные с помощью <F>. 

Пример 1.11. Подобным образом можно сконструировать следующий автомат для констант в Паскале.

