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

В общем случае кодирование автомата состоит в сопоставлении с каждым внутренним состоянием определенного набора значений переменных дополнительных входных сигналов ЛП автомата, с каждым состоянием входа - набора значений его основных входных сигналов и с каждым состоянием выхода — набора значений основных выходных сигналов ЛП. Однако во многих практических случаях состояния входа и выхода оказыва­ются уже закодированными и задача кодирования автомата сво­дится к кодированию или, как иногда говорят, размещению его внутренних состояний. Поэтому основное внимание уделим именно кодированию внутренних состояний автомата. На этом этапе синтеза автомата определяются многие его свойства, и прежде всего устойчивость по отношению к состязаниям элементов памяти.

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

С каждым внутренним состоянием автомата в результате процесса кодирования сопоставляется определенная кодовая комбинация ∆_i, образованная значениями переменных, характеризующих состояния ЭП. Если такое сопоставление осуществляется произвольным образом, то может оказаться, что двум внутренним состояниям x_i и x_j, между которыми должен быть переход (соседние внутренние состояния), будут приписаны кодовые комбинации ∆_i и ∆_j отличающиеся значениями нескольких переменных (несоседние кодовые комбинации) (рис. 6.8,а). Тогда и возникают условия для состязаний элементов памяти, состояниями которых отличаются кодовые комбинации внутренних состояний x_i и x_j. Из-за наличия состязаний автомат из внутреннего состояния x_i под воздействием состояния входа ρ_r может попасть не в x_j, а в другое внутренне состояние x_k и x_l в зависимости от того, какой из элементов памяти, участвующих в состязании, раньше изменит свое состояние (рис. 6.8,б). Если затем при том же состоянии входа ρ_r автомат из x_k и x_l перейдет во внутреннее состояние x_j (рис. 6.8,в), то такие состязания являются допустимыми, или некритическими, так как функция переходов автомата при этом искажаться не будет.

Если же автомат из x_l или x_k при состоянии входа ρ_r перейдет в какое-либо другое состояние (x_m) или не изменит своего внутреннего состояния (рис. 6.8,г), то такие состязания являются критическими, или недопустимыми, так как при этом исказится функция переходов автомата и в дальнейшем он будет функционировать неправильно.

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

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

Определение контекстно-свободных (КС) грамматик.

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

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

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

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

{ aⁿ bⁿ | n ≥ 0 }

является контекстно-свободным, но не регулярным. Он генерируется грамматикой с порождающими правилами

S ® aSb | ε

С другой стороны, язык

{ aⁿ bⁿ cⁿ | n ≥ 0 }

является контекстно-зависимым, а не контекстно-свободным.

Контекстно-свободные грамматики имеют ряд характеристик, для которых справедливы следующие положения.

· каноническая форма

· самовложение

 

Каноническая форма.

 

а) Каждая КС-грамматика эквивалентна (т.е. генерирует тот же язык) грамматике в нормальной форме Хомского, т.е. со всеми порождающими правилами вида

A ® BC | a

при обычных условиях, касающихся терминалов и нетерминалов.

б) Каждая КС-грамматика эквивалентна грамматике в нормальной форме Грейбаха, т.е. со всеми порождающими правилами вида

A ® bα

где α – строка нетерминалов (возможно, пустая).

 

Самовложение.

Если в грамматике G есть нетерминал A, для которого

A Þ α ₁ A α ₂

(здесь α ₁ и α ₂ являются непустыми строками терминалов и/или нетерминалов), то о такой грамматике говорят, что она содержит самовложение. Например, две приведенные ниже грамматики содержат самовложение:

1) G ₁ = ({ S }, { a, b }, P, S), где элементы P:

S ® aSb

S ® ε

2) G ₂ = ({ S, A }, { begin, end,[,]}, P, S), где элементы P:

S ® begin A end

S ® ε

A ® [ S ]

В последнем случае об A и S говорят, что они проявляют свойство самовложения. Теоретически любая КС-грамматика, не содержащая самовложения, эквивалентна регулярной грамматике и генерирует регулярный язык. С другой стороны, регулярная грамматика не может содержать самовложения. Именно самовложение позволяет эффективно различать КС (нерегулярные) и регулярные языки. Как видно из второго примера, согласование скобок и т.п. требует самовложения, поэтому его нельзя специфицировать посредством регулярной грамматики.

 

Автомат магазинного типа.

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

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

б) все то же самое, но без чтения входного символа.

Автомат магазинного типа можно представить кратным (K, S, Г, d, S ₀, Z ₀),где K – конечное множество состояний, S – входной алфавит, Г – алфавит магазинный, d – множество переходов, S ₀ –начальное состояние, Z ₀ – символ магазина, который первоначально находится в стеке.

Рассмотрим, например, автомат магазинного типа М, определенный следующим образом:

K = { A },

S = { '(', ')'},

Г = { O, I },

S ₀ ={ A },

Z ₀ = I.

d задается как d (A, I, '(') = (A, IO) (что означает: в состоянии A с I в вершине стека при чтении '(' перейти к состоянию A и заменить I на IO).

d (A, O, '(') = (A, OO),

d (A, O, ')') = (A, ε),

d (A, I, ε) = (A, ε).

Автомат М распознает согласуемые пары скобок. Открывающие скобки (представляемые как O) помещаются в стек и удаляются оттуда, когда встречается соответствующая закрывающая скобка. Строка скобок принимается, если после считывания всей строки стек остается пустым. Это – обычный способ принятия строк автоматами магазинного типа, хотя можно также определить автоматы магазинного типа, которые принимают строки по конечному состоянию. Эти два типа эквивалентны.

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

При разборе происходит эффективное моделирование соответствующего автомата магазинного типа. Некоторые КС языки не могут анализироваться детерминированным образом (т.е. без возврата). Язык, допускающий детерминированный анализ, называется детерминированным; большинство языков программирования являются детерминированными или, по крайней мере, почти таковыми.

Между КС-грамматиками и автоматами магазинного типа существует полное соответствие, и детерминированность автомата может зависеть от того, какая грамматика используется для генерирования языка. Метод разбора является детерминированным (для конкретной грамматики), если при разборе данной грамматики не требуется делать возврат. Некоторые языки можно разбирать детерминировано с помощью только одного из методов грамматического разбора. В частности, ряд языков можно разбирать детерминировано снизу вверх, но не сверху вниз. Далее мы будем рассматривать исключительно детерминированные методами разбора. Недетерминированные методы могут применяться к таким строчно-ориентированным языкам, как Фортран. Для языков же сильно рекурсивных (С++, Паскаль), где компилятор может быть вынужден возвращаться назад не только в текущей строке, но и в большой части программы, издержки, возникающие в случае возврата, просто неприемлемы. Другой недостаток возврата заключается в том, что он может вызвать отмену действий компилятора, которые осуществляются параллельно с синтаксическим анализом.

S-грамматика.

LL(1)-грамматика – это грамматика такого типа, на основании которой можно получить детерминированный синтаксический анализатор, работающий по принципу сверху вниз. Прежде чем более точно определить LL(1)-грамматику, введем понятиеs-грамматики.

S-грамматика представляет собой грамматику, в которой:

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

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

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

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

Грамматика с порождающими правилами

S® pX

S® qY

X ® aXb

X ® x

Y® y

Y® aYd

представляет собой s-грамматику, тогда как следующая грамматика, которая генерирует тот же язык, не является ею:

S ® R

S ® T

R ® pX

T ® qY

X ® aXb

X ® x

Y ® aYd

Y ® y

поскольку правые части двух правил не начинаются с терминалов.

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

Рассмотрим проблему разбора строки paaaxbbb с помощью приведенной выше s-грамматики. Начав с символа S, попытаемся генерировать строку. Применим левосторонний вывод. Результат приводится ниже.

Исходная строка: paaaxbbb

Вывод: S ® pX ® paXb ® paaXbb ® paaaXbbb ® paaaxbbb

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

LL(1)-грамматика является обобщением s-грамматики, и принцип ее обобщения все еще позволяет строить нисходящие детерминированные анализаторы. Две буквы L в LL(1) означают, что строки разбираются слева направо (Left) и используются самые левые выводы (Left), а цифра 1 – что варианты порождающих правил выбираются с помощью одного предварительно просмотренного символа. Кстати, если речь идет, например, о LL(2)-грамматике, это значит, что строки разбираются слева направо и используются самые левые выводы, а варианты порождающих правил выбираются с помощью двух предварительно просмотренных символов. Аналогично, термин LR(1)-грамматика подразумевает, что строки разбираются слева направо (Left), используются самые правые выводы (Right), а варианты порождающих правил выбираются с помощью одного предварительно просмотренного символа. Более подробно LR-грамматики будут рассмотрены в параграфе, посвященном методам восходящего разбора.

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

S ® RY

S ® TZ

R ® paXb

T ® qaYd

можно вывести, что если для R и T нет других порождающих правил, порождающее правило S ® RY желательно применять в разборе сверху вниз (нисходящий разбор – от начального символа – к строке) только когда предварительно просматриваемым символом является p. Аналогично порождающее правило S ® TZ рекомендуется в тех случаях, когда таким символом окажется q.

Это приводит к идее множеств символов-предшественников, определяемых как

a Î S(A) Û A Þ aα,

где A – нетерминальный символ, α – строка терминалов и/или нетерминалов, а S (A) обозначает множество символов-предшественников A. В грамматике с порождающими правилами

P ® Aс

P ® Bd

A ® a

A ® aA

B ® b

B ® bB

a и b – символы-предшественники для P. Определим также множество символов-предшественников для строки терминалов и/или нетерминалов:

aÎ S(α) Û α Þ aβ,

где α и β – строки терминалов и/или нетерминалов (β может быть пустой строкой).

Необходимым условием того, чтобы грамматика обладала признаком LL(1), является непересекаемость множеств символов-предшественников для альтернативных правых сторон порождающих правил.

Следует проявлять осторожность в тех случаях, когда нетерминал в начале правой части может генерировать пустую строку. Например, в грамматике

P ® AB

P ® BG

A ® aA

A ® ε

B ® bB

B ® c

имеем S (AB) = {a, b,c}, причем b и cвходят в множество, т.к. А может генерировать пустую строку; S (BG) = {b, c} – множества пересекаются, следовательно грамматика не будет LL(1).

Рассмотрим также грамматику с порождающими правилами

T ® AB

A ® PQ

A ® BC

P ® pP

P ® ε

Q ® qQ

Q ® ε

B ® bB

B ® е

C ® cC

C ® f

для которой S (PQ) = { p, q } и S (BC) = { b, e }

Однако так как PQ может генерировать пустую строку, следующим просматриваемым символом при применении порождающего правила A ® PQ может быть b или e (вероятные символы, следующие за A), и одного следующего просматриваемого символа недостаточно, чтобы различить две альтернативные правые части для A (b и e являются также символами предшественниками для BC).

Поэтому вводится понятие направляющих символов

Направляющие символы.

Направляющие символы определяются так:

если A – нетерминал, то его направляющими символами будут

S (A) + (все символы, следующие за A, если A может генерировать пустую строку).

Иными словами, это множество всех символов-предшественников + все символы, следующие за A, если A может генерировать пустую строку. В общем случае для заданного варианта α нетерминала P (P ® α) имеем:

DS (P, α) = { а | а Î S (α) или (α Þ ε и a Î F (P))}

где F (P) есть множество символов, которые могут следовать за P. Так, в приведенном выше примере направляющие символы – это символы

DS (A, PQ) = { p,q,b,e }

DS (A, BC) = { b,e }

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