Формальные языки и грамматики

Содержание

1 Формальные языки и грамматики.....................................................................

1.1 Операции над цепочками символов...............................................................

1.2 Способы задания языков................................................................................

1.2.1 Определение языков посредством множеств..............................................

1.2.2 Формы Бэкуса-Наура...................................................................................

1.2.3 Диаграммы Вирта........................................................................................

1.2.4 Формальные грамматики.............................................................................

1.2.4.1 Определение формальной грамматики....................................................

1.2.4.2 Классификация языков и грамматик........................................................

1.2.4.3 Эквивалентность грамматик.....................................................................

1.2.5 Механизмы распознавания языков.............................................................

1.2.5.1 Определение распознавателя....................................................................

1.2.5.2 Схема работы распознавателя.................................................................

1.2.5.3 Классификация распознавателей..............................................................

2 Регулярные языки..............................................................................................

2.1 Регулярные выражения...................................................................................

2.2 Лемма о разрастании для регулярных языков..............................................

2.2 Конечные автоматы.........................................................................................

2.2.1 Определение конечного автомата...............................................................

2.2.2 Распознавание строк конечным автоматом................................................

2.2.3 Преобразование конечных автоматов........................................................

2.2.3.1 Преобразование конечного автомата к детерминированному виду......

2.2.3.2 Минимизация конечного автомата...........................................................

2.2.3.2.1 Устранение недостижимых состояний автомата...................................

2.2.3.2.2 Объединение эквивалентных состояний автомата................................

2.4 Взаимосвязь способов определения регулярных языков.............................

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

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

3 Контекстно-свободные языки............................................................................

3.1 Задача разбора................................................................................................

3.1.1 Вывод цепочек..............................................................................................

3.1.2 Дерево разбора............................................................................................

3.1.2.1 Нисходящее дерево разбора....................................................................

3.1.2.2 Восходящее дерево разбора.....................................................................

3.1.3 Однозначность грамматик...........................................................................

3.2 Преобразование КС-грамматик ....................................................................

3.2.1 Проверка существования языка..................................................................

3.2.2 Устранение недостижимых символов..........................................................

3.2.3 Устранение e-правил....................................................................................

3.2.4 Устранение цепных правил..........................................................................

3.2.5 Левая факторизация правил........................................................................

3.2.6 Устранение прямой левой рекурсии...........................................................

3.3 Автомат с магазинной памятью......................................................................

3.3.1 Определение МП-автомата..........................................................................

3.3.2 Разновидности МП-автоматов.....................................................................

3.3.3 Взаимосвязь МП-автоматов и КС-грамматик............................................

3.3.3.1 Построение МП-автомата по КС-грамматике.........................................

3.3.3.2 Построение расширенного МП-автомата по КС-грамматике................

3.4 Нисходящие распознаватели языков.............................................................

3.4.1 Рекурсивный спуск.......................................................................................

3.4.1.1 Сущность метода.......................................................................................

3.4.1.2 Достаточные условия применимости метода...........................................

3.4.2 Распознаватели LL(k)-грамматик................................................................

3.4.2.1 Определение LL(k)-грамматики................................................................

3.4.2.2 Необходимое и достаточное условие LL(1)-грамматики........................

3.4.2.3 Построение множеств FIRST(1, A)...........................................................

3.4.2.4 Построение множеств FOLLOW(1, A)......................................................

3.4.2.5 Алгоритм «сдвиг-свертка» для LL(1)-грамматик....................................

3.5 Восходящие распознаватели языков..............................................................

3.5.1 Грамматики предшествования.....................................................................

3.5.1.1 Грамматики просторного предшествования...........................................

3.5.1.1.1 Определение грамматики простого предшествования.........................

3.5.1.1.2 Поиск основы сентенции........................................................................

3.5.1.1.3 Построение множеств L(A) и R(A)........................................................

3.5.1.1.4 Матрица предшествования....................................................................

3.5.1.1.5 Алгоритм «сдвиг-свертка» для грамматик простого предшествования

3.5.1.2 Грамматики операторного предшествования..........................................

3.5.1.2.1 Определение грамматики операторного предшествования.................

3.5.1.2.2 Построение множеств L^t(A) и R^t(A).......................................................

3.5.1.2.3 Матрица операторного предшествования............................................

3.5.1.2.4 Алгоритм «сдвиг-свертка» для грамматик простого предшествования

3.5.2 Распознаватели LR(k)-грамматик................................................................

3.6 Соотношение классов КС-грамматик.............................................................

4 Принципы построения трансляторов................................................................

4.1 Лексика, синтаксис и семантика языка...........................................................

4.2 Определение транслятора, компилятора, интерпретатора и ассемблера....

4.3 Общая схема работы транслятора.................................................................

4.5 Лексический анализ.........................................................................................

4.5.1 Задачи лексического анализа......................................................................

4.5.2 Диаграмма состояний с действиями............................................................

4.5.3 Функция scanner...........................................................................................

4.6 Синтаксический анализ ..................................................................................

4.6.1 Задачи синтаксического анализа.................................................................

4.6.2 Нисходящий синтаксический анализ...........................................................

4.7 Семантический анализ....................................................................................

4.8 Генерация кода................................................................................................

4.8.1 Формы внутреннего представления программы........................................

4.8.1.1 Тетрады.....................................................................................................

4.8.1.2 Триады.......................................................................................................

4.8.1.3 Синтаксические деревья............................................................................

4.8.1.4 Польская инверсная запись......................................................................

4.8.1.5 Ассемблерный код и машинные команды...............................................

4.8.2 Преобразование дерева операций в код на языке ассемблера..................

4.9 Оптимизация кода...........................................................................................

4.9.1 Сущность оптимизации кода.......................................................................

4.9.2 Критерии эффективности результирующей объектной программы.........

4.9.3 Методы оптимизации кода..........................................................................

4.9.4 Оптимизация линейных участков программ..............................................

4.9.4.1 Свертка объектного кода..........................................................................

4.9.4.2 Исключение лишних операций.................................................................

4.9.5 Оптимизация циклов....................................................................................

4.9.6 Оптимизация логических выражений.........................................................

4.9.7 Оптимизация вызовов процедур и функций...............................................

4.9.8 Машинно-зависимые методы оптимизации................................................

5 Формальные методы описания перевода..........................................................

5.1 Синтаксически управляемый перевод............................................................

5.1.1 Схемы компиляции......................................................................................

5.1.2 СУ-схемы......................................................................................................

5.1.3 МП-преобразователи...................................................................................

5.1.4 Практическое применение СУ-схем............................................................

5.2 Транслирующие грамматики.........................................................................

5.2.1 Понятие Т-грамматики.................................................................................

5.2.2 Т-грамматика с подпрограммами...............................................................

5.2.3 МП-преобразователь для Т-грамматики....................................................

5.3 Атрибутные транслирующие грамматики.....................................................

5.3.1 Синтезируемые и наследуемые атрибуты...................................................

5.3.2 Определение и свойства АТ-грамматики....................................................

5.3.3 ФормированиеАТ-грамматики ...................................................................

Формальные языки и грамматики

Основные понятия теории формальных языков

В основе каждого языка лежит алфавит.

ОпределениеАлфавитом V называется конечное множество символов.

ОпределениеЦепочкой a в алфавите V называется любая конечная последовательность символов этого алфавита.

Определение Цепочка, которая не содержит ни одного символа, называется пустой цепочкой и обозначается e.

ОпределениеФормальное определение цепочки символов в алфавите V:

1) e - цепочка в алфавите V;

2) если a - цепочка в алфавите V и а – символ этого алфавита, то a а – цепочка в алфавите V;

3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу утверждений 1) и 2).

ОпределениеДлиной цепочки a называется число составляющих ее символов (обозначается |a|).

ОпределениеКонкатенацией (сцеплением) цепочек a и b называется цепочка g=ab, в которой символы данных цепочек записаны друг за другом.

Для любой цепочки a справедливо утверждение ae=ea.

ОпределениеСтепенью n цепочки a называется конкатенация n цепочек a. (обозначается aⁿ).

Для любой цепочки a справедливы утверждения a⁰=e и aⁿ=a^n-1a=aa^n-1 для n³1.

ОпределениеРеверсом (обращением) цепочки a называется цепочка a^R, составленная из символов цепочки a, записанных в обратном порядке.

ПримерПусть алфавит V={a, b, c, d}, тогда для цепочек этого алфавита a=ab и b=bcd будет справедливо |a|=2, |b|=3, ab= abbcd, a²=abab, b^R=dcb.

Обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e, а через V⁺ - множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e.

ОпределениеФормальным языком L в алфавите V называют произвольное подмножество множества V^*.

ПримерПусть алфавит двоичных цифр , тогда , а .

Задать язык L в алфавите V можно тремя способами:

1) перечислением всех допустимых цепочек языка (на языке множеств);

2) указанием способа порождения (генерации) цепочек языка (грамматики, формы Бэкуса-Наура и диаграммы Вирта;

3) определением метода распознавания цепочек языка (распознаватели).

ПримерЯзык L в алфавите , состоящий из пустой строки и всевозможных строк, каждая из которых содержит строку нулей и последующую строку единиц той же длины, можно описать с помощью формальной системы определения множеств как L={0ⁿ1ⁿ | n³0}.