문법 스펙 해결 Shift/충돌 감소

Question

Jison (Bison)을 사용하여 간단한 마크 업 언어를 작성하고 있습니다. 나는 이것에 대해 명확하게 새롭지 만, 약간의 변형이 잘 작동하고있다. 나는 단지 S/R 갈등의 원인을 이해하지 못한다.

두 개의 렉서 동작 (시작 조건이 다름)이 '텍스트'를 반환하지 않아 문법에 규칙이 적게 들거나 사용자에게 표시되는 오류 메시지가 일관된. 컨텍스트에 상관없이 '텍스트'규칙을 일반화하려고 시도했지만 각 토큰에 다른 이름을 부여하려고했지만 S/R 충돌에 영향을 미치지 않습니다.

일반 텍스트, 하위 배열 및 다양한 특수 노드가있는 json 개체를 만들려면 구문 분석기가 지원됩니다.

사양 :

/* lexical grammar */ 
%lex 

%s bracketed 

%% 

<bracketed>(\\.|[^\\\,\[\]])+  { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; } 
<INITIAL>(\\.|[^\\\[])+    { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; } 
"["         { this.begin('bracketed'); return '['; } 
"]"         { this.popState(); return ']'; } 
","         return ',' 
<<EOF>>        return 'END' 

/lex 

%start template 

%%  

template 
    : sentence END 
    ; 

sentence 
    : /* empty */ 
    | sentence Text 
    | sentence '[' ']' 
    | sentence '[' dynamic ']' 
    ; 

dynamic 
    : sentence 
    /*| dynamic ',' sentence*/ 
    ; 

경고 :

Conflict in grammar: multiple actions possible when lookahead token is ] in state 5 
- reduce by rule: sentence -> 
- shift token (then go to state 6) 

States with conflicts: 
State 5 
    sentence -> sentence [ .] #lookaheads= END Text [ ] 
    sentence -> sentence [ .dynamic ] #lookaheads= END Text [ ] 
    dynamic -> .sentence #lookaheads= ] 
    sentence -> . #lookaheads= ] Text [ 
    sentence -> .sentence Text 
    sentence -> .sentence [ ] 
    sentence -> .sentence [ dynamic ] 

다른 생성 알고리즘은 다소 문제가 있지만, 그들은 모두 문제가있는 것 같다.

감사합니다.

Answer 1

충돌이 두 가지 규칙에서 기본적으로 제공 :

이유는 sentence과 [을보고하고 Text되는 다음 토큰보고 후, 파서가를 이동할지 여부를 알려하지 않는 것을

sentence: sentence '[' Text ']' 
     | sentence '[' sentenceList ']' 

Text을 입력하거나 첫 번째 규칙과 일치 시키거나 두 번째 규칙과 일치하는쪽으로 시작하여 Text을 처리합니다.

2 토큰 미리보기를 사용하는 파서 생성기가있는 경우 문제가되지 않지만 bison은 LALR (1)입니다 (1은 하나의 토큰 미리보기 임).

몇 가지 당신이 시도 할 수 있습니다 :

• 이 텍스트 다음-부산물] 텍스트 --따르지 않을-부산물에서] 등 두 가지 토큰을 구분하기 위해 렉서에 추가 내다을 다음 두 토큰을 모두 사용하도록 규칙을 다시 작성하십시오.

• GLR 파서를 사용하려면 bison의 % glr-parser 기능을 사용하십시오. 문장을 두 가지 방식으로 구문 분석하고 나중에 일치하지 않는 문장을 버립니다.

• 리팩터링 2 토큰 미리보기가 필요없는 문법. 귀하의 경우 작동

한 리팩토링은 그들에게 확인하기 위해 sentence 규칙을 재 작성하는 것 모두 오른쪽 재귀 대신 재귀 왼쪽 :

sentence: /* empty */ 
     | Text sentence 
     | '[' ']' sentence 
     | '[' Text ']' sentence 
     | '[' sentenceList ']' sentence 
     ; 

이것은 sentence을 가진 방지 (또는 다른 규칙 sentenceList과 같이 sentence으로 시작하는)는 sentence: /*empty*/ 규칙의 널 (NULL) 감소로 시작합니다. 따라서 파서는 문제가되는 경우에 다음 토큰을 볼 때까지 줄이기를 지연하여 Text을 자유롭게 바꿀 수 있습니다.그러나 파서가 전체 입력을 파서 스택으로 옮겨서 한 번에 한 문장 씩 줄이는 파서가되기 때문에 메모리 사용과 관련된 의미가 있습니다.

는 [sentenceList]에 [Text] 및 [] 구조를 포괄하는 것입니다 할 수있는 또 다른 리팩토링 : 그래서 지금 sentenceList 하나 이상의 (대신 두 개 이상) 쉼표로 구분 된 문장이다

sentence: /* empty */ 
     | sentence Text 
     | sentence '[' sentenceList ']' 
     ; 

sentenceList: sentence 
      | sentenceList ',' sentence 

하고, sentence '[' sentenceList ']' 규칙에 대한 조치에서 sentenceList을 확인하여 두 개 이상의 문장인지 확인하고 적절히 행동하십시오.