В.А. Серебряков - Теория и реализация языков программирования (1134641), страница 15
Текст из файла (страница 15)
Контекстно-свободные грамматикии автоматы с магазинной памятьюПусть G = (N , T , P , S) — КС-грамматика. Введем несколько важныхпонятий и определений.Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним.Если S ⇒∗ u в процессе левостороннего вывода, то u — левая сентенциальная форма. Аналогично определим правосторонний вывод. Обозначим шагилевого (правого) вывода ⇒ l (⇒ r ).Упорядоченным графом называется пара (V , E ), где V есть множествовершин, а E — множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v , v1 ), (v , v2 ), .
. . , (v , vn )). Этот элемент указывает,что из вершины v выходят n дуг, причем первой из них считается дуга,входящая в вершину v1 , второй — дуга, входящая в вершину v2 , и т. д.Упорядоченным помеченным деревом называется упорядоченный граф(V , E ), основой которого является дерево и для которого определена функцияf : V → F (функция разметки), где F — некоторое множество.Упорядоченное помеченное дерево D называется деревом вывода (илидеревом разбора) цепочки w в КС-грамматике G = (N , T , P , S), если выполняются следующие условия:1) корень дерева D помечен S ;2) каждый лист помечен либо a ∈ T , либо e;3) каждая внутренняя вершина помечена нетерминалом A ∈ N ;4) если X — нетерминал, которым помечена внутренняя вершина и X1 , .
. .. . . , Xn — метки ее прямых потомков в указанном порядке, то X → X1 . . .. . . Xk — правило из множества P ;5) цепочка, составленная из выписанных слева направо меток листьев,равна w.4.1. Контекстно-свободные грамматики и автоматы с магазинной памятью71Процесс определения принадлежности данной строки языку, порождаемому данной грамматикой, и, в случае указанной принадлежности, построениядерева разбора для этой строки называется синтаксическим анализом.
Можно говорить о восстановлении дерева вывода (в частности, правостороннегоили левостороннего) для строки, принадлежащей языку. По восстановленному выводу можно строить дерево разбора.Грамматика G называется неоднозначной, если существует цепочка w,для которой имеется два или более различных деревьев вывода в G.Грамматика G называется леворекурсивной, если в ней имеется нетерминал A, такой, что для некоторой цепочки α существует вывод A ⇒ + Aα.Автомат с магазинной памятью (МП-автомат) состоит из управляющего устройства, входной ленты (входа) и так называемого магазина.Один конец магазина называется верхушкой, другой — дном. Формально этосемерка M = (Q, T , Γ, D, q0 , Z0 , F ), где:1) Q — конечное множество состояний управляющего устройства;2) T — конечный входной алфавит;3) Γ — конечный алфавит магазинных символов;4) D — отображение множества Q × (T ∪ {e}) × Γ в множество конечныхподмножеств Q × Γ∗ , называемое функцией переходов;5) q0 ∈ Q — начальное состояние управляющего устройства;6) Z0 ∈ Γ — символ, находящийся в магазине в начальный момент (начальный символ магазина);7) F ⊆ Q — множество заключительных состояний.Конфигурация МП-автомата — это тройка (q , w, u), где1) q ∈ Q — текущее состояние управляющего устройства;2) w ∈ T ∗ — непрочитанная часть входной цепочки; первый символ цепочкиw находится под входной головкой; если w = e, то считается, что всявходная лента прочитана;3) u ∈ Γ∗ — содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считаетсяпустым.Такт работы МП-автомата M будем представлять в виде бинарногоотношения ⊢, определенного на конфигурациях.
Будем писать(q , aw, Zu) ⊢ (p, w, vu),если множество D(q , a, Z) содержит (p, v), где q , p ∈ Q, a ∈ T ∪ {e}, w ∈ T ∗ ,Z ∈ Γ и u, v ∈ Γ∗ (верхушка магазина слева).72Глава 4. Синтаксический анализНачальной конфигурацией МП-автомата M называется конфигурациявида (q0 , w, Z0 ), где w ∈ T ∗ , т. е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине имеется только начальный символ Z0 .Заключительной конфигурацией называется конфигурация вида (q , e, u),где q ∈ F , u ∈ Γ∗ , т. е.
управляющее устройство находится в одном из заключительных состояний, а входная цепочка целиком прочитана.Введем транзитивное и рефлексивно-транзитивное замыкания отношения⊢, а также его степень k > 0 (обозначаемые ⊢+ , ⊢∗ и ⊢k соответственно).Говорят, что цепочка w допускается МП-автоматом M , если(q0 , w, Z0 ) ⊢∗ (q , e, u) для некоторых q ∈ F и u ∈ Γ∗ .Множество всех цепочек, допускаемых автоматом M , называется языком,допускаемым (распознаваемым, определяемым) автоматом M (обозначаетсяL(M )).Пример 4.1. Рассмотрим МП-автоматM = ({q0 , q1 , q2 }, {a, b}, {Z , a, b}, D, q0 , Z , {q2 }),у которого функция переходов D содержит элементы:D(q0 , a, Z) = {(q0 , aZ)},D(q0 , b, Z) = {(q0 , bZ)},D(q0 , a, a) = {(q0 , aa), {q1 , e)},D(q0 , a, b) = {(q0 , ab)},D(q0 , b, a) = {(q0 , ba)},D(q0 , b, b) = {(q0 , bb), (q1 , e)},D(q1 , a, a) = {(q1 , e)},D(q1 , b, b) = {(q1 , e)},D(q1 , e, Z) = {(q2 , e)}.Нетрудно показать, что L(M ) = {wwR |w ∈ {a, b}+ }, где wR обозначает обращение(«переворачивание») цепочки w.Иногда допустимость определяют несколько иначе: цепочка w допускаетсяМП-автоматом M , если (q0 , w, Z0 ) ⊢∗ (q , e, e) для некоторого q ∈ Q.
В такомслучае говорят, что автомат допускает цепочку опустошением магазина. Этиопределения эквивалентны, ибо справедливаТеорема 4.1. Язык допускается МП-автоматом тогда и только тогда, когда он (некоторым другим автоматом) допускается опустошениеммагазина.Д о к а з а т е л ь с т в о . Пусть L = L(M ) для некоторого МП-автоматаM = (Q, T , Γ, D, q0 , Z0 , F ). Построим новый МП-автомат M ′ , допускающийтот же язык опустошением магазина.Пусть M ′ = (Q ∪ {q0′ , qe }, T , Γ ∪ {Z0′ }, D′ , q0′ , Z0′ , ∅), где функция переходов D′ определена следующим образом:4.1.
Контекстно-свободные грамматики и автоматы с магазинной памятью731) если (r, u) ∈ D(q , a, Z), то (r, u) ∈ D′ (q , a, Z) для всех q ∈ Q, a ∈ T ∪ {e}и Z ∈ Γ (моделирование M );2) D′ (q0′ , e, Z0′ ) = {(q0 , Z0 Z0′ )} (начало работы);3) для всех q ∈ F и Z ∈ Γ ∪ {Z0′ } множество D′ (q , e, Z) содержит (qe , e)(переход в состояние сокращения магазина без продвижения);4) D′ (qe , e, Z) = {(qe , e)} для всех Z ∈ Γ ∪ {Z0′ } (сокращение магазина).Автомат сначала переходит в конфигурацию (q0 , w, Z0 Z0′ ) соответственноопределению D′ в п.
2), затем в (q , e, Y1 . . .Yk Z0′ ), q ∈F соответственно п. 1),затем в (qe , e, Y1 . . .Yk Z0′ ), q ∈ F соответственно п. 3), затем в (qe , e, e) соответственно п. 4). Нетрудно показать по индукции, что (q0 , w, Z0 ) ⊢+ (q , e, u)(где q ∈ F ) выполняется для автомата M тогда и только тогда, когда(q0′ , w, Z0′ ) ⊢+ (qe , e, e) выполняется для автомата M ′ . Поэтому L(M ) = L′ , гдеL′ — язык, допускаемый автоматом M ′ опустошением магазина.Обратно, пусть M = (Q, T , Γ, D, q0 , Z0 , ∅) — МП–автомат, допускающийопустошением магазина язык L.
Построим автомат M ′ , допускающий тот жеязык по заключительному состоянию.Пусть M ′ = (Q ∪ {q0′ , qf }, T , Γ ∪ {Z0′ }, D′ , q0′ , Z0′ , {qf }), где D′ определяется следующим образом:1) D′ (q0′ , e, Z0′ ) = {(q0 , Z0 Z0′ )} — переход в «режим M »;2) для каждого q ∈ Q, a ∈ T ∪ {e}, и Z ∈ Γ определим D′ (q , a, Z) == D(q , a, Z) — работа в «режиме M »;3) для всех q ∈ Q, (qf , e) ∈ D′ (q , e, Z0′ ) — переход в заключительное состояние.Нетрудно показать по индукции, что L = L(M ′ ).Одним из важнейших результатов теории контекстно-свободных языковявляется доказательство эквивалентности МП-автоматов и КС-грамматик.Теорема 4.2.
Язык является контекстно-свободным тогда и толькотогда, когда он допускается МП-автоматом.Д о к а з а т е л ь с т в о . Пусть G = (N , T , P , S) — КС-грамматика. Построим МП-автомат, допускающий язык L(G) опустошением магазина.Пусть M = ({q}, T , N ∪ T , D, q , S , ∅), где D определяется следующимобразом:1) если A → u ∈ P , то (q , u) ∈ D(q , e, A);2) D(q , a, a) = {(q , e)} для всех a ∈ T .74Глава 4. Синтаксический анализФактически этот МП-автомат в точности моделирует все возможные выводы в грамматике G. Нетрудно показать по индукции, что для любой цепочки w ∈ T ∗ вывод S ⇒ + w в грамматике G существует тогда и только тогда,когда существует последовательность тактов (q , w, S) ⊢+ (q , e, e) автомата M .Наоборот, пусть дан M = (Q, T , Γ, D, q0 , Z0 , ∅) — МП-автомат, допускающий опустошением магазина язык L.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
