Context-free-grammar для представления регулярных выражений

Я пытаюсь сделать контекстно-свободную грамматику для представления простых регулярных выражений. Символы, которые мне нужны, это [0-9] [a-z] [A-Z], а операторы - «|», «()» и «.». «?» Для конкатенации, и для последовательностей для теперь я только хочу «*» позже я добавлю «+», и т.д. Я попробовал эту грамматику в JavaCC:Context-free-grammar для представления регулярных выражений

void RE(): {} 
{ 
    FINAL(0) ("." FINAL(0) | "|" FINAL(0))* 
} 

void FINAL(int sign): { Token t; } 
{ 
    t = <SYMBOL> { 
     if (sign == 1) 
      jjtThis.val = t.image + "*"; 
     else 
      jjtThis.val = t.image; 
    } 
    | FINAL(1) "*" 
    | "(" RE() ")" 
}

Проблема в FINAL функции линии | FINAL(1) "*", который дает мне ошибку Left recursion detected: "FINAL... --> FINAL.... Помещение «*» слева от FINAL (1) разрешает проблему, но это не то, что я хочу.

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

источник

2013-05-16 pedroh

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

Я пытаюсь сделать грамматику для регулярных выражений, но очень простой. Некоторые примеры слов, которые я хочу принять: '(a * | b) .c, c | a, a.c *, 1 | 2, 1.3 и т. Д. Слова, которые я не хочу принимать, - это любой, который не соблюдает правильный формат, например: 'a ** b, a || b, a..b, a ((b) и т. Д. – pedroh

Возможный дубликат [Context- (http://stackoverflow.com/questions/977884/context-free-grammar-describing-regular-expressions) – Kevin

Следующая заботится о левой рекурсии

RE --> FACTOR ("." FINAL | "|" FINAL)* 
FINAL --> PRIMARY ("*")* 
PRIMARY --> <SYMBOL> | "(" RE ")"

Однако, это не даст. приоритет над | , Для этого вы можете сделать следующее

RE --> TERM ("|" TERM)* 
TERM --> FINAL ("." FINAL)* 
FINAL --> PRIMARY ("*")* 
PRIMARY --> <SYMBOL> | "(" RE ")"

Общее правило

A --> A b | c | d | ...

могут быть преобразованы в

A --> B b* 
B --> c | d | ...

где B является новым nonnterminal.

источник

2013-05-17 01:29:44

Спасибо, что разрешите мою проблему! – pedroh

Context-free-grammar для представления регулярных выражений

ответ

Смежные вопросы