Какие языки программирования не зависят от контекста? [...]
Моя интуиция говорит мне, что функциональные языки могут быть контекстно-свободными [...]
Краткая версия: Вряд ли есть какие-либо языки программирования реального мира, которые не имеют контекста в любом значении этого слова. Независимо от того, является ли язык контекстным или нет, это не имеет никакого отношения к его функциональности. Это просто вопрос того, насколько сложны языковые правила и функции для анализа.
Вот CFG для императив язык Brainfuck :
Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'
А вот CFG для функционала исчисление комбинатора SKI :
Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'
Эти CFG распознают все действительные программы двух языков, потому что они такие простые.
Более длинная версия: Обычно контекстно-свободные грамматики (CFG) используются только для примерно определения синтаксиса языка. Следует различать синтаксически правильные программы и программы, которые компилируют . Чаще всего компиляторы разделяют анализ языка на синтаксический анализ , который строит и проверяет общую структуру фрагмента кода, и семантический анализ , который проверяет значение программа.
Если под "контекстно-свободным языком" вы подразумеваете " ..., для которого все программы компилируют ", то ответ: вряд ли какой-либо. Языки, которые соответствуют этому закону, вряд ли имеют какие-либо правила или сложные функции, такие как наличие переменных, чувствительность к пробелам, система типов или любой другой контекст : информация определена в одном месте и основана на другом.
Если, с другой стороны, «контекстно-свободный язык» означает только « ..., для которого все программы проходят синтаксический анализ », ответ заключается в том, насколько сложен только синтаксис. Есть много синтаксических особенностей, которые трудно или невозможно описать одним CFG. Некоторые из них преодолеваются путем добавления дополнительного состояния к анализаторам для отслеживания счетчиков, таблиц поиска и т. Д.
Примеры синтаксических признаков, которые невозможно выразить с помощью CFG:
Языки, чувствительные к отступам и пробелам, такие как Python и Haskell. Отслеживание произвольно вложенных уровней отступа по существу зависит от контекста и требует отдельных счетчиков для уровня отступа; и сколько пробелов, которые используются для каждого уровня и сколько уровней.
Разрешение только фиксированного уровня отступа с использованием фиксированного количества пробелов будет работать путем дублирования грамматики для каждого уровня отступа, но на практике это неудобно.
Проблема синтаксического анализа Typedef говорит, что программы на C неоднозначны во время лексического анализа, потому что из одной только грамматики невозможно узнать, является ли что-то обычным идентификатором или псевдонимом typedef для существующего типа.
Пример:
typedef int my_int;
my_int x;
В точке с запятой необходимо обновить среду типов с помощью записи для my_int. Но если лексер уже посмотрел вперед на my_int, он будет использовать его как идентификатор, а не как имя типа.
Языки макросов и шаблонов, такие как Lisp, C ++, Template Haskell, Nim и т. Д. Поскольку синтаксис изменяется по мере его синтаксического анализа, одним из решений является преобразование синтаксического анализатора в самоизменяющуюся программу. Смотрите также " Является ли C ++ контекстно-зависимым или контекстно-зависимым? "
Часто приоритет оператора и ассоциативность не выражаются непосредственно в CFG, даже если это возможно . Например, CFG для грамматики небольшого выражения, где ^ связывает сильнее, чем ×, а × связывает сильнее, чем +, может выглядеть так:
E → E ^ E
E → E × E
E → E + E
E → (E)
E → num
Этот CFG является неоднозначным , однако, и часто сопровождается таблицей приоритетов / ассоциативности , например, например. ^ связывает сильнее, × связывает сильнее +, ^ ассоциируется справа, а × и + левоассоциативны.
Приоритет и ассоциативность могут быть закодированы в CFG механическим способом, так что он однозначен и создает только синтаксические деревья, где операторы ведут себя правильно. Пример этого для грамматики выше:
E₀ → EA E₁
EA → E₁ + EA
EA → ε
E₁ → EM E₂
EM → E₂ × EM
EM → ε
E₂ → E₃ EP
EP → ^ E₃ EP
E₃ → num
E₃ → (E₀)
Но неоднозначные CFG + таблицы приоритетов / ассоциативности являются общими, потому что они более читабельны и потому что различные типы LR parser библиотек генератора могут производить более эффективные синтаксические анализаторы за счет , устраняя конфликты сдвига / уменьшения вместо того, чтобы иметь дело с однозначной, преобразованной грамматикой большего размера.
Теоретически все конечные наборы строк являются регулярными языками, и поэтому все легальные программы ограниченного размера являются регулярными. Поскольку обычные языки являются подмножеством контекстно-свободных языков, все программы ограниченного размера не зависят от контекста. Аргумент продолжается,
Хотя можно утверждать, что приемлемым ограничением для языка будет разрешать только программы длиной менее миллиона строк, нецелесообразно описывать язык программирования как обычный язык: описание будет слишком большим .
- Основы проектирования компиляторов Торбена Моргенсена, гл. 2.10.2
То же самое касается CFG. Чтобы ответить на ваш подвопрос немного по-другому,
Какие языки программирования определены грамматикой без контекста?
Большинство реальных языков программирования определяются своими реализациями, и большинство синтаксических анализаторов для реальных языков программирования написаны от руки или используют генератор синтаксических анализаторов, который расширяет контекстный анализ. К сожалению, не часто можно найти точный CFG для вашего любимого языка. Когда вы это делаете, обычно это форма Бэкуса-Наура (BNF) или спецификация синтаксического анализатора, которая, скорее всего, не является чисто контекстно-свободной.
Примеры грамматических спецификаций из дикой природы: