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

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

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

  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
к библиотеке   Устройства ввода информации   к экономической информатике   к дискретной математике
Знаете ли Вы, что, как и всякая идолопоклонническая религия, релятивизм ложен в своей основе. Он противоречит фактам. Среди них такие:

1. Электромагнитная волна (в религиозной терминологии релятивизма - "свет") имеет строго постоянную скорость 300 тыс.км/с, абсурдно не отсчитываемую ни от чего. Реально ЭМ-волны имеют разную скорость в веществе (например, ~200 тыс км/с в стекле и ~3 млн. км/с в поверхностных слоях металлов, разную скорость в эфире (см. статью "Температура эфира и красные смещения"), разную скорость для разных частот (см. статью "О скорости ЭМ-волн")

2. В релятивизме "свет" есть мифическое явление само по себе, а не физическая волна, являющаяся волнением определенной физической среды. Релятивистский "свет" - это волнение ничего в ничем. У него нет среды-носителя колебаний.

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

4. В гравитационном релятивизме (ОТО) вопреки наблюдаемым фактам утверждается об угловом отклонении ЭМ-волн в пустом пространстве под действием гравитации. Однако астрономам известно, что свет от затменных двойных звезд не подвержен такому отклонению, а те "подтверждающие теорию Эйнштейна факты", которые якобы наблюдались А. Эддингтоном в 1919 году в отношении Солнца, являются фальсификацией. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 20.06.2017 - 15:36: СОВЕСТЬ - Conscience -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
18.06.2017 - 13:45: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> ЗА НАМИ БЛЮДЯТ - Карим_Хайдаров.
18.06.2017 - 13:32: СОВЕСТЬ - Conscience -> Просвещение от О.Н. Четвериковой - Карим_Хайдаров.
18.06.2017 - 09:31: СОВЕСТЬ - Conscience -> Проблема государственного терроризма - Карим_Хайдаров.
17.06.2017 - 16:30: АСТРОФИЗИКА - Astrophysics -> Происхождение тектитов и кимберлитов. Кометные молнии. - Карим_Хайдаров.
17.06.2017 - 06:56: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> неожиданное открытие Алена Аспекта - Карим_Хайдаров.
15.06.2017 - 17:36: СЕЙСМОЛОГИЯ - Seismology -> Эпистолярная сейсмология - Карим_Хайдаров.
15.06.2017 - 17:06: Беседка - Chatter -> ЭПИСТОЛЯРНАЯ ФИЗИКА - Карим_Хайдаров.
15.06.2017 - 12:01: Беседка - Chatter -> "Зенит"ы с "Протон"ами будут падать - Карим_Хайдаров.
15.06.2017 - 06:16: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> Эксперименты с трансформатором Тесла - Карим_Хайдаров.
14.06.2017 - 12:54: СОВЕСТЬ - Conscience -> РАСЧЕЛОВЕЧИВАНИЕ ЧЕЛОВЕКА. КОМУ ЭТО НАДО? - Карим_Хайдаров.
13.06.2017 - 07:45: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> БИОТРАНСМУТАЦИЯ ХИМИЧЕСКИХ ЭЛЕМЕНТОВ - Карим_Хайдаров.
Bourabai Research Institution home page

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