1.5.8. Грамматики, описывающие условные операторы и операторы цикла

Допустим, что рассматриваются условные операторы, аналогичные используемым в языке Паскаль, с разделителями 'if', 'then', 'else'.В качестве условия в таких операторах разрешается использовать отношения, состоящие из двух идентификаторов, соединенных знаками = и <. Структура такого оператора определяется двумя видами  последовательностей фиксированной длины, для описания которых можно воспользоваться простым перечислением компонентов. Первая последовательность определяет полный и сокращенный условные операторы, а вторая - конструкцию "отношение". Схема грамматики, задающая эти последовательности, может быть изображена так:

 

Г_{1. 28} : R = {  <V>.if.<R4><C2>,

<C2>.then.<S><C3>, <C3>.else.<S>, <C3>$, <R4><I><R3>, <R3>< <I>, <R3>= <I> } .

 

В этой грамматике <S>определяется схемой грамматикиГ_{1. 27} . Рассмотрим описание операторов цикла, подобных используемым в языке Паскаль, с разделителями'while', 'do', 'repeat', 'until'.Каждый оператор может быть описан в виде простой последовательности ограниченной длины, в которой используются построенные ранее грамматика Г_{1. 28} и грамматика Г_{1. 27}. На практике часто встречаются ситуации, когда удобнее работать с грамматикой, правая часть правил которой  начинается терминальным символом. Построение подобных грамматик сводится к тому, что для каждого терминального символа заданной конструкции языка строится отдельное правило. Для рассматриваемых операторов цикла такие схемы грамматик с использованием определенных ранее нетерминальных символов  имеют вид:

Г_{1. 29}:    R = { <W>.while. <R4><C4>,

<C4>.do. <S> }

Г_{1. 30}:    R = { <W1>.repeat.<S><C5>,

 <C5>.until.<R4> }.

 

1.5.9. Резюме

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

2. Контекстно-свободные грамматики и автоматы.

2.1 Приведенные грамматики.

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

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

Вначале рассмотрим алгоритм выявления символов, из которых нельзя вывести конечные цепочки.