암시적 우선순위

Question

나는 파서 생성기가 어떻게 작동하는지 이해하기 위해 "Flex and Bison"이라는 책을 읽고 있는데 다음 예가 있습니다.

calclist: /* nothing */
        | calclist exp EOL { printf("= %d\n", $1); }
        ;

exp: factor
   | exp ADD factor { $$ = $1 + $3; } 
   | exp SUB factor { $$ = $1 - $3; }
   ;

factor: term
      | factor MUL term { $$ = $1 * $3; } 
      | factor DIV term { $$ = $1 / $3; }
      ;

term: NUMBER
    | ABS term { $$ = $2 >= 0? $2 : - $2; }
    ;

그리고 책에서는 위의 문법이 별도의 비단말 기호를 사용하여 암묵적으로 우선순위를 갖는다고 말합니다.하지만 어떻게 작동하나요?다음과 같은 예가 있다고 가정합니다. 1 + 3 * 2 (공백은 그냥 건너뜁니다) 첫 번째 토큰을 읽습니다 1 다음과 같이 스택에 푸시됩니다. NUMBER 또는 term 또는 factor 문법을 통해 얼마나 오랫동안 "버블링"될까요?다음 토큰은 어떤 문법 규칙에서 확인되나요?이 문법 곱셈이 덧셈보다 우선순위가 더 높은 이유는 무엇입니까?

Answer 1

이것이 (명시적인 것이 아니라) "암시적인" 우선순위를 갖는 이유는 인수분해된 문법(별도의 비터미널)으로 인해 실제로 텍스트에서 말하는 것과 같습니다.

당신의 예를 통해 작업 1 + 3 * 2, 각 명령을 "문자 그대로" 따라 해석을 수행하는 컴퓨터로 자신을 상상해 보세요."exp"(표현식)를 찾으려면 먼저 요인을 찾아야 합니다.(다른 옵션은 "exp"를 찾는 것부터 시작하는 것이지만 "요인"을 찾아야 합니다.) 따라서 요인을 찾아야 합니다.하지만 그렇게 하려면 요인이 항이거나 항으로 시작하는 요인이기 때문에 "항"을 찾아야 합니다.이제 다음 중 하나인 용어를 찾아야 합니다. NUMBER 아니면 키워드 ABS.따라서 (문법 용어로) "수락"할 수 있습니다. 1, 실제로는 NUMBER, 구문 분석의 첫 번째 부분인 용어 찾기에 성공했습니다.(이제 제거 1 토큰 스트림에서 + 다음 토큰으로 사용됩니다.)

이제 용어가 있으므로 (정의에 따라) 요인도 있지만, 말하자면 "요인을 갖는 작업을 완료"하려면 더 긴 일치를 시도해야 합니다.요인 다음에 MUL 또는 DIV, 그 뒤에 뭔가가 있습니다.다음 토큰은 +:MUL도 아니고 DIV도 아닙니다.따라서 요소 구문 분석을 중단하고 지금까지 전체 구문 분석 체인을 요소로 반환해야 합니다. 1 요소이고 다음 토큰은 여전히 +.

이제 요인이 있으므로 (정의에 따라) 경험이 있지만 "경험이 있는 작업을 완료"하려면 다시 더 긴 일치를 시도해야 합니다.exp 다음에 ADD 또는 SUB, 그 뒤에 뭔가가 있습니다.다음 토큰은 아직 + 실제로는 ADD입니다...그래서 당신은 다음을 진행해야합니다 exp ADD factor { $$ = $1 + $3 }; 규칙.

이 시점에서 당신은(파서로서) 지금까지의 모든 것을 스택에 푸시하고 적절한 비터미널(이 경우에는 또 다른 "인자")을 찾는 작업을 다시 시작합니다.이제 요인에 대한 규칙부터 시작합니다."용어"를 찾아야 하며, 찾으면 다음을 포함하는 더 긴 버전의 규칙을 수행해 보십시오. MUL 또는 DIV.이 부분을 작업해보면 다음과 같은 사실을 알 수 있습니다. * 토큰은 실제로 MUL이므로 "요인" 결과가 factor MUL term { $$ = $1 * $3; } 규칙의 일부.이것은 일명 먹기/소모를 허용합니다. 3 * 2 순서를 지정하고 값을 반환합니다. 6 구문 분석 스택에 푸시한 규칙을 완성할 수 있는 "요소"에 대한 것입니다.

푸시 상태로 돌아온 후 1을 추가하고 전체 표현식을 수락(먹기)하여 "1 +" 구문 분석을 완료합니다.물론 1 + 6은 7이므로 문법이 올바른 값을 반환합니다.

Answer 2

우선 순위는 ADD 및 SUB의 피연산자가 요소가 된 결과이며 요소에만 MUL 및 DIV 연산자가 포함됩니다.MUL은 용어로 캡슐화되므로 ADD는 MUL과 경쟁하지 않습니다.

파서의 관점에서 이것을 생각해 보면 다음과 같습니다.구문 분석기가 ADD 연산자와의 관계를 고려하기 전에 표현이라는 용어를 줄여야 하며, 그 감소로 인해 MUL 연산자가 지워집니다.

주어진 A + X * Y, X * Y 표현은 다음과 같이 축소된다. term 이는 더 이상 표현하지 않는 단일 문법 기호입니다. * 연산자이므로 아무것도 없습니다. + 우선순위 문제가 있는 연산자;지금은 그냥 A + term.

그런데 문법은 틀에 얽매이지 않는 역전된 용어를 사용합니다.

다음은 용어입니다.A + B + C

다음과 같은 요인이 있습니다.알파벳

항이 추가되고("계열의 항") 인수가 곱해집니다("정수 또는 다항식의 인수").

정말 이 교과서에 나오는 내용인가요?어쨌든 시도해 보세요. 컴파일러:원리, 기술 및 도구 작성자: Aho, Sethi, Ullman.(1988년이지만 클래식).