Грамматика языка регулярных выражений с заданным алфавитом

Мне трудно понять, с чего начать этот вопрос. Вопрос в том, чтобы создать грамматику для языка регулярных выражений с алфавитом { ‘a’, ‘b’, ‘c’, ‘d’, ‘|’, ‘*’, ‘(‘, ‘)’ }. Предположим, что введена 1 строка (одна строка) и нет пробелов. Пустая строка недействительна, и она должна правильно отображать приоритет операторов, которые от низшего к высшему представляют собой объединение ('|'), конкатенацию и клини ('*'). Как лучше всего начать писать грамматику для этого? Мы будем очень признательны за любой вклад.

Не ищу ответа, просто не знаю, с чего начать. Пока у меня есть что-то вроде:

S -> S'('S')'S  
   | A  
A -> AA  
   | A'*'  
   | T  
T -> T'|'T  
   | X  
X -> 'a'  
   | 'b'  
   | 'c'  
   | 'd'

Но я не уверен, что я даже на правильном пути.

РЕДАКТИРОВАТЬ: после выполнения еще одной работы я пришел к выводу:

START -> EXPRESSION  
EXPRESSION -> EXPRESSION'|'EXPRESSION  
EXPRESSION -> PARENTHETICAL'*'  
EXPRESSION -> PARENTHETICAL  
EXPRESSION -> EXPRESSION PARENTHETICAL  
EXPRESSION -> PARENTHETICAL EXPRESSION  
EXPRESSION -> EXPRESSION PARENTHETICAL EXPRESSION  
EXPRESSION -> REPEAT  
PARENTHETICAL -> PARENTHETICAL'*'  
PARENTHETICAL -> '('EXPRESSION')'  
REPEAT -> REPEAT REPEAT
REPEAT -> TERMINAL'*'  
REPEAT -> TERMINAL  
TERMINAL -> TERMINAL'*'  
TERMINAL -> 'a'  
TERMINAL -> 'b'  
TERMINAL -> 'c'  
TERMINAL -> 'd'

Это также можно записать как:

S -> E  
E -> E'|'E  
E -> P'*'  
E -> P  
E -> E P  
E -> P E 
E -> E P E  
E -> R  
P -> P'*'  
P -> '('E')'  
R -> R R
R -> T'*'  
R -> T  
T -> T'*'  
T -> 'a'  
T -> 'b'  
T -> 'c'  
T -> 'd'

Я почти уверен, что это правильно, и я дважды проверил это с помощью множества различных тестовых входных данных. Любое подтверждение будет оценено.


regex grammar context-free-grammar
person Tony Dakhoul    schedule 22.03.2013    source источник
comment
Похоже на домашнее задание. Это?   -  person dotNET    schedule 22.03.2013
comment
Где конкретно вы застряли?   -  person Oliver Charlesworth    schedule 22.03.2013
comment
Да, это домашнее задание. Не ищу ответа, просто не знаю, с чего начать. Пока у меня есть что-то вроде: S -> S'('S')'S | A A -> Но я не уверен, что я на правильном пути.   -  person Tony Dakhoul    schedule 22.03.2013
comment
@TonyDakhoul включите этот последний комментарий в свой вопрос, чтобы люди его прочитали! Всегда полезно указать прямо в вопросе, что вы пробовали!   -  person Hugo Dozois    schedule 22.03.2013

Ответы (2)


arrow_upward
2
arrow_downward

Это всего лишь вопрос итерации. Я всегда предпочитаю начинать с правила Start-> NonTerminal, просто чтобы дать себе шанс на правильную грамматику. Я считаю, что вложенные скобки сведут нас к контекстно-свободной грамматике, но это нормально. Я считаю, что это облегчает этот шаг. Затем вы должны начать с оператора НАИМЕНЬШЕГО приоритета. Скобка и Union в вашем случае. Итак, изначально:

Start -> Expression
Expression -> Expression|Expression
Expression -> (Expression)

Обратите внимание, что я избегаю обычного '|' обозначение, потому что это один из символов в вашем алфавите. Это позволяет избежать путаницы. Затем мы можем добавить следующий оператор, конкатенацию, с набором правил, которые генерируют повторение.

Start -> Expression
Expression -> Expression|Expression
Expression -> (Expression)

Expression -> Repeat
Repeat -> RepeatRepeat
Repeat -> Terminal
Terminal -> a
Terminal -> b
Terminal -> c
Terminal -> d

Затем все, что осталось, это добавить звезду Клини в качестве оператора с самым низким приоритетом:

Start -> Expression
Expression -> Expression|Expression
Expression -> (Expression)

Expression -> Repeat
Repeat -> RepeatRepeat
Repeat -> Terminal
Terminal -> a
Terminal -> b
Terminal -> c
Terminal -> d

Repeat -> Terminal*
Expression -> (Expression)*

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

S -> E
E -> E|E
E -> (E)
E -> (E)*
E -> R
R -> RR
R -> T*
R -> T
T -> a
T -> b
T -> c
T -> d

Есть грамматика, в которой я уверен. Надеюсь, кто-нибудь проверит мою работу, потому что прошло несколько лет с тех пор, как я написал формальную грамматику.

РЕДАКТИРОВАТЬ:

В результате указанной двойной проверки было указано, что объединение выражений и выражений в скобках не работает. Тем не менее, мы можем добавить это. Первый шаг — добавить новое правило Expression -> Parenthetical и изменить Expression -> (Expression) и Expression -> (Expression)* на Parenthetical -> (Expression) и Parenthetical -> (Expression)* Затем пара быстрых правил для их объединения приводит к набору правил:

Start -> Expression
Expression -> Expression|Expression
Expression -> Parenthetical

Parenthetical -> (Expression)
Parenthetical -> (Expression)*

Expression -> Expression Parenthetical
Expression -> Parenthetical Expression
Expression -> Expression Parenthetical Expression

Expression -> Repeat
Repeat -> Repeat Repeat
Repeat -> Terminal
Terminal -> a
Terminal -> b
Terminal -> c
Terminal -> d

Repeat -> Terminal*
person FrankieTheKneeMan    schedule 22.03.2013
comment
Хм. Это не поддерживает (E)*, но это легко исправить. Я сделаю это через минуту. - person FrankieTheKneeMan; 22.03.2013
comment
Вопрос: Эта грамматика, которую вы написали, не допускает правильного выражения a(b|c)*d? Кроме того, не будут ли скобки технически иметь наивысший приоритет? Я знаю, что это не указано в задаче, но, например, это утверждение: abc|d Можно представить так: (a(b)c)|(d) - person Tony Dakhoul; 22.03.2013
comment
Это можно исправить, изменив E->(E) and E->(E)* на E->P, P->(E) и P->(E)*, а затем добавив правила E->EP, E->PE и E->EPE. Это, вероятно, можно было бы уменьшить. - person FrankieTheKneeMan; 22.03.2013
comment
А, я вижу, имеет смысл. Мой главный вывод из вашего ответа — всегда начинать с самого низкого приоритета, верно? Позвольте мне попытаться переписать мою грамматику, и я скоро опубликую ее. Еще раз спасибо за ваш ответ, очень признателен! - person Tony Dakhoul; 22.03.2013
comment
Ага. Не беспокойтесь о попытке сделать минимальную грамматику изначально, я точно этого не делал. Просто заставьте каждую часть работать, не ломая все предыдущие части. Вы всегда можете сократить свою грамматику позже. - person FrankieTheKneeMan; 22.03.2013
comment
Благодаря вашему совету я считаю, что у меня есть правильная грамматика для языка регулярных выражений. Если бы вы могли перепроверить это только ради меня, это было бы здорово, но в любом случае я очень ценю вашу помощь. знак равно - person Tony Dakhoul; 22.03.2013
comment
@TonyDakhoul Осторожно! EXPRESSION -> PARENTHETICAL'*' и PARENTHETICAL -> PARENTHETICAL'*' можно комбинировать для создания бесконечных звездочек, что недопустимо в регулярных выражениях. На самом деле, второе правило может сделать это само по себе. - person FrankieTheKneeMan; 22.03.2013
comment
То же самое с TERMINAL -> TERMINAL'*' - person FrankieTheKneeMan; 22.03.2013
comment
Как упомянул мой учитель, звезд может быть сколько угодно, это просто избыточно. Что-то вроде abc**** допустимо в языке, который он хочет, чтобы мы придумали. Но кроме этого, у него есть ваше одобрение? - person Tony Dakhoul; 22.03.2013
comment
@TonyDakhoul - Да, я так думаю. Опять же, прошли годы с тех пор, как мне приходилось писать формальные грамматики. Я бы сделал две вещи: дважды уточнил у своего Учителя о лишних звездочках, а затем (если тебе разрешено) продал бы их другим одноклассникам или друзьям, которые уже посещали занятия раньше. - person FrankieTheKneeMan; 22.03.2013

arrow_upward
-2
arrow_downward

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

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

Все дело в смысле.

Тем не менее, Grako имеет преобразователь регулярного выражения в CFG как единственный образец проекта.

person Apalala    schedule 23.03.2013
comment
Это имеет очень мало общего с вопросом, заданным здесь. Заданный вопрос касался грамматики, которая создает все строки, являющиеся допустимыми регулярными выражениями, с учетом предоставленного алфавита, а не о создании грамматики из регулярного выражения. Этот вопрос не о компиляторах, и ваш ответ (независимо от истинности содержащихся в нем утверждений) здесь неуместен. - person FrankieTheKneeMan; 25.03.2013
comment
@FrankieTheKneeMan Из исходного вопроса ... чтобы создать грамматику для языка регулярных выражений ..., ... следует правильно фиксировать приоритет операторов .... Именно об этом мой ответ. - person Apalala; 25.03.2013
comment
Ваш ответ совсем не об этом. Ваш ответ о том, чтобы взять регулярное выражение и превратить его в контекстно-свободную грамматику. По крайней мере, это то, что делает пример проекта, на который вы ссылаетесь. Это не то, что было задано. Был задан вопрос, как написать грамматику, которая генерирует все допустимые регулярные выражения. Это совсем другой процесс. - person FrankieTheKneeMan; 25.03.2013
comment
Язык, порожденный грамматикой, — это теоретическая концепция, малопригодная для практического применения, потому что самые интересные языки бесконечны. На практике, используя грамматики для создания парсеров, которые могут проверить, принадлежит ли данное предложение языку, и мы пишем грамматики, которые позволяют восстановить абстрактную структуру предложений, чтобы мы может придавать им семантику. Во всяком случае, грамматика, которую я разместил в качестве примера, генерирует язык регулярных выражений и может использоваться для любой задачи синтаксического анализа или может быть переведена в нотацию другого инструмента для создания синтаксического анализа, если так хотелось. - person Apalala; 26.03.2013