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