Языки и грамматики простейший компилятор


Содержание

ГРАММАТИКА ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

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

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

: : = AaBbCcDdEeFf и т.д.

:: = begin end if then else for next и т.д.

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

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

Все операторы языка в тексте программы отделяются друг от друга явными или неявными разделителями, например:

Операторы выполняются в порядке их следования в тексте программы. Лишь с помощью операторов перехода этот естественный порядок может быть нарушен.

Большая часть операторов ведет обработку величин.Величины могут бытьпостоянными и переменными. Значения постоянных величин не изменяются в ходе выполнения программы. Величина характеризуетсятипом, именем и значением.Наиболее распространенные типы величин — числовые (целые и вещественные), символьные, логические. Тип величины определяется ее значением.

Другая важная классификация величин — простые и структурированные. Простая величина в каждый момент может иметь не более одного значения. Ей соответствует одна ячейка памяти (поскольку термин «ячейка» несколько устарел, часто говорят «машинное слово») или ее эквивалент во внешней памяти компьютера. Структурированная величина, имея одно имя, может иметь разом несколько значений. Эти значения представляют собой элементы (компоненты) величины. Самый широкоизвестный пример — массив, у которого элементы различаются по индексам (номерам). Вопрос о структурировании величин — входных, выходных и промежуточных — для успеха решения прикладной задачи не менее важен, чем вопрос о правильном написании последовательности операторов.

Важнейшие характеристики структурированной величины таковы: упорядоченность (да или нет), однородность (да или нет), способ доступа к элементам, фиксированность числа элементов (да или нет). Так, массив является упорядоченной однородной структурой с прямым доступом к элементам и фиксированным их количеством.

Всем программным объектам в языках даются индивидуальныеимена. Имя программного объекта называют идентификатором (от слова «идентифицировать»). Чаще всего идентификатором является любая конечная последовательность букв к цифр, начинающаяся с буквы:

Как правило, в большинстве языков программированияв качестве идентификатора запрещается использовать служебные слова языка.

Многим слово «идентификатор» не нравится, и в настоящее время чаще употребляют слово «имя», поскольку

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

Summa, Time, i, j, integral, init и т. п.

Некоторым идентификаторам заранее предписан определенный смысл и их называют стантартными, например, Sin — это имя известной математической функции.

Описания или объявления программных объектов связаны с правилами обработки данных. Данные бывают разные и необходимо для каждого из них определить его свойства. Например, если в качестве данных выступает массив, то необходимо задать его размерность, границы индексов, тип элементов массива. Описательная часть языка программирования является необходимой как для системных программистов — разработчиков трансляторов, которые должны, в частности, проводить синтаксическую и семантическую диагностику программ, — так и для «прикладного» программиста, которому объявления программныхобъектов частооблегчают процесс разработки и отладки программ.

В некоторых языках стандартные описания простых числовых и символьных данных опускают (описания по умолчанию), или в них задаются правила описания по имени объекта. Например, в Фортране переменные, имена которых начинаются с букв I, J, К, L, M, N, могут принимать целые значения (при отсутствии явного описания типа, которое возможно), т.е. определены как числовые данные целого типа. В Бейсике-MSX данные строкового типа присваиваются переменным, имена которых заканчиваются специальным символом $: A$, S1$.

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

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

Переменные играют важнейшую роль в системах программирования. Понятие «переменная» в языках программирования отличается от общепринятого в математике. Переменная — это программный объект, способный принимать некоторое значение с помощью оператора присваивания. В ходе выполнения программы значения переменной могут неоднократно изменяться. Каждая переменная после ее описания отождествляется с некоторой ячейкой памяти, содержимое которой является ее значением. Синтаксис переменной, точнее, ее идентификатора, как правило, имеет вид:

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

Функция — это программный объект, задающий вычислительную процедуру определения значения, зависимого от некоторых аргументов. Вводится в языки программирования для задания программистом необходимых ему функциональных зависимостей. В каждом языке высокого уровня имеется в наличии библиотека стандартных функций: арифметических, логических, символьных, файловых и т.п. Функции -стандартные и задаваемые программистом — используются в программе в выражениях.

Выражения строятся из величин — постоянных и переменных, функций, скобок. знаков операций и т.д. Выражение имеет определенный тип, определяемый типом принимаемых в итоге его вычисления значений. Возможны выражения арифметические, принимающие числовые значения, логические, символьные, строковые и т.д. Выражение 5+7 является, несомненно, арифметическим, выражение А + В может иметь cамый разный смысл — в зависимости от того, что стоит за идентификаторами А и В.

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

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

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

Заголовок необходим для ссылок на модуль.

Интерфейс содержит объявления, включая процедуры и функции.

Раздел «реализация» содержит тела процедур и функций, перечисленных в интерфейсной части.

Раздел «инициализация»содержит операторы, необходимые для инициализации модуля.

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

Контрольные вопросы и задания

1. Какие преимущества имеют языки программирования высокого уровняпосравнению с машинно-ориентированными языками?

2. Каковы основные составляющие языка программирования высокого уровня?

3. В чем различия понятий языков программирования от аналогичных понятий математического «языка»?

4. С какой целью используются и что представляют собой металингвистические формулы Бэкуса-Наура?

5. Что представляет собой синтаксическая диаграмма Вирта?

6. В чем различие между постоянными и переменными величинами? Чем характеризуется величина?

7. В чем принципиальная разница между величинами простыми и структурированными?

8. Для чего служит описание величин в программах?

9. В чем состоит назначение функций? процедур? модулей?

§3. ПАСКАЛЬ КАК ЯЗЫК
СТРУКТУРНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8808 — | 7524 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Трансляция, компиляция и интерпретация

Программа  это последовательность инструкций, предназначенных для выполнения компьютером. В настоящее время программы оформляются в виде текста, который записывается в файлы. Этот текст является результатом деятельности программиста и, несмотря на специфику формального языка, остаётся программой для программиста.

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

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

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

Транслятор обычно выполняет также диагностику ошибок, формирует словари идентификаторов, выдаёт для печати тексты программы и т.д.

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

Язык, на котором представлена входная программа, называется исходным языком, а сама программа  исходным кодом. Выходной язык называется целевым языком или объектным кодом.

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

Адресный. Функциональное устройство, преобразующее виртуальный адрес (англ. Virtual address) в реальный адрес (англ. Memory address).

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

Многопроходной. Формирует объектный модуль за несколько просмотров исходной программы.

Обратный. То же, что детранслятор. См. также: декомпилятор, дизассемблер.

Однопроходной. Формирует объектный модуль за один последовательный просмотр исходной программы.

Оптимизирующий. Выполняет оптимизацию кода в создаваемом объектном модуле.

Синтаксически-ориентированный (синтаксически-управляемый). Получает на вход описание синтаксиса и семантики языка и текст на описанном языке, который и транслируется в соответствии с заданным описанием.

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

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

Компиля́тор (англ. compiler  составитель, собиратель) транслятор, выполняющий преобразование программы, составленной на исходном языке, вобъектный модуль. Программа, переводящая текст программы наязыке высокого уровня, в эквивалентную программу намашинном языке.

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

Компиляция трансляция программы, составленной на исходном языке, в объектный модуль. Осуществляется компилятором.

Компилировать проводить трансляцию машинной программы с проблемно-ориентированного языка на машинно-ориентированный язык.

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

Интерпретатор (англ. interpreter  истолкователь, устный переводчик) переводит и выполняет программу строка за строкой. Интерпретатор берёт очередной оператор языка из текста программы, анализирует его структуру и затем сразу исполняет (обычно после анализа оператор транслируется в некоторое промежуточное представление или даже машинный код для более эффективного дальнейшего исполнения). Только после того как текущий оператор успешно выполнен, интерпретатор перейдёт к следующему. При этом если один и тот же оператор будет выполняться в программе многократно, интерпретатор будет выполнять его так как, как будто встретил впервые. Вследствие этого программы, в которых требуется осуществить большой объём вычислений, будут выполняться медленно. Кроме того, для выполнения программы на другом компьютере там тоже должен стоять интерпретатор – ведь без него текст является просто набором символов.

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

Различия между компиляцией и интерпретацией.

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

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

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

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

Практически все языки программирования низкого уровняитретьего поколения, вродеассемблера,СиилиМодулы-2, являются компилируемыми, а болеевысокоуровневые языки, вродеPythonилиSQL, — интерпретируемыми.

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

4. Трансляция и интерпретация  разные процессы: трансляция занимается переводом программ с одного языка на другой, а интерпретация отвечает за исполнение программ. Однако, поскольку целью трансляции как правило является подготовка программы к интерпретации, то эти процессы обычно рассматриваются вместе.

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

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

есть ли простой компилятор для небольшого языка

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

18 ответов

Если вы хотите посмотреть на код, я очень впечатлен с MinCaml компилятора.

Это всего 2000 строк.

он компилирует довольно интересный язык.

Он генерирует реальный машинный код, ни один из этих Намби-памби C или LLVM материал : -)

скорость скомпилированного кода конкурирует с gcc и собственным OCaml компиляторы.

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

Я упоминал, что был очень впечатлен?

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

посмотреть «построим компилятор» для получения дополнительной информации. Обратите внимание, что он не завершен; у него закончился пар, прежде чем он закончил его, но есть много там легко усваиваемая информация.

около 1000 строк кода. Компилирует схему в LLVM ассемблер или в C. Я бы сказал, что это отлично подходит для работы над компиляторами. Если вы хотите пойти глубже, я рекомендую книгу «SICP».

посмотрите на простой компилятор для PL / 0 (небольшое подмножество Паскаля-без параметров, только целочисленные данные). Источник, написанный на Паскале, составляет всего около 500 строк кода и легко следовать. Возможно, это все, что вам нужно посмотреть.

однако, если вы хотите пойти немного дальше, как только вам это понравится, посмотрите на источник Pascal-S. Это компилятор для большего подмножества Pascal, но включает в себя некоторые дополнительные понятия, такие как передача параметров, дополнительные типы данных, массивы и записи (структуры). Тем не менее это всего лишь около 2000 строк кода, и легко следовать, как только вы освоили PL/0.

вы можете найти здесь источники:

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

во-первых, что касается языка:

  1. самым простым является игрушечный язык, например компиляция арифметических выражений.
  2. далее ассемблер-опять же действительно просто переводит, но показывает основы разбора и превращения в op-коды
  3. далее, вероятно, что-то вроде C, что очень близко к чистому ассемблеру, или что-то вроде LISP что очень близко к чистой теории.

далее, выбор компилятора.

вы можете начать с ассемблера-превращения ассемблера в машинный код. Это был первый шаг в производстве компиляторов — я бы предложил для чипа, такого как 6502 или 8080, которые оба очень просты. Что-то вроде комплект для разработки ассемблера может хорошо работать для вас (он поставляется с примерами)

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

почти каждое введение в написание компиляторов на академическом уровне начинается с минимального языка в качестве примера,книга Дракона http://en.wikipedia.org/wiki/Dragon_Book_%28computer_science%29 всегда рекомендуется, но есть и другие хорошие.

в университете я использовал C— который похож на C, но еще проще написать компилятор. Много ресурсов по адресу:http://www.cminusminus.org/qc—.html

Если вам нужен компилятор, и вы знаете такой язык, как Java, я бы предложил что-то вроде JavaCC, где язык указан с помощью грамматик. Есть много примеров грамматик здесь — выбрать что-то простое, как C, чтобы начать.

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

Я рекомендую «книгу дракона»:принципы разработки компилятора, по Ахо и Ульман. Прошло много лет с тех пор, как я его читал, поэтому я не помню точно, какие примеры доступны, но это очень хороший текст.

LISPes (Scheme и т. д.) являются простейшими фактическими языками. Вы можете посмотреть, как построить интерпретатор примитивной схемы в perl с помощью книги (бумажная версия здесь Лулу). Синтаксический анализ, проверка типов аналогичны в интерпретаторах и компиляторах. Тогда вот больше хардкорной книги по теме дизайна компилятора (также доступен как мертвое дерево на Люлю).

в моей бывшей ИТ-школе нам пришлось разработать компилятор на C++, но не с нуля:были шаги, кривая обучения и т. д..

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

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

Google UCSD Pascal. Это был прорыв в 70-х. Может быть, это больше, чем вы хотите, но тогда он был легко портирован на множество «микро» чипов.

Это только 300 строк обычного кода и реализует простой универсальный язык текст ссылки, что-то вроде этого вы искали?

вы можете посмотреть пример калькулятора в веселой книге Бьярне Страуструпа » язык программирования C++».

Если вы хотите что-то более продвинутое, прочитайте исходный код boost::spirit.

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

Как насчет просмотра небольшого компилятора C? C не очень компилируется, и я думаю, что это даст вам некоторое представление о построении компилятора.

Я начал видео-учебник по написанию ANTLR 3.компилятор х — проверьте

Я буду добавлять больше в ближайшее время! — Скотт!—1

Diplom Consult.ru

Транслятор – это программа, кот-ая переводит входную программу на скодном (входном) языке в эквивалентную ей на результирующем (выходном языке)

Компилятор – это транслятор, кот-ый осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на ассемлере.

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

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

Алфавит — это конечное множество символов, которое в дальнейшем будем обозначать V. Предполагается, что термин «символ» имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.

Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита. Далее цепочки символов будем обозначать греческими буквами: ,, , …

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

Более формально цепочка символов в алфавите V определяется следующим образом:

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

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

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

Длиной цепочки называется число составляющих ее символов. Например, если  = abcdefg, то длина  равна 7. Длину цепочки  будем обозначать |  |. Длина  равна 0.

Основной операцией над цепочками символов является операция конкатенации — это дописывание второй цепочки в конец первой, т.е. если  и  — цепочки, то цепочка  называется их конкатенацией. Например, если  = ab и  = cd, то  = abcd. Для любой цепочки  всегда  =  = .

Операция конкатенации не обладает свойством коммутативности, т.е. , но обладает ассоциативностью ()= ().

Обращением (или реверсом) цепочки  называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки  будем обозначать  R.

Например, если  = abcdef, то  R = fedcba. Для пустой цепочки:  =  R .

Для операции обращения справедливо следующее равенство «a,b: (ab) R = b R a R .

N-ой степенью цепочки a (будем обозначать  n ) называется конкатенация n цепочек .  0 = ;  n =  n-1 =  n-1 .

Понятие языка. Формальное определение языка. Методы задания языков

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

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

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

Обозначим через V * множество, содержащее все цепочки в алфавите V, включая пустую цепочку . Например, если V = <0,1>, то V* = <, 0, 1, 00, 11, 01, 10, 000, 001, 011, . >.

Обозначим через V + множество, содержащее все цепочки в алфавите V, исключая пустую цепочку . Следовательно, верно равенство V* = V + <>

Известно несколько различных способов описания языков:

1. Перечислением всех допустимых цепочек языка.

2. Указанием способа порождения цепочек языка (заданием грамматики языка).

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

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

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

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

Синтаксис и семантика языка

Синтаксис языка — это набор правил, определяющий допустимые конструкции языка. Синтаксис определяет «форму языка» — задает набор цепочек символов, которые принадлежат языку. Чаще всего синтаксис языка можно задать в виде строгого набора правил, но полностью это утверждение справедливо только для чисто формальных языков.

Например, строка «3+2» является арифметическим выражением, «3 2 +» — не является.

Семантика языка — это раздел языка, определяющий значение предложений языка. Семантика определяет «содержание языка» — задает значение для всех допустимых цепочек языка.

Например, используя семантику алгебры мы можем сказать, что строка «3+2» есть сумма чисел 3 и 2, а также то, что «3+2 = 5» — это истинное выражение

Илон Маск рекомендует:  Что такое код asp copyhere

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

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

Формально порождающая грамматика G — это четверка G (VT, VN, P, S), где

VT — множество терминальных символов (терминалов),

VN — множество нетерминальных символов (нетерминалов), не пересекающееся с VT,

P — множество правил (продукций) грамматики вида   , где V + , V*,

Sцелевой (начальный) символ грамматики, S  VN.

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

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

Каждое i , i = 1, 2, . ,n , будем называть альтернативой правила вывода из цепочки .

Такую форму записи правил грамматики называют формой Бэкуса-Наура. Она предусматривает также, что все нетерминальные символы берутся в <> скобки.

Грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Например, G1 = (<0,1>, , P1, S) и G2 = (<0,1>, , P2, S)

P1: S  0A1 P2: S  0S1 | 01

эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = <0 n 1 |>0>. Грамматики G1 и G2 называются почти эквивалентными, если L(G1) = L(G2)  <>. Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на .

Например, G1 = (<0,1>, , P1, S) и G2 = (<0,1>, , P2, S)

P1: S  0A1 P2: S  0S1 | 

почти эквивалентны, т.к. L(G1)=<0 n 1 |>0>, а L(G2)=<0 n 1 |>=0>, т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.

Контекстно-свободная грамматика G называется неоднозначной, если существует хотя бы одна цепочка   L(G), для которой может быть построено два или более различных деревьев вывода.

Это утверждение эквивалентно тому, что цепочка  имеет два или более разных левосторонних (или правосторонних) выводов. В противном случае грамматика называется однозначной.

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

Пример неоднозначной грамматики:

В этой грамматике для цепочки if b then if b then a else a можно построить два различных дерева вывода. Однако это не означает, что язык L(G) обязательно неоднозначный. Определенная нами неоднозначность — это свойство грамматики, а не языка, т.е. для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики. Если грамматика используется для определения языка программирования, то она должна быть однозначной.

В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена:

S  if b then S | if b then S’ else S | a

S’  if b then S’ else S’ | a

Проблема, порождает ли данная контекстно-свободная грамматика однозначный язык (т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой

Можно ли написать компилятор в машиный код на языке очень высокого уровня?

Можно ли написать компилятор в машиный код на языке очень высокого уровня?

1. Поверьте человеку, который пишет на Си с 1985 года (30 лет, вроде бы?) — НИКОГДА не пишите на Си ничего, если только к вашему виску не приставили пистолет. Исключение одно — ядро ОС. Да и то.

2. Что угодно можно написать на чём угодно. Вопрос удобства.

3. Писать компилятор надо на языке с развитыми средствами поддержки жизни проекта. Таких два — Java и C#. Можно (а если Вам это комфортно, то и нужно) использовать функциональные расширения соответствующих платформ. Scala/F#.

4. На говноязыках серьёзные вещи писать не нужно. Ключевое свойство говноязыка — обсуждение вокруг него о том, как бедные программеры перетрудились явно прописывать руками типы всех переменных. На таких ЯП можно писать затычки и примочки.

5. Не применяйте генераторы лексических и грамматических анализаторов, пока не научитесь писать компилятор руками. Ключевое слово — парсинг рекурсивным спуском. Это реально просто, если грамматика языка — LR1. Для начала надо взять простой язык. Очень простой.

6. Базовый компилятор с кодогенерацией для стековой машины нужно уметь писать за два дня. Если вы хотите это уметь.

7. Бекэнды (реальную кодогенерацию) писать НЕ НУЖНО. Вообще. Вы её хорошо не напишете ни-ко-гда. Проще генерировать на выходе Си и докомпилировать приличным си-компилятором.

Языки и грамматики простейший компилятор

Грамматика указывает на иерархию между символами в формальном языке. Все тексты, соответствующие правилам языка, соответствуют и его грамматике. Иными словами, грамматика — это набор правил, позволяющих:

  • Из грамматического символа верхнего уровня получить любой текст на языке путём рекурсивного раскрытия абстрактных символов в нечто конкретное
  • Для любого текста проверить, соответствует ли он грамматике языка, то есть можно ли весь текст назвать символом верхнего уровня на этом языке

В большинстве языков символом верхнего уровня является один файл исходного кода, называемый “модулем” или “единицей трансляции”. Например, в языке Python мы можем развернуть абстрактный символ “модуль Python” в список из двух абстрактных (нетерминальных) символов:

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

  • Нетерминальные символы абстрактны, и могут быть развёрнуты далее по правилам грамматики языка. Примеры таких символов: “ветвление”, “функция”, “присваивание”, “модуль программы”.
  • Терминальные символы конкретны, и не могут быть развёрнуты по правилам языка.
  • Правило грамматики задаёт преобразование цепочки символов в новую цепочку символов. В том числе это может быть замена одного символа на пять новых, замена трёх символов на ноль символов и так далее.

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

В промышленных компиляторах парсер (синтаксический анализатор) занимается обратной задачей — сворачивает токены, полученных лексером (лексическим анализатором), согласно правилам грамматики, и получает абстрактные (нетерминальные) символы “функция”, “ветвление”, “определение класса” и так далее. Набор символов языка и правил грамматики зависит от языка.

Иерархия Хомского

Иерархия Хомского — это общепринятое деление формальных языков на 4 уровня. Чем выше номер типа, тем более скудный язык и тем легче его разбирать программно:

  • Тип 0: неограниченные
    • правила замены символов ничем не ограничены, что делает машинный анализ таких текстов невозможным
  • Тип 1: контекстно-зависимые
    • правила замены символов зависят от контекста
    • в этом примере на C++ без контекста неясно, что это — сравнение двух переменных или специализация шаблона: vec b .
    • в этом примере неясно, объявлена ли функция “getSize”: getSize(sprite)
  • Тип 2: контекстно-свободные
    • правила описывают замену одного нетерминала на цепочку нетерминалов и терминалов (возможно, пустую), т.е. способ замены каждого нетерминала на другие символы не зависит от контекста
    • формально: в левой части правила может быть только нетерминал, A → β , где “A” — нетерминал, “β” — цепочка нетерминалов и терминалов
    • например, в языках программирования символ “присваивание” раскрывается однозначно независимо от того, что окружает присваивание
  • Тип 3: регулярные
    • праворегулярные грамматики могут содержать три вида правил: B → α , B → αC , B → ε , где “ε” — пустое множество, “B” и “С” — нетерминалы, и “α” — терминал
    • леворегулярные грамматики могут содержать три вида правил: A → α , A → Bα , A → ε , где “ε” — пустое множество, “A” и “B” — нетерминалы, и “α” — терминальный символ

Все реальные языки программирования являются контекстно-зависимыми (тип 1), но большинство может быть разобрано как контекстно-свободные (тип 2) с последующей постобработкой в виде проверок типов и т.п. Не случайно фронтенд компилятора делят на три стадии:

  • лексический анализ (в рамках регулярной грамматики текст делится на строковые литералы, числа, идентификаторы, операторы, разделители, убираются пробелы и комментарии)
  • синтаксический анализ (в рамках контекстно-свободной грамматики)
  • семантический анализ (проверка соответствия контекстно-зависимым правилам, таким как “переменная должна быть объявлена заранее”)

Регулярные грамматики

Любая регулярная грамматика имеет эквивалентное регулярное выражение, а также эквивалентный детерминированный конечный автомат (ДКА). Это всё три формы одной и той же сущности. Разобрать строку по правилам регулярной грамматики можно за один проход из начала в конец строки без дополнительной памяти с помощью ДКА.

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

  • Символ * задаёт итерацию (a.k.a. замыкание Клини)
    • Пример: “1*” ищет строки “”, “1”, “11”, …
  • Пустая строка задаёт конкатенацию двух выражений
    • Пример: “ab” ищет подстроку “ab”, “ab*” ищет подстроки вида “a”, “ab”, “abb”, …
  • Символ задаёт объединение
    • Пример: “a b c d” ищут подстроки “a”, “b”, “c”, “d”

Применения регулярных грамматик:

  • Регулярные выражения применяют не только для лексического анализа, но и для фильтрации. Утилита grep в Unix-системах с помощью регулярок фильтрует вывод другой команды.

С помощью регулярных выражений удобно проверять введённые пользователем данные. Например, для проверки кода страны в формате “ru_RU”: [A-Za-z] <2>.

Лексические анализаторы производят предварительный разбор текста, превращающий единый массив текстовых символов в массив отдельных слов (в теории компиляции вместо термина «слово» используют термин «токен»). Лексический анализатор можно создать на базе регулярной грамматики, и построить эквивалентный ДКА, что даст фантастически низкую сложность разбора O(N), где N — длина строки.

Контекстно-свободные грамматики

Контекстно-свободная грамматика, не являющаяся регулярной, не имеет ни эквивалентного регулярного выражения, ни эквивалентного детерминированного конечного автомата. При попытке сформировать ДКА количество его состояний будет расти бесконечно, и так же бесконечно будет возрастать глубина регулярного выражения. В контекстно-свободной грамматике правила для нетерминалов определяются без окружающего контекста, т.е. A → β , где “A” — нетерминал, “β” — цепочка нетерминалов и терминалов. Примеры таких грамматик:

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

Такие грамматики не получится разобрать в один проход из начала в конец строки с помощью ДКА, но можно разобрать с помощью прохода с возвратами (backtracking) и дополнительной памяти в виде стека (либо с помощью рекурсии, что эквивалентно стеку). Разбор можно вести как сверху вниз (ищем в файле функцию, в функции — имя, список параметров, тело и т.д.), так и снизу вверх. Методы разбора:

При описании грамматики обычно используются нотации BNF или EBNF. Вот пример грамматики в BNF:

При описании могут быть неоднозначности. Например, выражение “1 + 2 * 3” следует вычислять не слева направо, а в порядке приоритета операторов, где умножение приоритетнее, что даёт другое дерево выражения:

Устранить эту неоднозначность можно отдельным указанием приоритета операторов вне грамматики, либо введением промежуточных правил:

Ещё одна неоднозначность связана с ассоциативностью операторов. Например, присваивание правоассоциативное: “a = b = c” эквивалентно “a = (b = c)”

С другой стороны, в большинстве своём операторы — левоассоциативные, например, “2/2/2” вычисляется как “(2/2)/2=0,5”, а не “2/(2/2)=2”:

Эта сложность решается также введением дополнительных правил. Выше был приведён пример именно такого правила expr:

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

Можно устранить левую рекурсию с помощью добавления нового правила:

Примеры контекстно-свободных грамматик

Грамматика для простых предложений

Порождает предложения такого плана:

Но не порождает это предложение:

Набор правил выглядит так:

Грамматика для чисел в двоичной системе счисления

Для чисел вида ‘010110111’. Неоднозначная (ambiguous) версия грамматики:

Однозначная (unambiguous) версия грамматики:

Грамматика для простой арифметики

Поддерживает операторы ‘+’, ‘*’ и переменные X, Y, Z. Первая версия будет однозначной для LALR-парсеров, и неоднозначной для LL-парсеров:

Вторая версия будет однозначной и для LL-парсеров тоже:

Третья версия неоднозначная. Как думаете, почему?

Примеры ошибочных грамматик

Эта грамматика неоднозначная:

И эта тоже неоднозначная:


В этой есть иная проблема. Подумайте, какая:

Контекстно-зависимые грамматики

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

  • грамматика языка составляется как контекстно-свободная, и по этой грамматике пишется парсер
  • вводятся дополнительные правила (семантика языка), которая накладывает ограничение на уже разобранные парсером деревья разбора (parse tree), или на абстрактные синтаксические деревья (abstract syntax tree)

Примеры таких контекстных правил, которые можно проверить уже после разбора путём обхода дерева:

  • типы операндов в выражениях должны либо полностью совпадать, либо быть приводимыми к общему типу
  • все используемые переменные и функции должны быть определены или хотя бы объявлены в текущем модуле или в импортированных модулях, в пределах текущей области видимости или родительских областей видимости
  • нельзя создавать экземпляр абстрактного класса
  • если метод помечен как “override”, то один из реализуемых интерфейсов должен содержать объявление этого метода с такой же сигнатурой (возвращаемым типом и списком типов параметров)

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

  • паттерн проектирования Visitor
  • структура данных “ассоциативный массив” для хранения списка ране объявленных символов в процессе обхода дерево, эта структура также называется “таблица символов” в контексте теории компиляции
  • понимание работы областей видимости в языках программирования (на каждую область видимости — своя таблица символов, и искать символ надо путём подъёма по таблицам символов от текущей области видимости до глобальной)

Янушкевич Вадим Александрович

Факультет компьютерных наук и технологий

Кафедра компьютерной инженерии

Специальность «Системное программирование»

Как создать свой простой компилятор

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

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

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

И так, что же такое современный компилятор? Рассмотрим его сначала как черный ящик. На входе компилятору поступает файл с некоторыми (обычно текстовыми) данными – описание программы на исходном языке компилятора. На выходе компилятор выдает файл с другими данными – описание той же программы, но уже на другом языке – зачастую в машинном коде, или на языке ассемблера. То есть, компилятор можно рассматривать как переводчик программ с одного машинного языка на другой. Тут возникает проблема масштабируемости. Сейчас существует множество языков и множество целевых платформ (не забываем так же про виртуальные процессоры, такие как JVM, CLR, Parrot и т.д.). Когда создается новый язык программирования, Появляется необходимость использовать его на разных архитектурах, а как следствие приходится писать множество компиляторов. Эту проблему достаточно быстро осознали, и перешли к 3х этапной модели компиляции программ [1].

Компилятор разделили на 3 относительно независимые части:

  1. Парсер, генератор дерева синтаксического разбора
  2. Оптимизатор промежуточного представления кода
  3. Генератор кода из промежуточного представления в целевую платформу

Такая архитектура позволила уменьшить объем работы, связанный с созданием новых языков программирования, позволала переносить программы на новые платформы(кто бы мог подумать, есть способы конвертации С++ кода в JavaScript!), а так же упростила разработку и отладку компилятора в целом.

LLVM как библиотека для разработки компиляторов

Ярким примером такой системы компиляторов является Low Level Virtual Machine (LLVM). На рисунке наглядно показано, как с помощью LLVM реализуется компиляция различных языков.

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

Лексический и грамматический анализ исходного кода

И так, перейдем непосредственно к написанию парсера. Какой бы не были язык программирования, сразу в голову приходят однотипные действия. Нужно как-то вычленять лексемы, искать выражения, области видимости и т.д. Много работы было проведено в исследовании парсеров, и в итоге на данный момент была сформирована следующая концепция: сначала исходный текст разбивается на лексемы лексическим анализатором. Лексемами могут являться ключевые слова слова, имена переменных, пробелы, числа, специальные символы. Ниже приведен пример некого выражения на JSON- подобдном языке и его разбор лексическим анализатором.

После лексического разбора, лексемы и исходный текст отдаются синтаксическому анализатору. Синтаксический анализатор собирает вместе лексемы, формируя более сложные выражения. А из них в свою очередь еще более сложные. В итоге вся программа представляется парсером как одно выражение, и оно называется деревом синтаксического разбора. Этим деревом легко манипулировать, например на его основе можно сделать простой интерпретатор или компилятор. Причем, единственное отличие компилятора от интерпретатора только в том, что компилятор записывает в выходной поток соответствующую команду, а интерпретатор эту команду непосредственно исполняет [2].

Написание парсеров и лексеров дело рутинное и сложное. Но прогресс не стоит на месте и появилось множество программ которые по описанию лексики и грамматики языка генерируют парсер и лексер на Вашем любимом языке программирования.

Так сложилось, что я предпочитаю С/С++, поэтому для примеров буду использовать flex для получения набора токенов и bison для построения дерева разбора.

Программа на языке LEX состоит из 3х частей, первая часть – это обычный код на С, заключенный в символы %< … >%. Второй блок, это список регулярных выражений, и соответствующий им код на С. Каждый раз, когда лексер будет встречать что-то во входном потоке, подходящее под регулярное выражение, он будет исполнять соответствующий ему код на С. 3я часть программы, это тоже код на С, в данном примере она не требуется и потому отсутствует. Пример простейшей программы с использованием генератора lex:

Откомпилировать и запустить программу можно так: После чего вы получите программу, которая читает входной поток с клавиатуры, и при каждой встрече числа выводит слово «NUMBER», а каждый раз, когда встречает слово, выводит «WORD»

Грамматический анализ

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

Необходимо распознавать следующие токены: power, on/off (состояние STATE), set, speed и числа (NUMBER). Lex-анализатор выглядит следующим образом

В этом примере нужно отметить некоторые изменения, по сравнению с предыдущим примером. Во-первых, был подключен файл ‘y.tab.h’, во-вторых, на экран больше ничего не выводится, а лишь возвращаются имена токенов. Это изменение нужно потому, что поток токенов отдается на вход YACC, которому неважно, что выводится на экран. В файле y.tab.h как раз находятся определения этих токенов.

Теперь про сам файл y.tab.h. Он генерируется парсером BISON из файла грамматики, который мы сейчас напишем. Наш язык очень прост,такой же простой будет и его грамматика:

Первая часть грамматики означает, что имеются «команды» (commands), и эти команды состоят из отдельных «команд» (command). Как нетрудно заметить, это определение рекурсивно, ведь оно содержит в себе само себя. Благодаря рекурсии, программа способна постепенно сокращать набор команд одну за одной. Второе правило определяет, что из себя представляет команда. Предпологается лишь два типа команд — power_switch (вкл/выкл двигателя) и set_speed (установка скорости). Здесь используется знак ИЛИ — | . В целом правило означает: «command может быть power_switch или set_speed». Правило power_switch состоит из токена POWER (это просто слово «power»), после которого идет состояние (оно определено в Lex-файле как «on» или «off»). Немного более сложным является последнее правило set_speed, состоящее из токена SET (слово «set»), токена SPEED (слово «speed») и числа.

пример работы программы:

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

Языки и грамматики простейший компилятор

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

Классификация грамматик по Хомскому

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

Пусть грамматика обозначена как G(VT,VN,P,S), V=VTVN. В соответствии с иерархией Хомского выделяют 4 типа грамматик.

Тип 0 — грамматики с фразовой структурой, или без ограничений

На структуру их правил не накладывается никаких ограничений, т.е. правила имеют вид: , где V + , V*. Это самый общий тип грамматик. Грамматики, которые относятся только к этому и не могут быть отнесены ни к какому другому типу, являются самыми сложными по структуре.

Тип 1 — Контекстно-зависимые (КЗ) и неукорачивающие грамматики

К этому типу относятся два основных класса грамматик.

Контекстно-зависимые грамматики имеют правила вида 1A2 12, где 1,2V * , AVN, V + .

Неукорачивающие грамматики имеют правила вида , где ,V + , .

В КЗ-грамматиках при построении предложений заданного языка один и тот же нетерминальный символ может быть заменен различными терминальными цепочками в зависимости от контекста, в котором он встречается. Цепочки 1 и 2 в правилах обозначают контекст: 1 — левый контекст, 2 — правый контекст. В общем случае они могут быть пустыми.

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

Эти два класса грамматик эквивалентны.

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

Тип 2 — Контекстно-свободные (КС) грамматики

Контекстно-свободные (КС) грамматики имеют правила вида A , где AVN, V + . В правой части у них стоит всегда хотя бы один символ.

Такие грамматики еще называют неукорачивающими контекстно-свободными (НКС) грамматиками. Существует почти эквивалентный им класс укорачивающих контекстно-свободных (УКС) грамматик, отличие которого в том, что он допускает пустую цепочку, т.е. правила имеют вид A , где AVN, V * . В дальнейшем, если возможность наличия в языке пустой цепочки не имеет принципиального значения, будем говорить просто о КС-грамматиках.

КС-грамматики широко используются при описании синтаксических конструкций языков программирования.

Тип 3 — Регулярные грамматики

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

Леволинейные грамматики могут иметь правила двух видов: A B, или A , где A,BVN, VT + .

Праволинейные грамматики имеют правила тоже двух видов: A B, или A , где A,BVN, VT + .

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

Из определения типов видно, что любая регулярная грамматика является также КС-грамматикой, или любая грамматика может быть отнесена к типу 0. В то же время существуют УКС-грамматики, которые не относятся к типу 1, поскольку могут содержать правила вида A , недопустимые в этом типе. В общем, сложность грамматики обратно пропорциональна тому максимально возможному номеру типа, к которому может быть отнесена эта грамматика. Самыми простыми являются грамматики типа 3, самыми сложными — типа 0.

Классификация языков

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

Тип 0 — языки с фразовой структурой

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

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

Тип 1 — контекстно-зависимые (КЗ) языки

В общем случае время на распознавание языка типа 1 экспоненциально зависит от длины исходной цепочки символов.

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

Однако языки программирования имеют более простую структуру, поэтому в компиляторах КЗ-языки не применяются.

Тип 2 — контекстно-свободные (КС) языки

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

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

Тип 3 — регулярные языки

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

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

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

Содержание

Литература

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

Лекция 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лекция 2

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

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

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

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

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

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

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

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

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

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

  • 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
    • Добавление переменных. Представление о таблице символов
    • Добавление присваивания
    • Добавление типов
    • Добавление управляющих конструкций

«ОГЛАВЛЕНИЕ ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ИХ РЕАЛИЗАЦИЯ Язык и его реализация Компилятор, интерпретатор, конвертор Метаязыки ГЛАВА 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТРАНСЛЯЦИИ. 1 ФОРМАЛЬНЫЕ . »

ОГЛАВЛЕНИЕ

ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ИХ

Язык и его реализация

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

ГЛАВА 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТРАНСЛЯЦИИ.

ФОРМАЛЬНЫЕ ЯЗЫКИ И ГРАММАТИКИ

Основные термины и определения

Порождающие грамматики (грамматики Н. Хомского). 2

Еще несколько определений

Для чего надо решать задачу разбора

Домино Де Ремера

Разновидности алгоритмов разбора

Эквивалентность и однозначность грамматик

Иерархия грамматик Н. Хомского

АВТОМАТНЫЕ ГРАММАТИКИ И ЯЗЫКИ

Граф автоматной грамматики

Преобразование недетерминированного конечного автомата (НКА) в детерминированный конечный автомат (ДКА).


Таблица переходов детерминированного конечного автомата

Программная реализация автоматного распознавателя.

Дерево разбора в автоматной грамматике

Пример автоматного языка

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

Регулярные выражения и регулярные множества. 60 Эквивалентность регулярных выражений и автоматных грамматик

Для чего нужны регулярные выражения

Регулярные выражения как языки

Расширенная нотация для регулярных выражений. 65 КОНТЕКСТНО-СВОБОДНЫЕ (КС) ГРАММАТИКИ И ЯЗЫКИ. 66 Однозначность КС-грамматики

Алгоритмы распознавания КС-языков

Распознающий автомат для КС-языков

Самовложение в КС-грамматиках

Синтаксические диаграммы КС-языков

Определение языка с помощью синтаксических диаграмм.. 73 Синтаксический анализ КС-языков методом рекурсивного спуска

Требование детерминированного распознавания. 87 LL-грамматики

Левая и правая рекурсия

Синтаксический анализ арифметических выражений. 89 Включение действий в синтаксис

Обработка ошибок при трансляции

Рекурсивный спуск и табличный анализатор

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

Перевод выражений в обратную польскую запись. 1 Интерпретация выражений

Семантическое дерево выражения

Упражнения для самостоятельной работы

ГЛАВА 3. ТРАНСЛЯЦИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

ОПИСАНИЕ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

Расширенная форма Бэкуса-Наура (РБНФ)

Описания синтаксиса языков семейства Си

Описания синтаксиса языка Ада

ЯЗЫК ПРОГРАММИРОВАНИЯ «О»

Краткая характеристика языка «О»

Пример программы на «О»

Многопроходные и однопроходные трансляторы. 173 КОМПИЛЯТОР ЯЗЫКА «О»

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

ЛЕКСИЧЕСКИЙ АНАЛИЗАТОР (СКАНЕР)

Виды и значения лексем

Лексический анализатор языка «О»

Контекстный анализ модуля

Трансляция списка импорта

Контекстный анализ выражений

Контекстный анализ операторов

Архитектура виртуальной машины

Программирование в коде виртуальной машины. 2 Реализация виртуальной машины

Генерация кода для выражений

Генерация кода для операторов

Назначение адресов переменным

Расширенный набор команд виртуальной машины. 293 Процедуры без параметров и локальных переменных. 294 Процедуры с параметрами-значениями без локальных переменных

Процедуры с параметрами-значениями и локальными переменными

Простейшая оптимизация кода

Процедуры-функции с параметрами-значениями и локальными переменными

Трансляция оператора RETURN

Особенность трансляции параметров-переменных. 308 Пример программы на языке «О с процедурами». 3 КОНСТРУКЦИЯ ПРОСТОГО АССЕМБЛЕРА

Язык ассемблера виртуальной машины

АВТОМАТИЗАЦИЯ ПОСТРОЕНИЯ И МОБИЛЬНОСТЬ ТРАНСЛЯТОРОВ

Автоматический анализ и преобразование грамматик. 3 Автоматическое построение компилятора и его частей. 332 Использование языков высокого уровня

Унификация промежуточного представления

ПРИЛОЖЕНИЕ 1. ЯЗЫК ПРОГРАММИРОВАНИЯ ОБЕРОН-2

3. СЛОВАРЬ И ПРЕДСТАВЛЕНИЕ

4. ОБЪЯВЛЕНИЯ И ОБЛАСТИ ДЕЙСТВИЯ

5. ОБЪЯВЛЕНИЯ КОНСТАНТ

6. ОБЪЯВЛЕНИЯ ТИПОВ

6.1 Основные типы

6.4 Тип указатель

6.5 Процедурные типы

7. ОБЪЯВЛЕНИЯ ПЕРЕМЕННЫХ

9.2 Вызовы процедур

9.3 Последовательность операторов

9.4 Операторы IF

9.5 Операторы CASE

9.6 Операторы WHILE

9.7 Операторы REPEAT

9.8 Операторы FOR

9.9 Операторы LOOP

9.10 Операторы возврата и выхода

9.11 Операторы WITH

10. ОБЪЯВЛЕНИЯ ПРОЦЕДУР

10.1 Формальные параметры

10.2 Процедуры, связанные с типом

10.3 Стандартные процедуры

ПРИЛОЖЕНИЕ A: ОПРЕДЕЛЕНИЕ ТЕРМИНОВ

Расширение типов (базовый тип)

Совместимость по присваиванию

Совпадение списков формальных параметров

ПРИЛОЖЕНИЕ B: СИНТАКСИС ОБЕРОНА-2

ПРИЛОЖЕНИЕ C: МОДУЛЬ SYSTEM

ПРИЛОЖЕНИЕ D: СРЕДА ОБЕРОН

D2. Динамическая загрузка модулей

D5. Структуры данных времени выполнения

ПРИЛОЖЕНИЕ 2. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА

ПРИЛОЖЕНИЕ 3. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА

ОТЛИЧИЯ ВЕРСИЙ ДЛЯ КОМПИЛЯТОРОВ JOB И XDS

ИЗМЕНЕНИЯ В СТРУКТУРЕ КОМПИЛЯТОРА

ПРИЛОЖЕНИЕ 4. ТЕКСТ КОМПИЛЯТОРА ЯЗЫКА «О» НА

ПРИЛОЖЕНИЕ 5. ТЕКСТ КОМПИЛЯТОРА «О» НА ЯЗЫКЕ

ПРИЛОЖЕНИЕ 6. ТЕКСТ КОМПИЛЯТОРА «О» НА ЯЗЫКЕ

ГЛАВА 1. ЯЗЫКИ ПРОГРАММИРОВАНИЯ И ИХ

РЕАЛИЗАЦИЯ

С начала 50-х годов XX века создаются и развиваются языки программирования. Чтобы язык программирования можно было реально применять — писать программы на этом языке и исполнять их на компьютере, язык должен быть реализован.

Язык и его реализация Реализацией языка программирования называют создание комплекса программ, обеспечивающих работу на этом языке. Такой набор программ называется системой программирования.

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

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

Компилятор, интерпретатор, конвертор Различают несколько видов трансляторов: компиляторы, интерпретаторы, конверторы (рис. 1.1).

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

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

Интерпретатор — это переводчик и исполнитель исходной программы.

Различие между интерпретаторами и компиляторами можно проиллюстрировать такой аналогией. Чтобы пользоваться каким-либо англоязычным документом, мы можем поступить поразному. Можно один раз перевести документ на русский, записать этот перевод и потом пользоваться им сколько угодно раз.

Это ситуация, аналогичная компиляции. Заметьте, что после выполнения перевода переводчик (компилятор) больше не нужен.

Интерпретация же подобна чтению и переводу «с листа». Перевод не записывают, но всякий раз, когда нужно воспользоваться документом, его переводят заново, каждый раз при этом используя переводчика 1.

Одно из основных значений английского interpreter — устный (синхронный) переводчик.

Рис. 1.1. Схема работы компилятора и интерпретатора Нетрудно понять преимущества и недостатки компиляторов и интерпретаторов.

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

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

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

В действительности различие между интерпретаторами и компиляторами может быть не столь явным. Некоторые интерпретаторы выполняют предварительную трансляцию исходной программы в промежуточную форму, удобную для последующей интерпретации. Некоторые компиляторы могут не создавать файла объектного кода. Например, Turbo Pascal может компилировать программу в память, не записывая машинный код в файл, и тут же ее запускать. А поскольку компилирует Turbo Pascal быстро, то такое его поведение вполне соответствует работе интерпретатора.

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

Обычно ориентируются на версию ANSI Си — стандарт языка, принятый Американским Национальным Институтом Стандартов (American National Standards Institute, ANSI). Компиляторы ANSI Си есть практически в любой системе.

Кросскомпиляторы (cross-compilers) генерируют код для машины, отличной от той, на которой они работают.

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

Динамические компиляторы (Just-in-Time — JIT compilers), получившие в последнее время широкое распространение, транслируют промежуточное представление программы в объектный код во время исполнения программы.

Двоичные компиляторы (binary compilers) переводят объектный код одной машины (платформы) в объектный код другой. Такая разновидность компиляторов используется при разработке новых аппаратных архитектур, для переноса больших системных и прикладных программ на новые платформы, в том числе — операционных систем, графических библиотек и др.

Транслятор — это большая и сложная программа. Размер программы-транслятора составляет от нескольких тысяч до сотен тысяч строк исходного кода. Вместе с тем разработка транслятора для не слишком сложного языка — задача вполне посильная для одного человека или небольшого коллектива. Методы разработки трансляторов и будут рассмотрены в этой книге.

Рис. 1.2. Компилятор языка Оберон, написанный Никлаусом Виртом, с его «автографом» (NW). Фрагмент исходного текста основного модуля показан в левом окне Оберон-системы, частью которой является компилятор.

Компилятор написан на языке Оберон и может компилировать сам себя Транслятор связан в общем случае с тремя языками. Во-первых, это входной язык, с которого выполняется перевод. Во-вторых, целевой (объектный) язык, на который выполняется перевод. И, наконец, третий язык — это язык, на котором написан сам транслятор, — инструментальный язык. Трансляторы удобно изображать в виде Т-диаграмм 2 (рис. 1.3), которые предложил Х. Брэтман (H. Bratman) в 1961 году. Слева на такой диаграмме записывается исходный язык, справа — объектный, снизу — инструментальный.

Кроме того, что диаграмма имеет форму буквы «Т», примечательно, что с этой 2 буквы начинается и само слово «транслятор», как русское, так и английское.

Первые трансляторы, появившиеся в 1950-е годы, программировались на машинном языке или на языке низкого уровня — языке ассемблера (автокоде, как принято было говорить в то время).

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

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

Можно считать, что на рис. 1.3а изображен компилятор Turbo Pascal, Delphi или Free Pascal, транслирующий с языка Паскаль в машинный код IBM PC-совместимого компьютера и существующий в виде программы в машинном коде IBM PC. На рис. 1.3б показана Т-диаграмма компилятора c языка Оберон (см. рис. 1.2), транслирующего в машинный код компьютера Ceres и написанного на языке Оберон. Рисунок 1.3в соответствует конвертору. Си# — язык программирования, созданный в корпорации Microsoft. Первая реализация Си# вполне могла быть выполнена по такой схеме. В дальнейшем мы еще обратимся к Т-диаграммам и узнаем, как они могут сочетаться подобно костям домино, иллюстрируя процесс получения одних трансляторов с помощью других.

Интерпретатор, кстати, можно изобразить в виде I-диаграммы (Interpreter — интерпретатор). Сверху записываем название входного, а внизу — инструментального языка. Пример диаграммы для интерпретатора Бейсика, работающего на IBM PC, можно видеть на рис. 1.3г.

Метаязыки Говоря о Т-диаграммах, мы забыли еще об одном, четвертом языке, который неизбежно присутствует в разговоре о трансляторах и языках программирования. Это язык, например, русский, на котором мы ведем сам разговор. Язык, используемый для описания других языков, и называется метаязыком. В дальнейшем мы рассмотрим формализованные метаязыки, а пока в этой роли будем применять родной, естественный язык.

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

ГЛАВА 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ

ТРАНСЛЯЦИИ

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

Формальные языки и грамматики Основные термины и определения Введем в обиход основные понятия, которые будут использованы в определении формального языка.

Алфавит — конечное непустое множество символов.

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

Примеры алфавитов:

1 = <0, 1>2 = 3 = program Алфавит — это множество, поэтому при перечислении его элементов использованы фигурные скобки, как это принято в мате

Будем обозначать * — (бесконечное) множество всех цепочек над алфавитом, включая пустую цепочку; + — множество всех цепочек над алфавитом, не включая пустой цепочки. Например, если 1 = <0, 1>, то 1* представляет собой множество всех цепочек, которые могут быть составлены из символов 0 и 1.

В это множество входят пустая цепочка, все цепочки, состоящие из одного символа, все цепочки, состоящие из двух символов и т. д.: 1* = <, 0, 1, 00, 01, 10, 11, 000, 001, …>.

* = + < >, где — знак операции объединения множеств.

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

Языком над алфавитом называется произвольное множество цепочек, составленных из символов.

Будем обозначать язык над алфавитом (с алфавитом) — L() или просто L, если алфавит ясен из контекста.

Таким образом, речь идет о том, что язык — это некоторое, тем или иным образом определенное, подмножество множества всех цепочек, которые могут быть построены из символов данного алфавита. L() *. На рисунке 2.1 наглядно показано соотношение множеств * и L().

Рис. 2.1 Язык — подмножество множества всех цепочек над алфавитом

Принадлежащие языку цепочки называют также предложениями языка.

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

Примеры языков Пример 1. Определим язык L1 = , используя принятую в теории множеств нотацию, как множество всех цепочек, содержащих вначале некоторое количество символов a, а затем такое же количество символов b. Заметим, что L1 включает и пустую цепочку, поскольку n может равняться нулю.

Записанное выше правило, определяющее язык L1, разделяет все цепочки над алфавитом , то есть состоящие из символов a и b, на принадлежащие L1 и не принадлежащие ему.

Примеры цепочек, принадлежащих языку:

L1 — пустая цепочка принадлежит L1;

ab L1 — цепочка из одной буквы a, за которой следует b;

Цепочки, не принадлежащие языку L1:

aaab L1 — неодинаковое количество символов a и b;

abba L1 — порядок следования символов не соответствует определению L1.

Пример 2. Язык L2 = — множество всех цепочек, содержащих вначале некоторое (возможно нулевое) количество символов a, затем такое же количество символов b, затем — столько же букв c.

Например, aaabbbccc L2, в то время как aaabbc L2.

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

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

Обозначим его L3. Алфавит языка Дика — это множество из двух символов — открывающей «(» и закрывающей «)» скобок: 3 = < (, ) >. Цепочки, содержащие правильно расставленные скобки принадлежат языку Дика, все остальные последовательности открывающих и закрывающих круглых скобок — нет. Например: (())()() L3; ()(()))( L3.

Илон Маск рекомендует:  Подбор синонимов и антонимов с помощью редактора Word

Пример 4. Язык L4 — множество всех цепочек, содержащих одинаковое количество символов a и b.

Несмотря на простое «устройство», задать язык L4 формулой, подобной формулам для L1 или L2, оказывается затруднительно. Можно заметить, что рассмотренный ранее язык L1 является подмножеством языка L4:

L1 L4, поскольку любая цепочка, принадлежащая L1, принадлежит и языку L4. Но не наоборот. Так, aabb L1, aabb L4, abba L4, но abba L1.

Пример 5. В качестве языка L5 рассмотрим множество всех правильных арифметических выражений языка Паскаль, составленных из символов алфавита 5 = .

Например, a*(b+c) L5, но c++ L5.

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

Порождающей грамматикой называется четверка:

G = (T, N, P, S), где T — конечное множество терминальных (основных) символов — основной алфавит. Элементами множества T являются символы, из которых в конечном итоге и состоят цепочки языка, порождаемого данной грамматикой. Терминальный (от лат. terminus — предел, конец) и означает «конечный, концевой». T — это не что иное, как алфавит языка, порождаемого грамматикой.

В дальнейшем, если не оговорено особо, терминальные символы или просто терминалы будут обозначаться малыми буквами латинского алфавита: a, b, c и т. д.

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

Очевидно, что к получившейся цепочке ни одно из правил грамматики G1 больше не применимо. Процесс порождения завершен. Нетрудно заметить, что с помощью грамматики G1 можно породить любую цепочку языка L1 = , применив к начальному нетерминалу правило (1) (S aSb) n раз, а затем один раз правило (2). В то же время, грамматика G1 не порождает ни одной цепочки терминальных символов, не принадлежащей языку L1. То есть множество терминальных цепочек, порождаемых грамматикой G1, совпадает с языком L1. Другими словами, грамматика G1 порождает язык L1:

Можно убедиться, что грамматика G2 порождает цепочки терминалов вида anbncn и никакие другие. Количество повторений символов в результирующей цепочке определяется тем, на каком шаге применяется правило (2). Наличие правила (5) позволяет получить пустую цепочку, если применить это правило первым, в то время как попытка использования этого правила на последующих шагах не позволит вывести цепочку терминалов.

Грамматика G2 порождает множество терминальных цепочек, совпадающее с языком L2 = :

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

S (S) G3: (1) S SS (2) S (3) Нетрудно понять логику построения правил этой грамматики.

Смысл первого правила таков: заключив в скобки правильное скобочное выражение S, мы снова получим правильное скобочное выражение. Второе правило означает, что два правильных скобочных выражения, записанные одно за другим, дают новое правильное выражение. Наконец, по правилу (3) пустая цепочка считается правильным выражением. Если бы мы решили, что не следует разрешать пустые выражения, правило (3) можно было бы заменить на S ().

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

Единственным нетерминалом этой грамматики (он же начальный) будет Выражение:

Выражение Выражение + Выражение |

G4:

Выражение – Выражение | Выражение * Выражение | Выражение / Выражение | a | b | c | ( Выражение ).

Такая грамматика порождает цепочки терминалов, являющиеся правильными арифметическими выражениями. Символы a, b и c в таких выражениях обозначают операнды, а «+», «–», «*», и «/» — знаки операций. Разрешаются круглые скобки (в том числе вложенные). Примеры правильных выражений: (a+b)/(b*c), (a). Все операции двуместные, унарные плюс и минус не предусмотрены, поэтому, например, цепочка –a не принадлежит языку, порождаемому этой грамматикой.

Выражение — одно из основных понятий языков программирования. В дальнейшем грамматикам выражений будет уделено немалое внимание. Чтобы запись этих грамматик была короче, заменим нетерминал Выражение на E (от expression — выражение), вернувшись тем самым к принятым раньше соглашениям об именовании нетерминалов. Тогда грамматика, которую обозначим G5, запишется следующим образом:

G5:

Очевидно, что она порождает тот же язык, что и грамматика G4.

А именно:

Еще несколько определений В предыдущих примерах мы уже пользовались такими терминами как «вывод», «язык, порождаемый грамматикой». Теперь дадим формальные определения для этих и ряда других понятий.

Пусть имеются грамматика G = (T, N, P, S) и цепочка 1, составленная из терминалов и нетерминалов грамматики G, причем 1 представима в виде 1 = 12, где 1, 2 — цепочки терминалов и нетерминалов грамматики G, — непустая цепочка терминалов и нетерминалов грамматики G: 1, 2 (T N)*; (T N)+.

Пусть также среди множества правил P грамматики G есть правило. Тогда подцепочка цепочки 1 может быть заменена цепочкой, в результате чего будет получена цепочка 2 = 12. В этом случае говорят, что цепочка 2 непосредст

означающая, что цепочка n выводится из 1 в грамматике G (выводится за ноль или более шагов), что следует понимать так, + что, либо n совпадает с 1, либо 1 n.

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

Цепочка — есть сентенциальная форма грамматики G, если * S.

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

Язык, порождаемый грамматикой, есть множество всех её сентенций.

Можно сказать, что сентенции грамматики — это предложения порождаемого ею языка.

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

Рассмотрим грамматику S AB G6: (1) A aA | a (2) B bB | b (3)

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

Будем сопровождать процесс вывода построением дерева (рисунок 2.2). Корнем дерева будет вершина, соответствующая начальному нетерминалу S. Дочерними вершинами корня будут вершины A и B, соответствующие правой части первого примененного правила (рис. 2.2а). Вершины A и B следуют в дереве слева направо в том же порядке, что и в правиле (1): слева — А, справа — B.

Рис. 2.2. Построение дерева вывода

Продолжая вывод, мы можем выбрать, как правило для нетерминала A — правило (2), так и правило для B — правило (3). Используем вначале первую часть правила (2) (A aA):

S AB aAB и продолжим построение дерева (рис. 2.2б). Теперь выполним подстановку вместо нетерминала B цепочки bB по правилу (3):

S AB aAB aAbB, добавив к имеющейся вершине B дочерние вершины b и B (рис.

2.2в). Еще раз применим правило A aA и, чтоб получить цепочку, состоящую только из терминалов, выполним подстановки по правилам A a и B b. После этого вывод приобретет следующий вид:

S AB aAB aAbB aaAbB aaabB aaabb, a получившееся дерево показано на рис. 2.2г.

ВОПРОС

Какой язык порождает грамматика G6?

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

4 Одни авторы (и их переводчики) [Грис, 1975] считают «дерево разбора» и «синтаксическое дерево» синонимами, другие [Ахо, 2001] придают понятию «синтаксимвол грамматики, внутренние вершины — нетерминалы, листья дерева (концевые вершины) — терминалы. Обход листьев дерева слева направо дает цепочку терминалов, выведенную из начального символа грамматики (сентенцию) 5.

Нетрудно заметить, что построенное нами дерево будет соответствовать и другим выводам цепочки aaabb в грамматике G6. Вот один из них:

S AB AbB aAbB aAbb aaAbb aaabb.

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

Задача разбора Задача разбора состоит в восстановлении дерева вывода для заданной сентенции.

Разбор — это построение вывода для заранее заданной цепочки.

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

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

Могут рассматриваться и деревья вывода, листьями которых являются как терминалы, так и нетерминалы. В этом случае обход листьев дает сентенциальную форму грамматики. Однако такие деревья нам не потребуются.

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

Для чего надо решать задачу разбора Разбор (по-английски — parsing) называют также распознаванием или синтаксическим анализом. Синтаксический анализ имеет две цели — выяснение принадлежности цепочки языку и выявление ее структуры.

Работа любого транслятора основана на распознавании структуры предложений транслируемого языка. Синтаксический анализ — обязательная фаза в работе компиляторов и интерпретаторов языков программирования. Синтаксический анализатор — это часть транслятора, составляющая его основу.

Только распознавая структуру входной программы, определяя наличие или отсутствие отдельных ее частей — описаний, операторов, выражений и подвыражений — транслятор может выполнить работу по переводу программы на другой язык. Часто трансляторы в явном виде строят дерево программы, которое представляется внутренними динамическими структурами данных транслятора, а затем используется при формировании эквивалентной выходной программы. Если в ходе распознавания дерево вывода не строится, оно присутствует неявно, отражаясь в последовательности выполняемых синтаксическим анализатором действий.

Рассмотрению способов решения задачи разбора — синтаксического анализа будет посвящена большая часть этой главы.

Домино Де Ремера Де Ремер (De Remer F. L.) предложил наглядную интерпретацию задачи разбора, представив ее как игру в своеобразное домино.

Играющий располагает «костями» домино нескольких типов.

Типов столько, сколько правил в грамматике. Каждое правило дает один тип пластинки. Типы домино для грамматики G6 показаны на рис. 2.3. Считается, что «костяшек» каждого типа имеется сколько необходимо.

Рис. 2.3. Домино Де Ремера для грамматики G6

Верхняя часть каждого домино соответствует левой части правила грамматики, нижняя — правой. Верхняя и нижние пластинки соединены «резиновыми» нитями. Пластинки можно приставлять друг к другу плоскими сторонами полукруга, если на них записаны одинаковые символы. Фигуры домино нельзя переворачивать, и нельзя менять порядок следования символов (перекрещивать нити).

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

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

Полученная конфигурация домино для цепочки aaabb и грамматики G6 (набор домино на рис. 2.3) показана на рис. 2.5.

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

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

Рис. 2.6. Начало нисходящего и восходящего разбора в грамматике G6

Эквивалентность и однозначность грамматик Возьмем для примера грамматику арифметических выражений EE+E|E–E|E*E|E/E|a|b|c|(E).

G5:

Рассмотрим деревья вывода терминальных цепочек в этой грамматике. На рис. 2.7 показаны два различных дерева разбора выражения a+b*c. Возможность построить эти деревья убеждает в том, что цепочка a+b*c действительно принадлежит языку арифметических выражений.

Рис. 2.7. Деревья разбора цепочки a+b*c в грамматике G5

Но два разных дерева дают две разные трактовки структуры этой цепочки. Дерево слева объединяет a+b в одно подвыражение, которое затем участвует в роли операнда в операции умножения. Такая трактовка не соответствует общепринятому приоритету арифметических операций — умножение должно выполняться раньше сложения. Дерево справа представляет структуру, соответствующую правильному порядку выполнения операций.

Грамматика G называется однозначной, если любой сентенции x L(G) соответствует единственное дерево вывода.

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

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

G7:

Xa|b|c|(E) Содержательно X можно понимать как операнд выражения. Теперь для цепочки a+b*c можно построить единственное дерево разбора. Оно показано на рис. 2.8 слева. Можно убедиться, что в грамматике G7 единственное дерево вывода соответствует любому правильному выражению. Грамматика G7 однозначна.

Рис. 2.8. Дерево разбора выражения a+b*c в грамматике G7

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

Несмотря на однозначность, G7 непригодна для использования в трансляторе, поскольку приписывает выражениям неподходящую структуру. Уже на примере цепочки a+b*c (см. рис. 2.8) видно, что операции и операнды связываются неправильно. Нетрудно заметить, что G7 предполагает выполнение операций без учета их приоритета в порядке слева направо.

Исправить положение можно, определив нетерминалы для двух категорий подвыражений — слагаемых и множителей. После этого выражение представляется как последовательность сла

Тип 0. Произвольные грамматики. На вид их правил не накладывается каких-либо ограничений. Правила имеют вид:

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

Тип 1. Контекстно-зависимые грамматики. Правила таких грамматик имеют вид:

, где,, — цепочки терминалов и нетерминалов; A — нетерминальный символ. Такой вид правил означает, что нетерминал A может быть заменен цепочкой только в контексте, образуемом цепочками и.

Тип 2. Контекстно-свободные грамматики. Их правила имеют вид:

, где, A — нетерминал; — цепочка терминалов и нетерминалов.

Характерная особенность — в левой части правил всегда один нетерминальный символ.

Тип 3. Автоматные грамматики. Все правила автоматных грамматик имеют одну из трех форм:

aB a, где A, B — нетерминалы; a — терминал; — пустая цепочка.

Автоматные грамматики называют также регулярными.

Как можно видеть, грамматики типа 1 являются частным случаем грамматик типа 0, грамматики типа 2 — частный случай контекстно-зависимых грамматик, автоматные — частный случай контекстно-свободных. То есть, грамматика типа 3 является и грамматикой типа 2, и типа 1, и типа 0. Однако в дальнейшем, если не оговорено особо, будет иметься в виду что, например, контекстно-свободной называется грамматика, не являющаяся автоматной.

Языки, порождаемые грамматиками типа 0–3, называются соответственно языками без ограничений, контекстно-зависимыми, контекстно-свободными и автоматными (регулярными) языками. Но контекстно-свободным языком называют язык, для которого существует порождающая его контекстно-свободная, но не автоматная грамматика. Такой же подход применяется к контекстно-зависимым языкам и языкам без ограничений.

Примеры грамматик различных типов Рассмотрим грамматику G2, порождающую язык L2 = .

S aSBc G2: (тип 2) S abc (тип 2) cB Bc (тип 0) bB bb (тип 1) S (тип 3) Справа около каждого правила помечен тип грамматики, к которой оно может быть отнесено. Типом грамматики естественно считать минимальный из типов ее правил. Следовательно, грамматика G2 — это грамматика типа 0 — произвольная. Утверждается, однако, что может быть построена контекстно-зависимая грамматика (типа 1), порождающая тот же язык, что и G2. Проверку этого утверждения предоставлю читателям.

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

Na G9: (1) N Na (2) N Nb (3) Это грамматика типа 2, поскольку правила (2) и (3) относятся именно к этому типу. Рассмотрим язык L9 = L(G9), порождаемый этой грамматикой. Цепочка a принадлежит L9 по правилу (1).

Если к правильному предложению N языка приписать справа символ a, то снова получится правильное предложение (по правилу (2)). Аналогично, приписывание к N символа b снова дает предложение языка L9. Принадлежащие языку L9 цепочки начинаются символом a, за которым могут следовать a и b в произвольном порядке. Если под a понимать любую латинскую букву, а b воспринимать как цифру, то G9 можно считать грамматикой идентификаторов. Она порождает последовательности букв и цифр, начинающиеся с буквы, которые используются в языках программирования в роли имен переменных, типов и т. д.

Опираясь на такую содержательную трактовку G9 и L9, попытаемся сконструировать автоматную грамматику, порождающую язык идентификаторов.

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

щения грамматики G10. Отложим, однако, на некоторое время такое упрощение.

Автоматные грамматики и языки Рассмотрим автоматные грамматики и языки подробнее, имея целью построение алгоритмов распознавания этого класса языков.

Граф автоматной грамматики

Для каждой автоматной грамматики можно построить направленный граф по следующим правилам:

1. Каждому нетерминальному символу грамматики ставится в соответствие вершина графа, которая помечается этим символом.

2. При наличии правил вида Aa добавляется дополнительная вершина, которая помечается символом K.

3. Каждое правило вида A aB порождает дугу графа, ведущую из вершины A в вершину B.

Построим граф автоматной грамматики G10 (рис. 2.10). Двум нетерминалам этой грамматики будут соответствовать вершины N и B (п. 1). Поскольку в грамматике есть несколько правил, в правой части которых записан единственный терминал, добавим вершину K (п. 2).

Соединим вершины дугами, как это предписывается п. 3 и п. 4.

Вершину N пометим стрелкой как начальную (п. 5).

«ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Данная программа по литературе для учащихся 9 класса общеобразовательных учреждений с русским (неродным) и родным (нерусским) языком обучения составлена на основе проекта федерального компонента Государственного стандарта основного общего образования по литературе и Обязательного минимума содержания основных образовательных программ по литературе с изменениями и дополнениями с учетом приоритетных идей (актуальных) при учете ФГОС. Учебник-хрестоматия Н.Н. Вербовая. »

«DONEGAL LANGUAGE WWW.DONEGALLANGUAGESCHOOL.COM SCHOOL “ ” PDF Created with deskPDF PDF Writer Trial :: http://www.docudesk.com www.donegallanguageschool.com Tullan Strand, Bundoran, Co Donegal PDF Created with deskPDF PDF Writer Trial :: http://www.docudesk.com www.donegallanguageschool.com Добро пожаловать 4 Программы для детей Комплекс 1. Английский и верховая езда 5 Комплекс 2. Английский и серфинг 6 Курсы для взрослых Общий 8 Интенсивный 1 Деловой 12 Подготовка к экзаменам 12 Тет-а-тет 13. »

«Иванищева Ольга Николаевна СОЦИОЛИНГВИСТИЧЕСКИЙ ПОРТРЕТ РЕГИОНА: ПРОГРАММА И МЕТОДИКА (НА ПРИМЕРЕ ПРИГРАНИЧНОГО СЕВЕРНОГО РЕГИОНА) Статья посвящена разработке программы и методики социолингвистического портрета приграничного северного региона на примере Мурманской области как части Баренц региона, в работе описана специфика региона, предложен план анализа его социолингвистического разнообразия, определены новые параметры характеристики коммуникативной и языковой ситуаций. Адрес статьи. »

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Кемеровский государственный университет» ПФ КемГУ (Наименование факультета (филиала), где реализуется данная дисциплина) Рабочая программа дисциплины (модуля) «Специфика языкового сознания» (Наименование дисциплины (модуля)) Специальность подготовки 031001.65 «Филология» (шифр, название направления) Направленность (специализация). »

«Сергей Ним Как выучить английский язык http://www.litres.ru/pages/biblio_book/?art=9748783 ISBN 978-5-4474-0485-7 Аннотация Эта книга – не очередной учебник английского языка, а подробное руководство, которое доступным языком объясняет начинающему, как выучить английский язык. Вы узнаете, как все подходы к изучению языка можно выразить в одной формуле, что такое трудный и легкий способы учить язык, почему ваш английский не может быть «нулевым» и многое другое. Специально для книги автор создал. »

«Министерство высшего и среднего специального образования республики Узбекистан. Каракалпакский государственной университет имена Бердаха. Факультет иностранных языков Кафедра английской филологии Лекция: «Системная лингвистика» Для магистрантов Составитель: к.ф.н.доц. Юлдашев Н. Нукус-2009/2010. Лекция №1 Тема: Понятие структуры в лингвистике Проблемы для обсуждения 1. О термине “структура” в лингвистике. 2. “Курс общей лингвистики” Ф. де Соссюра – предмета современного структурализма. 3. Язык. »

«Министерство образования и науки Российской Федерации ФГБОУ ВО «Тверской государственный университет» Утверждаю Декан факультета ИЯ и МК Л.М. Сапожникова «» 20 г. Рабочая программа дисциплины (с аннотацией) «Практический курс первого иностранного языка» (немецкий язык) Направление подготовки 45.03.02 «Лингвистика» Профиль подготовки «Теория и методика преподавания иностранных языков и культур», «Перевод и переводоведение» Для студентов 1 и 2 курса очной формы обучения Уровень высшего. »

«Протокол согласования рабочей программы 1 Цель и задачи дисциплины Изучение иностранного языка является составной частью подготовки аспиранта (соискателя), который в соответствии с требованиями Государственного стандарта должен владеть иностранным языком на таком уровне, который позволяет вести научную работу с использованием иностранных источников, а также осуществлять профессиональную деятельность и общение в иноязычной среде. Данный курс обучения иностранному языку аспирантов и соискателей. »

«ИНСТИТУТ СОЦИАЛЬНЫХ И ГУМАНИТАРНЫХ ЗНАНИЙ ТЕОРИЯ ПЕРЕВОДА Казань ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ИНСТИТУТ СОЦИАЛЬНЫХ И ГУМАНИТАРНЫХ ЗНАНИЙ КАФЕДРА ПЕРЕВОДА УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ТЕОРИЯ ПЕРЕВОДА УДК ББК Т Рекомендовано к изданию Учебно-методическим советом Института социальных и гуманитарных знаний Составители кандидат педагогических наук, доцент кафедры теоретической лингвистики Института социальных и гуманитарных знаний Тарарина Л.И. ассистент кафедры перевода Артамонова А.А. »

«Министерство образования и науки РФ ГОУ ВПО «Дагестанский государственный технический университет» Кафедра иностранных языков для экономических специальностей УТВЕРЖДАЮ Исмаилов 2010г. ПОЛОЖЕНИЕ О ПРОВЕДЕНИИ КАНДИДАТСКОГО ЭКЗАМЕНА «ИНОСТРАННЫЙ ЯЗЫК» В АСПИРАНТУРЕ ДГТУ М ахачкала 201D 1. ОБЩИЕ ПОЛОЖЕНИЯ 1. 1. Настоящее Положение разработано на основании Федерального Закона «О высшем и послевузовском профессиональном образовании», «Типового положения «Об образовательном учреждении высшего. »

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования «БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ» ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ «УТВЕРЖДАЮ» Директор Педагогического института _Тарабаева В.Б. «_» _ 2014 г. Основная образовательная программа подготовки кадров высшей квалификации по направлению 45.06.01 Языкознание и литературоведение. Русская литература Присуждаемая. »

«РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ЯЗЫКОЗНАНИЯ в. в. ПОТАПОВ КРАТКИЙ ЛИНГВИСТИЧЕСКИЙ СПРАВОЧНИК язы ки и п и с ь м е н н о с т ь ф о н д «р азви ти я ф у н д а м е н т а л ь н ы х л и н г в и с т и ч е с к и х и с с л е д о в а н и й » м осква УДК 811 ББК 81.2 П 64 Издание осуществлено при финансовой поддержке Федерального агентства по печати и массовым коммуникациям врамках Федеральной целевой программы «КультураРоссии (2012—2020годы)» Потапов В. В. П 64 Краткий лингвистический справочник. »

«УП: B100100_11_1_СЕРВ.plm.xml 1. ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ Основной целью курса является повышение исходного уровня владения иностранным языком, достигнутого на предыдущей ступени 1.1 образования, и овладение студентами необходимым и достаточным уровнем коммуникативной компетенции для решения социальнокоммуникативных задач в различных областях бытовой, культурной, профессиональной и научной деятельности при общении с зарубежными партнерами, а также для дальнейшего самообразования. Для достижения. »

«Программа подготовки к вступительным испытаниям по русскому языку при поступлении на направления подготовки и специальности Костанайского филиала ФГБОУ ВПО «ЧелГУ» в 2015 году ТРЕБОВАНИЯ К УРОВНЮ ПОДГОТОВКИ ВЫПУСКНИКОВ В результате изучения русского языка на базовом уровне в старшей школе ученик должен знать основные функции языка; смысл понятий речевая ситуация и ее компоненты, литературный язык, языковая норма, культура речи; основные единицы и уровни языка, их признаки и взаимосвязь;. »

«Пенсионные пособия Обратиться в Социальное страхование В Интернете Наша страница в Интернете www.socialsecurity.gov— это ценный источник информации обо всех программах Социального обеспечения. Там вы также сможете: • Подать заявку на пенсию, инвалидность, и Медикэр льготы; • Просмотрите свой статус Social Security Statement (Заявления о Социальной Страховке); • Найти адрес местного отделения Социального обеспечения; • Запрос на замену карты Медикэр, а также; • Найти копии наших публикаций. »

«МИНИСТЕРСТВО ЗДРАВООХРАНЕНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ БЕЛОРУССКОЕ ОБЩЕСТВЕННОЕ ОБЪЕДИНЕНИЕ ПРЕПОДАВАТЕЛЕЙ РУССКОГО ЯЗЫКА КАК ИНОСТРАННОГО БЕЛОРУССКАЯ ОБЩЕСТВЕННАЯ ОРГАНИЗАЦИЯ ПРЕПОДАВАТЕЛЕЙ РУССКОГО ЯЗЫКА И ЛИТЕРАТУРЫ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ МЕДИЦИНСКИЙ УНИВЕРСИТЕТ КАФЕДРА БЕЛОРУССКОГО И РУССКОГО ЯЗЫКОВ ДИАЛОГ ЯЗЫКОВ И КУЛЬТУР Программа VI РЕСПУБЛИКАНСКИХ СТУДЕНЧЕСКИХ ЧТЕНИЙ И НАУЧНО-ПРАКТИЧЕСКОГО СЕМИНАРА «АСПЕКТЫ ПРЕПОДАВАНИЯ РУССКОГО ЯЗЫКА В. »

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА Отчет по мероприятию: «Создание и внедрение инновационной образовательной программы «Мониторинг и управление глобальными процессами в больших городах» в рамках деятельности Московской кафедры ЮНЕСКО МГУ по глобальной проблематике» НИМ 4. «Закономерности эволюции крупных городских систем (на примере г. Москвы)» Москва 201 «Закономерности эволюции крупных городских систем (на примере г. Москвы)» Состав научно-образовательного коллектива. »

«Государственное бюджетное образовательное учреждение города Москвы средняя общеобразовательная школа с углубленным изучением иностранных языков № «Мультипрофильный образовательный комплекс «Пресненский» РАССМОТРЕНО СОГЛАСОВАНО УТВЕРЖДАЮ на заседании М/О на заседании М/С Директор ГБОУ СОШ № 1240 Протокол № 1 от Т.Ю. Щипкова Протокол №_1_ от «28_»августа_2014 г. «9 »_сентября_2014 г. Приказ № 5/2_от «9»сентября_2014 г. Рабочая программа учебной дисциплины история (наименование учебного предмета). »

«РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт лингвистических исследований RUSSIAN ACADEMY OF SCIENCES Institute for Linguistic Studies ACTA LINGUISTICA PETROPOLITANA TRANSACTIONS OF THE INSTITUTE FOR LINGUISTIC STUDIES Vol. IV, part Edited by N. N. Kazansky St. Petersburg Nauka ACTA LINGUISTICA PETROPOLITANA ТРУДЫ ИНСТИТУТА ЛИНГВИСТИЧЕСКИХ ИССЛЕДОВАНИЙ Том IV, часть Отв. редактор Н. Н. Казанский Санкт-Петербург Наука RUSSIAN ACADEMY OF SCIENCES INSTITUTE FOR LINGUISTIC STUDIES COLLOQUIA CLASSICA ET. »

«11 3 – 3 УЧЕБНЫХ ЕДИНИЦЫ Экзаменационные требования Вопросник № 18 Чтение Умение прочитать текст и ответить на вопросы по его содержанию. Характер текста – адаптированный (художественный, газетно-публицистический, научнопопулярный). Объём 0,75 печатной страницы. Время чтения про себя 10 минут. Письмо Умение продолжить приведенное начало текста. В соответствии с содержанием предложенного абзаца закончить текст и написать не менее 6 предложений. Умение правильно написать изученные слова, а также. »

2020 www.programma.x-pdf.ru — «Бесплатная электронная библиотека — Учебные, рабочие программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL