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

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

пример: все ли языки программирования / написания сценариев являются контекстно-свободными грамматиками? Java основана на CFG, но действительно ли это так, что все языки программирования основаны на CFG?

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

Некоторый контекст для вопроса: я смотрел на спецификацию языка Java, которая также предоставляет правила грамматики . Это заставило меня задуматься над этим вопросом.

Два раза нет.

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

class A {
  String a = "a";
  int b = a + d;
}

является синтаксически правильной Java-программой, но не будет компилироваться, потому что dне определена и aне имеет подходящего типа.

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

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

Разбор perl не решаем.

http://www.jeffreykegler.com/Home/perl-and-undecidability/perl-and-undecidability-files/TPR3.pdf?attredirects=0

http://www.perlmonks.org/?node_id=663393

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

Точнее, кажется, что существует гомоморфизм из языка блоков Python вида

если условие:
     линия 1
     line2
     line3
еще:
     строка4

$0^n10^n10^n$

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

http://wwwhome.math.utwente.nl/~mantheyb/journals/BotEATCS_BoehmeManthey_CompilingCPP.pdf

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

int myfun(int a) { ... }
int myfun(int a, int b) { ... }
int myfun(int a, int b, int c, ...) { ... }
...
int I_m_I_cfg = myfun(1,2);
...

Я сделал небольшой поиск в Google и обнаружил эту статью: « Булева грамматика для простого булева языка » А. Охотина (2004); по его словам, реальная проблема заключается в том, чтобы найти язык программирования, который полностью описывается формальной грамматикой:

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

Раздел «Введение» статьи является коротким, но очень понятным.

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

Языки, основанные на отступах, не являются, естественно, свободными от контекста, как сказал Дэвид, но они становятся контекстно-свободными по отношению к параметризованному токену отступа.

Haskell позволяет изменять приоритет операторов с помощью infix и infixl. Модуль строгой прагмы в Perl реализован с использованием лексических настроек $ ^ H и% ^ H, которые делают его неконтекстным, возможно, и другие настройки.

Существуют языки расширения макросов, такие как TeX, в которых синтаксический анализ afaik не имеет смысла без выполнения.

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

Ява и ассемблер, вероятно, оба не зависят от контекста.

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

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

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

Однако многие языки фактически не являются контекстно-свободными (когда используются символы объявления перед использованием, например, в Java, C (++), D).

Интересный факт: у D есть полная функция времени компиляции по Тьюрингу и расширение шаблона, что делает сам язык не-разрешимым по Тьюрингу. Однако создатель языка сделал все возможное, чтобы сделать синтаксис CFG.

Что касается "Все ли языки программирования / написания сценариев являются контекстно-свободными грамматиками?" часть обеспокоена, ответ однозначный

В отношении основного вопроса «для языка, который в конечном итоге может быть скомпилирован / преобразован в инструкции системного уровня», я не знаю, почему это обязательно должен быть CFG. Тем не менее, могут быть лучшие объяснения.

Язык программирования должен основываться на некотором грамматическом формализме, примером которого является CFG. В то время как CFGs являются наиболее распространенными (и это обычно преподается на курсах по компиляции в университетах), существуют и другие формализмы, такие как грамматики синтаксического анализа, о которых вы можете прочитать больше здесь (pdf) или в Википедии для более читаемого размера.