к библиотеке   Устройства ввода информации   к экономической информатике   к дискретной математике

Введение в теорию трансляторов

Основания теории трансляторов

  1. Понятие информации
  2. Формальная логика
  3. Булева алгебра
  4. Математическая логика
  5. Математическая статистика
  6. Нечеткая логика
  7. Теория ранговых измерений
  8. Теория принятия решений
  9. Кластерный анализ
  10. Распознавание образов

Элементы теории трансляторов

  1. Типы алгоритмов
  2. Восстановление после ошибок
  3. Восстановление в режиме паники
  4. Восстановление на уровне фразы
  5. Продукции ошибок
  6. Разновидности трансляторов
  7. Фазы компиляции
  8. Группировка фаз
  9. Инструменты создания трансляторов
  10. Трансляторы трансляторов
  11. Генераторы анализаторов
  12. ПО для разработки анализаторов
  13. Литература

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

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


Пример разбора выражения в дерево

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

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

Всё что угодно, имеющее "синтаксис", поддается автоматическому анализу:

Типы алгоритмов

Нисходящий парсер (англ. top-down parser) - такой парсер, в котором продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности лексем.
Восходящий парсер (англ. bottom-up parser) - такой парсер, в котором продукции восстанавливаются из правых частей, начиная с токенов-лексем и кончая стартовым символом.

Восстановление после ошибок

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

Таким образом перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:

Ниже описаны наиболее известные стратегии восстановления после ошибок.

Восстановление в режиме паники

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

Восстановление на уровне фразы

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

Продукции ошибок

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

Разновидности трансляторов

Что такое компилятор? Что такое интерпретатор? Что такое исходный язык? Что такое целевой язык?

Интерпретаторы

Фазы трансляции

На примере выражения p := i + r * 60

 id1 := id2 + id3 * 60
  • Обнаружение ошибок. Лексические, синтаксические и семантические ошибки.
  • Генерация промежуточного кода

На примере трехадресного кода

 t1 := IntToReal(60)
 t2 := id3 * t1;
 t3 := id2 + t2;
 id1 := t3;
  • Оптимизация кода
 t1 := id3 * 60.0;
 id1 := id2 + t1;
  • Генерация кода (основное - назначение переменных регистрам)
 MOVF id3, R2
 MULF #60.0, R2
 MOVF id2, R1
 ADDF R2, R1
 MOVF R1, id1
Методы построения трансляторов

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

Математическим обеспечением фаз лексического и синтаксического анализа является теория формальных языков. Обычно лексические анализаторы генерируются с помощью регулярных выражений.

Синтаксический анализ основывается на теории контекстно-свободных (КС) грамматик. Общая форма КС-грамматики не позволяет разбирать язык достаточно простым (в частности, автоматически сгенерированным) парсером, потому языки программирования обычно принадлежат одному из нескольких специальных подклассов КС-языков (LL, LR, LALR), которые проще разбирать и некоторые из которых будут подробно изучены в курсе.

Упомянутые достижения теории формальных языков насчитывают уже несколько десятков лет, и в этой области не ожидается каких-либо новых разработок, тем более что имеющиеся теоретические результаты хорошо решают практические задачи. По другому обстоит дело с изучением других двух разделов компиляции: семантическим анализом и оптимизацией. Работы по формальному описанию семантики языков программирования интенсивно появлялись в 70-80-х годах. Однако ни одна из построенных теорий не вошла в широкое употребление при построении трансляторов, и сегодня дело обстоит таким образом, что семантика вначале описывается на естественном языке, а затем реализуется в компиляторе большим набором вручную закодированных условных операторов.

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

На этапе построения семантического дерева строится таблица символов - в нее заносятся имена, присутствовавшие в исходном тексте, к ним добавляются такие атрибуты как тип, отведённая память, область видимости.

Группировка фаз

Перечисленные выше фазы обычно группируются в два модуля - front-end и back-end, в зависимости от того, к какой стороне процесса компиляции они ближе, к исходному языку или к машинному коду для целевой платформы, соответственно. Возможность отдельно разрабатывать front-end и back-end повышает эффективность труда разработчиков трансляторов - насколько, зависит от эффективности используемого внутреннего представления, связывающего эти два модуля. В последнее время всё чаще выделяют middle-end - части компилятора, активно работающие с промежуточным представлением.

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

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

Инструментарий для создания трансляторов

Трансляторы трансляторов

Генераторы лексических и синтаксических анализаторов

Обзор.

Yacc, Lex
Byson, Flex
CoCo
ANTLR
Gold Parser Builder
GPPG 

Создание лексического анализатора (сканера) с помощью gplex

Общая структура .l файла

Особенности .l файла gplex

Возвращение типов лексем

Лексемы идентификаторов, чисел.

Ключевые слова

Позиция лексемы

Начальные состояния сканера, их изменение, использование для вырезания комментариев:

%x COMMENT
%%
"/*" { BEGIN(COMMENT);}
<COMMENT> "*/" { BEGIN(INITIAL);}
<COMMENT> <<EOF>> { Console.WriteLine("Комментарий не закрыт");}

Создание синтаксического анализатора с помощью gppg

Общая структура .y файла

Задание типов лексем

Таблица приоритетов и ассоциативности

Особенности .y файла gppg

Примеры

  1. Простейший калькулятор
    • Простейший калькулятор с приоритетом операций
    • Создание дерева разбора программы
    • Преобразование в XML
    • Добавление переменных. Представление о таблице символов
    • Добавление присваивания
    • Добавление типов
    • Добавление управляющих конструкций

ПО для разработки анализаторов

ANTLR - генератор парсеров

Bison - генератор парсеров

Coco/R - генератор сканера и парсера

GOLD - парсер

gppg - генератор парсеров для языка C#

JavaCC - генератор парсеров для языка Java

Lemon Parser - генератор парсеров

Lex - генератор сканеров

LRgen - генератор сканеров и парсеров

PEG.js - генератор парсеров для Javascript

Jison - генератор парсеров для Javascript

Ragel - генератор встраиваемых парсеров

Rats! - генератор парсеров для Java

Rebol

SableCC - генератор интерпретаторов

Spirit Parser Framework - генератор парсеров

Xerces - XML парсер

Yacc - генератор парсеров

SHProto - генератор FSM-парсеров

AGFL - генератор парсеров естественного языка

Литература

  1. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. - М.: Вильямс, 2001.
  2. Карпов Ю. Г. Основы построения трансляторов. - М.: BHV, 2005.
  3. Свердлов С. З. Языки программирования и методы трансляции. - М.: Питер, 2007.
  4. Опалева Э. А., Самойленко В.П. Языки программирования и методы трансляции. - М.: BHV, 2005.
  5. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. - 2-е изд. - М.: Вильямс, 2008. - ISBN 978-5-8459-1349-4
  6. Робин Хантер Основные концепции компиляторов = The Essence of Compilers. - М.: "Вильямс", 2002. - С. 256. - ISBN 5-8459-0360-2
к библиотеке   Устройства ввода информации   к экономической информатике   к дискретной математике
Знаете ли Вы, в чем фокус эксперимента Майкельсона?

Эксперимент А. Майкельсона, Майкельсона - Морли - действительно является цирковым фокусом, загипнотизировавшим физиков на 120 лет.

Дело в том, что в его постановке и выводах произведена подмена, аналогичная подмене в школьной шуточной задачке на сообразительность, в которой спрашивается:
- Cколько яблок на березе, если на одной ветке их 5, на другой ветке - 10 и так далее
При этом внимание учеников намеренно отвлекается от того основополагающего факта, что на березе яблоки не растут, в принципе.

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

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

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 26.02.2017 - 08:28: ЭКОЛОГИЯ - Ecology -> ПРОБЛЕМА ПРЕСНОЙ ВОДЫ - Карим_Хайдаров.
25.02.2017 - 07:30: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> Эксперименты с трансформатором Тесла - Карим_Хайдаров.
25.02.2017 - 07:22: СОВЕСТЬ - Conscience -> Просвещение от В.В. Пякина - Карим_Хайдаров.
24.02.2017 - 16:47: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
22.02.2017 - 16:11: СЕЙСМОЛОГИЯ - Seismology -> КРАТКОСРОЧНЫЙ ПРОГНОЗ ЗЕМЛЕТРЯСЕНИЙ - Карим_Хайдаров.
22.02.2017 - 02:43: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
21.02.2017 - 12:35: СОВЕСТЬ - Conscience -> Просвещение от Андрея Фурсова - Карим_Хайдаров.
19.02.2017 - 19:48: СОВЕСТЬ - Conscience -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров.
19.02.2017 - 11:33: СОВЕСТЬ - Conscience -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
19.02.2017 - 10:05: СОВЕСТЬ - Conscience -> Проблема государственного терроризма - Карим_Хайдаров.
17.02.2017 - 20:33: СОВЕСТЬ - Conscience -> Просвещение от академика С.Ю. Глазьева - Карим_Хайдаров.
16.02.2017 - 05:00: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> ЗАЩИТА ОТ КОМЕТНОЙ БОМБАРДИРОВКИ - Карим_Хайдаров.
Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution