иерархия chomsky и языки программирования

Я читал, что большинство языков программирования можно анализировать как контекстно-свободную грамматику (CFG). По вычислительной мощности он равен мощности недетерминированного автомата с выталкиванием вниз. Я прав?

Технически да. Полезно - нет.

Есть по крайней мере два полезных способа подумать над этими вопросами:

• Если вы думаете о наборе строк, у вас есть язык .
• Если вы думаете об алгоритме определения того, является ли строка языком или нет, у вас возникает проблема принятия решения .

Сложность состоит в том, что хотя большинство языков программирования имеют базовую структуру, которая легко описывается контекстно-свободной грамматикой (интересным исключением является Tcl), многие предложения, описываемые контекстно-свободной грамматикой, на самом деле не являются «на языке» , где под «на языке» я имею в виду «действующая программа на рассматриваемом языке». Эти лишние предложения обычно исключаются некоторой формой статической семантики . Например, следующее высказывание является предложением в контекстно-свободной грамматике программ C, но оно не входит в набор допустимых программ C:

int f(void) { return n + 1; }

Проблема здесь в том, что n не входит в область . C требует «объявления перед использованием», и это свойство не может быть выражено с помощью контекстно-свободной грамматики.

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

Если это правда, то как CFG может содержать неограниченную грамматику (UG), которая является полной по Тьюрингу?

CFG ничего не «хранит» - он просто описывает язык.

... даже если языки программирования описываются с помощью CFG, они фактически используются для описания машин Тьюринга, то есть с помощью UG.

Здесь вы пропускаете важные уровни косвенного обращения.

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

Они кажутся мне немного запутанными, но вы на правильном пути. Ключевой вопрос: «В чем разница между языком и языком программирования ?») Ответ заключается в том, что язык программирования имеет вычислительную интерпретацию .Вычислительные интерпретации бывают множества прекрасных разновидностей, и не все из них являются полными по Тьюрингу. Но магия заключается в интерпретации, а не в синтаксисе, поэтому иерархия Хомского здесь не очень актуальна.

Чтобы доказать мою точку зрения, приведу крайний пример: обычный язык [1-9] [0-9] * является полным по Тьюрингу при следующей интерпретации:

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

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

Если у тебя сейчас голова не болит, значит, должна.