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

какие языки программирования контекстно-свободной? [...]

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

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

вот CFG для важно язык Brainfuck:

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

и вот CFG для функциональноеЛыжное комбинаторное исчисление:

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

эти CFGs признают все допустимые программы двух языков, потому что они так просты.

---

больше вариант: обычно используются только контекстно-свободные грамматики (CFGs к примерно укажите синтаксис языка. Нужно различать синтаксически корректных программ и программы, которые компилируются. Чаще всего компиляторы разбивают анализ языка на анализ синтаксис который строит и проверяет общую структуру фрагмента кода, и семантический анализ проверки смысл программы.

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

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

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

• языки, чувствительные к отступам и пробелам, такие как Python и Haskell. Отслеживание произвольно вложенных уровни отступа по существу зависят от контекста и требуют отдельных счетчиков для уровня отступа; как количество пробелов, используемых для каждого уровня, так и количество уровней.

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

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

  пример:

    typedef int my_int;
    my_int x;
  

  в точке с запятой, тип среды должен быть обновлен с записью для my_int. Но если лексер уже посмотрел вперед на my_int, он будет лексировать его как идентификатор, а не имя типа.

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

• часто приоритет оператора и ассоциативность не выражаются непосредственно в CFGs, даже если это *возможно. Например, 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₀)
  

  но неоднозначные CFGs + таблицы приоритета / ассоциативности распространены, потому что они более читаемы и потому что различные типы LR parser библиотеки генераторов могут создавать более эффективные Парсеры с помощью исключения сдвига/уменьшения конфликтов вместо того, чтобы иметь дело с однозначной, преобразованной грамматикой большего размера.

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

хотя можно утверждать, что было бы приемлемым ограничением для языка разрешать только программы менее миллиона строк, нецелесообразно описывать язык программирования как обычный язык: описание было бы слишком большой.
     - Торбен Моргенсен Основы проектирования компиляторов, гл. 2.10.2

то же самое касается CFGs. Чтобы решить ваш под-вопрос немного по-другому,

какие языки программирования определена С помощью контекстно-свободной грамматики?

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

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

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

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

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

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

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

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

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

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

VHDL несколько зависит от контекста.

(Гугл: парсинг-комплекс-это очень сложно)

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

пример:

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