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

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

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

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

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

Компиляторы и интерпретаторы

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

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

Простая Схема Компиляции

Моя цель-заставить

Интерпретация-это процесс выполнения кода в исходном файле более или менее непосредственно. Я позволю тебе думать. Что это волшебство.

Итак, как вы переходите от простого для чтения исходного языка к трудному для понимания целевому языку?

Фазы компилятора

Компилятор может быть разделен на фазы различными способами. Но есть один способ. Который наиболее распространен.

Это имеет лишь небольшое количество смысла. Когда вы видите его в первый раз. Но вот оно идет:

Поддельные фазы компилятора

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

Лексический анализ

ОН ЖЕ

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

 // source.ect 3 + 3.2; 5.0 / 1.9; 6 * 2; 

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

Как это делается на самом деле. Довольно просто: дайте лексеру (менее претенциозно звучащему способу сказать лексический анализатор) какой-то материал. Которого следует ожидать. А затем скажите ему. Что делать. Когда он увидит этот материал. Это называется правилами. Вот вам пример:

int cout  "I see an integer!"  endl; 

Когда int проходит через лексер и это правило выполняется. Вы будете встречены вполне очевидным восклицанием

Это не то, как мы будем использовать лексер. Но полезно видеть. Что выполнение кода произвольно: нет правил. По которым вы должны создать какой-то объект и вернуть его. Это просто обычный старый код. Может даже использовать более одной линии. Окружая ее скобками.

Кстати, мы будем использовать что-то под названием FLEX для нашего лексинга. Это делает вещи довольно легкими. Но ничто не мешает вам просто сделать программу. Которая делает это самостоятельно.

Чтобы понять. Как мы будем использовать flex. Посмотрите на этот пример:

 // scanner.lex /* Definitions */ %{ #include   using namespace std; extern "C" int yylex(); %} /* Rules next */ %% [0-9]+.[0-9]+ cout  "FLOAT: ("  yytext  ")"  endl; [0-9]+ cout  "INT: ("  yytext  ")"  endl; "+" cout  "PLUS"  endl; "-" cout  "MINUS"  endl; "*" cout  "TIMES"  endl; "/" cout  "DIVIDED BY"  endl; ";" cout  "SEMICOLON"  endl; [\t\r\n\f] ; /* ignore whitespace */ %% /* Code */ int main() { yylex(); } 

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

%% используется для разделения разделов файла .lex.

Первый раздел — это объявления-в основном переменные. Чтобы сделать лексер более читабельным. Это также место. Где вы импортируете. Окруженный %{и %}.

Вторая часть-это правила. Которые мы видели раньше. Это в основном большой if else ifблок. Он выполнит строку с самым длинным совпадением. Таким образом. Даже если вы измените порядок float и int. Поплавки все равно будут совпадать. Так как совпадение 3 символов3.2-это больше. Чем 1 символ 3. Обратите внимание. Что если ни одно из этих правил не совпадает. Он переходит к правилу по умолчанию. Просто печатая символ в стандартную форму.

Затем вы можете использовать yytextдля ссылки на то. Что он видел. Что соответствовало этому правилу.

Третья часть-это код. Который представляет собой просто исходный код C или C++. Который запускается при выполнении. yylex(); это вызов функции. Которая запускает лексер. Вы также можете заставить его читать входные данные из файла. Но по умолчанию он читает из стандартного ввода.

Допустим, вы создали эти два файла как source.ectи scanner.lex. Мы можем создать программу на C++ с помощью flexкоманды (если вы flexее установили). Затем скомпилировать ее и ввести наш исходный код. Чтобы получить наши потрясающие инструкции печати. Давайте приведем это в действие!

evan:ectlang/ $ flex scanner.lex evan:ectlang/ $ g++ lex.yy.c -lfl evan:ectlang/ $ ./a.out (3) PLUS FLOAT: (3.2) SEMICOLON FLOAT: (5.0) DIVIDED BY FLOAT: (1.9) SEMICOLON INT: (6) TIMES INT: (2) SEMICOLON evan:ectlang/ $  

Эй, круто! Вы просто пишете код C++. Который соответствует входным данным правилам. Чтобы что-то сделать.

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

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

ОН ЖЕ

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

В основном грамматики сопоставляют нетерминальные символы с некоторой комбинацией терминальных и нетерминальных символов. Терминалы-это листья дерева; у не-терминалов есть дети. Не беспокойтесь об этом. Если это не имеет смысла. Код, вероятно. Будет более понятным.

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

 // parser.y %{ #include   using namespace std; extern "C" void yyerror(char *s); extern "C" int yyparse(); %} %union{ int intVal; float floatVal; } %start program %token intVal> INTEGER_LITERAL %token floatVal> FLOAT_LITERAL %token SEMI %type floatVal> exp %type floatVal> statement %left PLUS MINUS %left MULT DIV 

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

Объединение-это сопоставление Итак. Когда мы видим intVal, вы можете заменить это в своей голове int, а когда мы видим floatVal, вы можете заменить это в своей голове float. Позже ты поймешь почему.

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

Каждое объявление (начиная с %) объявляет некоторый символ. Во-первых, мы видим. Что начинаем с нетерминального program. Затем мы определяем некоторые маркеры. Скобки определяют тип возврата: таким INTEGER_LITERALобразом. Терминал возвращает an intVal. SEMIТерминал ничего не возвращает. Аналогичная вещь может быть сделана с использованием нетерминалов type, как это видно при определении expкак нетерминала. Возвращающего a floatVal.

Наконец мы переходим к старшинству. Мы знаем PEMDAS. Или любую другую аббревиатуру. Которую вы. Возможно, узнали. Которая говорит вам о некоторых простых правилах приоритета: умножение предшествует сложению и т. Д. Теперь мы заявляем об этом здесь странным образом. Во-первых, чем ниже в списке. Тем выше приоритет. Во-вторых, вы можете задаться вопросом. Что leftэто значит. Это ассоциативность: в значительной степени. Если мы имеем a op b op c, делаем aи bидем вместе, или. Может bбыть, и c? Большинство наших операторов делают первое. Куда aи bидут вместе в первую очередь: это называется левой ассоциативностью. Некоторые операторы. Такие как возведение в степень. Делают обратное: a^b^cожидают. Что вы поднимете b^cтогда a^(b^c) Однако мы не будем этим заниматься. Посмотрите на страницу Bison. Если вы хотите больше подробностей.

Ладно, я, наверное. Наскучил вам декларациями. Вот правила грамматики:

 // parser.y %% program: /* empty */ | program statement { cout  "Result: "  $2  endl; } ; statement: exp SEMI exp: INTEGER_LITERAL { $$ = $1; } | FLOAT_LITERAL { $$ = $1; } | exp PLUS exp { $$ = $1 + $3; } | exp MINUS exp { $$ = $1 - $3; } | exp MULT exp { $$ = $1 * $3; } | exp DIV exp { $$ = $1 / $3; } ; 

Это грамматика. О которой мы говорили раньше. Если вы не знакомы с грамматикой. Это довольно просто: левая сторона может превратиться в любую из вещей на правой стороне. Разделенных |(логическим or). Если он может идти по нескольким путям. Это нет-нет. Мы называем это двусмысленной грамматикой. Это не двусмысленно из — за наших деклараций приоритета-если мы изменим его так . Чтобы плюс больше не был левым ассоциативным. А вместо этого был объявлен как tokenlikeSEMI, мы увидим. Что получаем конфликт shift/reduce. Хотите узнать больше? Посмотрите, как работает Bison, подсказка. Он использует алгоритм разбора LR.

Хорошо, так expможет стать одним из таких случаев: an INTEGER_LITERAL, a FLOAT_LITERALи т. Д. Обратите внимание. Что это также рекурсивно. Поэтому expможет превратиться в два exp. Это позволяет использовать сложные выражения. Например 1 + 2 / 3 * 5. expПомните . Что каждый из них возвращает тип float.

То, что находится внутри скобок. То же самое. Что мы видели с лексером: произвольный код C++. Но с более странным синтаксическим сахаром. В этом случае перед нами стоят специальные переменные $. Переменная$$-это в основном то. Что возвращается. $1 это то. Что возвращается первым аргументом, то, $2что возвращается вторым и т. Д. Под exp PLUS expимеет аргумент 1 exp, аргумент 2 PLUSи аргумент 3 exp. Итак, при выполнении кода мы добавляем результат первого выражения к третьему.

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

Теперь давайте напишем кодовую часть. Это то. Что на самом деле будет запущено. Когда мы пройдем через парсер:

 // parser.y %% int main(int argc, char **argv) { if (argc  2) { cout  "Provide a filename to parse!"  endl; exit(1); } FILE *sourceFile = fopen(argv[1], "r"); if (!sourceFile) { cout  "Could not open source file "  argv[1]  endl; exit(1); } // Sets input for flex to the file instead of standard in yyin = sourceFile; // Now let's parse it! yyparse(); } // Called on error with message s void yyerror(char *s) { cerr  s  endl; } 

Ладно, это начинает становиться интересным. Наша основная функция теперь читает из файла. Предоставленного первым аргументом. А не из стандартного in. И мы добавили некоторый код ошибки. Это довольно самоочевидно. И комментарии хорошо объясняют. Что происходит. Поэтому я оставлю это как упражнение для читателя. Чтобы понять это. Все, что вам нужно знать, это то. Что теперь мы вернулись к лексеру. Чтобы предоставить токены парсеру! Вот наш новый лексер:

 // scanner.lex %{ extern "C" int yylex(); #include "parser.tab.c" // Defines the tokens  %} %% [0-9]+ { yylval.intVal = atoi(yytext); return INTEGER_LITERAL; } [0-9]+.[0-9]+ { yylval.floatVal = atof(yytext); return FLOAT_LITERAL; } "+" { return PLUS; } "-" { return MINUS; } "*" { return MULT; } "/" { return DIV; } ";" { return SEMI; } [ \t\r\n\f] ; /* ignore whitespace */ 

Эй, теперь он действительно стал меньше! Мы видим. Что вместо печати мы возвращаем терминальные символы. Некоторые из них. Такие как ints и floats. Мы сначала устанавливаем значение. Прежде чем двигаться дальше (yylval это возвращаемое значение терминального символа). Кроме того, он просто дает парсеру поток терминальных токенов для использования по своему усмотрению.

Круто, тогда давай запустим его!

evan:ectlang/ $ bison parser.y evan:ectlang/ $ flex scanner.lex evan:ectlang/ $ g++ lex.yy.c -lfl evan:ectlang/ $ ./a.out source.ect Result: 6.2 Result: 2.63158 Result: 12 

Ну вот и все — наш парсер печатает правильные значения! Но на самом деле это не компилятор. Он просто запускает код C++. Который выполняет то. Что мы хотим. Чтобы создать компилятор. Мы хотим превратить его в машинный код. Для этого нам нужно добавить еще немного…

До Следующего Раза…

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

Я поместил исходный код на свой Github, если вам интересно увидеть конечный продукт. По мере того. Как будет выпущено больше сообщений. Это репо будет видеть больше активности.

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

Часть 2 уже готова!

Дополнительные Ресурсы

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

  • Кодовая база Flex: https://github.com/westes/flex — инструмент лексического анализа. Который мы использовали.
  • Документация Зубра: https://www.gnu.org/software/bison/ — генератор парсера. Который мы использовали. Потрясающая документация здесь.
  • Разбор LALR: https://web.cs.dal.ca/~sjackson/lalr1.html — хорошо сделанное объяснение того. Как LALR(1) парсеры (например. Тогенерирует Bison!) работа.
  • Разрешение конфликтов синтаксического анализа: http://www.cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/conflict.html — как исправить сдвиг/уменьшение или уменьшить/уменьшить конфликты, как тот. Который мы видели раньше.
  • Иерархия Хомского: https://en.wikipedia.org/wiki/Chomsky_hierarchy — я не вдавался в подробности. Но мы использовали контекстно-свободную грамматику. Чтобы Зубр мог ее скомпилировать. Если вам нужна контекстная чувствительность. Это для более поздних этапов.
  • Таблица символов: https://www.tutorialspoint.com/compiler_design/compiler_design_symbol_table.htm — использование таблиц символов. Как компиляторы работают с переменными.

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

Реальные фазы компилятора