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

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

Мой вопрос, как именно языки программирования связаны с формальными языками? Везде, где я читаю, говорится что-то вроде «формальные языки используются для определения грамматики языков программирования».

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

b -> a

aaa->c

Это можно применять так, чтобы:

abab->aaaa aaaa-> ca

Как примечание: если мы определим, что алфавит нашего формального языка как {a, b, c}, то a и b не являются терминалами, а c является терминальным, поскольку его нельзя преобразовать (пожалуйста, исправьте меня, если я ошибаюсь по поводу что).

Итак, учитывая все это, как это применимо к языкам программирования? Часто также утверждается, что регулярное выражение используется для анализа языка в его текстовой форме, чтобы убедиться в правильности грамматики. Это имеет смысл. Затем утверждается, что регулярные выражения определяются формальными языками. Регулярное выражение возвращает true или false (по моему опыту, по крайней мере) в зависимости от того, достигают ли конечные автоматы, которые представляют регулярное выражение, целевую точку. Насколько я понимаю, это не имеет ничего общего с трансформациями *.

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

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

* Если вы не считаете что-то похожим (a|b)*b*c->trueна производственное правило, в этом случае правило требует автоматов с конечным состоянием (например, регулярное выражение). Это не имеет смысла, так как мы только что сказали

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

1. Лексический анализ: обрабатывает необработанный текст на куски, такие как ключевые слова , числовые константы , строки , идентификаторы и так далее. Это классически реализовано с использованием некоторого типа конечного автомата, похожего по духу на детерминированный конечный автомат (DFA).

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

$\to$$\to$$\to$

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

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

Это тяжелый материал для школьного задания.

Ответ Ювала Фильмуса действительно хорош, так что это скорее дополнительный ответ, чтобы прояснить некоторые из высказанных им замечаний.

Формальный язык - это математическая конструкция. Их использование для языков программирования является лишь одним из многих возможных применений; фактически лингвист Ноам Хомский внес значительный вклад в раннюю теорию формальных языков. Он изобрел Хомскую Иерархию, который классифицирует формальные языки на регулярные, контекстно-свободные и т. д. Формальные языки также применяются в лингвистике для описания синтаксиса естественных языков, таких как английский. Думайте об этом как о действительных числах: мы можем использовать действительные числа, чтобы описать как конкретные вещи, такие как расстояние от Лос-Анджелеса до Нью-Йорка, так и абстрактные вещи, такие как отношение длины окружности к ее диаметру. Хотя обе эти вещи существуют независимо от действительных чисел, действительные числа являются полезной системой для их описания. Формальные языки являются полезной системой для описания как английского, так и Python, потому что оба имеют схожий структурированный формат.

$a + b + c = d$$a + b = d - c$$a$$b$$c$ например, в долларах, а затем уравнение имеет значение.

Классически, язык программирования будет иметь две грамматики: лексическая грамматика и синтаксическая грамматика. Лексическая грамматика имеет дело с такими символами, как буквы, точки с запятой, фигурные скобки и скобки. Обычно это обычная грамматика, поэтому она может быть выражена с помощью регулярных выражений или DFA или NFA. (Существуют доказательства в теории формального языка, показывающие, что эти три эквивалентны по мощности - это означает, что они принимают один и тот же набор языков.) Фаза лексинга компилятора или интерпретатора является своего рода мини-интерпретатором для грамматики обычного языка. Он читает правила грамматики и, следуя этим правилам, объединяет отдельные символы в токены. Например, если язык имеет ifутверждение , что выглядит более или менее как Кассиопеян, лексер может причислить символы iи fв единый знакIFЗатем найдите открывающую скобку и выведите токен OPEN_PAREN, затем обработайте все, что находится между скобками, а затем найдите закрывающую скобку и выведите a CLOSE_PAREN. Когда лексер завершил создание токенов, он передает их парсеру, который определяет, действительно ли токены формируют допустимые операторы языка программирования. Так что, если вы пишете ip a == bна Python, лексер просто делает все возможное, чтобы угадать, что это за токен ip(вероятно, он будет использоваться для идентификатора большинством лексеров), и передает его анализатору, который жалуется, потому что вы не можете иметь идентификатор в этой позиции.

$a \rightarrow b$

Давайте посмотрим на правила грамматики для ifзаявления Python . Это правило:

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

Это правило говорит нам, как синтаксический анализатор будет выяснять, является ли строка токенов, отправленных ifлексером, -составлением. Любое слово в одинарных кавычках должно появляться в исходном коде, поэтому парсер будет искать простое слово if. Затем парсер попытается сопоставить некоторые токены с правилом для test:

test: or_test ['if' or_test 'else' test] | lambdef

testопределяется в терминах других правил в грамматике. Обратите внимание, как testтакже включает себя в своем определении; это называется рекурсивным определением. Это большая мощь контекстно-свободных языков, которых нет в обычных языках, и она позволяет определять такие вещи, как вложенные циклы для синтаксиса языка программирования.

Если парсер удастся сопоставить несколько токенов test, он попытается сопоставить двоеточие. Если это удастся, он попытается сопоставить еще несколько токенов, используя правило для suite. Раздел ('elif' test ':' suite)*означает, что мы можем иметь любое количество повторений буквального текста elif, за которым следует что-то, что соответствует test, затем двоеточие, а затем что-то, что соответствует suite. Мы также можем иметь ноль повторений; звездочка в конце означает «ноль или столько, сколько мы хотим».

В самом конце есть ['else' ':' suite]. Эта часть заключена в квадратные скобки; это означает, что у нас может быть ноль или один, но не больше. Чтобы соответствовать этому, синтаксический анализатор должен соответствовать буквальному тексту else, двоеточию, а затем a suite. Вот правило для suite:

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

Это в основном блок в C-подобных языках. Поскольку Python использует строки и отступы для средних вещей, лексер выходы NEWLINE, INDENTи DEDENTлексемы сказать анализатор , где новая линия начала, где запущен код с отступом, и где он был возвращен на внешний уровень отступа.

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

В качестве упражнения я бы порекомендовал взять грамматику некоторого языка программирования, с которым вы знакомы (опять же, Python , Java , а также C # , Javascript , C ), и попытаться разобрать что-то простое, например, может быть x = a + b;или if (True): print("Yay!"). Если вы ищете что-то более простое, есть также хорошая грамматика для JSON , которая в основном охватывает только синтаксис литералов объектов в Javascript (например {'a': 1, 'b': 2}). Удачи, это умопомрачительный материал, но он оказывается действительно интересным, когда вы не в какой-то сумасшедший срок.

В двух словах

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

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

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

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

С гораздо большим количеством деталей

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

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

Слова - это синтаксические объекты, представляющие более или менее элементарные семантические понятия. Но эти элементарные понятия должны быть объединены различными способами, чтобы придать более сложный смысл. Мы пишем, the dogчтобы передать, что мы имеем в виду конкретную собаку, и the dog bites the catпередать более сложную идею. Но то, как слова организованы, должно быть зафиксировано правилами, чтобы мы могли определить, какая из собак и кошек на самом деле кусает другую.

Таким образом, у нас есть такие правила sentence -> subject verb complement, которые должны соответствовать предложениям и сообщать нам, как сформулированы идеи, связанные с каждой частью. Эти правила являются синтаксическими правилами, так как они говорят нам, как должно быть организовано представление нашего сообщения. Сам subjectможет быть определен правилом subject -> article nounи так далее.

$2x+1=23$$x$$1$$23$

equation -> expression "=" expression  
expression -> expression "+" expression 
expression -> number

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

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

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

То же самое относится и к словам. Некоторые последовательности букв (или звука) являются допустимыми словами, а другие - нет.

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

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

Структура слов довольно проста в большинстве языков (программирования или естественных), так что они обычно определяются с помощью того, что обычно считается самым простым видом формального языка: обычными языками. Они могут быть определены с помощью регулярных выражений (regexp) и довольно легко идентифицируются с помощью запрограммированных устройств, называемых конечными автоматами. В случаях языков программирования примерами слова являются идентификатор, целое число, строка, действительное число, зарезервированное слово, такое как if или repeat, символ пунктуации или открытая скобка. Примерами семейств слов являются идентификатор, строка, целое число.

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

statement -> assignment
statement -> loop
loop ->  "while" expression "do" statement
assignment -> "identifier" "=" expression
expression -> "identifier"
expression -> "integer"
expression -> expression "operator" expression

С такими правилами вы можете написать:

while aaa /= bbb do aaa = aaa + bbb / 6 что является заявлением.

И способ его создания может быть представлен древовидной структурой, называемой деревом разбора или синтаксическим деревом (здесь не полный):

                          statement
                              |
            _______________  loop _______________
           /      /                 \            \
      "while" expression           "do"       statement
       __________|_________                       |
      /          |         \                  assignment
 expression "operator" expression          _______|_______
     |           |          |             /       |       \
"identifier"   "/="   "identifier" "identifier"  "="   expression
     |                      |            |                 |
    aaa                    bbb          aaa             ... ...

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

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

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

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

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

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

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

Например, предложение the dog bites the catможет быть проанализировано с помощью правила sentence -> subject verb complement. Зная значение этих 3 поддеревьев subject, verbи complementправило, которое их составляет, говорит нам, что субъект выполняет действие и что укушен кот.

Это только интуитивное объяснение, но оно может быть формализовано. Семантика построена вверх от составляющих. Но это скрывает много сложности.

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

Есть существенные различия. Главным из них, я бы сказал, является то, что синтаксический анализ реальных языков программирования - это обработка синтаксических ошибок. С формальным языком вы бы просто сказали «ну, это не на языке», но компилятор, который говорит, что это не очень полезно - он должен сказать вам, что не так, и если это была маленькая ошибка, в идеале продолжайте синтаксический анализ, чтобы он мог сообщить больше ошибок. Много исследований (и усилий по внедрению) идет в это. Так что на самом деле вас даже не волнует истинный / ложный результат, вы просто хотите проанализировать структуру входных данных. Формальные языки здесь используются в качестве инструмента, и они во многом совпадают, но вы действительно решаете другую проблему.

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

Формальный язык - это набор слов, где слово - это строка символов из некоторого алфавита.

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

Таким образом, обычный язык, соответствующий выражению (a|b)*c*d, определяется правилами производства;

S->ACd
A->
A->aA
A->bA
C->
C->cC

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

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

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

Таким образом, существует много общего между алгеброй регулярных выражений и алгеброй команд. Это подробно исследовано Дейкстрой в «Объединении трех исчислений». Это также основа CCS Милнера, которая дает ответ на вопрос: что, если мы добавим параллелизм?