Mathos

Предыдущая статья: Регулярки - применение. Итог темы об автоматных языках в vk.com

Статья для повторения:Эквивалентность и однозначность грамматики или почему иногда 2+2*2=8?

При разборе автоматных языков мы ведь не строили никаких деревьев? Нет ли здесь противоречия? Нет. Из-за свойства автоматной грамматики её правила вида A → a и A → ε всегда приводят к конечным символам, а правило вида A → aB всегда задаёт однозначную последовательность для ДКА, и все деревья автоматных грамматик приобретают вид:

Поэтому нам будет полезно ввести определение однозначности не прибегая к дереву. Для этого рассмотрим две грамматики мат.выражений:

G1: E → E + E | E – E | E * E | E / E | x | ( E )

G2:
E → T | E + T | E – T
T → M|T * M| T / M
M → x | (E)

Попробуем построить выражение x + x * x более чем одним левосторонним выводом, для G1:

E => E * E => E + E * E => x + E * E => x + x * E => x + x * x

E => E + E => x + E => x + E * E => x + x * E => x + x * x

Теперь для G2:

E =>E + T=>T + T =>M + T=>x + T=>x + T * M=>x + M * M =>x + x * M => x + x * x

А вот второй вывод для G2 мы не можем построить, так как по правилам грамматики, мы не можем подставить * или операнд (x) раньше, чем + . Если мы построим деревья, то мы увидим, что в G1 они будут выглядеть по разному, ну а в G2 у нас всегда только одно дерево. Таким образом:

КС-грамматика называется однозначной, если для каждого предложения языка, порождаемого этой грамматикой, существует единственный левосторонний вывод или единственный правосторонний вывод.

Теперь о главном признаке: Если для некоторого неконечного символа А в грамматике, при выводе цепочки мы заново приходим к разложению А, а слева и справа от символа у нас уже имеются непустые цепочки конечных и неконечных символов, говорят, что такая грамматика имеет самовложение. К примеру наша грамматика G2, такой и является:
E => T => M => ( E )

Самовложение характерный признак КС-грамматики в противном случае:
КС-грамматика, не содержащая самовложения, эквивалентна автоматной грамматике.

Итак, на этом урок окночен.

З.Ы. Если вы в своей задаче встречаетесь с самвложением, отложите Regex, выпейте чаю, освободите себя от дурных мыслей, Regex-ы вам не нужны. Подписывайтесь.

Предыдущая статья: Регулярные выражения и регулярные множества - ещё один способ задания автоматного языка в vk.com

Чем выгодно отличаются регулярные выражения от рисунка порядка и записи грамматики, так это то, что они представляют из себя строки. Что даёт нам возможность легко обрабатывать их программно и автоматизированно создавать распознаватели автоматных языков. Реализация которых может быть представлена в виде таких схем:

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

Регулярные выражения (далее РВ) по своей сути являются языком из алфавита { |, (, ), *, a}, где а - множество различных символов алфавита задаваемого языка. Можно ли с помощью РВ задать язык РВ? Ответ: нет, так как язык РВ не является автоматным, из-за самовложения он является КС-языком. Ниже представлена его грамматика с учётом приоритетов операций:

R → T | R ′′|′′ T
T → M | RM
M → a | M* | ( R ) | ε

Запись ′′|′′ представляет знак | используемый в регулярных выражениях.

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

a? = (a|)
a+ = (aa*)
a{2,4} = (aa|aaa|aaaa)

Сокращение для «или»:
[abcd] = (a|b|c|d) - нужно отметить ещё, что символы между [ и ] не нужно экранировать.

Сокращения часто встречающихся множеств, один пример:
\d = (0|1|2|3|4|5|6|7|8|9)

А то и вовсе добавлены управляющие символы движка распознавателя, для указания где в строке нужно искать совпадение в ^ начале или в $ конце? В любом случае вам придётся открывать руководство конкретно-используемого инструмента, так как на долго в голове всё это удержать не возможно.

С помощью всего этого запись: (+|-|)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* превратилась в [+-]?\d+ , но вам никто не запрещает писать по «старинке».

В этой же статье я хотел вам показать взаимосвязь регулярных выражений с автоматными языками и распознавателями.

Итог: С помощью автоматных грамматик и регулярных выражений определяется синтаксис простейших конструкций языков программирования, таких как идентификаторы, различные литералы цифр, знаки операций.

Путеводитель по пройденным статьям:
1. Что такое язык программирования? Не спешим отвечать, знакомимся с определением формальных языков
2. Грамматика языка и порождающие грамматики. Сказ о «правильных» скобочках
3. Хомски и его иерархия грамматик
4. Дерево вывода предложения (сентенции) грамматики. Синтаксическое дерево
5. Задача разбора, для чего она нужна? Или что такое parsing?
6. Эквивалентность и однозначность грамматики или почему иногда 2+2*2=8?
7. Графы автоматных грамматик. Что же, начинаем знакомится с конечными автоматами?
8. Конечные автоматы, что там внутри?
9. Обещанная реализация КА и попытка создать таблицу переходов не детерминированному автомату
10. Преобразование НКА в ДКА, один из алгоритмов
11. Синтаксические диаграммы автоматных языков - рисунок порядка автоматных языков
12. Регулярные выражения и регулярные множества - ещё один способ задания автоматного языка

Ну как-то так, друзья. Дальше в лес КС-грамматик, присоединяйтесь.