간단한 (?) 문법의 시프트 감소 충돌

Question

나는 들소에서 문법을 설명하려고하지만 할 수 있는지 확신 할 수 없습니다.

%token A B C D SEP 

%% 

items   : /* empty */ 
       | items_nonempty 
       ; 

items_nonempty : item 
       | items_nonempty SEP item 
       ; 

item   :  B 
       |  B  SEP D 
       |  B SEP C 
       |  B SEP C SEP D 
       | A SEP B 
       | A SEP B  SEP D 
       | A SEP B SEP C 
       | A SEP B SEP C SEP D 
       ; 

는 "items"는 SEP 토큰 분리 item 요소의 (가능한 빈) 시퀀스이다 : 내 의도 문법이있다.

각 항목은 SEP으로 분리 된 순서로 최대 4 개의 토큰 (A B C D)으로 구성됩니다. 항목에있는 A, C 및 D 토큰은 선택 사항입니다.

각 항목 내에서와 항목 자체간에 동일한 구분 기호 토큰 SEP를 다시 사용합니다.

의도 한 문법이 분명하기를 바랍니다. 나는 그것이 모호하지 않다고 생각하지만 바이슨에 의해 분석 될 수있을만큼 충분히 제한적인지는 확신 할 수 없다. 불행히도 파서 지식은 꽤 녹슬다.

주어진대로 문법을 사용하면 bison은 4 개의 시프트/감소 충돌을보고합니다. '산출물'을 보면 나는 그들이 어디에서 발생했는지, 왜 그런지를 이해한다. 하지만 S/R 충돌을 없애기 위해 의도 된 문법을 작성하는 방법 (및 가능한 경우)을 놓치고 있습니다.

%expect 선언을 사용하지 않을 것입니다. 마찬가지로, 나는 스캐너가 파서에 넘겨지기보다는 분리 자 토큰을 소비하게 내키지 않는다.

이 문법을 위생 처리하는 방법에 대한 힌트를 크게 주시면 감사하겠습니다.

Answer 1

문법은 실제로는 모호하지 않습니다. LL (7)이며 LRR (2)라고 생각합니다. 그래서 그 중 하나에 대한 발전기가 있다면, 그것은 일을 할 것입니다.

lookahead-1 충돌은 항목 사이 및 항목 내에서 동일한 구분 기호를 사용하는 것으로 발생하며 구분 기호 나 항목 구조를 포기할 경우 사라집니다.

그래서 할 수있는 것은 다른 문법으로 두 번 구문 분석하는 것입니다. 첫 번째 패스에서는 항목의 구조를 확인하는 것입니다, 당신은 구분이 제대로 배치되지 확인할 수 있고, 문법 통과 번째 (더 중요한)에서 뭔가 같은

items   : 
       | items_nonempty 
       ; 
items_nonempty : item 
       | items_nonempty SEP item 
       ; 
item   : A 
       | B 
       | C 
       | D 
       ; 

수 있습니다.

items   : 
       | items_nonempty 
       ; 
items_nonempty : item 
       | items_nonempty item 
       ; 
item   : B 
       | B D 
       | B C 
       | B C D 
       | A B 
       | A B D 
       | A B C 
       | A B C D 
       ; 

이 경우 렉서가 구분 기호를 무시할 수 있습니다.

위의 두 가지 모두 LALR (1)이고 전자는 LL (1)이고 후자는 LL (4)이지만 일부 인수 분해로 LL (1)로 만들 수 있습니다.

이것은 bison이나 lexer 도구가 제공하는 특별한 오퍼링과 독립적 인 솔루션입니다. 나는 그들이 할 수있는 일에 대해 배우기를 고대하고 있습니다.

Answer 2

이것은 하나의 시프트/감소했다 컨플릭트

opt_a 규칙 형 (2)에 (4)로부터 S/R의 수를 변경

%token A B C D SEP 

%% 

items 
    : /* empty */ 
    | items_nonempty 
    ; 

items_nonempty 
    : item 
    | items_nonempty SEP item 
    ; 

item 
    : opt_a B opt_c_d_list 
    ; 

opt_a 
    : /* Nothing */ 
    | A SEP 
    ; 

opt_c_d_list 
    : /* Nothing */ 
    | opt_c_d_list c_or_d 
    ; 

c_or_d 
    : SEP C 
    | SEP D 
    ; 

잔류 문제 동일한 9월이 후 C 또는 D를 sepaerates이다 B와 Yacc는 앞을 내다 볼 수 없습니다.'B SEP D SEP C'를 금지하려면 의미 론적 검사가 필요합니다. 위의 규칙은 그것을 허용 할 것입니다.

SEP C?를 읽고 C를 반환하고 SEP D를 읽는 중 D를 반환하도록 토크 나이저를 수정 해보십시오. 어휘 피드백과 시작 조건을 flex에 사용할 수도 있습니다. B를 읽을 때 스위치를 켜서 SEP C가 C로 반환되고 SEP D가 D로 반환됩니다. 가능하면 다음과 같이 명확한 문법이없는 S/R 충돌로 작동합니다 :

%token A B C D SEP 

%% 

items 
    : /* empty */ 
    | items_nonempty 
    ; 

items_nonempty 
    : item 
    | items_nonempty SEP item 
    ; 

item 
    : opt_a B opt_c opt_d 
    ; 

opt_a 
    : /* Nothing */ 
    | A SEP 
    ; 

opt_c 
    : /* Nothing */ 
    | C 
    ; 

opt_d 
    : /* Nothing */ 
    | D 
    ; 

Answer 3

기본적인 문제는 작성된 문법이이 item의 끝을 발견했을 때 결정 내다보기의 두 토큰을 필요로하고 따라서 또는 경우를 줄일 수 있다는 것입니다 거기에 또 다른 부분은 현재 항목의 SEP 다음 lookahead의 문자로 볼 수 있습니다.

는 접근 방법이 효과적으로 더 내다보기를 얻을 수

• 사용 btyacc 또는 들소의 GLR 지원을 시도 할 수있다.

• 단일 항목의 임의의리스트를 접수 한 후 잘못된 세트를 적어도 1 B 1-4 항목의 세트로 재 그룹 및 거부 후 패스를 사용하여 문법을 작성

(이 군터의 제안이다)

• 스캐너를 사용하여 간단한 SEP 토큰을 반환하는 대신 SEP 다음 토큰이 무엇인지에 따라 SEP_BEFORE_A_OR_B 또는 SEP_NOT_BEFORE_A_OR_B을 반환합니다.

• 스캐너에서 토큰을 결합 - 하나의 토큰으로 SEP_C 및 SEP_D (C 또는 D a로 다음 구분)

Answer 4

당신은 하나의 규칙에 다른 토큰을 다음 SEP를 포함 할 수 있습니다를 반환합니다. 글 아주 간결하게, 당신의 문법은 다음과 같이 표현 될 수있다 :

%token A B C D SEP 
%% 
items : /* empty */ | item | itemsSEP item ; 
item : a B | a b C | a b c D ; 
itemsSEP : itemSEP | itemsSEP itemSEP ; 
itemSEP : a b c d ; 
a : /* empty */ | A SEP ; 
b : B SEP ; 
c : /* empty */ | C SEP ; 
d : /* empty */ | D SEP ; 

을 그래서 지금은 분리 다음 항목에 대한 itemSEP하지만 분리가 따르지 마지막에 item 있습니다. 그것들은 소문자의 단일 문자가 아닌 터미널에서 만들어지며, 각 터미널에는 다음 구분자도 포함되어 있으며 선택적 인수를 처리합니다. item의 마지막 인수 만이 항상 원시 터미널입니다. 그 다음에 구분 기호가 없으므로.

문법이 LALR (1)이므로이 방법으로 표현 된 문법을 사용하면 Shift-Reduction 충돌이 발생하지 않습니다. 모든 단계에서 적용 할 감소가 무엇인지 정확하게 알 수 있습니다. 규칙의 핵심이 하나만 제거하면 더 많은 토큰을 볼 수 있습니다.