- •1. Формальные языки и грамматики
- •1.1. Введение
- •1.1.1. Трансляторы, интерпретаторы и компиляторы
- •1.1.2. Стадии работы компилятора
- •1.1.3. Построение компилятора
- •1.2. Определение формальной грамматики и языка
- •1.2.1. Первичные понятия
- •1.2.2. Примеры, иллюстрирующие первичные понятия
- •1.2.3. Пустой язык
- •1.2.4. Резюме
- •1.3. Типы формальных языков и грамматик
- •1.3.1. Грамматики типа 0
- •1.3.2. Грамматики типа 1
- •1.3.3. Грамматики типа 2
- •1.3.4. Грамматики типа 3
- •1.3.5. Вывод в кс-грамматиках и правила построения дерева вывода
- •1.3.6. Синтаксический разбор
- •1.3.7. Левый и правый выводы
- •1.3.8. Неоднозначные и эквивалентные грамматики
- •1.3.9. Резюме
- •1.4. Способы задания схем грамматик
- •1.4.1. Форма Наура-Бэкуса
- •1.4.2. Итерационная форма
- •1.4.3. Синтаксическая диаграмма
- •1.4.4. Резюме
- •1.5. Построение грамматик и грамматики, описывающие основные конструкции языков программирования
- •1.5.1. Рекомендации по построению грамматик
- •1.5.2. Описание списков
- •1.5.3. Пример построения грамматик
- •1.5.4. Грамматики, описывающие целые числа без знака и идентификаторы
- •1.5.5. Грамматики для арифметических выражений
- •1.5.6. Грамматика для описаний
- •1.5.7. Грамматика, задающая последовательность операторов присваивания
- •1.5.8. Грамматики, описывающие условные операторы и операторы цикла
- •1.5.9. Резюме
- •2. Автоматные грамматики и распознаватели
- •2.1. Автоматные распознаватели
- •2.2. Недетерминированные распознаватели
- •2.3. Преобразование некоторых типов языков и грамматик к автоматному виду.
- •2.4 Построение распознавателя для заданного конечного языка
- •2.5 Минимизация числа состояний распознавателя
- •2.6 Резюме
- •3. Контекстно-свободные грамматики и магазинные автоматы.
- •3.1 Приведенные грамматики.
- •3.2.Преобразование кс-грамматик
- •3.3 Магазинные автоматы.
- •3.4. Нисходящие распознаватели, ll(k) и разделенные грамматики. Построение распознавателя.
- •3.5. Функции перв, след и выбор.
- •3.6. Слаборазделенные и ll(1) - грамматики. Преобразование грамматик к виду ll(1)
2.3. Преобразование некоторых типов языков и грамматик к автоматному виду.
Автоматные грамматики являются самыми простыми из всех типов грамматик. Прозрачный способ перехода от автоматных грамматик к распознавателям обуславливает их широкое использование для описания работы и построения, как блоков цифровых устройств, так и блоков компиляторов. Несколько увеличить сферу применения автоматных грамматик можно путем определения способа их построения для конечных языков и линейных грамматик.
Определение. Язык, содержащий конечное множество цепочек терминального алфавита, называется конечным языком.
Утверждение. Для любого конечного языка, в который не входит пустая цепочка, можно построить автоматную грамматику, порождающую этот язык.
Пусть задан язык L=α1,α2,...,αn , где αi Î VТ*. Возьмем некоторую цепочку αi=a1,a2,...,am, символы которой aj Î VТ. Выберем в качестве начального символа искомой грамматики символ <I> и m-1 нетерминальный символ A1, A2,..., Am-1. По выбранной цепочке построим m правил вывода искомой автоматной грамматики:
<I> ® a1<A1> , <A1> ® a2<A2>, <A2> ® a3<A3>,..., <Am-1> ® am .
Аналогичным образом построим правила вывода для каждой цепочки αk Î L , выбирая каждый раз новые нетерминальные символы.
Чтобы сократить число нетерминальных символов при построении правил грамматики для слов с одинаковыми начальными частями, следует использовать одинаковые нетерминальные символы. Например, если слово αi+1=a1,a2,a3’,...,am’ содержит начальный отрезок a1,a2, совпадающий с начальным отрезком слова αi, то правила грамматики должны иметь вид:
<I> ® a1<A1> , <A1> ® a2<A2>, <A2> ® a3’<A3’>,..., <Am-1’> ® am’ .
Совокупность всех введённых нетерминальных символов составит словарь VA, а совокупность правил - множество R искомой грамматики.
КС-грамматики, у которых в правой части правил содержится несколько терминальных символов и только один нетерминальный символ, который может быть расположен в крайней левой или крайней правой позиции, называют линейными. В зависимости от положения нетерминального символа такие грамматики делят на праволинейные и леволинейные. Основное отличие этих грамматик заключается в порядке построения цепочек языка. В общем случае показано, что эти виды грамматик эквивалентны, поэтому остановимся на рассмотрении только праволинейных грамматик.
Определение. Правило называется праволинейным, если оно имеет вид <A> ® α <B>, где α Î VТ* и <B> ÎVA. Правило называется заключительным, если оно имеет вид <A> ® α, где α Î VТ*.
Определение. Грамматика КС называется праволинейной, если все её правила праволинейные или заключительные.
Утверждение. По любой праволинейной грамматике может быть построена эквивалентная ей автоматная грамматика.
Возьмём некоторое правило заданной грамматики r=<A>® α<B> Î R. Пусть оно имеет вид <A> ® a1, a2,..., am <B>, где ai Î VТ, A, B Î VА и m > 2. Если m = 1, то такие правила преобразовывать не нужно, их следует просто перенести в искомую грамматику. Выберем m-1 нетерминальный символ A1, A2,..., Am-1 и преобразуем выбранное правило в группу правил вида.:
<A> ® a1 <A1>, <A1> ® a2<A2>, ...,<Am-1> ® am <B>.
Если исходное правило имело вид <A> ® a1 a2...am, то последнее из построенных правил должно иметь вид <Am-1> ® am. Выберем для каждого правила, у которого m ³ 2 , новые нетерминальные символы и выполним описанное преобразование. Добавляя к построенным правилам правила, правая часть которых состоит из одного символа или у которых m=1, получим А-грамматику, эквивалентную заданной.
При построении правил автоматной грамматики, как и в случае построения грамматики для конечного языка, необходимо учитывать наличие повторяющихся начальных отрезков правил заданной линейной грамматики.