Я читал, что большинство языков программирования можно анализировать как контекстно-свободную грамматику (CFG). С точки зрения вычислительной мощности он равен мощности недетерминированного автомата с выталкиванием вниз. Я прав?
Технически да. Полезно - нет.
Есть как минимум два полезных способа подумать над этими вопросами:
- Если вы думаете о наборе строк, у вас есть язык.
- Если вы думаете об алгоритме определения того, является ли строка языком или нет, у вас возникает проблема принятия решения.
Сложность состоит в том, что, хотя большинство языков программирования имеют базовую структуру, которая легко описывается контекстно-свободной грамматикой (интересным исключением является Tcl), многие предложения, описываемые контекстно-свободной грамматикой, на самом деле не находятся "в language ", где под" на языке "я имею в виду" действующая программа на рассматриваемом языке ". Эти лишние предложения обычно исключаются некоторой формой статической семантики. Например, следующее высказывание является предложением в контекстно-свободной грамматике программ 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 может быть выражена с использованием конечного последовательность цифр.
Следовательно, язык целочисленных литералов является полным по Тьюрингу.
Если сейчас голова не болит, значит, должно.
person
Norman Ramsey
schedule
01.06.2010
