Как создаются компьютерные языки с использованием концепции теории автоматов?

Языковой дизайн, как правило, имеет два важных уровня:

1. Лексический анализ — определение того, как выглядят токены. Что такое строковый литерал, что такое число, каковы допустимые имена переменных, функций и т. д.
2. Синтаксический анализ — определение того, как токены работают вместе, чтобы сделать осмысленные утверждения. Можете ли вы присвоить значение литералу, как выглядит блок, как выглядит оператор if и т. д.

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

Входными данными для этапа лексирования являются необработанные символы исходного кода. Таким образом, алфавит будет ASCII или Unicode или любой другой ввод, который ожидает ваш компилятор. Результатом является поток токенов с метаданными, такими как string-literal (value: hello world), которые могут представлять "hello world" в исходном коде.

Синтаксический анализ обычно выполняется с использованием подмножества контекстно-свободных языков, называемых LL или LR парсеры. Это связано с тем, что реализация CFG (PDA) недетерминирована. Анализ LL и LR — это способы принятия детерминированных решений относительно того, как анализировать данное выражение.

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

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

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

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

В более общем смысле мы говорим о теории вычислений.

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

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

Статья в Википедии о структурированном программировании рассказывает часть истории.

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