Ответ 1
Я читал, что большинство языков программирования можно разобрать как свободную от контекста грамматику (CFG). В терминах вычислительной мощности он равен одному из неподдающихся детонации автоматов. Я прав?
Технически да. Использовать, нет.
Есть как минимум два полезных способа подумать об этих вопросах:
- Если вы думаете о наборе строк, у вас есть язык.
- Если вы думаете об алгоритме, чтобы решить, есть ли строка на языке или нет, у вас есть проблема с решением.
Трудность состоит в том, что, хотя большинство языков программирования имеют базовую структуру, которая легко описывается без контекстной грамматики (Tcl представляет собой интересное исключение), множество предложений, которые описываются контекстно-свободной грамматикой, на самом деле не являются "на языке" , где "на языке" я имею в виду "действительную программу на соответствующем языке". Эти дополнительные предложения обычно исключаются из некоторой формы статической семантики. Например, следующее высказывание - это предложение в контекстно-свободной грамматике программ на C, но оно не входит в набор действительных программ C:
int f(void) { return n + 1; }
Проблема здесь в том, что n не входит в объем. C требует "объявления перед использованием", и это свойство не может быть выражено с использованием контекстно-свободной грамматики.
Типичная процедура принятия решения для реального языка программирования является частью переднего конца компилятора или интерпретатора и имеет по крайней мере две части: один, синтаксический анализатор, эквивалентен в силе принятия решения автоматом pushdown; но второй выполняет дополнительные проверки, которые исключают многие высказывания как недействительные. Если для этих проверок требуется какое-либо свойство определения перед использованием, они не могут быть выполнены автоматом pushdown или неконтекстно-грамматикой.
Если это правда, тогда как CFG может хранить неограниченную грамматику (UG), которая завершена?
CFG не "держит" что-нибудь, просто описывает язык.
... даже если языки программирования описаны CFG, они фактически используются для описания машин для turing, и поэтому через UG.
Вы пропускаете некоторые важные уровни косвенности здесь.
Я думаю, что из-за, по крайней мере, двух разных уровней вычислений, первый, который является синтаксическим анализом CFG, фокусируется на синтаксисе, связанном со структурой (представлением?) языка, в то время как другой фокусируется на семантике ( смысл, интерпретация самих данных?), связанные с возможностями языка программирования, который полностью завершен. Опять же, правильны ли эти предположения?
Они кажутся мне немного запутанными, но ты на правильном пути. Ключевой вопрос: "Какая разница между языком и языком программирования?" Ответ заключается в том, что язык программирования имеет вычислительную интерпретацию. Вычислительные интерпретации встречаются во многих прекрасных вариантах, и не все из них являются Тьюрингом. Но магия в интерпретации, а не в синтаксисе, поэтому иерархия Хомского здесь не очень важна.
Чтобы доказать свою точку зрения, крайний пример: регулярный язык [1-9][0-9]* является полным Тьюринга при следующей интерпретации:
- Язык SK-combinator полностью завершен Turing.
- Существует только счетное количество программ SK.
- Они легко могут быть перечислены однозначно и детерминистически.
- Поэтому мы можем связать каждое положительное целое с программой SK.
- Если мы интерпретируем последовательность цифр как положительное целое стандартным способом, мы можем одинаково хорошо интерпретировать одну и ту же последовательность цифр как SK-программу, и, кроме того, любая программа SK может быть выражена с использованием конечной последовательности цифр.
Следовательно, язык целочисленных литералов является Тьюрингом-полным.
Если ваша голова не болит сейчас, она должна.