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



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

из того, что я собираю C++ не является контекстно-свободным из-за таких вещей, как макросы и шаблоны. Моя интуиция говорит мне, что функциональные языки могут быть контекстно-свободными, но у меня нет никаких жестких данных для резервного копирования.

дополнительная репутация для кратких примеров : -)

119   8  

8 ответов:

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

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

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

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

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

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

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

вот 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), или спецификация парсера, которая, скорее всего, не является чисто контекстно-свободной.

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

в зависимости от того, как вы понимаете вопрос, ответ меняется. Но 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
    Ничего не найдено.

Добавить ответ:
Отменить.