YACC : 문법의 시프트/감소 충돌 찾기

Question

나는 theory of computation이라는 책을 읽었으며 YACC에서 구현 된 2 장의 언어 PL이 있습니다. 이 프로그램은 매우 기본입니다. 지정된 문법 규칙이 있으며 프로그램을 실행 한 후 지정된 파일에 지정된 문법의 구문이 있는지 여부를 확인합니다. 모든 규칙은 책에 나와 있으며 구현하려고합니다.

그러나 구현할 때 shift/reduce 충돌 코드가 표시됩니다. 웹에서 오류를 검색 한 결과 오류가 문법 모호성을 나타냅니다. 나는 그것을 발견하려고했지만 할 수 없었다. in here 비슷한 질문이 있고 사용자가 경고를 지적했으며 일부 언어가 모호하기 때문에 무시할 수 있습니다.

문제 : 모호함이있을 경우

이

• 누군가가 지적 할 수 있습니까?

• 다음과 같은 코드를 실행하려고하면 프로그램에서 이해하지 못합니다. 구문 오류가 발생합니다. 이것은 내가 적용한 문법 규칙에 따라 받아 들여 져야합니다. 잘못된 구문으로 문법을 전달합니까?

  while X = 10; 
  X = Y + 10; 
  end; 
  

내 코드 :

는

%start program 
    %% 
    LETTER : 'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' 
      | 'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' 
      | 'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z' 
      ; 

    DIGIT : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 
     ; 

    name : LETTER 
     | name DIGIT 
     | name LETTER 
     ; 


    numeral : DIGIT 
     | numeral DIGIT 
     ; 


    operation : '+' 
       | '-' 
       | '*' 
       | '/' 
       | '=' 
       | '<' 
       | '>' 
       | '>' '=' 
       | '<' '=' 
       ; 

    expression : name 
      | numeral 
      | '(' '!' expression ')' 
      | '(' expression operation expression ')' 
      ; 

    assignment : name '<' '-' expression 
       ; 

    instruction : assignment 
       | 'g' 'o' 't' 'o' name 
       | 's' 't' 'o' 'p' 
       ; 


    labelinstr : name ':' instruction ';' 
       | instruction ';' 
       ; 

    loop : 'l' 'o' 'o' 'p' expression ';' 
     | name ':' 'l' 'o' 'o' 'p' expression ';' 
     ; 

    ifthen : 'i' 'f' expression 't' 'h' 'e' 'n' ';' 
      | name ':' 'i' 'f' expression 't' 'h' 'e' 'n' ';' 
      ; 
    while : 'w' 'h' 'i' 'l' 'e' ';' 
      | name ':' 'w' 'h' 'i' 'l' 'e' expression ';' 
      ; 


    end : 'e' 'n' 'd' ';' 
     | name ':' 'e' 'n' 'd' ';' 
     ; 

    program : labelinstr 
      | loop program end 
      | while program end 
      | ifthen program end 
      | ifthen program end 'e' 'l' 's' 'e' ';' program end 
      | program program 
      ; 





    %% 
    #include <stdio.h> 

    yylex() { 
     int c; 
     while ((c=getchar()) == ' ' || c == '\n' || c == '\t') { 
     printf("%c",c);} 
     printf("%c",c); 
     return(c); 
    } 

Answer 1

모호성 문제는 구문 오류와 관련이 없습니다. 다음을 고려하십시오 :

while : 'w' 'h' 'i' 'l' 'e' ';' 
     | name ':' 'w' 'h' 'i' 'l' 'e' expression ';' 
     ; 

대체 방법 중 하나에 뭔가가 없습니다. 라벨이 붙은 동안 루프를하고 싶은데 라벨이 지정되지 않은 상태에서는 아무 것도 반복하지 않으시겠습니까?

while : 'w' 'h' 'i' 'l' 'e' expression ';' 
     | name ':' 'w' 'h' 'i' 'l' 'e' expression ';' 
     ; 

제외 : 실제로 라벨을 제외해야합니다. 당신은 이미 "라벨 진술"생산을하고 있습니다. 그걸 써.

while X = 10; 

식 간단한 이름 또는 번호, 또는 괄호 중 하나이기 때문에 X = 10 자체에 유효하지 않습니다.

X = Y + 10; 

이는 다음과 같습니다 : 이러한 수정으로

X <- (Y + 10) ; 

구문 오류가 (이 충돌이 여전히 있지만 그들은 관련이없는) 더 이상이

while (X = 10) ; 

이

는 할당되지 않습니다 .

Answer 2

변화를 식별하는 첫 번째 단계는/충돌을 감소하는 bison에 -v 플래그를 사용하고있을 것이다 결과 파일의 상태 머신을 검토하는 것입니다 충분 .output. 그러면 어떤 주에서 오류를 표시하고 어떤 규칙으로 해당 주를 유도하는지 알려줍니다. 예를 들어, 프로그램과 함께, 우리는 변화와이 개 상태를 참조/충돌을 감소, 주 65 상태 주 (84)는 상대적으로 간단한 84

입니다 : "다른 매달려"고전과 유사

State 84 

    72 program: ifthen program end . 
    73  | ifthen program end . 'e' 'l' 's' 'e' ';' program end 

    'e' shift, and go to state 101 

    'e'  [reduce using rule 72 (program)] 
    $default reduce using rule 72 (program) 

문제. 일반적으로 end;과 같은 문 자 종료자를 사용하면이 문제가 해결되지만 else 절의 경우에도 end;을 가지고 있다고 호기심을 갖고 제시하는 문법을 사용해야합니다. 따라서

if (a > 3) then a <- 3; else a <- 2; end, 

은 유효하지 않습니다. 대신, 문법은 end가와 else 조항없이 문을 구분하지 않기 때문에 매달려 다른 문제를 해결하는 데 도움이되지 않습니다

if (a > 3) then a <- 3; end; else a <- 2; end; 

주장, 그래서 다음은 여전히 ​​모호 :

if (a > 3) then if (a < 7) then a <- 3; end; else a <- 7; end; 

문법이 맞지 않을 것 같습니다. 나는 if 제작이되어야한다고 생각 :

 | ifthen program end 
     | ifthen program 'e' 'l' 's' 'e' ';' program end 

다른 문제는 상태 (65)에 : 분명히 모호한 즉

State 65 

    74 program: program . program 
    74  | program program . 

(여기, 내가 전환을 생략했다).당신은 있다고 가정 :

statement statement statement 

이로 해석 될 수있는 하나 바인딩을 왼쪽에서 오른쪽 또는 오른쪽에서 왼쪽으로 :

[program: [program: statement] [program: [program: statement] [program: statement]]] 
[program: [program: [program: statement] [program: statement]] [program: statement]] 

대략 일반적으로 솔루션입니다 말하기 뭔가 같은 :

statement: if_statement 
     | loop_statement 
     | ... 

program: statement 
     | program statement 

개인적으로는 라벨을 제외 할 수 있습니다.