Return язык программирования

Утка-логотип Разработка языка и построение интерпретатора от начала до конца.

Часть 1: Предпосылка

Языки программирования бывают разных парадигм. Несмотря на это. На языковом фронте. Как правило. Существуют два основных лагеря. Есть статические языки и есть динамические. Чтобы избежать слишком большой истории и какого-либо углубленного анализа. Эта статья упростит ситуацию с помощью ряда допущений. Одно предположение. Которое мы сделаем. Может быть не всегда верным. Состоит в том. Что программы. Написанные на статических языках. Компилируются в машинный код. В то время как программы. Написанные на динамических языках. Выполняются в интерпретаторе.

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

В качестве примера рассмотрим случай объявления переменных в Java:

int num1, num2; String text; 

Это был бы прототип статического языка. При первом объявлении переменных они должны быть сопряжены с типом. Для сравнения с динамически типизированным языком рассмотрим пример из Python.

 global num1, num2 global text 

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

Дополнительные примеры динамически типизированных языков. Помимо Python. Включают JavaScript, Ruby. Lua, Clojure. Scheme и Lisp и ряд других. Помимо стиля синтаксиса и степени выразительности. Эти языки программирования во многом схожи по своей системе типов. Так называемые динамически типизированные языки иногда называют утиными или утиными языками.

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

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

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

Часть 2: Синтаксис

На этом этапе может быть легко собрать вместе документ синтаксических выражений. Учебники для начинающих. Вики или грамматические руководства в качестве объяснения языка и вообще отбросить тему. Перейдя к более продуктивным задачам. Иногда кажется. Что дизайн языка. Вплоть до его истинной грамматики. Является чем-то большим для вкладышей в справочном руководстве, чем то. Что существует. Что было написано. Создано или изменено с течением времени. Цель этого объяснения не состоит в том. Чтобы предположить. Что ваш язык программирования должен быть высечен в камне и именно так великие концепции приходят к осуществлению. Вместо этого. Верные природе нашей задачи. Мы будем на каждом шагу смотреть на то. Как вещи могут быть изменены. Расширены и эволюционировать с течением времени. То, что может быть подходящим для одной задачи. Не является решением всех проблем. И наличие способа изменить ситуацию или повторно использовать наши усилия всегда хорошо.

Имея это в виду. Мы как бы замалчиваем то. Что представляет собой фундаментальная механика утиного языка на атомном уровне. Вместо этого мы исследуем. В чем суть. Мы хотим обнаружить интенцию самого языка. Если мы сможем проникнуть в сознание. В фэн-шуй или в основные установки языка программирования. Этого будет достаточно. Однако языки программирования-это системы. Которые мы используем для выражения идей. А для того. Чтобы любая форма общения была полезной. Мы должны найти общий язык.

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

Чтобы найти корневую концепцию. С которой мы можем работать. Давайте начнем с утверждений. Есть операторы. Которые формируют операции. Учитывая два значения. Сложите их вместе и назначьте результат. Если выражение истинно. Выполните блок операторов. Вычислите выражения. А затем выполните вызов процедуры с аргументами. И Так Далее. Блок операторов будет описан в терминах списка операторов. Заданное объявление функции. Своего рода оператор. Есть имя для функции. Список имен параметров и список операторов. Составляющих тело. Оператор If/Else имеет аналогичную природу. IT это утверждение. Содержащее дополнительные утверждения.

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

if some condition then ; here is a block of statements end 

Вот как выглядит наше основное утверждение if. Учитывая, что мы часто захотим выполнить операторы. Если наше условие ложно. Нам лучше добавить поддержку операторов else.

if some condition then ; here is a block of statements ; to run if the condition is true else ; here is a block of statements ; to run if the condition is false end 

Глядя на синтаксис. Который у нас есть. Мы, кажется. Заимствовали нотацию конечного блока от Lua. Думаю, это просто совпадение. Мы могли бы так же легко стилизовать наш язык после BASIC и terminated IF операторов с ENDIF . А не просто ключевое слово end. У меня нет для этого никакого реального оправдания.

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

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

function our_new_function(parameter1, parameters2) ; here we have statements that do work ; if this function returns a value then we might have return ourResult ; at the end end 

Мы не будем накладывать никаких ограничений на их размещение. Функции могут быть определены внутри функций. В этом случае они будут локальными по отношению к тому месту. Где они определены. Мы не хотим вводить ограничения при формировании наших определений с самого начала. Потому что они могут быть основаны на ожиданиях. Которые не соответствуют действительности. Если ограничения. Которые мы накладываем на себя. Искусственны. Тогда мы будем тратить время и усилия на то. Чтобы навязать искусственные ограничения. И это станет напрасным усилием. В функциях использование end в качестве ключевого слова кажется более оправданным. Так как оно намного короче . Чем функция end Хорошей промежуточной точкой может быть endf. Это зависит от того. Хотим ли мы позволить END быть конкретной командой. Которая завершает запущенную программу. Я всегда думал. Что это может быть полезной инструкцией. Но она не часто включается в языки. Вместо этого у нас может быть системная команда quit (). Которую мы можем вызвать из нашей программы.

Наш язык должен иметь некоторый общий язык с существующими языками. Поэтому мы будем использовать знакомые конструкции. Такие как циклы for и while. Циклы For будут использовать диапазоны явным образом. Там будут начальное и конечное значения. И тело цикла будет выполняться как для них обоих. Так и для каждого промежуточного значения. Это предполагает. Что мы начинаем с целых чисел или. Возможно. Чисел с плавающей запятой. Но всегда увеличиваемся с шагом в единицу.

Наш синтаксис цикла for.

for j = 1 to 100 do ; this prints the numbers 1 through 100 println(j) loop 

Наш синтаксис цикла while.

while running do println("still running") loop 

Мы разрешим все основные операции. Которые мы привыкли ожидать. А именно сложение. Вычитание. Умножение и деление. А также деление по модулю (то. Что мы могли бы реализовать сами). Конкатенация строк для удобства, отрицание. Не и булевы выражения. Таковы основные принципы.

Мы пытаемся создать наиболее гибкий и программируемый язык. Поэтому мы также должны думать о четко динамических элементах. Которые мы можем добавить. Массивы принципиально полезны. Давайте добавим массивы. Которые позволяют использовать любой индекс. Не указывая размер контейнера. Давайте расширим эту функциональность массива. Чтобы разрешить использование значений любого типа в качестве индексов. Кроме того, давайте создадим словарные типы со знакомой объектной нотацией. Они будут похожи на классы или структуры из родственных языков. Чтобы повысить гибкость. Это будет один и тот же объект внутренне они представлены как массивы. И синтаксис для каждого из них может использоваться взаимозаменяемо.

 arr1 = [] arr2 = [1, 2, 3, 4] dict2 = {firstArray: arr1, secondArray: arr2} dict1 = {"a": 1, "b": 2, "c": 3} arr2[4] = 5 dict2.arr2[5] = 6 dict1.d = 4 

Наш пример массива и словаря.

Еще одна особенность. Повышающая нашу гибкость,-это возможность превращать функции в первоклассные объекты. Это означает. Что мы можем использовать функции в качестве параметров. Возвращать их в качестве значений и присваивать им именованные переменные. Мы можем переименовать функцию и использовать исходное имя для чего-то другого. Мы можем присоединять функции к объектам и использовать их как классы. Хотя передача функций в качестве объектов первого класса является функциональной идеей. Здесь она пересекается с идеями динамических языков. Поэтому мы примем эту функцию. Для того чтобы отслеживать объекты и сложные типы. Имеет смысл реализовать управление памятью через сборку мусора. Вместо того. Чтобы передать эту большую ответственность программисту. Адаптирующемуся к использованию нашего языка.

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

Часть 3: Настройка

Случайный читатель. Идущий следом. Может быть и не заинтересован в развитии своего собственного языка на данный момент. Возможно, их больше интересует механика. В качестве довольно сложного упражнения я предлагаю каждому попробовать создать свой собственный интерпретируемый язык программирования. Тем не менее. Я собираюсь обрисовать процесс и инструменты . Которые я использовал для создания языка программирования Duck, хотя я признаю. Что есть несколько способов осуществления этого процесса.

Например, я решил написать все на языке программирования Си. Это действительно более сложная задача. Чем это должно быть. Но я объясню свое решение дальше. Разработчику может быть проще создать язык с любой другой средой. По-настоящему преданный делу инженер, возможно. Уже нацелился на платформу и решил начать с самого начала с рукописного языка ассемблера. Это не очень портативное решение. Другой начинающий разработчик может начать с современного языка. Такого как Java или C#. Это отличный выбор. И я бы рекомендовал выбирать поднимите все инструменты. С которыми вы знакомы. По причинам. Которые могут быть или не быть очевидными. Я бы рекомендовал создать этот динамический язык. Который мы создаем в статической среде хоста. Таким образом. Такой язык. Как Go. Был бы предпочтительнее для схемы. Я знаю. Что ряд курсов преподают языки программирования. Реализуя схему или интерпретатор Lisp. То, что мы делаем. Недалеко от этого. За исключением больших различий в стиле и синтаксисе. И обычно эти курсы требуют написания языкового переводчика на самом языке или предполагают выполнение аналогичной задачи. То причина, по которой я бы рекомендовал держаться подальше от этого курса. Заключается в том. Что он начинает приводить к намеренно непрактичным решениям. Производительность. Которую вы можете получить от самодостаточной среды. На самом деле находится только на полпути. И любые преимущества создаваемого нами решения. Как правило. Отнимаются. Создание специальных интерфейсов для языка может быть очень полезно. И есть способы повысить производительность и производительность за счет создания специального диалекта, но то. Что мы собираемся сделать. — это совершенно новый язык.

Я отмечу, что есть один способ. Которым реализация этого динамического языка в интерпретируемом или скриптовом языке может быть полезна. И это было бы в случае кросс-компиляции. То есть когда наш код Утки сводится к какому-то другому языку. Например JavaScript или Python. Перед выполнением. Это было бы прекрасно. Но тогда мы имеем дело с компиляцией кода и другими сложностями. Которые лучше всего рассмотреть в разделе II этой серии.

Причины, поддерживающие мое решение использовать C. Заключаются главным образом в том. Что:

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

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

  • Это не собранный мусор. Хотя этот вопрос можно обсуждать. Цель этого проекта заключается в том. Чтобы создать что-то новое. Таким образом. Создавая новый язык с функциями более высокого уровня. Легче почувствовать чувство выполненного долга. Когда мы работаем над функциями. Которых у нас не было с самого начала. Это также помогает нам контролировать время выполнения для нашего конечного интерпретатора. Поскольку мы сами несем ответственность за управление памятью.

  • Это трудно. Это вряд ли можно назвать причиной. Я бы сказал. Что одной из причин было бы потому что это быстроНо, по сути. Это упражнение будет непростым. Так что оно может быть и хорошим.

Теперь это не особенно квалифицируется как языковая проблема. Но в качестве дополнительной проблемы проект строится с нуля. Подтягиваясь по-своему. Это означает, что. Как вы видите. Части разработки вокруг парсера и лексера собираются вместе. Два фундаментальных компонента языка. Все это будут части и инструменты ручной работы. Далее будет объяснена внутренняя работа генератора синтаксического анализатора. Это полностью упускает из виду любые споры. Которые могут возникнуть по поводу таких инструментов. Как Bison, Flex. Yacc или Lex. Ряд инструментов. О которых я знаю очень мало.

Мы также работаем с нашим собственным интерфейсом и нашим собственным бэкэндом. Это означает. Что мы не подключаемся к LLVM или связываемся с Clang или чем-то подобным. Мы используем компилятор ANSI со скриптом CMake.

Если вы сами разрабатываете что-то параллельно с этим проектом или самостоятельно. Я бы рекомендовал использовать все эти замечательные инструменты и ресурсы. Которые значительно ускорят ваше путешествие и вы сможете закончить свой проект еще до того. Как закончите читать это руководство.

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

Часть 4: Лексер

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

Взяв исходный файл в качестве входных данных. Лексер создаст новый буфер и удалит избыточные пробелы. Однострочные комментарии и многострочные комментарии. Последовательные символы пробела будут заменены одним пробелом. Если только этот поток не включает новую строку. И в этом случае будет использоваться новая строка. Этот процесс используется для очисткиТеперь мы будем работать символ за символом. Чтобы изолировать и идентифицировать токены. Составляющие исходный код Утки.

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

import, include, return, break, continue, throw, function, end, if, then, else, for, to, do, loop, step, in, while, let, begin, try, complete, catch, object, static, operator, this, and, or, not, is, mod, new, true, false

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

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

Предположим. Что мы встречаем символ из алфавита. Тогда мы могли бы рассматривать идентификатор (то. Что мы используем в программе для обозначения переменной. Процедуры или поля) или ключевое слово. Следуя соглашениям об именовании идентификаторов в нашем языке. Мы позволим всему. Что начинается с буквы и продолжается с любой комбинации букв. Цифр или подчеркиваний. Называть переменную. Поэтому мы будем продолжать сканирование до тех пор. Пока не дойдем до символа. Который не совпадает. Или до конца ввода; В этот момент мы либо добавим идентификатор. Либо ключевое слово. наш список лексем. Нам нужно будет проверить наш список ключевых слов. Чтобы увидеть. Является ли этот идентификатор на самом деле ключевым словом. В этом случае наш лексер вместо этого выдает В противном случае мы добавляем маркер идентификатора к лексемам и прикрепляем строковый литерал для идентификатора.

Если мы сталкиваемся с числом. Мы будем продолжать. Пока мы видим числа или десятичные точки. Пока мы не увидим другой символ или не достигнем конца ввода. Если эта последовательность содержит десятичную точку. То мы будем считать. Что это действительное число или константа с плавающей запятой. В противном случае мы будем интерпретировать это число как целое. Мы добавляем токен для целого числа или поплавка к нашим токенам лексера и включаем литеральную строку для последовательности. Чтобы использовать ее. Когда нам нужен доступ к этому значению.

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

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

, = ( ) [ ] + - * / . == != > = >= ! { } :

Заметив, что мы заметно пропустили кавычки. Мы должны вернуться назад и добавить строки в коллекцию объектов. Которые мы лексируем. Главным образом потому. Что мы не хотим лексировать то. Что находится внутри цитируемых строк, и мы. Конечно же. Не хотим их разбирать. Поэтому, если мы сталкиваемся с глифом. Который является строкой, или. В частности. Если мы сталкиваемся с символом. Который является открывающей кавычкой. Так что либо одинарная. Либо двойная кавычка. То мы должны сканировать входные данные. Пока не найдем соответствующую конечную кавычку. Затем мы добавим это в наш список лексем в качестве строкового токена и включим цитируемый текст как литеральная строка.

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

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

Часть 5: Парсер

Мы еще не можем говорить о парсере. Пока не поговорим о генераторах парсеров. Здесь я должен упомянуть. Что в нашем стремлении найти наиболее гибкий способ делать вещи. Мы, возможно. Предпринимаем некоторые дополнительные шаги. Как я уже говорил. Предприимчивый программист может начать с самого начала программировать на ассемблере. Хотя мы сделали свой выбор не идти по этому пути. Мы должны смотреть на другие. Более прямые пути. Которые мы оставляем. Это в некотором смысле предметно-специфический язык. Который мы строим. Если бы мы действительно были в гармонии с тем. Что мы хотели. Наше результирующее программирование чтобы язык выглядел и как он должен себя вести. Мы могли бы объединить все шаги синтаксического анализа и лексики в один. Или, в любом случае. Мы могли бы отказаться от создания парсера и начать писать его вручную.

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

К сожалению. Парсеры сверху вниз имеют свои ограничения. Не становясь слишком педантичными. Мы просто скажем. Что наш рекурсивный парсер спуска будет ограничен его сложностью в написании. Набором языковых структур. Которые он может анализировать. И, возможно. Его эффективностью во время выполнения. В качестве контрапункта он может быть очень гибким к незначительным изменениям в языке. Я также хотел бы отметить. Что в качестве одного из методов ручного синтаксического анализа рекурсивный парсер нисходящего спуска лежит близко к области методов самостоятельного синтаксического анализа. Которые вполне могут быть способны анализировать любую грамматику. От а с точки зрения теории вычислений. Функция может быть записана на любом достаточно подходящем языке. Чтобы распознать любой детерминированный язык. Но мы ищем более уверенный ответ.

Существует класс языков. Известных как контекстно-свободные языки. На которых мы остановимся. Контекстно-свободные языки-это класс языков. Которые могут быть распознаны или сгенерированы контекстно-свободной грамматикой. Это относится и к нам. Поскольку мы. Скорее всего. Будем писать наш язык программирования как контекстно-свободный язык или что-то близкое к нему. В любом случае. Мы объединим мощь нашего лексера. Нашего парсера и любой обработки. Которую мы могли бы сделать до или после синтаксического анализа. Чтобы сформировать наш язык программирования. На этом этапе нам нужно заняться контекстно-свободными языками и тем. В какой степени они применимы. Поэтому мы мы сделаем краткий обзор того. Что такое языки LR(k). Что такое языки LR(1) и как мы можем использовать алгоритм LR для написания универсального синтаксического анализатора для любого вида грамматики. Который мы можем придумать. Мы будем работать с контекстно-свободными грамматиками. И нам нужно будет придумать свою собственную нотацию. Для этого мы будем использовать форму BNF. Потому что она легко понятна.

То, что мы описываем,-это парсер снизу вверх. Который работает слева направо и производит самый правый вывод. Парсер берет наш входной поток токенов и создает абстрактное синтаксическое дерево. Дерево связанных производств. Основанное на наборе правил. Которые мы ему предоставляем, описывая. Как формируются производства. Это парсер shift-reduce. То есть он работает с одним токеном за раз. Используя стек. Чтобы либо сдвинуть токен. Либо уменьшить производство.

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

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

Давайте сначала рассмотрим пример из нашей грамматики.

 ::=  +   ::=  *   ::=   ::=   ::=  

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

Чтобы помочь нашему пониманию. Мы также начнем рассматривать другую формальную грамматику. Язык сбалансированных скобок. Который также является подмножеством окончательной контекстно-свободной грамматики нашего языка программирования.

 ::= (  )  ::=    ::=  

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

Это приводит к следующей основной концепции. Наша грамматика формируется терминальными и нетерминальными символами/лексемами. Знак Следовательно. Это терминал. Нет никакого способа. Чтобы знак плюс расширился в нашей программе до большего количества символов или токенов. Это само по себе конечное производство.

Нетерминалы-это символы. Которые мы определили в самой грамматике. Поскольку мы сформировали правила с левой и правой частями. Разделенными на:: = оператор. Мы заметили. Что символы разделены угловыми скобками. И мы уже приняли во внимание маркеры. Которые признаем терминальными символами. А как насчет других символов? Он является синонимом лексерного токена. Создаваемого целыми числами на этапе лексинга. Это то. Что мы определяем внутри синтаксического анализатора. Но что это означает? Это синоним пустого производства. Во втором примере речь идет о производстве. Которого мы достигаем. Когда у нас заканчиваются скобки.

Мы сами можем определить булевы типы как символ. Который сводится к true или false. Которые затем становятся ключевыми словами.

Наш генератор парсеров загрузит контекстно-свободную грамматику в виде файла Для удобства мы допустим комментарии в грамматике в виде строк. Начинающихся с точки с запятой’;’. Затем мы начинаем работать по очереди. Если эта строка не является пустой или начинается с комментария. То это новое правило. Во-первых, мы должны определить левую сторону. Мы используем newlines для специальной цели при перечислении правил. Поэтому они не могут встречаться где-либо слева или справа однако использование пробелов и других символов допустимо до тех пор. Пока везде. Где встречается нетерминальный символ. Он используется с точно таким же соответствующим литералом. Как только мы определим левую часть. Мы сгенерируем для нее идентификатор символа. Это уникальное число. Соответствующее данному символу. По ходу дела мы будем составлять таблицу символов. Так что если мы снова встретим тот же символ. То будем использовать одно и то же целочисленное значение. После идентификации левой стороны. Мы будем искать символ BNF. Который разделяет производство.

При разборе правой части продукционного правила мы будем искать либо другой символ. Обозначенный угловыми скобками. Либо ключевое слово/токен. В случае, если нам нужно меньше или больше символов. Чтобы появиться в наших производственных правилах. Мы будем использовать обратную косую черту. Чтобы разграничить их. Например Столкнувшись с ключевым словом. Это будет добавленный в список токенов и его номер токена будут добавлены в правило. Таким образом. В конечном итоге у нас есть правила. Которые определяются левосторонним (LHS) нетерминальным символом и правой стороной (RHS) терминальных и нетерминальных символов. Все из которых определяются путем идентификации целочисленных констант. У нас также есть таблица ключевых слов и символов. Которые мы можем предоставить лексеру.

Построение таблиц LR(1) Parse

Вернемся к идеям грамматик LR(k) и LR(1). Грамматика LR(k) — это грамматика. Для которой синтаксический анализатор LR(k) может успешно генерировать дерево синтаксического анализа при заданном k знаки внимания. Грамматика LR(1) — это грамматика. Для которой синтаксический анализатор LR(1) может успешно сгенерировать дерево синтаксического анализа при наличии одного маркера lookahead. Множество языков LR(k) содержит множество всех детерминированных. Контекстно-свободных языков. Интересно, что набор языков LR(1) содержит набор языков LR(k). Что означает. Что любая грамматика LR(k) может быть распознана синтаксическим анализатором LR(1). Если она переписана как грамматика LR(1). Это удобно, потому что попытка справиться с чрезмерным количеством lookahead токены. Как при построении таблиц синтаксического анализа. Так и при синтаксическом анализе. Могут стать очень надоедливыми. С точки зрения формирования нашей грамматики это означает. Что каждое из наших производственных правил должно быть дифференцировано от других с помощью одного токена lookahead. Суммируя, мы должны сделать однозначные грамматики.

Процесс построения таблицы синтаксического анализа из грамматики немного сложнее. В псевдо-обзоре алгоритма процесс выглядит следующим образом. Во-первых, nullable non-терминалы должны быть идентифицированы. Действительно. Этот парсер распознал бы пустой поток лексинговых токенов. Это также транзитивное свойство. Если нетерминальный символ сводится к другому нетерминальному символу. Который является нулевым. То он само по себе является обнуляемым нетерминальным. Кроме того, если нетерминальный символ сводится к производству с любым количеством нулевых нетерминальных символов. Без каких-либо терминалов. То он является нулевым нетерминальным. Все эти символы сначала идентифицируются в таблице.

Далее генерируется таблица первых наборов. Учитывая любой нетерминальный символ или левый производственный символ. Первый набор FIRST(a) представляет возможные терминальные токены. Которые могут появиться в качестве первого токена в любом данном производстве. Это строится как набор. Просматривая все возможные производства. Которые могут быть взяты. Принимая во внимание. Какие производства обнуляются.

Затем генерируется таблица следующих наборов. Используя первый набор и набор обнуляемых нетерминалов в качестве ссылок. Набор FOLLOW или FOLLOW(a) представляет возможные терминальные токены. Которые могут появиться после производства. Алгоритм LR(1) при синтаксическом анализе использует look-a-head одного символа. Так что это помогает синтаксическому анализатору определить. В какое состояние переходить дальше. Для других производств он будет включать набор терминалов. Которые могут появиться после этого производства в любом контексте. Который может быть найден в данной грамматике.

Первый Набор Примеров

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

Чтобы помочь в понимании концепции ПЕРВОГО(а) набора. Я приведу примеры для каждой (небольшой) выборки грамматик.

Пример из арифметического языка.

Символ Первый набор
целое число
целое число
целое число

Здесь мы видим. Что каждое из этих произведений должно начинаться с целочисленного токена.

Теперь рассмотрим язык скобок.

Символ Первый набор
(

Этот еще проще.

Следуйте Приведенным Примерам

Теперь перейдем к примерам из следующего набора. Эти наборы требуют создания ПЕРВОГО набора. Но они также должны учитывать другие токены в производственном правиле. Построение этих наборов включает в себя изучение каждого производственного правила и наблюдение за тем. Какие токены следуют за любыми возможными символами. Кроме того, процесс будет завершен только тогда. Когда будут рассмотрены все возможности. Поскольку каждый символ может зависеть от ПЕРВОГО и ПОСЛЕДУЮЩИХ наборов другого символа. Алгоритм действительно должен выполняться повторно до тех пор. Пока не будет больше изменений в наборе СЛЕДОВАНИЯ.

Здесь давайте рассмотрим арифметический язык.

Символ Следуйте за Набором
+,
*, +,
*, +,

В этом случае мы добавили маркер конца файла. Это потому. Что любой из этих символов может быть последним символом в нашем языке. Единственное. Что следует за этим. — это наш конец ввода. За выражением может следовать знак

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

Символ Следуйте за Набором
(, ),

Из правила № 1 ясно. ЧтоНо откуда взялся символ открывающих скобокРассмотрим правило № 2, где . Поэтому мы добавим. Что открывающие скобки означают.

Примечание: все может усложниться. Когда у нас есть обнуляемые нетерминальные символы. Зажатые в середине грамматического правила. На мгновение рассмотрим это мнимое правило . Чтобы привести еще более сложный пример. Рассмотрим мнимое правило

Каноническая коллекция LR(1) Наборы предметов

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

Наконец, сама таблица синтаксического анализа построена с использованием канонической коллекции и наших оригинальных правил грамматики. Используя наборы Goto каждого набора элементов из канонической коллекции и маркер lookahead для каждого элемента в наборе элементов. Строится таблица действий shift и reduce. Это дает таблицу Goto и таблицу действий. Первая из которых определяет переходы состояний из одного состояния синтаксического анализатора в другое с учетом нетерминального символа. А вторая определяет действия shift. Reduce или accept для синтаксического анализатора с учетом состояния и терминального символа сверху из ввода программы. Действие принять указывает. Что операция синтаксического анализа завершена. Если синтаксический анализатор не может создать соответствующее синтаксическое дерево из источника. Потому что он не распознает язык. То может возникнуть ряд различных ошибок. Которые препятствуют принятию источника.

Фактический код для построения таблиц синтаксического анализа LR(1) выглядит следующим образом:

int BuildLRParser(GRAMMAR_TABLE grammar. LR_TABLE* парсер) { LR_ITEM_COLLECTION* C; FindNullableNonterminals(&grammar); BuildFirstSets(&grammar); BuildFollowSets(&grammar); // построение коллекции наборов элементов для грамматики LR(1) C = CanonicalCollection(&grammar); RemoveEpsilons(&grammar); *parser = ConstructTable(C, &grammar); FreeCollection(C); возврат 0

Опять же. Этот процесс начинается с правил и построения Первого и Последующих наборов после нахождения обнуляемых нетерминальных символов. Затем каноническая коллекция формируется путем взятия элементов LR. Которые являются производствами в паре с позицией синтаксического анализа. Мы пишем это как точку в середине постановки. Эта информация объединяется с символом lookahead . Который предоставляет информацию о следующем ожидаемом вводе. Начиная с начала корневого производства с конца файла lookahead. Каноническая коллекция создает набор элементов LR. Алгоритм многократно продвигает токен и находит закрытие этих предметов. Чтобы расширить набор. Есть и другие наборы. Которые не помещаются внутри закрытия этого набора элементов. Поэтому каноническая коллекция-это коллекция. Построенная из этих наборов.

Как уже было сказано ранее. Существует ряд готовых решений для генераторов парсеров. Которые уже разработаны и протестированы. Многие из них используют алгоритмы LALR или SLR, которые. Как мы увидим. Немного менее обобщены и менее эффективны. Чем алгоритм LR(1). Но в целом более компактны в таблицах. Которые они генерируют. Специально разработанный генератор парсеров был разделен из проекта языка программирования Duck на собственный репозиторий, доступный здесьдля тех . Кто ищет исходный код.

Разбор на основе стека

Сам синтаксический анализатор запускается из нулевого состояния и работает с потоком токенов. Полученным лексером. Чтобы обеспечить ввод в алгоритм LR(1). Действия извлекаются из таблицы действий на основе этого входного токена и состояния анализаторов. Если встречается действие reduce. Тоывая размер соответствующего производства. Это множество символов и состояний выскакивает из стека и добавляется в лист дерева. Затем это дерево помещается в стек. А также в следующее состояние из таблицы Goto. Последовательные состояния берутся из верхней части стека. Чтобы определить следующий ход парсера.

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

Наконец, когда действие accept достигнуто. Синтаксический анализ завершен. Если обнаруживается другое состояние. Стек пуст или возникает другая необработанная ошибка. Мы можем сказать. Что синтаксический анализ не удался. И предоставить входной маркер. Что он не удался. Поскольку у нас есть номера строк для токенов. Мы можем указать. В какой строке синтаксический анализ потерпел неудачу. И, имея немного больше знаний о синтаксическом анализаторе. Мы можем определить. Произошла ли ошибка из-за нехватки входных данных. Из-за конкретной синтаксической ошибки или из-за других особых случаев. И учитывая конкретный неудачный токен/производство. Которое мы могли бы легко предоставить настраиваемые сообщения об ошибках. Указывающие на то. Что было не так с источником входного сигнала. Это все вспомогательные потребности.

В качестве примера того. Как будет выглядеть наше результирующее синтаксическое дерево. Давайте еще раз рассмотрим упрощенный пример. Грамматика нашего языка имеет дело с рядом различных языковых конструкций. У нас есть функции if/else. While loops и for loops. Каждый из этих операторов должен иметь некоторый тип кода для выполнения. Поэтому мы также должны иметь операторы присваивания. Наши циклы и условные выражения нуждаются в условиях для оценки. Поэтому мы также требуем булевых выражений. Это требует целой системы выражений.

Чтобы поддерживать все необходимые нам математические операции. А также логику. Композицию функций. Ссылки на переменные и массивы. Нам нужно будет создать грамматику для выражений. Включение всего этого описания здесь может быть чрезмерным. Поэтому давайте снова рассмотрим только арифметические и алгебраические выражения. Давайте предположим. Что у нас есть наши операции. Настроенные для сложения. Умножения и деления по модулю. Как мы упоминали ранее. Глядя на наш первый пример грамматики. Мы можем видеть. Как мы могли бы установить иерархию для порядков операций. Кроме того, мы добавим скобки как еще одно требование для поддержания приоритета оператора.

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

-1 * 2 + 3 mod 4

Поскольку мы отказались включить отрицательные числа в определение нашего лексера. Нам также придется добавить отрицание к одному из операторов в нашем языке программирования. После того. Как эта последовательность пройдет через лексер. Она будет передана парсеру. Парсер распознает его как оператор. Который просто читает как автономное выражение. Выражение состоит из терминов и факторов. А затем генерирует абстрактное синтаксическое дерево. Первоначально это дерево будет содержать ряд ветвей. Которые соединяют узлы тривиальными способами. Как мы уже говорили. Иногда выражение-это просто термин. И иногда термин — это просто фактор. Чтобы избежать работы с тривиальными конструкциями или. По крайней мере. Для просмотра того. Как выглядит это синтаксическое дерево. Мы хотим исключить тривиально простые произведения. С этим легко справиться. Составив список всех тривиальных постановок. Затем давайте посмотрим. Как выглядит синтаксическое дерево для этого оператора.

Синтаксис выражений

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

Часть 6: Переводчик

Именно здесь вещи покидают внешний интерфейс. Удивительно. Но по моему опыту. Проектирование и внедрение frontend занимает большую часть усилий. А бэкенд-работа может быть довольно легко оптимизирована. Это может быть из-за выбора. Который мы сделали. Взяв на себя полный контроль над решением и предложив максимальную гибкость. Мы заранее сделали так много вариантов. Которые привели к обработке всех возможностей. Теперь мы остаемся с чем-то простым: конкретные грамматические правила. Которые мы построили. И проанализированный и обработанный источник. Который соответствует этой структуре. Хотя эта структура в значительной степени построенное из универсальных типов данных. Мы можем быть уверены. Что это абстрактное синтаксическое дерево удовлетворяет многим жестким ограничениям времени выполнения. Итак, возникает один вопрос: как наиболее эффективно оперировать этими данными? Хотя это может быть не лучшим решением. Мой прямой ответ состоял в том. Чтобы использовать генерацию кода из самой грамматики языка программирования.

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

Пример:

 int ReduceProgram(SYNTAX_TREE* node) { 0]; int error = 0; error = InterpretNode(stmt_list1); 

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

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

 int ReduceComparisonA(SYNTAX_TREE* node) { 0]; 2]; Сравнение значений; Арифметика ЗНАЧЕНИЙ; int error = 0; error = InterpretNode(comparison1); сравнение = gLastExpression; if (error) return error; error = InterpretNode(arithmetic1); арифметика = gLastExpression; if (error) return error; /* EQUAL */ gLastExpression = CompareEquality(сравнение. Арифметика); 

Мы можем видеть. Как наши простые производственные правила способны разделить работу. Которую мы делаем. На управляемые куски. Вместо этого мы можем сосредоточиться на атомарной операции равенства. Здесь мы сделали внешнюю фактическую логику CompareEquality. Чтобы сделать наш код более читабельным. Поскольку у нас есть список из 50-100 грамматических произведений, мы хотим. Чтобы они были как можно короче. Это позволяет нам держать их в одном месте и обеспечивать что все они следуют одним и тем же условностям.

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

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

Основная депеша становится примерно такой

/* уменьшить один узел */ int InterpretNode(SYNTAX_TREE* node) { if (node == NULL0) { printf(Null production.\n); возврат 1failed_production = узел; переключательcase 0x01: return ReduceProgram(node); case 0x02: return ReduceStmtListA(node); case 0x03: return ReduceStmtListB(node); case 0x04: return ReduceIdentifierListA(node); case 0x05: return ReduceIdentifierListB(node); case 0x06: return ReduceOptEndlA(node); случай 0x07: возврат ReduceOptEndlB(узел); case 0x08: return ReduceStmtA(node); case 0x09: return ReduceStmtB(node); case 0x0A: return ReduceStmtC(node); ... case 0x74: return ReduceBooleanA(node); case 0x75: return ReduceBooleanB(node); дефолт: printf(Unknown production %i.\nвозврат 1

Здесь мы позволяем генератору кода несколько помочь нам. Создав таблицу переходов. Которую мы будем использовать для идентификации производств. В этом нет особой необходимости. Одним из вариантов. Который мы сделали здесь. Была возможность отслеживать ошибки на производственной основе. Тогда мы могли бы отслеживать наши производственные функции с помощью указателей функций . Хранящихся в абстрактном синтаксическом дереве. Преимущество. Которое это дает. Заключается в исключении одного вызова функции для каждого правила определение. Это может быть большим благом для производительности. Вместо этого мы не будем сейчас заниматься исполнением . Есть несколько способов оптимизировать наш код и логику. Чтобы обеспечить гораздо лучшую производительность в будущем.

Сама среда выполнения обманчиво проста. В общем, все наши вычисления хранятся в одной глобальной переменной (очень плохая конструкция). Это выражение. GLastExpression. Представляет значение из последней операции или вызова функции. Что-то вроде операции сложения вычислит свой первый операнд. Сохранит результат во временном значении. Вычислит второй операнд. Сохранит результат во временном значении. А затем добавит два результата и сохранит их в регистре gLastExpression. Работа таким образом позволяет нам использовать возвращаемые значения для кодов ошибок. Особенно когда не все произведения возвращают выражение как таковое. Данные, необходимые для выполнения простых вычислений. И наши временные переменные автоматически сохраняются в стеке. Наши более сложные требования к хранению будут удовлетворены кучей.

Мы будем продолжать заполнять тела каждой из наших постановок. Такие операции. Как сложение. Вычитание и умножение. Довольно просты. Все наши порядки операций обрабатывались синтаксическим анализатором. Поэтому все. Что нам нужно. — это фактическая арифметика. Которую мы выполняем. Это может быть что-то вроде проверки того. Имеем ли мы дело с числовыми типами. Добавления чисел. Если один или несколько операндов являются вещественными числами. Хранящими результат в переменной с плавающей запятой. И если мы имеем дело со строками. То вместо этого делаем что-то вроде конкатенации строк. Все это на самом деле специфично для реализации.

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

Давайте посмотрим на нашу грамматику для определения функций. Определенного вида утверждения.

 ::= function     end  ::=   ::= ( )  ::= ()  ::=   ::= ,  

Оператор определения функции имеет идентификатор. Имя функции. Необязательный список параметров или аргументов и блок операторов. Представляющий тело функции.

Что нам нужно сделать с этой информацией. Так это создать запись для этой функции в текущей области. В которой мы находимся. Или наше текущее закрытие функции. Эта запись нуждается в информации об именах параметров. Теле функции и нашей текущей области действия. Которая будет храниться в этой записи. И она будет храниться под именем функции.

Наши цели проектирования заключались в том. Что мы хотели использовать функции как объекты первого класса. Поэтому нам нужно хранить их так же. Как мы храним строки. Целые числа и плавающие точки. Поскольку мы работаем со значениями и храним их. Мы создадим свой собственный тип данных для хранения переменных. Называемый типом ЗНАЧЕНИЯ. Это будет объединение всех возможных типов. Которые мы можем хранить. Таким образом. У него будет поле. Определяющее тип объекта. А затем у него будут поля для возможных целочисленных. Плавающих, строковых. Функциональных или словарных значений.

Целые числа и числа с плавающей запятой могут храниться непосредственно в ЗНАЧЕНИИ. Другие типы должны храниться по ссылке. Строки будут выделены в куче. А затем доступны как постоянные символьные указатели. Функциональные объекты. Которые хранят своего рода заголовок информации. Также будут храниться в куче. Как и словари.

Как мы уже говорили. Объект функции должен знать имена своих параметров. Тело содержащихся в нем операторов и. Наконец, область. В которой он объявлен. Операторы внутри тела функции будут иметь доступ к переменным. Объявленным вокруг функции. Но не к переменным из контекста. Из которого вызывается функция. Если только эти два уровня области не пересекаются. В этом случае язык Duck будет использовать лексическую область. А не динамическую. Позже будет важно рассмотреть все способы взаимодействия этих перекрывающихся областей при построении сборщика мусора.

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

Рассмотрим случай. Когда мы допускаем присвоение переменных из выражений или из других назначений:

 ::=  =   ::=  =  

Здесь мы должны рассмотреть. Каково определение l-значения. l-значение-это именованная переменная в левой части оператора присваивания. Для продолжения нам понадобится более полное определение. l-значение может быть просто именем глобальной или локальной переменной. Здесь область действия переменной определяется тем. Когда она впервые назначена. И областью действия исполняемого кода. Поскольку мы не реализовали ничего подобного объявлению переменных. L-значение также может быть индексом в массиве или свойством словаря. В общем случае l-значения могут использоваться как ссылки. А ссылки могут использоваться для обращения к l-значениям.

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

 ::=   ::= (  )  ::=  .   ::=  [  ]  ::=   ::=  ( )  ::=  (  ) 

Это показывает нам. Что нам нужно тщательно работать. Чтобы определить. Какую переменную-член мы ссылаемся в присваивании. То, что мы должны также рассмотреть, — это то. Что может составлять правую часть задания.

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

Таким образом. Когда мы имеем дело с назначением. У нас есть более строгие правила на левой стороне. Чем на правой. При вычислении выражения присваивания мы хотим начать сначала с правой части и, надеюсь. Вернуться с результирующим значением. Которое мы можем сохранить. При разыменовании вещей мы можем работать так же. Как и с другими производствами выражений. И определять результат и хранить его как gLastExpression. Для идентификатора мы ищем переменную. Используя имя идентификатора. Для ссылки, будь то словарь или массив. Мы сначала определяем значение ссылки. В качестве объекта значения используйте этот объект с нашим идентификатором для получения целевого значения. Наши правила уменьшения l-значений будут другими. В любой момент времени нам нужно будет отслеживать только одно l-значение. Если он используется с правой стороны. То это происходит до разыменования. Но после идентификации. С левой стороны. L-значение может быть уменьшено до индекса ссылки. В этом случае. После того как мы определили значение для хранения или присвоения. Мы оценим эту ссылку и удержим объект. Затем мы будем использовать его в качестве хранилища контекст. Если ссылки нет. Контекст — это текущий уровень области действия.

Чтобы уточнить более четко. Мы будем использовать глобальный регистр gLValueIdentifier при работе с именованными l-значениями. В том случае. Если мы индексируем массив. Как в четвертом правиле. Мы будем использовать регистр gLValueIndex. Наконец, есть два случая присвоения: хранение значения в переменной или хранение значения в словаре. Таким образом. Мы должны отслеживать не только то. С каким из них мы имеем дело. Но и заданную область или словарь для хранения. Поэтому мы введем еще два регистра. GLValueContext и gLValueDictionary. Тогда главной заботой было бы сохранить все это прямо по ходу дела.

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

Наконец, мы должны рассмотреть наши контрольные утверждения. Одной из первых структур. Которые мы рассматривали при разработке и построении языка. Был оператор if. Оператор else. Цикл for и цикл while. То, что мы не упомянули. Было еще одним утверждением if. Но мы покажем. Как мы можем их поддержать.

При внедрении контрольных структур лучше всего подходить к делу с более высокого уровня. Оператор if-может вести себя. Сначала получая выражение, условное. Из интерпретации части его синтаксического дерева. Тогда тело if может быть интерпретировано условно. Если это выражение Нам нужно определить свои собственные правила для логической логики при принуждении значений из других типов. Аналогично, циклы while будут вести себя одинаково. За исключением многократной оценки условия и, возможно. Тела цикла. Пока цикл не завершится. Для петель может быть больше всего сложные. Но включающие в себя сходную логику и в основном определяемые реализацией.

Обсуждая синтаксис для ‘else if’ больше. Чем процедуры того. Как будут выполняться ветви else. Которые должны быть примерно такими же трудными. Как и другие элементы нашего языка. Нам придется вернуться к грамматике.

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

 ::= if  then     ::= else   end  ::= else   ::= end 

К счастью для нас. Томы используем новые строки и фразы

Это определяет большое количество способов. Которыми мы настроены обрабатывать все различные типы утверждений и выражений в нашем языке. Но также оставляет нас с некоторыми свободными концами с точки зрения того. Как мы будем реализовывать все это. Я знаю. Что было бы непросто начать здесь с нуля. Поэтому лучше всего подойти к построению интерпретатора после того. Как у нас уже есть набор доступных ресурсов. Это также во многом зависит от языка и инструментов. Которые мы используем для создания интерпретатора. Используя C с минимальными библиотеками. Нам нужно создать ряд наших собственных данных типы. Включая списки, деревья. Словари и хэш-таблицы.

Часть 7: Виртуальная Среда

Прежде всего. Мы должны иметь некоторое представление о данных. С которыми мы будем работать и манипулировать во время выполнения нашего языка. Как мы уже решили, значения. Используемые в программе Duck, должны храниться вместе с информацией об их типе из-за ее динамической природы. Мы также обнаружили. Что встроенные типы для целых чисел и чисел с плавающей запятой могут передаваться по значению. Хранящемуся в структуре ЗНАЧЕНИЙ. И что строки. Функции и словари должны передаваться по ссылке. Как указатели в структуре ЗНАЧЕНИЙ.

При оценке и хранении информации на различных уровнях области нам нужен способ доступа и назначения переменных. Имеющих имена. В этом случае. Простейшем случае. Мы будем использовать список структур ЗНАЧЕНИЙ в паре со строковыми идентификаторами и пометим его как КОНТЕКСТ. КОНТЕКСТ может иметь родителя. Который представляет более высокий уровень области видимости. И поэтому мы имеем дерево идентифицированных переменных. При обращении к переменной мы будем продолжать эту цепочку родителей до тех пор. Пока не определим искомое значение. Начиная с локальной области и заканчивая глобальной областью.

Типы словарей и массивов будут храниться по-разному. Доступ к словарю будет осуществляться в виде хэш-таблицы. Значения. Используемые в качестве индексов. Будь то строки. Целые числа. Плавающие точки или ссылки на объекты. Сначала будут использоваться в качестве входных данных для хэш-функции. Которая найдет контейнер. А затем данное значение будет сохранено или извлечено. Это дает нам лучшую производительность. Поскольку она ближе к постоянному времени O(1). Кроме того, мы можем использовать некоторую оптимизацию. Подобную этой. Для обычного поиска переменных для повышения производительности.

Интересный случай для рассмотрения-это когда вызывается функция. Когда это происходит. Анонимные выражения. Которые передаются в качестве аргументов. Привязываются к именованным переменным. Параметрам. И создается новая область действия. Закрытие функции. Родительским контекстом замыкания функции является контекст или область действия. В которой была объявлена функция. Мы определили это. Когда приняли решение использовать лексический анализ.

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

Живой переводчик

Один из лучших способов проверить и использовать наш новый язык программирования-это живой. Интерактивный терминал. Мы называем это Циклом чтения-оценки-печати или REPL. Реализация чего — то подобного для нас не составит труда. Но потребуется еще несколько дополнений или настроек в систему. Которую мы уже имеем. Напомним, что наш парсер использовал ряд состояний. Чтобы организовать наш исходный код программы в абстрактное синтаксическое дерево при условии ввода из лексера. Теперь помните. Что было несколько способов для этого процесса. Чтобы потерпеть неудачу. Один из этих случаев сбоя был. Когда парсер искал больше ввод. Как правило. Для сменной работы. Что ж, вместо того. Чтобы потерпеть неудачу на этом этапе. Интерактивный интерпретатор предлагает нам возможность запуска программы по частям. А также позволяет пользователю терминала предоставлять программу построчно.

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

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

/* Duck REPL ** Enter statements to be evaluated. */ duck.println("Duck Language REPL - type quit() to exit") running = true while running do program = "" typing = true expr = 0 duck.println("Type expression or statements:") while typing do line = duck.prompt(" > ") program = program + line + duck.newline parsable = duck.parses(program) if parsable == 1 then typing = false else if parsable == -1 then duck.println("Syntax error.") duck.print(duck.newline) program = "" end loop expr = eval(program) if expr or Type(expr) != 'NIL' then duck.print(">> ") duck.println(expr) end duck.print(duck.newline) loop 

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

Часть 8: Библиотека

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

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

Способ взаимодействия нашей библиотеки с утиным языком относительно прост. При запуске язык будет связывать библиотеки. Входящие в его дистрибутив. На этом этапе библиотека имеет возможность создавать крючки для своих общих функций. Данных и постоянных данных. Функции интегрируются путем предоставления сначала указателя на процедуру. А затем списка именованных параметров. Поскольку мы допускаем передачу объектов любого типа в качестве переменных. Нашему внешнему коду придется извлекать объекты-ЗНАЧЕНИЯ и обрабатывать их вручную.

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

Часть 9: Сборщик Мусора

Учитывая все эти проблемы. В той или иной степени. Мы должны рассмотреть нашу программу. Интерпретатор и его объем памяти. При первой реализации среды выполнения языка программирования имеет смысл переопределить распределители по умолчанию. Malloc и free. С помощью нашего собственного распределителя и деаллокатора. Это позволяет нам отслеживать использование памяти и освобождать посторонние данные при выходе из среды.

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

Существует ряд схем. Которые мы можем использовать для отслеживания и освобождения динамических объектов. Большинство из которых называются Мы хотим обеспечить наших программистов автоматическим управлением памятью. Поэтому эту область мы должны исследовать. Есть несколько способов справиться с этим. И мы рассмотрим их плюсы и минусы.

Наивно полагать. Что одним из лучших способов освобождения переменных по требованию может быть подсчет ссылок. Учитывая динамический объект. Такой как массив, мы знаем. Что при его создании он имеет 1 ссылку. Которая является любой областью действия или временным значением. В котором он находится. Если значение отбрасывается или наш глобальный регистр перезаписывается. То он имеет 0 ссылок и должен быть освобожден. Если она назначена именованной переменной. То число ее ссылок увеличивается. А если она назначена нескольким именованным переменным. То снова увеличивается. Если область действия или контекст. Содержащий эти ссылки. Будет уничтожен. То его счетчик ссылок будет уничтожен. уменьшается. Пока, наконец. Если последняя ссылка на объект потеряна. Он должен быть уничтожен или освобожден.

Существует ряд преимуществ подсчета ссылок как метода сбора мусора. Прежде всего. Он не требует остановки выполнения для восстановления памяти. Это то. Что происходит автоматически. Когда объекты входят в область видимости и выходят из нее. Он также относительно прост для понимания и должен быть прост в реализации.

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

Что приводит нас к следующей форме сбора мусора: сборщик мусора трассировки. Этот метод включает в себя сначала хранение списка каждого динамического значения. Каждой динамической строки. Каждого контекста. Каждой функции и каждого словаря или хэш-таблицы с момента их выделения. Это не обязательно должен быть список. Это может быть любая структура данных. Которая позволяет нам находить и находить элементы. А также перебирать каждый из них. Что мы будем делать. Так это время от времени. Когда наша программа работает. Мы будем останавливать выполнение. Затем мы рассмотрим все переменные. Которые в настоящее время запущенная программа имеет доступ ко всему стеку вызовов. Включая весь стек вызовов. Это должно включать локальные переменные. Глобальные переменные. Любой объект. Который ссылается на другую переменную. И любые функции. Которые могут получить доступ к заданному контексту или закрытию при выполнении. Когда все. Что еще Все. Что мы не идентифицировали, теперь

Этот метод также имеет ряд плюсов и минусов. Это требует случайной остановки программы. Известной как сборщик мусора stop-the-world. Что может нанести ущерб некоторым приложениям. Кроме того, это может потребовать дополнительной предварительной реализации. Поскольку она включает в себя отслеживание большого количества объектов и всех их взаимодействий. Однако, оказавшись на месте. Это очень эффективный способ освободить память. Которая способна находить мертвые ссылки. Включая циклические ссылки. Это также очень закулисно. Пока распределение отслеживается.

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

Конечные примечания

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

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

С точки зрения мощности нашего генератора синтаксического анализа. Мы можем анализировать ранние Java-программы. Начиная с версии 1.0. Это происходит потому. Что язык изначально был разработан как грамматика LR(1) или полностью детерминированная. Более поздние функции изменили это. Например C и C++. Которые также не являются строго контекстно-свободными. Это проблемы. Но они не являются непреодолимыми и обычно требуют добавления нескольких дополнительных этапов или шагов к нашему конвейеру лексики и синтаксического анализа. Дополнения, такие как препроцессор и постпроцессор. В основном помогли бы нам с этой задачей.

Итак, мы уже видим. Как можно создать такой язык. Как Cscript. Который может сам запускать программы на языке Си. Выполняя их в интерпретаторе. Это просто показывает. Насколько интересным может быть дизайн языка программирования. Даже не рассматривая его практическое применение.

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

В конечном счете. Если мы хотим пойти глубже, чем это. Нам нужно будет начать смотреть на методы компилятора. Наш язык имеет полностью динамические типы. А это означает. Что если мы выполняем даже простые операции. Нам нужно определить. С какими типами мы работаем. Если бы мы собирались начать компилировать этот код. У нас все равно было бы большое количество накладных расходов. Вместо того чтобы сложение превращалось в единый операционный код. Оно включало бы вызов функции. Которая сортировала бы для нас всю эту информацию. Хотя это все еще может быть значительно быстрее. Это представляет собой большую работу для нас. языковые дизайнеры. В качестве интересного упражнения было бы забавно попытаться скомпилировать наш язык на другой динамически типизированный скриптовый язык. Это дает нам немного больше переносимости. Позволяя нашему коду работать в большем количестве мест. Как часть дизайна языка Утки. Одно намерение состоит в том. Чтобы позволить программам работать на настольных компьютерах и в Интернете. По этой причине я реализовал интерпретатор Duck в JavaScript. Это здорово в концепции. Однако это не достигает 100% производительности. Отличным следующим шагом было бы реализовать наши общие библиотеки в JavaScript. А затем предложить способ кросс-компиляции программ.

Хотя это был бы интересный проект, я уверен. Что мы все задаемся вопросом. Можем ли мы теперь создать наш собственный статический язык. Одним из важных шагов в постоянном совершенствовании языка и шагом к тому. Чтобы сделать его более независимым. Является способность к самостоятельному использованию. Нашему утиному языку не хватает ресурсов. Чтобы написать сам Утиный интерпретатор. Но при этом он все еще полезен с точки зрения производительности. Хотя это, безусловно. Было бы возможно. Это было бы бесполезно. Вместо этого нам придется начать с самого начала для этого проекта. Пожалуйста, см. раздел Разработка языка программирования: II,

Желаю удачи.

Рекомендации

Легендарные

Книга о Зеленом драконе Книга Красного Дракона

[1] Альфред Ахо и Джеффри Уллман.

[2] Альфред Ахо. Рави Сети и Джеффри Уллман.

[3] Официальный Сайт Языка программирования Duck

[4] Генератор синтаксического анализа языка программирования Duck

[5] Кит Купер и Линда Торчон. Morgan Kaufmann 2011.

[6] CSSE 304 и CSSE 404