В чем разница между EBNF и CFG

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

Я спрашиваю, потому что есть вопросы, которые просят преобразовать EBNF в CFG, но в моем нынешнем понимании они выглядят одинаково. Итак, каковы намерения, стоящие за этим обращением?

2 3
context-free-grammar

2 ответа:

EBNF можно использовать для написания контекстно-свободной грамматики.

Латинский алфавит можно использовать для написания английского языка.

Паскаль можно использовать для выражения алгоритма.

"контекстно-свободная грамматика" - это абстрактная вещь, которую вы можете записать в форме EBNF для машинного ввода. Собственно контекстно-свободная грамматика-это математический объект. Он имеет стандартную нотацию, но стандартная нотация действительно предназначена для потребления человеком.

4

Резюме: EBNF не является прямым эквивалентом формализма CFG, но многие грамматики EBNF могут быть механически преобразованы.

Контекстно-свободная грамматика - это четыре кортежа из:

  • Набор нетерминалов V

  • Набор терминалов Σ, который не связан с V

  • Множество произведений вида

    v → ω

Где v - элемент V и ω - элемент (V ⋃ Σ)* (что is, возможно-пустая строка терминалов и нетерминалов.

  • начальный символ S, являющийся элементом V.

(см. статью Википедии и ссылки на нее. Существует другой эквивалентный формализм, который использует множество нетерминальных V и алфавит A, который является союзом V и Σ.)

Ранний конкретный синтаксис CFGs был предложен Джоном Бэкусом в 1959 году для описания языка программирования Algol. формализм обычно называют Backus-Naur Form, название предложил Дональд Кнут, признавая вклад соавтора доклада Algol Питера Наура. Основное отличие BNF от приведенного выше формализма CFG состоит в том, что произведения с общей левой стороной сокращаются с помощью символа |:

     v → ω1 | ω2
    ⇒
      v → ω1
      v → ω2

Однако на практике использование регулярных операторов, в частности операторов повторения, таких как звезда Клина, оказалось намного проще в написании и использовании. взять в толк. Ряд расширений к BNF были предложены и использованы в различных грамматиках, особенно Никлаусом Виртом. В частности, стало общепринятым использовать форму расширенного BNF в стандартных протокольных документах, как RFC (IETF internet standards), так и различных стандартах ISO. Эти формализмы были в конечном счете" стандартизированы " как расширенный BNF, ISO/IEC 14977 и несколько похожий расширенный BNF, RFC-5234.

Чтобы преобразовать EBNF в формализм CFG, это необходимо расширить все виды использования повторения-включая конечное повторение -, чередование и операторы опциональности до примитивной формы, что требует введения новых не-терминалов. Кроме того, и EBNF, и ABNF допускают спецификации, которые могут быть невозможно преобразовать в CFG, включая ограничения, написанные на английском языке. (См. первую заметку в моем ответе на Ebnf-это грамматика LL(1)?)

2