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

Грамматика обозначает синтаксические правила разговора на естественных языках. Компьютерные науки в значительной степени используют теорию формальных языков. В 1956 году Ноам Хомский дал математическую модель грамматики для написания компьютерных языков. Когда можно получить набор всех строк из грамматики, говорят, что язык генерируется из этой грамматики. Два типа грамматики - это обычная грамматика и контекстно-свободная грамматика. Любой язык, который можно описать с помощью регулярного выражения, является регулярным языком. Грамматика без контекста - это обобщение регулярных выражений. Можно использовать регулярные выражения для написания регулярных языков и контекстно-свободной грамматики для написания контекстно-свободной грамматики.

Регулярное выражение, контекстно-свободная грамматика

Что такое регулярное выражение

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

X -> a или X -> a Y

Где X, Y ϵ N (нетерминальный) и a ϵ T (терминальный)

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

Регулярное выражение представляет определенный набор строк в алгебраическом виде. Вот некоторые важные правила, которым следует следовать при написании регулярного выражения.

1. Терминальные символы, нулевой символ и пустой символ являются регулярными выражениями.
2. Объединение двух регулярных выражений - это регулярное выражение.
3. Объединение двух регулярных выражений - это регулярное выражение.
4. Итерация или закрытие - это регулярное выражение.

Регулярное выражение для набора {0, 1, 2} выглядит следующим образом.

R = 0 + 1 + 2

Набор {abb, a, b, bba} может быть представлен следующим регулярным выражением.

R = abb + a + b + bba

Рассмотрим набор, {ϵ, 0, 00, 000,…}

Ε - это пустая строка. Регулярное выражение R = 0 *. Это означает закрытие символа, включая пустой символ.

В наборе {1, 11, 111, 1111,…..}

Регулярное выражение R = 1 ^+. Это + обозначает закрытие символа, исключая пустой символ.

Что такое контекстно-свободная грамматика

В формальной теории языка контекстно-свободный язык (CFL) - это язык, созданный с помощью контекстно-свободной грамматики. Четыре параметра определяют контекстно-свободную грамматику (G).

G = {V, ∑, S, P}

V: набор переменных или нетерминальных символов.

∑: Набор обозначений клемм

S: начальный символ

P: Правило производства

Контекстно-свободная грамматика имеет следующий формат для производственного правила.

A -> a, где a = {V, ∑} * и A ϵ V

Один из примеров контекстно-свободной грамматики следующий. Каждая продукция состоит из нетерминального символа и регулярного выражения.

Для создания языка, который генерирует равное количество букв a и b, имеет формат a б . Контекстно-свободная грамматика выглядит следующим образом.

G = {(S, A), (a, b), (S -> aAb, A -> aAb | ϵ)}

Учитывая начальный символ,

S -> а А б

Применяя A -> aAb

→ а а А б б

Применяя снова A -> aAb,

→ а а а А б б б

Применяя A -> ϵ (этот символ обозначает пустую строку)

→ а а а б б б

→ а ³ б ³

При рассмотрении вывода количество а равно количеству b. Он имеет б форма.

Связь между регулярным выражением и контекстно-свободной грамматикой

Разница между регулярным выражением и контекстно-свободной грамматикой

Определение

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

использование

Регулярные выражения помогают представить определенные наборы строк алгебраическим способом. Это помогает представлять обычные языки. Контекстно-свободная грамматика помогает определить все возможные строки контекстно-свободного языка.

Заключение

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

Ссылка:

1. «Регулярные выражения». Www.tutorialspoint.com, Tutorials Point, 8 января 2018 г., доступно здесь 2. «Введение в контекстную грамматику». Www.tutorialspoint.com, Tutorials Point, 8 января 2018 г., доступно здесь.

Изображение предоставлено:

1. «Toolbaricon RegEx» от M0tty - собственная работа (CC BY-SA 4.0) через Commons Wikimedia