Уровень стека слишком глубокий, используя Citrus для анализа выражений Грамматика

Question

Я пытаюсь обработать то, что в конечном итоге будет логической логикой, используя грамматику в Treetop-like Citrus для Ruby. Я получаю рекурсию, но я не понимаю, почему именно. Вот текст, который я пытаюсь процесс (он должен иметь символ новой строки в самом конце):

COMMANDWORD # MYCOMMENT 

Вот мой Citrus грамматика (предназначенная для борьбы с более продвинутыми вещами):

grammar Grammar 
    rule commandset 
    command+ 
    end 

    rule command 
    identifier command_detail* comment_to_eol* "\n" 
    end 

    rule command_detail 
    assign_expr | expr 
    end 

    rule assign_expr 
    identifier ":=" expr 
    end 

    rule expr 
    # Stack overflow 
    or_expr | gtor_expr 
    # No problem! 
    # or_expr 
    end 

    rule or_expr 
    # Temporarily match everything except a comment... 
    [^#]+ 
    # What I think will be correct in the future... 
    # gtor_expr "OR" expr 
    end 

    rule gtor_expr 
    and_expr | gtand_expr 
    end 

    rule and_expr 
    gtand_expr "AND" gtor_expr 
    end 

    rule gtand_expr 
    not_expr | gtnot_expr 
    end 

    rule not_expr 
    "NOT" gtnot_expr | gtand_expr 
    end 

    rule gtnot_expr 
    parens_expr | identifier 
    end 

    rule parens_expr 
    "(" expr ")" 
    end 

    rule identifier 
    ws* [a-zA-Z0-9]+ ws* 
    end 

    rule ws 
    [ ] 
    end 

    rule comment_to_eol 
    "#" [^\n]* 
    end 
end 

важные вещи находятся в правиле expr и правиле or_expr. Я изменил or_expr, поэтому он соответствует всем, кроме комментария. Если я придерживаюсь текущего правила expr, я получаю переполнение стека. Но если я переключу его так, что у него нет выбора между or_expr и gtor_expr, он отлично работает.

Мое понимание «выбора» заключается в том, что оно попытается оценить их по порядку. Если первый выбор не удался, тогда он попробует второй. В этом случае первый выбор, очевидно, может преуспеть, поэтому почему я получаю переполнение стека, если включить второй вариант, который никогда не следует принимать?

Answer 1

цикл может возникнуть из-за того, что gtand_expr -> not_expr, а not_expr -> gtand_expr.

Я думаю, что вы можете заменить правило not_expr с

not_expr -> "NOT" not_expr | gtnot_expr 

И вы должны попробовать простые правила, используя операторы регулярных выражений:

expr -> orexpr 
orexpr -> andexpr ("OR" andexpr)* 
andexpr -> notexpr ("AND" notexpr)* 
notexpr -> "NOT"? atomicexpr 
atomicexpr -> id | "(" expr ")"