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

Я только что узнал, что Regular Grammars имеют соответствующие Finite State Acceptors, которые будут соответствовать Regular Expressions.

Есть ли эквивалентное преобразование с Context Free Grammars? Насколько я знаю, контекстно-свободные грамматики могут быть представлены Push Down Automata, что, в свою очередь, будет соответствовать чему?

Спасибо всем, кто избавит меня от этого.


regex grammar context-free-grammar automata pushdown-automaton
person Jer Yango    schedule 02.02.2014    source источник

Ответы (4)


arrow_upward
2
arrow_downward

Из Википедии Context Free Grammar:

популярной нотацией для контекстно-свободных грамматик является Форма Бэкуса-Наура.

… точно так же, как регулярные выражения — это обозначения для обычных грамматик.

person Bergi    schedule 02.02.2014
comment
Действительно, BNF, вероятно, является эквивалентом. Может ли он также стать регулярным выражением? @Tim упомянул, что это все еще может быть регулярным выражением. - person Jer Yango; 02.02.2014
comment
Что ж, некоторые контекстно-свободные грамматики также являются регулярными, так что, по крайней мере, они могут быть представлены в виде регулярных выражений :-) То, что упомянул Тим, - это не теоретические регулярные выражения из компьютерных наук, а реализации механизмов регулярных выражений, которые часто имеют функции, выходящие за рамки обычных языков - up к рекурсии, которая действительно заставляет их соответствовать любому контекстно-свободному языку. Однако по мере увеличения сложности регулярные выражения становятся непригодными для использования, и в зависимости от информации, которую необходимо извлечь, синтаксический анализатор на основе стека обычно является лучшим выбором. - person Bergi; 02.02.2014

arrow_upward
2
arrow_downward

На самом деле, ответ все еще может быть «Regex».

Современные диалекты регулярных выражений, особенно те, которые поддерживают рекурсию (например, PHP, Perl, .NET, JGSoft и другие) могут прекрасно обрабатывать контекстно-свободные языки.

person Tim Pietzcker    schedule 02.02.2014
comment
Хахаха. Я бы назвал их «регулярными выражениями реального мира». - person SnowOnion; 17.12.2018

arrow_upward
0
arrow_downward

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

Некоторый пример языка BNF

Поскольку BNF является контекстно-независимым, синтаксический анализатор может быть сгенерирован автоматически. Оригинальный и самый известный пример, конечно же, Yacc. другие были созданы с тех пор, как был изобретен Bison для создания gcc. В настоящее время существует множество генераторов синтаксических анализаторов, результатом которых является синтаксический анализатор, написанный на одном из популярных языков. .

person waTeim    schedule 02.02.2014

arrow_upward
0
arrow_downward

Возникла проблема с формулировкой вопроса, поскольку он относится к грамматикам, а не к языкам.

Обычный язык – это язык, который может быть определен над множествами с помощью операций объединения, конкатенации и замыкания. . Как Регулярные выражения, так и Обычные грамматики — это удобные способы представления обычных языков.

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

person Apalala    schedule 03.02.2014