Какие языки программирования не имеют контекста?

Ответ 1

Набор синтаксически корректных программ не имеет контекста для почти всех языков.

Набор программ, которые компилируются, не является контекстным для почти всех языков. Например, если набор всех компиляционных программ на C был свободным от контекста, то, пересекаясь с обычным языком (также называемым регулярным выражением), набор всех компилирующих программ на C, которые соответствуют

^int main\(void\) { int a+; a+ = a+; return 0; }$

будет контекстно-свободным, но это, очевидно, изоморфно языку a ^ kba ^ kba ^ k, который хорошо известен как неконтекстно-свободный.

Ответ 2

Какие языки программирования не имеют контекста? [...]

TL; DR: Вряд ли, но Brainfuck и Калькулятор комбинаторов SKI - это два из-за простоты их синтаксиса.

Более длинная версия: Вряд ли, но это зависит. Обычно контекстно-свободные грамматики (CFG) используются только для грубого определения синтаксиса языка. Нужно различать синтаксически правильные программы и программы, которые компилируются. Чаще всего компиляторы разбивают анализ языка на синтаксический анализ, который строит и проверяет общую структуру фрагмента кода и семантический анализ, который проверяет смысл программы.

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

Моя кишка говорит мне, что функциональные языки могут быть контекстными [...]

Здесь CFG для императивного языка Brainfuck:

Program → Instr Program | ε
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Prog ']'

И здесь CFG для функционального расчёта комбинатора SKI:

Program → E
E → 'S' E E E
E → 'K' E E
E → 'I'
E → '(' E ')'

Независимо от того, является ли язык контекстом или нет, он не имеет никакого отношения к тому, что он является функциональным. Это просто вопрос о том, насколько сложны языковые правила и функции для анализа.

Если, с другой стороны, "контекстно-свободный язык" означает только "... для которого все программы передают синтаксический анализ", ответ заключается в том, насколько сложным является только синтаксис. Существует много синтаксических признаков, которые трудно или невозможно описать только с помощью CFG. Некоторые из них преодолеваются путем добавления дополнительного состояния для парсеров для отслеживания счетчиков, поисковых таблиц и т.д.

Примеры синтаксических признаков, которые невозможно выразить с помощью CFG:

• Высокие отступы и языки с прописными буквами, такие как Python и Haskell. Отслеживание произвольно вложенных уровней отступов в основном зависит от контекста и требует отдельного счетчика для уровня отступов. (Разрешение только фиксированного уровня отступов будет работать путем дублирования грамматики для каждого уровня отступов.)

• C Typedef Parsing Problem говорит, что программы C неоднозначны во время лексического анализа, потому что он не может знать только из грамматики, если что-то является регулярным идентификатором или псевдонимом typedef для существующего типа.

• Языки, основанные на макро и шаблонах, такие как Lisp, С++, Template Haskell, Nim и т.д. Поскольку синтаксис изменяется по мере его разбора, одно решение состоит в том, чтобы сделать синтаксический анализатор в программу самомодификации. Как выражено в ответе на вопрос Является ли С++ контекстно-зависимым или контекстно-зависимым?, ответ не является ни тем.

Пример синтаксического признака, который можно выразить как CFG, но часто это не так:

• Часто приоритет и ассоциативность операторов не выражаются непосредственно в CFG. Например, CFG для небольшой грамматики выражений, где × связывает более жесткие, чем +, может выглядеть так:

  E → E ^ E
  E → E × E
  E → E + E
  E → (E)
  E → num
  

  Этот CFG ambiguous, но часто сопровождается таблица приоритетов/ассоциативности, например, например что ^ связывает сжатие, × связывает более жесткие, чем +, что ^ является право-ассоциативным и что × и + являются лево-ассоциативными.

  Приоритет и ассоциативность могут быть закодированы в 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 могут создавать более эффективные парсеры устраняют конфликты сдвига/уменьшения вместо того, чтобы иметь дело с однозначной, преобразованной грамматикой большего размера.

В теории все конечные множества строк являются регулярными языками, поэтому все законные программы ограниченного размера регулярны. Поскольку обычные языки являются подмножеством контекстно-свободных языков, все программы ограниченного размера не имеют контекста. Аргумент продолжается,

Хотя можно утверждать, что было бы приемлемым ограничением для языка, позволяющего использовать только программы с меньшим чем миллионом строк, не представляется возможным описать язык программирования как обычный язык: описание будет слишком большим.
    - nbsp; 2.10.2

То же самое касается CFG. Чтобы решить свой подзапрос несколько иначе,

Какие языки программирования определены без контекстной грамматики?

Большинство языков программирования в реальном мире определяются их реализациями, и большинство парсеров для реальных языков программирования либо написаны вручную, либо использует генератор синтаксического анализатора, который расширяет контекстно-свободный синтаксический анализ. К сожалению, это не так часто, чтобы найти точный CFG для вашего любимого языка. Когда вы это делаете, обычно это форма Бэксу-Наура (BNF) или спецификация парсера, которая скорее всего не является чисто контекстно-свободным.

Примеры грамматических характеристик дикой природы:

• BNF для стандартного ML
• BNF-like для Haskell
• BNF для SQL
• грамматика Yacc для PHP
• ... и т.д.

Ответ 3

В зависимости от того, как вы понимаете вопрос, ответ меняется. Но IMNSHO, правильный ответ, состоит в том, что все современные языки программирования на самом деле чувствительны к контексту. Например, нет никакой свободной от контекста грамматики, которая допускает только синтаксически правильные C-программы. Люди, которые указывают на бесплатные грамматики контекста yacc/bison для C, не имеют смысла.

Ответ 4

Чтобы перейти к самому драматическому примеру неконтекстно-свободной грамматики, грамматика Perl, насколько я понимаю, turing-complete.

Ответ 5

Я думаю Haskell и ML поддерживают свободный контекст. См. Ссылку для Haskell.

Ответ 6

Если я понимаю ваш вопрос, вы ищете языки программирования, которые можно описать с помощью контекстных бесплатных грамматик (cfg), чтобы cfg генерировал все действующие программы и только действующие программы.

Я считаю, что большинство (если не все) современных языков программирования не являются свободными от контекста. Например, если у вас есть определенные пользователем типы (очень распространенные в современных языках), вы автоматически настраиваете контекст.

Существует разница между проверкой синтаксиса и проверкой семантической корректности программы. Синтаксис проверки не зависит от контекста, тогда как проверка семантической корректности не является (опять же, на большинстве языков).

Это, однако, не означает, что такой язык не может существовать. Например, без описания lambda calculus можно описать с использованием контекстной свободной грамматики и, конечно же, Тьюринга завершена.

Ответ 7

VHDL несколько чувствителен к контексту.

(Google: parsing-vhdl-is-very-hard)

Ответ 8

Большинство современных языков программирования не являются контекстными языками. В качестве доказательства, если я вникаю в корень CFL, его соответствующий машинный КПК не может обрабатывать строковые сопоставления, такие как {ww | w is a string}. Поэтому большинство языков программирования требуют этого.

Пример:

int fa; // w
fa=1; // ww as parser treat it like this