Лекции по конструированию компиляторов глава 3 синтаксический анализ


Содержание

Основы конструирования компиляторов

Автор Серебряков В.А. Галочкин М.П.
Издательство Едиториал УРСС
Год 1999
Формат PDF

Предлагаемая вниманию читателя книга основана на курсе лекций, прочитанных на факультете вычислительной математики и кибернетики Московского государственного университета и факультете управления и прикладной математики Московского физико-технического института в 1991-1999 гг. Авторы надеются, что издание книги восполнит существенный пробел в литературе на русском языке по разработке компиляторов.

Содержание книги представляет собой «классические» разделы предмета: лексический и синтаксический анализ, организация памяти компилятора (таблицы символов) и периода исполнения (магазина), генерация кода. Рассматриваются некоторые средства автоматизации процесса разработки трансляторов, такие как LEX, YACC, СУПЕР, методы генерации оптимального кода. Сделана попытка на протяжении всего изложения провести единую «атрибутную» точку зрения на процесс разработки компилятора. В книге не затрагиваются чрезвычайно важные вопросы глобальной оптимизации и разработки компиляторов для машин с параллельной архитектурой. Авторы надеются восполнить эти пробелы в будущем.

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

Синтаксический разбор языков программирования

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

Но ввиду отсутствия образования, не могу вникнуть в суть ГРАММАТИК СИНТАКСИЧЕСКОГО РАЗБОРА.
То есть суть почти понимаю и могу решать простые задачи и упражнения по разбору (чисто их правилами разбора), но очень в отрыве от любого кода или даже просто алгоритма. Программирую на бейсике .
Книги конечно читаю, но там всё объяснение в формулах и всё как-то не однозначно.
Очень хотелось бы получить ответы от знающих людей на несколько вопросов по этой теме, что-бы было от чего отталкиватся.

1) Насколько я понял LL(1) грамматика самая простая и быстрая, это так -?
Простая всмысле ручного программирования, и парсер будет самый эффективный по скорости разбора -?

2) Является ли EcmaScript (JavaScript) языком подходящим для LL(1) грамматики -? или только LR грамматики -?

3) ТЕРМИНАЛЫ это — «for», «next», «else», то есть конкретные однозначные имена операторов, переменных и тд. НЕТЕРМИНАЛЫ это — формулы, выражения, конструкции, то есть не конкретный оператор с именем «FOR», а просто абстактно любой «оператор» Я правильно понял -?

4) Из википедии: Синтаксический LL-анализатор (LL parser) — в информатике нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик. Он анализирует входной поток слева направо, и строит левый вывод грамматики.

Низходящий — я понял, анализирует поток слева на право — это начиная с первой буквы до конца текста или опять какая-то абстракция с подставами правил — ?
Как понять левый вывод грамматики — на примере каком нибудь -? хоть на яблоках .

Если не трудно, подскажите пж-ста, конкретные однозначные ответы, задолбали эти абстракции.
СПАСИБО.

06.08.2020, 18:32

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

Запоминание разных языков программирования
Приветствую. Только начал изучать C++, до этого изучал VB.Net. В связи с этим возник вопрос.

Описание языков программирования + фреймворки
Задача: нужно быстро получить общее представление о том, на чем сейчас программирует народ. .

Необходим совет по изучению языков программирования.
Здрастсвуйте. Есть такой вопрос. Решил выучить язык программирования. Выбор пал на С++ или C#. Я.

Как делаются диалекты языков программирования?
Как делаются диалекты языков программирования? Прошу расписать полный путь (допустим у нас взят.

10.08.2020, 12:24 [ТС] 2

Здравствуйте. Жаль ни кто подсказать не может.
У меня за неделю неожиданно продвинулись познания, поэтому отвечу сам себе

1) Да
2) с ECMASCRIPT точно справится «Грамматики с операторным предшествованием»
3) Да с оговорками
4) Анализирует поток слева на право — это начиная с первой буквы до конца текста.

Виной всему эта книга : Конспективное изложение теории языков часть 1, 2015г
Есть ещё часть 2, практическая.

Написано по доходчивей, чем обычно пишут в такой литературе.
Вот пример объяснения грамматики:

Рассмотрим грамматику, которая описывает синтаксическую конструкцию «объявление переменной» в стиле языка Си:
G12a(, , <
(1) S→ t «;»
(2) A→ d | (3) A «,»d
>,S).
В этой грамматике:
(1), (2), (3) — номер применяемого правила.
— символ «t» обозначает произвольный тип переменной;
— символ «d» обозначает произвольный идентификатор;
— символы «;» и «,» обозначают сами себя. Символы заключены в кавычки, чтобы отличить их от соответствующих знаков пунктуации.
— символ «S» является целевым и обозначает оператор объявления, то есть всю конструкцию оператора.
— символ «A» обозначает список объявляемых переменных.
Правило (1) S→ tA«;» имеет следующий смысл:
Строка объявления – это тип, список переменных, точка с запятой.
Правило (2) A→ d: список переменных – это идентификатор
Правило (3) A→ A «,»d : список переменных – это список переменных, запятая, идентификатор
С помощью этой грамматики порождаются цепочки вида:
«тип ид;»
«тип ид, ид;»
«тип ид, ид, ид;» и т.д.
Здесь «тип» обозначает произвольный тип t (тип объявляемой переменной), а «ид», соответственно- некоторый произвольный идентификатор d (имя переменной).
Грамматика порождает цепочку «тип ид;» следующим образом:
S → (1) tA; →(2) td;
Цепочка вида «тип ид, ид;»
Преобразовывается так:
S → (1) tA; → (3) tA,d; → (2) td,d;.

Моё . Описание смысла этого преобразования :
Оператор объявления переменных (S) содержит : тип переменных(t), список переменных(A), точка с запятой(
Далее, если при чтении текста программы выясняется, что переменная в списке не одна, то применяем правило (3) и распиливаем список переменных (A) на список переменных(A)+ запятая(,)+ имя переменной(d)), то есть выдёргиваем переменную(d) и запятую из списка(A) и пишем их рядом. И так пока в списке(A) не останется только одна переменная (d).

Если в списке остаётся только одна переменная, то применяем правило (2), то есть полностью заменяем (оставшийся) список переменных(A) на имя последней переменной(d), а символ (A) полностью исключаем из формулы.

Остальное я не буду переписывать.
Не знаю, можно ли выкладывать ссылки сюда? Я накопытил более 100 книг и больших статей по теме.

Спасибо себе, дальше я сам

11.08.2020, 14:25 [ТС] 3

Всем привет!
Кому интересна тема » компиляторы, интерпретаторы, трансляторы, синтаксический разбор языков программирования, грамматики разбора и подобное «.

Вот подборка литературы (РУС) на данную темы.

Вот перечень файлов в архиве:

Вирт — Разработка ОС и компилятора. 2012 с исходниками
31-Конечный-автомат
instruction_tables — таблица времени выполнения инструкций ассемблера
LL(k)-ГРАММАТИКИ И ТРАНСЛЯЦИИ
Абельсон Х. Структура и интерпретация компьютерных программ.2004
Автоматное программирование
Алгоритмы оптимизации кода
Алгоритмы, языки, автоматы и компиляторы
Ахо — Компиляторы — Принципы, Технологии, Инструменты 2003
Ахо, — Компиляторы. Принципы, технологии, инструменты.2ed.2008
Баранов язык ФОРТ и его реализации 1988
Вирт Н. — Построение компиляторов (Классика программирования) — 2010
Виртуальные машины компиляция
Восходящие анализаторы
Генератор синтаксических анализов для КС грамматик 2010
Гриффитс А.GCC. Настольная книга. Диасофт.[RUS,624p,2004]
Гуренко В.В. Введение в теорию автоматов
Давайте создадим компилятор
ИНТЕРПРЕТАТОР СКРИПТОВОГО ЯЗЫКАJAVASCRIPT
Интерпретация Лиспа
Карпов — Основы построения трансляторов (2005)
Конечные автоматы. Разбор выражений
Конспективное изложение теории языков 2015
Конструирование компиляторов (учебное пособие) 2015
Креншоу Д. Пишем компилятор
Лекции Грамматики слабого предшествования
Лекции о компиляции
ЛЕКЦИИ ПО ТЕОРИИ АЛГОРИТМОВ 2009
Лекции по транслятору
ЛЕКЦИЯ № 3 ТЕОРИЯ ЯЗЫКОВ И ФОРМАЛЬНЫХ ГРАММАТИК
Лингвистическое обеспечение а. систем
МАГАЗИННЫЕ АВТОМАТЫ ГЛАВА 5
МЕТОДЫ ТРАНСЛЯЦИИ конспект лекций ч1
Методы трансляции уч. пособие 2000
Методы ускорения алгоритмов распознавания символов
Недетерминированные конечные автоматы 2007
Недетерминированные конечные автоматы
О некоторых свойствах автоматов с магазинной памятью
Опалёва. Языки программирования и методы трансляции (2005)
Основы разработки трансляторов в САПР
Основы трансляции конспект лекций
Основы функционального программирования 2004
Парсер-комбинаторы и левая рекурсия
Построение простейшего дерева вывода
Практикум по теории языков и трансляции 2015
Приведение грамматики к виду LL(1)
Принципы построения распознавателей КС-языков без возвратов
Программа управления компиляцией GNU make Версия 3.79
Проект «исследовательский компилятор»
Разбор и вычисление выражений
Редкая профессия
Робин Хантер — основные концепции компиляторов 2002
Свердлов Языки программирования и методы трансляции 2007
Серебряков В.А. — Основы конструирования компиляторов — 2001
Способы внутреннего представления программ
Сравнение алгоритмов восходящих и нисходящих.
Теорема о равносильных определениях LL(1)
Теория автоматов 2001
Теория и практика языков программирования 2013
Теория и реализация языков программирования 2006
Теория синтаксического анализа, перевода и компиляции 1978
Теория синтаксического анализа, перевода и компиляции. 1978 Том 2
Теория языков программирования и методы трансляции
Технологии трансляции 2008
Трансляторы.chm
Фомичев — Формальные языки
Формальные грамматики и языки 1999
Формальные языки и основы трансляторов 2003
Элементы теории конечных автоматов 2010
Языки и трансляции 2008
Языки программирования и методы трансляции 2007
Языки программирования и методы трансляции 2013 конспект
Языки программирования и методы трансляции ч2
Языки программирования и методы трансляции
ЯЗЫКИ ПРОГРАММИРОВАНИЯ концепции и принципы 1986
Курс о теории формальных языков
Курс Основы построения трансляторов
Папка со статейками из инета

Пользуйтесь на здоровье!

12.08.2020, 16:12 [ТС] 4

Уточнение по поводу терминальных — нетерминальных символов. Что бы не было вопросов.

Лексический анализ текста — это разбор символов входного текста (из букв и цифр) на лексемы.
Лексема – простейшая смысловая конструкция распознаваемого языка,
может состоять из нескольких символов (знаков, букв, цифр), например это может быть
ключевое слово («FOR» , «NEXT» и т.д.») или идентификаторы («A» -имя переменной)
или знаки пунктуации («,» «.» «:» «;» и т.д.) или знаки математических операций («+» «-» «*» «/» и т.д.)
или литералы («123» — непосредственная запись значения: символьная, числовая или строковая)

Лексема определённой категории – токен.

После лексического анализа образуется поток токенов- лексем, который является входным текстом для синтаксического анализа, а токены – ТЕРМИНАЛЬНЫМИ символами для синтаксических грамматик разбора.

Нетерминальные символы – это условные символы, обозначающие КОНСТРУКЦИИ языка, состоящие из токенов, а не отдельные токены. Например: IF – токен, THEN – токен, ELSE – токен, а условный символ «А», обозначающий синтаксическую конструкцию «IF then Else» — это и есть НЕТЕРМИНАЛЬНЫЙ символ «А».

А в основном, смысл грамматик разбора в подмене по ОПРЕДЕЛЁННЫМ ПРАВИЛАМ нетерминалов «А» на терминалы «а» — они же токены.
Всё просто.

Конспект лекций «Методы построения компиляторов»

Содержание

Литература

  1. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. — М.: Вильямс, 2001.
  2. Карпов Ю. Г. Основы построения трансляторов. — М.: BHV, 2005.
  3. Свердлов С. З. Языки программирования и методы трансляции. — М.: Питер, 2007.
  4. Опалева Э. А., Самойленко В.П. Языки программирования и методы трансляции. — М.: BHV, 2005.

Лекция 1

Введение в компиляцию

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

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

  • Интерпретаторы
  • Форматтеры текста
  • Статические анализаторы кода
  • Препроцессоры
    • макросы define
    • включение файлов #include
    • условная компиляция #ifdef
    • расширения языка, которые препроцессор переводит в код на языке

Фазы компиляции

  • Лексический анализ (сканирование)
  • Синтаксический анализ (разбор, „парсинг“)
  • Семантический анализ

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

  • Обнаружение ошибок. Лексические, синтаксические и семантические ошибки.
  • Генерация промежуточного кода

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

  • Оптимизация кода
  • Генерация кода (основное — назначение переменных регистрам)

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

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

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

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

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

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

Лекция 2

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

  • Front-end и back-end компиляторы.

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

  • Проходы. Группировка фаз компилятора в проходы (например, объединение фаз лексического, синтаксического, семантического анализа и генерации кода).
Илон Маск рекомендует:  Атрибут low в HTML

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

  • Уменьшение количества проходов (на примере предварительного описания подпрограмм). Технология обратных поправок.

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

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

  • Генераторы лексических анализаторов (сканеров)
  • Генераторы синтаксических анализаторов (парсеров)
  • Автоматические генераторы кода

Компиляторы компиляторов

  • Lex + Yacc
  • Flex + Bison
  • CoCo
  • Antlr
  • Gold Parser Builder
  • GPLex + GPPG

Порождающие грамматики

Определение. Символы: терминалы и нетерминалы. Продукции (правила вывода). Стартовый символ.

Опр. формальной грамматики (порождающей грамматики Хомского)

V = Σ + N — множество всех нетерминалов и терминалов

X * — множество всех цепочек символов из X

Классификация формальных грамматик по Хомскому (1956 г.)

  • Грамматика типа 0 (общего вида). Правила имеют вид α→β
  • Грамматика типа 1 (контекстно зависимая, КЗ)


Правила имеют вид αAβ → αγβ. γ принадлежит V + , т.е. грамматика является неукорачивающей Добавляется также правило S → ε α,β называются левым и правым контекстом

  • Грамматика типа 2 (контекстно свободная, КС)

Правила имеют вид A → α. α ∊ V* Наиболее близкая к БНФ

  • Грамматика типа 3 (автоматная, регулярная)

Правила имеют вид A → aB, A → a, A → ε (правая регулярная грамматика) Автоматные языки содержатся в КС языках

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

Порождение (вывод)

Далее будем говорить только о КС-грамматиках.

Грамматика G порождает (выводит) цепочки из стартового символа, используя правила вывода.

Опр. Сентенциальной формой грамматики называется строка, которая может быть выведена из стартового символа.

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

Опр. Языком над алфавитом (словарём) Σ называется подмножество L множества Σ * .

Опр. Языком L(G), порождаемым грамматикой G, называется множество всех ее предложений:

Опр. Две грамматики называются эквивалентными, если языки, ими порождаемые, совпадают:

Утв. Проблема эквивалентности КС-грамматик алгоритмически неразрешима.

Левый, правый вывод (порождение). Деревья вывода (разбора)

Опр. Если в процессе вывода заменяется всякий раз самый левый нетерминал, то такой вывод называется левым.

Левый и правый вывод для предложения i + i * i

Дерево вывода (дерево разбора) строки предложения. В отличие от порождения, из него исключена информация о порядке вывода.

Крона дерева разбора — цепочка меток листьев слева направо

Неоднозначные грамматики

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

Пример неоднозначной грамматики. Грамматика арифметических выражений.

Два дерева разбора для цепочки i + i * i

Преобразование в эквивалентную однозначную грамматику:

Пример неоднозначной грамматики. Грамматика условного оператора

Два дерева разбора для цепочки if b then if b then a

Преобразование в эквивалентную однозначную грамматику:

Утверждение. Проблема неоднозначности произвольной КС-грамматики алгоритмически не разрешима

Леворекурсивные грамматики, их проблемы. Алгоритм устранения левой рекурсии.

Перевод (трансляция)

Ранее мы решали вопрос о принадлежности некоторой цепочки α интересующему нас языку L, задаваемому грамматикой G. Но задача компиляции шире: не только распознать входную цепочку, но и сгенерировать выходную.

Определение. Пусть Σ и Δ — два алфавита (называемые „входным“ и „выходным“ соответственно). L1 ⊂ Σ*, L2 ⊂ Δ*. Переводом с языка L1 на язык L2 называется отображение τ: L1 → L2.

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

Схема синтаксически управляемого перевода (СУ-схема)

Неформальное определение. СУ-схема это грамматика, в которую с каждым синтаксическим правилом встроен элемент перевода.

Пример. Перевод алгебраического выражения в ПОЛИЗ (польская инверсная запись). Запишем правила грамматика вместе с элементами перевода.

Правило Элемент перевода
E → E + T E = E T +
E → T E = T
T → T * P T = T P *
T → P T = P
P → (E) P = E
P → P =

Выведем цепочку a * (b + c) и одновременно переведём её в ПОЛИЗ: a b c + * (как обычно, используем левый вывод):

Определение. Схема синтаксически управляемого перевода это пятёрка

Причём α и β в каждом конкретном правиле содержат одни и те же нетерминалы с точностью до перестановки.

Далее считаем, что задана некоторая СУ-схема T = (N, Σ, Δ, R, S).

Определение. Входная грамматика, соответствующая СУ-схеме T, это четвёрка

Определение. Выходная грамматика, соответствующая СУ-схеме T, это четвёрка

Определение. СУ-перевод (СУ-трансляция) это множество

обозначаемое обычно τ(T).

СУ-перевод можно понимать как трансформацию синтаксических деревьев (соответствующих выводу входной и выходной цепочек).

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

Позволяют решать задачу перевода в более сложных случаях, чем СУ-схемы. ТГ это разновидность КС-грамматик, где символы (терминалы) разделены на два множества, Σi и Σa (a от action), называемые „входными“ и „операционными“ соответственно. При использовании ТГ, чтобы различать элементы Σi и Σa, будем заключать последние в фигурные скобки, ‘<’, ‘>’, считая получившиеся на письме три символа одним символом алфавита.

Пример. Перевод простого алгебраического выражения в ПОЛИЗ .

Определение. Пусть α ∊ (Σi ∪ Σa)*. Тогда α называется активной цепочкой. Входные (операционные) символы активной цепочки, записанные отдельно в том же порядке, как они встречались в ней, образуют входную (операционную) цепочку.

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

Атрибутные грамматики и трансляция

В АГ с каждым символом грамматики может быть связан один или несколько атрибутов. Для каждого синтаксического правила вводятся семантические правила, устанавливающие функциональные зависимости между атрибутами.

Дерево, содержащее атрибуты, называется аннотированным. Атрибуты придают смысл синтаксической структуре, описываемой деревом, и потому аннотированное дерево называется также семантическим деревом.

Пример. Вычисление простого арифметического выражения .

  1. Синтезированные — значения таких атрибутов зависят только от значений атрибутов потомков в дереве разбора.
  2. Унаследованные — значения таких атрибутов зависят от значений атрибутов родительского узла, узлов-братьев и сестёр (дочерних для родительского), а также других атрибутов самого узла.

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

Понятие синтаксического анализатора.

Нисходящие (top-down) и восходящие (bottom-up) синтаксические анализаторы

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

Опр. Синтаксический анализатор, работающий методом рекурсивного спуска и не требующий откатов, называется предиктивным синтаксическим анализатором.

Нерекурсивный предиктивный анализ

Схема работы со стеком, таблицей разбора, входным буфером

Алгоритм нерекурсивного предиктивного анализа

Множества FIRST и FOLLOW

Алгоритм построения таблиц предиктивного анализа.

Определение LL(1) грамматики. Пояснение названия.

Утв. LL(1) грамматика не может быть леворекурсивной или неоднозначной.

Эквивалентное определение LL(1) грамматики.

Восстановление после ошибок в предиктивном анализе.

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

Наиболее распространенная разновидность — ПС-анализ (перенос-свертка — shift-reduce)

Понятие основы. Примеры.

Обращенное правое порождение и обрезка основ.

Стековая реализация ПС-анализа. Основные операции:

Утв. Основа всегда находится на вершине стека и никогда — внутри него. Доказательство.

Понятие активного префикса.

LR-анализаторы. SLR, канонический LR и LALR анализаторы.

Общая схема и алгоритм LR-анализа. Пример.

Неоднозначности вида shift-reduce и их разрешение.

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

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

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

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

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

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

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

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

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

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

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

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

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

Основы конструирования компиляторов. Лексический анализ на C#

Задачей лексического анализа является разбить входную последовательность (в моем случае код на языке «Паскаль») на слова и лексемы.

Для начала я создал 5 типизированных листов для хранения данных, а именно: идентификаторов, констант, ключевых слов, разделителей и свертки. Также необходим массив разделителей

и массив ключевых слов. Я ограничился одиннадцатью ключевыми словами, так как статья написана как начальный пример реализации лексического анализа языка «Паскаль» на языке C#.
Итак, массив ключевых слов:

На входе мы имеем путь к .txt-файлу с программой в переменной path. Считываем весь в файл в AllTextProgram и начинаем.

В цикле for берем последовательно каждый символ из AllTextProgram и отправляем его в метод Analysis. Отдельно я рассматриваю лишь два исключения. Первое – это апострофы, которые в моем случае встречаются при использовании ключевого слова «writeln». Если встречаем апостроф, то отходим от правил и идем по переменной AllTextPorgram, пока ни найдем второй апостроф. Второе – это комментарии в программе. Для последних я просто считаю число открывающихся и закрывающихся фигурных скобок и ожидаю пока разница ни будет равна нулю.
Казалось бы программа должна зациклиться, если последующий апостроф не найден или кол-во фигурных скобок не равно 0. Да, это верно, в этих циклах необходимо добавить дополнительные условия выхода из проверки. Эти условия для систематизации я решил сделать на этапе синтаксического анализа.

Переменная type отвечает за номер таблицы, к которому относится лексема.
Идентификаторы – таблица 1
Константы – таблица 2
Ключевые слова – таблица 3
Разделители – таблица 4

Теперь настало время поговорить что же происходит в методе Analysis. Это лучше сделать в виде комментариев к коду. Сразу отмечу, что в переменной temp будем хранить промежуточный результат работы, пока ни встретим разделитель. Встретив разделитель, нам необходимо отправить переменную temp в метод Result, чтобы определить к идентификатору, константе или ключевому слову относится нынешняя лексема.

Заключительным для рассматрения является методе Result, где мы определяем, что же мы нашли. В самом начале проверяем переменную temp на принадлежность к ключевым словам. Проверяем в начале, чтобы не перепутать найденную лексему с идентификатором. Если найденное не является ключевым словом, то через switch проверяем тип таблицы, определенный заранее в методе Analysis. Не зыбываем проверить, чтобы найденный идентификатор/константа/разделитель уже не значился в таблице.

И легкий пример, чтобы показать как это все работает.
На входе программа:

program main; < proam >
var sum: real;
f, per_1, x_1,i:integer;
begin

x_1:=18;
f:= 456;
for i:=10 downto per_1-f+i*(x_1+1) do
begin
per_1 := per_1 + x_1*sum*f;
x_1:=-x_1-1;
f:=(f+1)*(x_1-24700);
sum:=(x_1+2.5)*4 — (x_1-6)*(x_1+2);
end;
writeln( ‘summa = ‘ , sum);
end.

Курсовая работа: Лексический и синтаксический анализатор языка высокого уровня

Государственное образовательное учреждение

высшего профессионального образования

Кубанский государственный технологический университет

Армавирский механико-технологический институт

Кафедра внутризаводского электрооборудования и автоматики

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по дисциплине: Теория языков программирования

на тему: «Лексический и синтаксический анализатор языка высокого уровня»

Государственное образовательное учреждение


высшего профессионального образования

Кубанский государственный технологический университет

Армавирский механико-технологический институт

Кафедра внутризаводского электрооборудования и автоматики

Заведующий кафедрой ВЭА

Проф. ____________ В.И. Куроедов

ЗАДАНИЕ

на курсовой проект

специальности 230105(2204) «Программное обеспечение вычислительной техники и автоматизированных систем»

Тема проекта: «Лексический и синтаксический анализатор языка высокого уровня»

Содержание задания: Спроектировать и построить лексический и синтаксический анализаторы для заданного формального языка программирования. Построить и реализовать в лексическом анализаторе распознаватель лексем с заданной структурой: нагруженное дерево (один элемент дерева хранит один символ (букву входного алфавита) лексемы).

Учебный язык включает директиву using, функцию main(), описание переменных, констант, цикла for, операторов присваивания, арифметические операции. За основу лексики, синтаксиса и семантики учебного языка принять стандарты языка программирования С#.

Пояснительная записка 35 – 40 листов

Графическая часть 2-3 листа формата А3

1. Ключко В.И. Теория вычислительных процессов и структур. Учебное пособие, — КубГТУ, 1998;

2. Соколов А.П. Системы программирования: теория, методы, алгоритмы: Учеб. Пособие, — М.:

Финансы и статистика, 2004. – 320 с.: ил.

3. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. — СПб.: Питер, 2001. — 736 с.

Срок выполнения проекта:

с «___»____________ «___»_____________20___ г.

Срок защиты «___»____________ 20___ г.

Дата выдачи задания «___»_____________20___ г.

Дата сдача проекта на кафедру «___»_____________20___ г.

Руководитель канд. техн. наук, доцент _____________________

Задание принял студент______________________________

ГОСТ Р ИСО 9001-2001 Системы менеджмента качества. Требования.

ГОСТ 7.1-2003 СИБИД. Библиографическая запись. Библиографическое описание. Общие требования и правила составления.

ГОСТ 19.101-77 ЕСПД. Виды программ и программных документов.

ГОСТ 19.102-77 ЕСПД. Стадии разработки.

ГОСТ 19.103-77 ЕСПД. Обозначение программ и программных документов.

ГОСТ 19.105-78 ЕСПД. Общие требования к программным документам

ГОСТ 19.202-78 ЕСПД. Спецификация. Требования к содержанию и оформлению.

ГОСТ 19.404-79 ЕСПД. Пояснительная записка Требования к содержанию и оформлению.

ГОСТ 19.701-90 ЕСПД. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения.

Пояснительная записка к курсовому проекту содержит 37 листов, 8 рисунков, 3 таблицы, 9 литературных источников, 2 приложения. К пояснительной записке прилагается 1 диск с готовой программой и материалами к ней, а также графическая часть, состоящая из трех листов.

СИНТАКСИС, ЛЕКСЕМА, КОНСТАНТА, АВТОМАТ – РАСПОЗНАВАТЕЛЬ, РЕГУЛЯРНОЕ МНОЖЕСТВО, ФОРМАЛЬНАЯ ГРАМАТИКА, ТЕРМИНАЛ, НЕТЕРМИНАЛ, АВТОМАТ С МАГАЗИННОЙ ПАМЯТЬЮ

Объект: лексический и синтаксический анализатор.

Цель: практическое применение теории формальных грамматик и теории автоматов для проектирования трансляторов.

Рассмотрен синтаксис заданного языка программирования, разработана грамматика регулярных множеств. Спроектированы автоматы для лексического анализа и распознавания лексем. Разработана формальная LL(1) грамматика для заданного языка программирования, спроектирован автомат с магазинной памятью для нисходящего анализа программы. Написана программа на языке высокого уровня Microsoft Visual C++ для лексического и синтаксического анализа текста на учебном языке программирования.

Конструирование компиляторов

Детерминированный нисходящий и восходящий синтаксический анализ (СА), устройство и конфигурация LL(1) анализатора, условия для грамматик. Функции FIRST и FOLLOW и их интерпретация. Вычисления FOLLOW для нетерминала при k=1. Грамматики предшествования.

Подобные документы

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

учебное пособие, добавлен 28.05.2014

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

курсовая работа, добавлен 06.08.2020

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

курсовая работа, добавлен 05.04.2020

Характеристика особенностей организации таблицы идентификаторов. Анализ принципов работы лексического анализатора. Изучение схемы распознавателя. Характеристика методов проектирования синтаксического анализатора. Матрица операторного предшествования.

курсовая работа, добавлен 09.11.2020

Характеристика и сущность LL(k)-грамматик. Основные особенности предсказывающих алгоритмов разбора. Проведение анализа разбора для LL(1)- грамматик и LL(k)- грамматик. Основные принципы k- предсказывающего алгоритма разбора. Сущность понятия FIRST(x).

реферат, добавлен 24.10.2011

Характеристика процесса конструирования модели синтаксического анализа. Описание предметной области. Регулярная грамматика для лексического анализа. КС-грамматика. Нисходящий синтаксический анализатор. Логическое проектирование. Проектирование интерфейса.

курсовая работа, добавлен 04.11.2020

Определение формальных языков при помощи регулярных выражений. Рассмотрение контекстно-свободных грамматик для регулярных языков и метода грамматического разбора сверху-вниз. Алгоритм работы таблично-управляемого анализатора для LL(1)-грамматики.

шпаргалка, добавлен 09.01.2014

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

курсовая работа, добавлен 03.01.2015

Синтаксический разбор текста по заданной грамматике с построением дерева разбора. Назначение таблицы идентификаторов. Метод упорядоченного списка. Назначение лексического анализатора. Процесс программирования работы недетерминированного МП-автомата.

контрольная работа, добавлен 12.01.2014

Определения компилятора и интерпретатора. Последовательность обработки при компиляции и место компилятора. Фазы компиляции и инструменты для создания компиляторов. Компилятор Java: исходная программа, входные данные. Лексический и синтаксический анализ.

Лекции по конструированию компиляторов

Название: Лексический и синтаксический анализатор языка высокого уровня
Раздел: Рефераты по информатике
Тип: курсовая работа Добавлен 23:48:55 08 декабря 2010 Похожие работы
Просмотров: 565 Комментариев: 11 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно Скачать
Название Лекции по конструированию компиляторов
страница 1/11
Дата 21.12.2012
Размер 2.15 Mb.
Тип Книга

Предлагаемая вниманию читателя книга основана на курсе лекций,

прочитанных автором на факультете вычислительной математики и

кибернетики Московского государственного университета в 1991-

1993 гг. Автор надеется, что издание книги восполнит

существенный пробел в литературе на руссом языке по разработке

Содержание книги представляет собой «классические» разделы

предмета: лексический и синтаксический анализ, организация

памяти, генерация кода. Сделана попытка на протяжении всего

изложения провести единую «атрибутную» точку зрения на процесс

разработки компилятора. В книге не затрагиваются чрезвычайно

важные вопросы глобальной оптимизации и разработки

компиляторов для машин с параллельной архитектурой. Автор

надеется восполнить эти пробелы в будущем.

Книга будет полезной как студентам и аспирантам

программистских специальностей, так и профессионалам в этих

Глава 1. Введение 6

1.1. Место компилятора в программном обеспечении 6

1.2. Структура компилятора 7

Глава 2. Лексический анализ 11

2.1. Регулярные множества и регулярные выражения 13

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

2.3. Построение детерминированного конечного

автомата по регулярному выражению 17

2.4. Построение детерминированного конечного

автомата с минимальным числом состояний 20

2.5. Программирование лексических анализаторов 22

2.6. Конструктор лексических анализаторов LEX 27

Глава 3. Синтаксический анализ 31

3.1. Основные понятия и определения 31

3.2. Таблично-управляемый предсказывающий разбор 33

3.2.1. Алгоритм разбора сверху-вниз 33

3.2.2. Множества FIRST и FOLLOW 37

3.2.3. Конструирование таблиц

предсказывающего анализатора 39

3.2.4. LL(1)-грамматики 40

3.2.5. Удаление левой рекурсии 41

3.2.6. Левая факторизация 43

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

3.2.8. Диаграммы переходов для рекурсивного спуска 46

3.2.9. Восстановление после синтаксических ошибок 48

3.3. Разбор снизу-вверх типа сдвиг-свертка 49

3.3.2. LR(k)-анализаторы 51

3.3.3. LR грамматики 56

3.3.4. Конфликты разбора типа сдвиг-свертка 62

3.3.5. Восстановление после синтаксических ошибок 63

Глава 4. Промежуточные представления программы 64

4.1. Представление в виде ориентированного графа 64

4.2. Трехадресный код 64

4.3. Линеаризованные представления 69

4.4. Организация информации в генераторе кода 72

4.5. Уровень промежуточного представления 73

Глава 5. Элементы теории перевода 74

5.1. Преобразователи с магазинной памятью 74

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

5.3. Атрибутные грамматики 79


5.3.1. Определение атрибутных грамматик 79

5.3.2. Атрибутированное дерево разбора 80

5.3.3. Язык описания атрибутных грамматик 81

Глава 6. Контекстные условия языков программирования 85

6.1. Описание областей видимости и блочной структуры 85

6.2. Структура среды Модулы-2 86

6.3. Занесение в среду и поиск объектов 90

Глава 7. Организация таблиц символов компилятора 98

7.1. Таблицы идентификаторов и таблицы символов 98

7.2. Таблицы идентификаторов 99

7.3. Таблицы символов и таблицы расстановки 102

7.4. Функции расстановки 103

7.5. Таблицы на деревьях 104

7.6. Реализация блочной структуры 108

7.7. Сравнение различных методов реализации таблиц 109

Глава 8. Генерация кода 110

8.1. Модель машины 110

8.2. Динамическая организация памяти 113

8.3. Назначение адресов 122

8.4. Трансляция переменных 124

8.5. Трансляция целых выражений 130

8.6. Распределение регистров при вычислении

арифметических выражений 132

8.7. Трансляция логических выражений 143

8.8. Выделение общих подвыражений 151

8.9. Генерация оптимального кода методами

синтаксического анализа 155

8.9.1. Сопоставление образцов 155

8.9.2. Синтаксический анализ для Т-грамматик 158

8.9.3. Выбор дерева вывода наименьшей стоимости 165

Глава 9. Системы автоматизации построения трансляторов 169

9.1. Система Супер 169

9.2. Система Yacc 172

Глава 1. Введение

1.1. Место компилятора в программном обеспечении

Компиляторы составляют существенную часть программного

обеспечения ЭВМ. Это связано с тем, что языки высокого уровня

стали основным средством разработки программ. Только очень

незначительная часть программного обеспечения, требующая

особой эффективности, программируется с помощью ассемблеров. В

настоящее время распространено довольно много языков

программирования. Наряду с традиционными языками, такими, как

Фортран, широкое распространение получили так называемые

«универсальные языки» (Паскаль, Си, Модула-2, Ада и другие), а

также некоторые специализированные (например, язык обработки

списочных структур Лисп). Кроме того, большое распространение

получили языки, связанные с узкими предметными областями,

такие, как входные языки пакетов прикладных программ.

Для некоторых языков имеется довольно много реализаций.

Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа

IBM/PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых

компиляторах связана с бурным развитием архитектур ЭВМ. Это

развитие идет по различным направлениям. Совершенствуются

старые архитектуры как в концептуальном отношении, так и по

отдельным, конкретным линиям. Это можно проиллюстрировать на

примере микропроцессора Intel-80X86. Последовательные версии

этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586

отличаются не только техническими характеристиками, но и, что

более важно, новыми возможностями и, значит, изменением

(расширением) системы команд. Естественно, это требует новых

компиляторов (или модификации старых). То же можно сказать о

микропроцессорах Motorola 68010, 68020, 68030, 68040.

В рамках традиционных последовательных машин возникает

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

могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как

Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин

с RISC-архитектурами. Естественно, для каждой новой системы

команд требуется полный набор новых компиляторов с

Наконец, бурно развиваются различные параллельные

архитектуры. Среди них отметим векторные, многопроцессорные, с

широким командным словом (вариантом которых являются

суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с

параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и

другие), через рабочие станции (например, IBM/RS-6000) и

кончая персональными (например, на основе микропроцессора I-

860). Естественно, для каждой из машин создаются новые

компиляторы для многих языков программирования. Здесь

необходимо также отметить, что новые архитектуры требуют

разработки совершенно новых подходов к созданию компиляторов,

так что наряду с собственно разработкой компиляторов ведется и

большая научная работа по созданию новых методов трансляции.

1.2. Структура компилятора

Обобщенная структура компилятора и основные фазы компиляции

показаны на рис. 1.1.

На фазе лексического анализа (ЛА) входная программа,

представляющая собой поток символов, разбивается на лексемы —

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

формализмом, лежащим в основе реализации лексических

анализаторов, являются конечные автоматы и регулярные

выражения. Лексический анализатор может работать в двух

основных режимах: либо как подпрограмма, вызываемая

синтаксическим анализатором за очередной лексемой, либо как

полный проход, результатом которого является файл лексем.

В процессе выделения лексем ЛА может как самостоятельно

строить таблицы имен и констант, так и выдавать значения для

каждой лексемы при очередном обращении к нему. В этом случае

таблица имен строится в последующих фазах (например, в

процессе синтаксического анализа).

Вход | анализ | +————-+ || Поток лексем +||

| Конечные | || и констант || |

| анализ | +————-+ || Дерево разбора ||

| Контекстно-сво- | || имен и констант|||

| Атрибутные | || + таблица символов || |

| промежуточного | || Промежуточная форма ||

| представления | || (префиксная, пост- ||

| Потоковый | || (ориентированный граф)|| |

| Таблицы решений, | || Объектный ||

На этапе ЛА обнаруживаются некоторые (простейшие) ошибки

(недопустимые символы, неправильная запись чисел,

идентификаторов и др.).

Основная задача синтаксического анализа — разбор структуры

программы. Как правило, под структурой понимается дерево,

соответствующее разбору в контекстно-свободной грамматике

языка. В настоящее время чаще всего используется либо LL(1)-

анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ

и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный


спуск чаще используется при ручном программировании

синтаксического анализатора, LR(1) — при использовании систем

автоматизации построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое

дерево со ссылками на таблицу имен. В процессе синтаксического

анализа также обнаруживаются ошибки, связанные со структурой

На этапе контекстного анализа выявляются зависимости между

частями программы, которые не могут быть описаны контекстно-

свободным синтаксисом. Это в основном связи «описание-

использование», в частности анализ типов объектов, анализ

областей видимости, соответствие параметров, метки и другие. В

процессе контекстного анализа строится таблица символов,

которую можно рассматривать как таблицу имен, пополненную

информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном

анализе, являются атрибутные грамматики. Результатом работы

фазы контекстного анализа является атрибутированное дерево

программы. Информация об объектах может быть как

рассредоточена в самом дереве, так и сосредоточена в отдельных

таблицах символов. В процессе контекстного анализа также могут

быть обнаружены ошибки, связанные с неправильным

Затем программа может быть переведена во внутреннее

представление. Это делается для целей оптимизации и/или

удобства генерации кода. Еще одной целью преобразования

программы во внутреннее представление является желание иметь

переносимый компилятор. Тогда только последняя фаза (генерация

кода) является машинно-зависимой. В качестве внутреннего

представления может использоваться префиксная или постфиксная

запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно

делят на машинно-зависимые и машинно-независимые, локальные и

глобальные. Часть машинно-зависимой оптимизации выполняется на

фазе генерации кода. Глобальная оптимизация пытается принять

во внимание структуру всей программы, локальная — только

небольших ее фрагментов. Глобальная оптимизация основывается

на глобальном потоковом анализе, который выполняется на графе

программы и представляет по существу преобразование этого

графа. При этом могут учитываться такие свойства программы,

как межпроцедурный анализ, межмодульный анализ, анализ

областей жизни переменных и т.д.

Наконец, генерация кода — последняя фаза трансляции.

Результатом ее является либо ассемблерный модуль, либо

объектный (или загрузочный) модуль. В процессе генерации кода

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

распределение регистров, выбор длинных или коротких переходов,

учет стоимости команд при выборе конкретной последовательности

команд. Для генерации кода разработаны различные методы, такие

как таблицы решений, сопоставление образцов, включающее

динамическое программирование, различные синтаксические

Конечно, те или иные фазы транслятора могут либо

отсутствовать совсем, либо объединяться. В простейшем случае

однопроходного транслятора нет явной фазы генерации

промежуточного представления и оптимизации, остальные фазы

объединены в одну, причем нет и явно построенного

Лекции по конструированию компиляторов глава 3 синтаксический анализ

| Таблицы решений, | || Объектный ||

На этапе ЛА обнаруживаются некоторые (простейшие) ошибки

идентификаторов и др.).

Основная задача синтаксического анализа — разбор структуры

программы. Как правило, под структурой понимается дерево,

соответствующее разбору в контекстно-свободной грамматике

языка. В настоящее время чаще всего используется либо LL(1)-

анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ

и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный

спуск чаще используется при ручном программировании

синтаксического анализатора, LR(1) — при использовании систем

автоматизации построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое

дерево со ссылками на таблицу имен. В процессе синтаксического

анализа также обнаруживаются ошибки, связанные со структурой

На этапе контекстного анализа выявляются зависимости между

частями программы, которые не могут быть описаны контекстно-

свободным синтаксисом. Это в основном связи «описание-

использование», в частности анализ типов объектов, анализ

областей видимости, соответствие параметров, метки и другие. В

процессе контекстного анализа строится таблица символов,

которую можно рассматривать как таблицу имен, пополненную

информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном

анализе, являются атрибутные грамматики. Результатом работы

фазы контекстного анализа является атрибутированное дерево

программы. Информация об объектах может быть как

рассредоточена в самом дереве, так и сосредоточена в отдельных

таблицах символов. В процессе контекстного анализа также могут

быть обнаружены ошибки, связанные с неправильным

Затем программа может быть переведена во внутреннее

представление. Это делается для целей оптимизации и/или

удобства генерации кода. Еще одной целью преобразования

программы во внутреннее представление является желание иметь

переносимый компилятор. Тогда только последняя фаза (генерация

кода) является машинно-зависимой. В качестве внутреннего

представления может использоваться префиксная или постфиксная

запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно

делят на машинно-зависимые и машинно-независимые, локальные и

глобальные. Часть машинно-зависимой оптимизации выполняется на

фазе генерации кода. Глобальная оптимизация пытается принять

во внимание структуру всей программы, локальная — только

небольших ее фрагментов. Глобальная оптимизация основывается

на глобальном потоковом анализе, который выполняется на графе

программы и представляет по существу преобразование этого

графа. При этом могут учитываться такие свойства программы,

как межпроцедурный анализ, межмодульный анализ, анализ

областей жизни переменных и т.д.

Наконец, генерация кода — последняя фаза трансляции.

Результатом ее является либо ассемблерный модуль, либо

объектный (или загрузочный) модуль. В процессе генерации кода

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

распределение регистров, выбор длинных или коротких переходов,

учет стоимости команд при выборе конкретной последовательности

команд. Для генерации кода разработаны различные методы, такие

как таблицы решений, сопоставление образцов, включающее

динамическое программирование, различные синтаксические

Конечно, те или иные фазы транслятора могут либо

отсутствовать совсем, либо объединяться. В простейшем случае

однопроходного транслятора нет явной фазы генерации

промежуточного представления и оптимизации, остальные фазы

объединены в одну, причем нет и явно построенного


Лекции по конструированию компиляторов

Назва Лекции по конструированию компиляторов
старонка 1/11
Дата канвертавання 26.11.2012
Памер 2.15 Mb.
Тып Книга
В.А.Серебряков

Предлагаемая вниманию читателя книга основана на курсе лекций,

прочитанных автором на факультете вычислительной математики и

кибернетики Московского государственного университета в 1991-

1993 гг. Автор надеется, что издание книги восполнит

существенный пробел в литературе на руссом языке по разработке

Содержание книги представляет собой «классические» разделы

предмета: лексический и синтаксический анализ, организация

памяти, генерация кода. Сделана попытка на протяжении всего

изложения провести единую «атрибутную» точку зрения на процесс

разработки компилятора. В книге не затрагиваются чрезвычайно

важные вопросы глобальной оптимизации и разработки

компиляторов для машин с параллельной архитектурой. Автор

надеется восполнить эти пробелы в будущем.

Книга будет полезной как студентам и аспирантам

программистских специальностей, так и профессионалам в этих

Глава 1. Введение 6

1.1. Место компилятора в программном обеспечении 6

1.2. Структура компилятора 7

Глава 2. Лексический анализ 11

2.1. Регулярные множества и регулярные выражения 13

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

2.3. Построение детерминированного конечного

автомата по регулярному выражению 17

2.4. Построение детерминированного конечного

автомата с минимальным числом состояний 20

2.5. Программирование лексических анализаторов 22

2.6. Конструктор лексических анализаторов LEX 27

Глава 3. Синтаксический анализ 31

3.1. Основные понятия и определения 31

3.2. Таблично-управляемый предсказывающий разбор 33

3.2.1. Алгоритм разбора сверху-вниз 33

3.2.2. Множества FIRST и FOLLOW 37

3.2.3. Конструирование таблиц

предсказывающего анализатора 39

3.2.4. LL(1)-грамматики 40

3.2.5. Удаление левой рекурсии 41

3.2.6. Левая факторизация 43

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

3.2.8. Диаграммы переходов для рекурсивного спуска 46

3.2.9. Восстановление после синтаксических ошибок 48

3.3. Разбор снизу-вверх типа сдвиг-свертка 49

3.3.2. LR(k)-анализаторы 51

3.3.3. LR грамматики 56

3.3.4. Конфликты разбора типа сдвиг-свертка 62

3.3.5. Восстановление после синтаксических ошибок 63

Глава 4. Промежуточные представления программы 64

4.1. Представление в виде ориентированного графа 64

4.2. Трехадресный код 64

4.3. Линеаризованные представления 69

4.4. Организация информации в генераторе кода 72

4.5. Уровень промежуточного представления 73

Глава 5. Элементы теории перевода 74

5.1. Преобразователи с магазинной памятью 74

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

5.3. Атрибутные грамматики 79

5.3.1. Определение атрибутных грамматик 79

5.3.2. Атрибутированное дерево разбора 80

5.3.3. Язык описания атрибутных грамматик 81

Глава 6. Контекстные условия языков программирования 85

6.1. Описание областей видимости и блочной структуры 85

6.2. Структура среды Модулы-2 86

6.3. Занесение в среду и поиск объектов 90

Глава 7. Организация таблиц символов компилятора 98

7.1. Таблицы идентификаторов и таблицы символов 98

7.2. Таблицы идентификаторов 99

7.3. Таблицы символов и таблицы расстановки 102

7.4. Функции расстановки 103

7.5. Таблицы на деревьях 104

7.6. Реализация блочной структуры 108

7.7. Сравнение различных методов реализации таблиц 109

Глава 8. Генерация кода 110

8.1. Модель машины 110

8.2. Динамическая организация памяти 113

8.3. Назначение адресов 122

8.4. Трансляция переменных 124

8.5. Трансляция целых выражений 130

8.6. Распределение регистров при вычислении

арифметических выражений 132

8.7. Трансляция логических выражений 143

8.8. Выделение общих подвыражений 151

8.9. Генерация оптимального кода методами

синтаксического анализа 155

8.9.1. Сопоставление образцов 155

8.9.2. Синтаксический анализ для Т-грамматик 158

8.9.3. Выбор дерева вывода наименьшей стоимости 165

Глава 9. Системы автоматизации построения трансляторов 169

9.1. Система Супер 169

9.2. Система Yacc 172

Глава 1. Введение

1.1. Место компилятора в программном обеспечении

Компиляторы составляют существенную часть программного

обеспечения ЭВМ. Это связано с тем, что языки высокого уровня

стали основным средством разработки программ. Только очень

незначительная часть программного обеспечения, требующая

особой эффективности, программируется с помощью ассемблеров. В

настоящее время распространено довольно много языков

программирования. Наряду с традиционными языками, такими, как

Фортран, широкое распространение получили так называемые

«универсальные языки» (Паскаль, Си, Модула-2, Ада и другие), а

также некоторые специализированные (например, язык обработки

списочных структур Лисп). Кроме того, большое распространение

получили языки, связанные с узкими предметными областями,

такие, как входные языки пакетов прикладных программ.

Для некоторых языков имеется довольно много реализаций.

Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа

IBM/PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых

компиляторах связана с бурным развитием архитектур ЭВМ. Это

развитие идет по различным направлениям. Совершенствуются

старые архитектуры как в концептуальном отношении, так и по

отдельным, конкретным линиям. Это можно проиллюстрировать на

примере микропроцессора Intel-80X86. Последовательные версии

этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586

отличаются не только техническими характеристиками, но и, что


более важно, новыми возможностями и, значит, изменением

(расширением) системы команд. Естественно, это требует новых

компиляторов (или модификации старых). То же можно сказать о

микропроцессорах Motorola 68010, 68020, 68030, 68040.

В рамках традиционных последовательных машин возникает

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

могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как

Intel, Motorola, Sun, DEC, начинают переходить на выпуск машин

с RISC-архитектурами. Естественно, для каждой новой системы

команд требуется полный набор новых компиляторов с

Наконец, бурно развиваются различные параллельные

архитектуры. Среди них отметим векторные, многопроцессорные, с

широким командным словом (вариантом которых являются

суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с

параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и

другие), через рабочие станции (например, IBM/RS-6000) и

кончая персональными (например, на основе микропроцессора I-

860). Естественно, для каждой из машин создаются новые

компиляторы для многих языков программирования. Здесь

необходимо также отметить, что новые архитектуры требуют

разработки совершенно новых подходов к созданию компиляторов,

так что наряду с собственно разработкой компиляторов ведется и

большая научная работа по созданию новых методов трансляции.

1.2. Структура компилятора

Обобщенная структура компилятора и основные фазы компиляции

показаны на рис. 1.1.

На фазе лексического анализа (ЛА) входная программа,

представляющая собой поток символов, разбивается на лексемы —

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

формализмом, лежащим в основе реализации лексических

анализаторов, являются конечные автоматы и регулярные

выражения. Лексический анализатор может работать в двух

основных режимах: либо как подпрограмма, вызываемая

синтаксическим анализатором за очередной лексемой, либо как

полный проход, результатом которого является файл лексем.

В процессе выделения лексем ЛА может как самостоятельно

строить таблицы имен и констант, так и выдавать значения для

каждой лексемы при очередном обращении к нему. В этом случае

таблица имен строится в последующих фазах (например, в

процессе синтаксического анализа).

Вход | анализ | +————-+ || Поток лексем +||

| Конечные | || и констант || |

| анализ | +————-+ || Дерево разбора ||

| Контекстно-сво- | || имен и констант|||

| Атрибутные | || + таблица символов || |

| промежуточного | || Промежуточная форма ||

| представления | || (префиксная, пост- ||

| Потоковый | || (ориентированный граф)|| |

| Таблицы решений, | || Объектный ||

На этапе ЛА обнаруживаются некоторые (простейшие) ошибки

(недопустимые символы, неправильная запись чисел,

идентификаторов и др.).

Основная задача синтаксического анализа — разбор структуры

программы. Как правило, под структурой понимается дерево,

соответствующее разбору в контекстно-свободной грамматике

языка. В настоящее время чаще всего используется либо LL(1)-

анализ (и его вариант — рекурсивный спуск), либо LR(1)-анализ

и его варианты (LR(0), SLR(1), LALR(1) и другие). Рекурсивный

спуск чаще используется при ручном программировании

синтаксического анализатора, LR(1) — при использовании систем

автоматизации построения синтаксических анализаторов.

Результатом синтаксического анализа является синтаксическое

дерево со ссылками на таблицу имен. В процессе синтаксического

анализа также обнаруживаются ошибки, связанные со структурой

На этапе контекстного анализа выявляются зависимости между

частями программы, которые не могут быть описаны контекстно-

свободным синтаксисом. Это в основном связи «описание-

использование», в частности анализ типов объектов, анализ

областей видимости, соответствие параметров, метки и другие. В

процессе контекстного анализа строится таблица символов,

которую можно рассматривать как таблицу имен, пополненную

информацией об описаниях (свойствах) объектов.

Основным формализмом, использующимся при контекстном

анализе, являются атрибутные грамматики. Результатом работы

фазы контекстного анализа является атрибутированное дерево

программы. Информация об объектах может быть как

рассредоточена в самом дереве, так и сосредоточена в отдельных

таблицах символов. В процессе контекстного анализа также могут

быть обнаружены ошибки, связанные с неправильным

Затем программа может быть переведена во внутреннее

представление. Это делается для целей оптимизации и/или

удобства генерации кода. Еще одной целью преобразования

программы во внутреннее представление является желание иметь

переносимый компилятор. Тогда только последняя фаза (генерация

кода) является машинно-зависимой. В качестве внутреннего

представления может использоваться префиксная или постфиксная

запись, ориентированный граф, тройки, четверки и другие.

Фаз оптимизации может быть несколько. Оптимизации обычно

делят на машинно-зависимые и машинно-независимые, локальные и

глобальные. Часть машинно-зависимой оптимизации выполняется на

фазе генерации кода. Глобальная оптимизация пытается принять

во внимание структуру всей программы, локальная — только

небольших ее фрагментов. Глобальная оптимизация основывается

на глобальном потоковом анализе, который выполняется на графе

программы и представляет по существу преобразование этого

графа. При этом могут учитываться такие свойства программы,

как межпроцедурный анализ, межмодульный анализ, анализ

областей жизни переменных и т.д.

Наконец, генерация кода — последняя фаза трансляции.

Результатом ее является либо ассемблерный модуль, либо

объектный (или загрузочный) модуль. В процессе генерации кода

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

распределение регистров, выбор длинных или коротких переходов,

учет стоимости команд при выборе конкретной последовательности

команд. Для генерации кода разработаны различные методы, такие

как таблицы решений, сопоставление образцов, включающее

динамическое программирование, различные синтаксические

Конечно, те или иные фазы транслятора могут либо

отсутствовать совсем, либо объединяться. В простейшем случае

однопроходного транслятора нет явной фазы генерации

промежуточного представления и оптимизации, остальные фазы

объединены в одну, причем нет и явно построенного

Автоматизированный практикум по методам конструирования компиляторов Андреев, Олег Юрьевич

Данная диссертационная работа должна поступить в библиотеки в ближайшее время
Уведомить о поступлении

480 руб. | 150 грн. | 7,5 долл. ‘, MOUSEOFF, FGCOLOR, ‘#FFFFCC’,BGCOLOR, ‘#393939’);» onMouseOut=»return nd();»> Диссертация, — 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат — бесплатно , доставка 10 минут , круглосуточно, без выходных и праздников

Андреев, Олег Юрьевич. Автоматизированный практикум по методам конструирования компиляторов : автореферат дис. . кандидата технических наук : 05.13.11.- Ленинград, 1991.- 14 с.: ил.

Введение к работе

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

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

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

Целью настоящей работы является создание лабораторного практикума по методам конструирования компиляторов (ШКК), основывающе на разработанном в настоящей диссертации базовом компиляторе (БК), являщимся основным конструктивом, с-помощью и на базе которого пользователь ыо

ет конструировать из фрагментов задач функционирующую ііглюстрпрованкуіо комішліфующую систему. Тем самым у пользователя вырабатывается практический навык написания компиляторов, он становится готов к самостоятельной реализации .компиляторов.

В соответствии с поставленной целью в работе решаются следую
щие задачи: ,

— создание базового компилятора практикума, в котором все

Разы выполнены в виде отдельных задач, весь процесс ноі.ішиїягппі иллюстрируется и имеется воз:точность замены отдельных модулей на аналог::чные, написанные пользователем самостоятельно ;

разработка .нового подхода к составлению атрибутных грамматик, позволяющего быстрее обучить пользователя работе по составлению АГ ;

разработка простого :: универсального по отнопенпэ к исходному и объектному языкам компилятора языка внутреннего представле-ніїя ;

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

е методы автоматической генерации кода.

В соответствии с поставленной целью з работе решены следующие задачи:

предложен ковки подход к разработке атрибутных грамматик, при котором схег.іа обхода НСД планируется на начальном этапе разработки АГ, а не вычисляется как свойство j

e имеющейся грамматики ;

разработан просто:; :: универсальный по отношению к исходному и объектному языкам компилятора язык внутреннего представления программ для генерации кода, где универсальность достигается возможностью замены основных конструкций языка и/или их семантики;

реализована методика активного обучения конструированию компиляторов, заключающаяся в 33. 6110 отдельных составляющих модулей иллюстрированного базового компилятора программами, написанными пользователем ;

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

Практическая ценность работы заключается:

— в пэвызнпп интенсивности и качества обучения конструирова
нию компиляторов ;

Е прпобретек:і:: навыков для дальнейпеп самостоятельной работы по проектированию і: реализации транслирующих систем ;

в возможности использования ЕХ для отладки грагммгтцк и д; опробацпн ілєтодое нейтрализации ошибок при разработке промышленных компиляторов.

Ьнедрение результатов работы

Практикум по методам конструирования компиляторов (2.3К) ::_ шел апробацию в HIE математики Ленинградского государственного университета, используется в разработках предприятия «1-!нйоГ«Ьгр». Практиігум используется для обучения в Таганрогском радио-техлипч коїл институте и на механико-математическом г.аіультете І.Ьсковсно: государственного университета.

Работа догладывалась на республиканском совещании-сеї.ікнгре «Использование 5ЕЛ з учебкой п научно-исследовательской работе студентов», ігооходиееєм в І988году в Новосибирске.

Объем п структура работы

Диссертация включает в себя 5 глав с приложениями и состой из ІЇ4 страниц текста. Первая глава — вводная. Излагается поста ка задачи, производится обзор существующий программ для обуче;и: комп::дяц::п. Іторая глава посвящена лексическому и синтаксические анализу. Обосновывается выбор использованный в ILIUK глетодов, ог сывактся архитектура и возможности пользователя. Б третье:’: глаї описывается семантический анализ е ILECK, вводится понятие дина:’ ческого подхода і: проектированию атрибутных грамматик. Четверта глава посвящена генерации кода е ЕК, вводится универсальный язі внутреннего представления программ. Б пятой главе рассказываете о возможностях пользователя при работе с ILI3.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL