우선 순위 문제

Question

비교적 간단한 문법을 ​​사용하여 파서를 생성하려고하는데 우선 순위가 제대로 작동하지 않는 문제가 있습니다.

나는 15 개의 shift/reduce 오류를 처리 할 수 ​​있었지만,이 나머지 몇 가지를 고치는 방법을 잃어 버렸습니다. 그들은 아마도 내 우선 순위 문제와 관련이 있습니다.

I는 다음과 같은 정의 된 문법이 있습니다

%nonassoc T_LEN T_OPENPAREN T_CLOSEPAREN T_NUM T_ID T_QUOTE T_TRUE T_FALSE 
%left T_GT T_GTE T_LT T_LTE T_EQ 
%left T_OR 
%left T_AND 
%left T_NOT 

Start   : Expression         { astRoot = new MainNode($1); } 
       ; 

Expression  : Expression T_OR Expression     { $$ = new OrNode($1, $3); } 
       | Expression T_AND Expression     { $$ = new AndNode($1, $3); } 
       | Expression Expression       { $$ = new AndNode($1, $2); } 
       | T_NOT Expression        { $$ = new NotNode($2); } 
       | T_GT Expression        { $$ = new GreaterNode($2); } 
       | T_GTE Expression        { $$ = new GreaterEqualNode($2); } 
       | T_LT Expression        { $$ = new LessNode($2); } 
       | T_LTE Expression        { $$ = new LessEqualNode($2); } 
       | T_EQ Expression        { $$ = new EqualNode($2); } 
       | T_LEN T_OPENPAREN T_NUM T_CLOSEPAREN   { $$ = new LenNode(new IntegerNode($3)); } 
       | T_OPENPAREN Expression T_CLOSEPAREN   { $$ = $2; } 
       | T_TRUE          { $$ = new BoolTrueNode; } 
       | T_FALSE          { $$ = new BoolFalseNode; } 
       | T_ID           { $$ = new IdentifierNode($1); } 
       | T_NUM           { $$ = new IntegerNode($1); } 
       | T_QUOTE          { $$ = new QuoteNode(new IdentifierNode($1)); } 
       ; 

의 I 내가 원하는 값을 얻을 수없는 다음과 같은 분석을 시도 : 내 파서 출력의

100 T_AND 200 T_AND 300 T_AND 400 T_OR 1000 
output => And("100", And("200", And("300", Or("400", "1000")))); 
expect => Or(And("100", And("200", And("300", "400"))), "1000"); 

마지막으로 관련 부품 is :

State 27 conflicts: 15 shift/reduce 

0 $accept: Start $end 

1 Start:  Expression 

2 Expression: Expression T_OR Expression 
3   | Expression T_AND Expression 
4   | Expression Expression 
5   | T_NOT Expression 
6   | T_GT Expression 
7   | T_GTE Expression 
8   | T_LT Expression 
9   | T_LTE Expression 
10   | T_EQ Expression 
11   | T_LEN T_OPENPAREN T_NUM T_CLOSEPAREN 
12   | T_OPENPAREN Expression T_CLOSEPAREN 
13   | T_TRUE 
14   | T_FALSE 
15   | T_ID 
16   | T_NUM 
17   | T_QUOTE 

State 27 

    2 Expression: Expression . T_OR Expression 
    3   | Expression . T_AND Expression 
    4   | Expression . Expression 
    4   | Expression Expression . 

    T_LEN  shift, and go to state 1 
    T_OPENPAREN shift, and go to state 2 
    T_NUM  shift, and go to state 3 
    T_ID   shift, and go to state 4 
    T_QUOTE  shift, and go to state 5 
    T_TRUE  shift, and go to state 6 
    T_FALSE  shift, and go to state 7 
    T_GT   shift, and go to state 8 
    T_GTE  shift, and go to state 9 
    T_LT   shift, and go to state 10 
    T_LTE  shift, and go to state 11 
    T_EQ   shift, and go to state 12 
    T_OR   shift, and go to state 25 
    T_AND  shift, and go to state 26 
    T_NOT  shift, and go to state 13 

    T_LEN  [reduce using rule 4 (Expression)] 
    T_OPENPAREN [reduce using rule 4 (Expression)] 
    T_NUM  [reduce using rule 4 (Expression)] 
    T_ID   [reduce using rule 4 (Expression)] 
    T_QUOTE  [reduce using rule 4 (Expression)] 
    T_TRUE  [reduce using rule 4 (Expression)] 
    T_FALSE  [reduce using rule 4 (Expression)] 
    T_GT   [reduce using rule 4 (Expression)] 
    T_GTE  [reduce using rule 4 (Expression)] 
    T_LT   [reduce using rule 4 (Expression)] 
    T_LTE  [reduce using rule 4 (Expression)] 
    T_EQ   [reduce using rule 4 (Expression)] 
    T_OR   [reduce using rule 4 (Expression)] 
    T_AND  [reduce using rule 4 (Expression)] 
    T_NOT  [reduce using rule 4 (Expression)] 
    $default  reduce using rule 4 (Expression) 

    Expression go to state 27 

내가 이해할 수있는 가장 좋은 점은 암시 적으로 ules 3과 4). 이것이 문제의 근원이라면 어떻게 해결해야합니까?

감사합니다.

Answer 1

이 질문을 쓰는 동안, 나는 암묵적인 것이 문제의 근원 일 수 있다는 것을 깨달았습니다. 이제는 무엇이 잘못 될지에 대한보다 확실한 이해를 통해 정확한 Google 검색어를 작성하여 this post으로 안내 할 수있었습니다.

답변을 읽은 후 솔루션 종류가 방금 떨어졌습니다. 필자는 바이슨의 우선 순위 선언을 통한 암시 적 우선 순위보다는 문법을 통한 명시적인 우선 순위를 선택했다. 이것은 나에게 다음과 같은 문법 주었다

Start   : Expression         { astRoot = new MainNode($1); } 
       ; 

Term   : T_TRUE          { $$ = new BoolTrueNode; } 
       | T_FALSE          { $$ = new BoolFalseNode; } 
       | T_ID           { $$ = new IdentifierNode($1); } 
       | T_NUM           { $$ = new IntegerNode($1); } 
       | T_QUOTE          { $$ = new QuoteNode(new IdentifierNode($1)); } 
       | T_LEN T_OPENPAREN T_NUM T_CLOSEPAREN   { $$ = new LenNode(new IntegerNode($3)); } 
       | T_OPENPAREN Expression T_CLOSEPAREN   { $$ = $2; } 
       ; 

Prefix   : Term 
       | T_NOT Prefix         { $$ = new NotNode($2); } 
       | T_GT Term          { $$ = new GreaterNode($2); } 
       | T_GTE Term         { $$ = new GreaterEqualNode($2); } 
       | T_LT Term          { $$ = new LessNode($2); } 
       | T_LTE Term         { $$ = new LessEqualNode($2); } 
       | T_EQ Term          { $$ = new EqualNode($2); } 
       ; 

Factor   : Prefix 
       | Prefix Factor         { $$ = new AndNode($1, $2); } 
       ; 

Andor   : Factor 
       | Andor T_AND Factor       { $$ = new AndNode($1, $3); } 
       ; 

Expression  : Andor 
       | Expression T_OR Andor       { $$ = new OrNode($1, $3); } 
       ; 

을 그리고 이것은 나에게 0 교대/갈등과 내가 지금까지 내 모든 테스트에서 기대하고있어 값을 감소했다.

T_NOT T_GT 100 => Not(Greater("100")) => valid 
T_GT T_NOT 100 => Greater(Not("100")) => invalid 

사람이 내가 제시 한 문법과 숨겨진 문제를보고하지 않는 한, 나는이 가지고 생각 : 또한 내 문법 배열이 방법은 다음과 진술의 타당성으로 명백한 언어의 미묘한 뉘앙스를 만들어 내 문제를 완전히 해결했다.