Синтаксический анализ А-языков

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

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

S®+Nï-Nï0Fï1Cï…ï9Cï0T

T®.D

N®1Cï…ï9Cï0T

C®0Fï…ï9Fï0Cï…ï9Cï.D

D®0Dï…ï9Dï0Fï…ï9F

Граф состояний, соответствующий данной грамматике, показан на рис. 1.6.

Для приведения грамматики к вполне детерминированной форме предварительно выполняется ее модификация: вводится предконечное состояние F’,символ конца цепочки - ^, затем все правила вида: A®a заменяются на A®aF’ и добавляется правило F’®^F.

Для обозначения ошибочного состояния вводится нетерминал - E.

Теорема: Для любой А-грамматики существует эквивалентная ей А-грамматика во вполне детерминированной форме.

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

Пусть имеется А-грамматика G=<S,V_T,V_N,R>. Эта грамматика приводится к модифицированной форме. В результате получим:V_T={^,…}; V_N={S,F^',F,…}.

А-грамматика во вполне детерминированной форме из модифицированной строится следующим образом: 1.G=<V_T,V_N,<S>,R>, <S>=S,<F>=F, <F^'>=F^'

Если в исходной грамматике имеется правило вида: A®aB, то в новой, построенной грамматике, будет правило:<A>®a<B>.

Если в исходной грамматике имеются правила вида: A®aB₁ï…ïaB_n, то в результирующей грамматике будет правило: <A>®a<B₁…B_n>.

Для появившихся новых нетерминалов добавляются правила вида: <B₁…B_n>®c<C₁…C_n>, если в исходной грамматике имеются правила следующего вида:

B₁®cC₁,….B₁®cCn_...

B_n®cC1,….B_n®cC_n..

При этом в новый нетерминал нетерминалы C_i включаются один раз. В результате такого построения для любого терминала а существует единственное правило вида: <…A…>®a<…B…>.

Используя описанный алгоритм, приведем к вполне детерминированной формe А-грамматику чисел с фиксированной точкой:

<S>®+<N>ï-<N>ï 0<FT>ï1<C>ï…ï9<C>

<T>®.<D>

<N>®1<C>ï…ï9<C>ï0<T>

<C>®0<FC>.ï…ï9<FC>ï.<D>

<D>®0<FD>ï…ï9<FD>

<F^’>®^<F>

<F^’T>®^<F>ï.<D>

<F^’C>®^<F>ï0<F^’C>ï…ï9<F^’C>ï.<D>

<F^’D>®^<F>ï0<F^’D>ï…ï9<F^’D>

Переобозначим нетерминалы следующим образом:

<S> - S, <N> - A, <F^”T> - B, <C> - C, <D> - D, <T> - G,

<F^’C> - H, <F^’D> - I.

Получим:

S®+Aï-Aï0Bï1Cï..ï9C

A®1Cï..ï9Cï0G

C®0Hï..ï9Hï.D

G®.D

D®0Iï…ï9I

B®.Dï;F

H®0Hï…ï9Hï.D

I®0Iï…ï9Iï;F Граф для полученной грамматики имеет вид:

Рис. 1.7

Анализатор- это программа, позволяющая определить принадлежность цепочки языку, порождаемому некоторой грамматикой. Ниже приведена программа, анализирующая правильность написания чисел с фиксированной точкой (автомат Глини) на языке Turbo Pascal.

Type Tsost: (S,A,B,C,D,G,H,I,F,E);

Var Sost: Tsost; (*Текущее соcтояние*)

St: String[255];(*Входная строка-цепочка символов языка*)

j: integer;(*Тек. номер позиции в строке*)

k: char;(*Тек. символ строки*)

x,z,q: real;(*x- число,z – знак, q- значение порядка дробной части числа*)

Begin

J:=1; sost:=S; read(st);

X:=0; z:=+1.; q:=0.1;

While((sost<>F) and(sost<>E)and(j<>length(st))) do

Begin

k:=st[j};

Inc(j);

Case sost of

S: case k of

‘-‘: begin

sost:=A;

z:=-1;

end;

‘+’: begin

sost:=A;

end;

‘0’: begin

sost:=B;

end;

‘1’..’9’: begin

sost:=C;

x:=x*10.+(ORD(k)-48)

{48=ORD(0)}

end;

else

begin writeln(‘Ошибка-ожидается знак или цифра’);

sost:=E;

end;

end;{case}

A: case k of

‘0’: begin

sost:=G;

end;

‘1’..’9’: begin

sost:=C;

x:=x*10.0+(ORD(k)-48);

end;

else begin writeln(‘Ошибка в целой части числа’);

sost:=E;

end:

end;{case}

B:case k of

‘.’: begin

sost:=D;

end;

‘;’: sost:=F;

else(*сообщение об ошибке и sost:=E*)

end;{case}

C: case k of

‘0’..’9’: begin

sost:=H;

x:=x*10.0+(ORD(k)-48);

end;

‘.’: begin

Sost:=E;

еnd;

else begin writeln(‘Ошибка! Ожидается точка’);

sost:=E;

end;

end;{case}

G: if k=’.’ Then sost:=D

еlse begin writeln(‘Ошибка! Ожидается точка’);

sost:=E;

end;

H: case k of

‘0’..’9’: begin

Sost:=H;

x:=x*10.+(ORD(k)-48);

end;

‘.’: sost:=D;

else begin writeln(‘Ошибка! Ожидается точка или цифра’);

sost:=E;

end;

end;{case}

D: case k of

‘0’..’9’: begin

sost:=I;

x:=x+(ORD(k)-48)*q; q:=q/10;

else begin writeln(‘Ошибка!’);

sost:=E;

end;

end;{case}

I: case k of

‘0’..’9’: begin

sost:=I;

x:=x+(ORD(k)-48)*q: q:=q/10:

end;

‘;’: sost:=F;

else begin writeln(‘Ошибка!’);

sost:=E;

end;

end;{case}

end{case по состояниям};

end {while};

if sost=F then begin X:=x*z; writeln(‘Число сформировано’,x);end;

if sost=E then writeln(‘Обнаружена ошибка’);

end.

Семантикой для данного анализатора является значение числа.

Способы включения семантики:

1) применение функции Val(S:String; Var x; Var Code:Integer) (добавляется в состояние F);

2) последовательное формирование числа при переходе автомата в соответствующие состояния:

x:=0, z:=1, q:=0.1

x:=z*(x*10+(значение текущей цифры числа х))

x:=x+(значение текущей цифры числа х)*q, где x – формируемое число, z- знак числа, q – значение порядка текущей цифры дробной части числа.

Алгоритм построения анализатора:

1. Составляется автоматная грамматика.

2. Если полученная грамматика недетерминированная, то она приводится к вполне детерминированной форме.

3. По полученной грамматике строится граф состояний.

4. В соответствие с графом пишется программа.

5. Осуществляется добавление семантических правил в анализатор.

Упражнения

1.1. Дайте определение грамматике. Перечислите классы грамматик по Хомскому и дайте их определения. Как определить, содержит ли язык, порождаемый грамматикой, бесконечное число цепочек?

1.2. Что общего в А- и КС- грамматиках? Какие грамматики являются частным случаем других грамматик?

1.3. Постройте КС- и А- грамматики для цепочек вида x ⁿ y ^m z ^k, где n,k > 0 и m ³ 0. Покажите деревья вывода цепочк xxxyyz, xxzzz и xyz по полученной КС-грамматике.

1.4. Приведите граф состояний для A-грамматики из упр. 1.3. Введите признак конца цепочки, например символ “; ”, и преобразуйте граф к детерминированной форме. Напишите программу синтаксического анализа цепочек x ⁿ y ^m z ^k, в качестве семантики подсчитайте количество x, y и z.

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

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

1.7. Постройте КС-грамматику, детерминированную А-грамматику и граф состояний для языка индексов ФОРТРАН а. При построении грамматики терминалами считать { a b c...y z 0 1 2...8 9 () + - * }. Индексы ФОРТРАНа - это ограниченное арифметическое выражение, заключенное в круглые скобки. Ниже перечислены все возможные варианты этих индексов: (И) (К) (К*И) (И+К) (И-К) (К*И+К) (К*И-К), где И - идентификатор, а К - целая константа без знака.

1.8. Напишите процедуру анализа идентификатора с предупреждением в случае, когда количество символов в нем больше шести; процедуру анализа целой константы без знака с преобразованием символьного представления в число и предупреждением о переполнении (максимальное значение - 65535). Используя эти процедуры, напишите по А-грамматике программу анализа индексов ФОРТРАН а из упражнения 1.7.

1.9. Постройте КС - грамматики для цепочек (n > 0, m ³ 0)

(а) x ⁿ y ⁿ z ^m,

(б) x ^m y ⁿ z ⁿ,

(в) x ⁿ y ^m z ⁿ.

1.10. Постройте КС - грамматики для следующих цепочек в бинарном алфавите (S={0,1}, n, m > 0):

(a) 0 ⁿ 1 ^m 0 ^m 1 ⁿ;

(б) aaa^R, где a - любая цепочка из нулей и единиц, а a^R - обращение (сим­мет­рич­ный поворот) цепочки a;

(в) 0 ⁿ 1 ²ⁿ⁺³;

(г) всех цепочек, содержащих равное количество нулей и единиц;

(д) всех цепочек, содержащих равное количество нулей и единиц и такие, у которых количество нулей в каждой левой подцепочке не меньше чем единиц;

(е) 1ⁿ0^m1^p, где n+p>m>0.

1.11. Опишите языки, порождаемые следующими грамматиками с начальным нетерминалом S:

(a) S ® 10S0 S ® aA

A ® bA A ® a

(б) S ® SS S ® 1A0

A ® 1A0 A ® e

(в) S ® 1A S ® B0

A ® 1A A ® C

B ® B0 B ® C

C ® 1C0 C ® e

(г) S ® aSS S ® a

(д) S ® bADc D ® Gl

A ® aGs G ® e

1.12. Какие из приведенных ниже цепочек можно вывести в данной грамматике? В каждом случае постройте левый вывод, правый вывод и дерево вывода.

S ® aAcB S ® BdS

B ® aScA B ® cAB

A ® BaB A ® aBc

A ® a B ® b

(a) aacb

(б) aaacbdaacb

(в) aabcbd

(г) acabaaaacbcacb

(д) aaaaacbcacccab

1.13. (а) Найдите КС-грамматику для логических выражений, составленных из логических переменных, констант, скобок и знаков операций отрицания (Ø), дизъюнкции (Ú) и конъюнкции (Ù). Приоритеты обычные: Ø выполняется перед Ù, а Ù - перед Ú.

(б) Добавьте к указанному языку первичные логические выражения, каждое из которых представляет собой арифметическое выражение, за которым следует знак отношения (>, ³, =, ¹, <, £) и еще одно арифметическое выражение, и постройте соответствующую грамматику.

1.14. Постройте КС-грамматику оператора FORMAT языка ФОРТРАН, ограничиваясь форматами A, X, I, F. Примеры правильных цепочек:

10 FORMAT(I5)

100 FORMAT (X10,A5,3A4,I6,4(I3,X2,5(F8.3,X4,3A2,I6),X2,2(3A3,I4)),I7)

Глава 2. РАСПОЗНАВАТЕЛИ И АВТОМАТЫ.

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

Входную ленту можно рассматривать как линейную последовательность клеток (ячеек). Причем в каждой ячейке может содержаться только один входной символ из некоторого конечного алфавита S. Самую левую и самую правую ячейки могут занимать особые символы - концевые маркеры; маркер может стоять только на правом конце ленты; его может не быть совсем.

Входная головка в каждый данный момент читает (обозревает) одну входную ячейку. За один шаг работы распознавателя входная головка может сдвинуться на ячейку вправо R, остаться неподвижной N или сдвинуться влево L. Распознаватель, который никогда не передвигает свою входную головку влево, называется односторонним. Обычно предполагается, что входная головка только читает, т.е. в ходе работы распознавателя символы на входной ленте не меняются. Но можно рассматривать и такие распознаватели - преобразователи, входная головка которых не только читает, но и пишет, например, машина Тьюринга общего вида.

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

Поведение вспомогательной памяти для заданного класса распознавателей можно охарактеризовать с помощью двух функций: функции доступа к памяти (ФДП) и функции преобразования памяти (ФПП).

ФДП - это отображение множества состояний (конфигураций) памяти в конечное множество информационных символов, которое может совпадать с алфавитом памяти. Например, единственная информация, доступная в каждый данный момент в магазине (стеке) - верхний символ магазина. Таким образом, функция доступа к магазинной памяти f - это такое отображение Z ^* в Z, где Z - алфавит памяти, что

f(z₁z₂...z_n) = z₁,

где z _i Î Z для всех

ФПП - это отображение, описывающее изменение памяти. Она отображает состояние памяти и управляющую цепочку в состояние памяти. Если предполагается, что операция над магазинной памятью заменяет верхний символ конечной цепочкой символов памяти, то соответствующую ФПП можно определить как такое отображение g: Z ⁺ ´ Z ^* ® Z ^*, что

g(z₁z₂...z_n,x₁x₂...x_m) = x₁x₂...x_mz₂...z_n,

где z _i , x _j Î Z для всех и . Если верхний символ магазина z₁ заменяется пустой цепочкой, то z₂ станет верхним символом магазина.

Вообще именно тип внешней памяти определяет название распознавателя. Например, распознаватель, память которого организована как магазин, называется распознавателем с магазинной памятью. (Обычно его называют автоматом с магазинной памятью или МП-автоматом.)

Ядром же распознавателя является управляющее устройство с конечной памятью, под которым можно понимать программу, управляющую поведением распознавателя. Управляющее устройство представляет собой множество состояний Q вместе с отображением d, которое описывает как меняются состояния в соответствии с текущим входным символом (т.е. находящимся под входной головкой) и текущей информацией, извлеченной из внешней памяти. Управляющее устройство определяет также в каком направлении сдвинуть входную головку и какую информацию поместить в память.

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

(1) входная головка сдвигается на одну ячейку вправо, влево или сохраняет исходное положение;

(2) в память помещается некоторая информация;

(3) изменяется состояние управляющего устройства.

Поведение распознавателя удобно описывать в терминах конфигурации - мгновенного снимка распознавателя, на котором изображены:

(1) состояние устройства;

(2) содержимое входной ленты вместе с положением входной головки;

(3) содержимое памяти.

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

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

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

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

Язык, определяемый распознавателем - это множество входных цепочек, которые он допускает.

Для каждого класса грамматик в иерархии Хомского существует естественный класс распознавателей, определяющий тот же класс языков. Справедливы следующие утверждения:

Язык L автоматный тогда и только тогда, когда он определяется односторонним детерминированным конечным автоматом.

Язык L контекстно свободный тогда и только тогда, когда он определяется односторонним недетерминированным МП - автоматом.

Язык L контекстно-зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным линейно-ограниченным (ЛО-) автоматом.

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

Глава 3. АВТОМАТНЫЕ ГРАММАТИКИ И КОНЕЧНЫЕ АВТОМАТЫ

3.1.Автоматные грамматики и конечные автоматы.

3.2.Эквивалентность недетерминированных и детерминированных А-грамматик

Упражнения

3.1. Автоматные грамматики и конечные автоматы.

Автоматную грамматику можно представить в виде таблицы, где строки соответствуют терминалам, а столбцы нетерминалам. На пересечении строки a и столбца A записываются нетерминалы B, которые входят в правила A ® aB. На рис. 3.1 представлена таблица переходов, построенная для А-грамматики из примера 1.9. Приведенная таблица представляет собой ничто иное, как функциональную таблицу или таблицу переходов конечного автомата.

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

Дата добавления: 2014-01-11