Трудно ми е да разбера откъде да започна с този въпрос. Въпросът е да се създаде граматика за езика на регулярните изрази с азбуката { ‘a’, ‘b’, ‘c’, ‘d’, ‘|’, ‘*’, ‘(‘, ‘)’ }. Да приемем 1 ред за въвеждане (единичен низ) и без интервали. Празният низ не е валиден и трябва правилно да улови приоритета на операторите, които от най-ниския до най-високия са обединение ('|'), конкатенация и kleene ('*'). Какъв би бил най-добрият начин да започнете да пишете граматиката за това? Всеки принос ще бъде много оценен.
Не търся отговор, просто не знам как да започна. Досега имам нещо като:
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'
Доста съм сигурен, че това е правилно и го проверих два пъти с куп разнообразни тестови входни данни. Всяко потвърждение ще бъде оценено.
