2

Пред. страница . След. страница Раздел Содержание

2.3. Преобразование некоторых типов языков и грамматик к автоматному виду.

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

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

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

Пусть задан язык L=α₁,α₂,...,α_n , где α_i Î V_Т*. Возьмем некоторую цепочку α_i=a₁,a₂,...,a_m, символы которой a_j Î V_Т. Выберем в качестве начального символа искомой грамматики символ и m-1 нетерминальный символ A1, A2,..., Am-1. По выбранной цепочке построим m правил вывода искомой автоматной грамматики:

® a₁<A1> , <A1> ® a₂<A2>, <A2> ® a₃<A3>,..., <Am-1> ® a_m .

Аналогичным образом построим правила вывода для каждой цепочки α_k Î L , выбирая каждый раз новые нетерминальные символы.

Чтобы сократить число нетерминальных символов при построении правил грамматики для слов с одинаковыми начальными частями, следует использовать одинаковые нетерминальные символы. Например, если слово α_i+1=a₁,a₂,a₃’,...,a_m^’ содержит начальный отрезок a₁,a_2,совпадающий с начальным отрезком слова α_i, то правила грамматики должны иметь вид:

® a₁<A1> , <A1> ® a₂<A2>, <A2> ® a₃’<A3’>,..., <Am-1’> ® a_m’ .

Совокупность всех введённых нетерминальных символов составит словарь V_A, а совокупность правил - множество R искомой грамматики.

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

Определение. Правило называется праволинейным, если оно имеет вид <A> ® α , где α Î V_Т* и ÎV_A. Правило называется заключительным, если оно имеет вид <A> ® α, где α Î V_Т*.

Определение. Грамматика КС называется праволинейной, если все её правила праволинейные или заключительные.

Утверждение. По любой праволинейной грамматике может быть построена эквивалентная ей автоматная грамматика.

Возьмём некоторое правило заданной грамматики r=<A>® α Î R. Пусть оно имеет вид <A> ® a₁, a₂,..., a_m, где a_i Î V_Т, A, B Î V_А и m > 2. Если m = 1, то такие правила преобразовывать не нужно, их следует просто перенести в искомую грамматику. Выберем m-1 нетерминальный символ A1, A2,..., Am-1 и преобразуем выбранное правило в группу правил вида.:

<A> ® a₁ <A1>, <A1> ® a₂<A2>, ...,<Am-1> ® a_m.

Если исходное правило имело вид <A> ® a₁ a₂...a_m, то последнее из построенных правил должно иметь вид <Am-1> ® a_m. Выберем для каждого правила, у которого m ³ 2 , новые нетерминальные символы и выполним описанное преобразование. Добавляя к построенным правилам правила, правая часть которых состоит из одного символа или у которых m=1, получим А-грамматику, эквивалентную заданной.

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

Пред. страница . След. страница Раздел Содержание