Shift/Reduce 충돌을 해결하는 문법 사양

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: sentence '[' Text ']'
        | sentence '[' sentenceList ']'

그 이유는, 한 번 본 후에 sentence 그리고 [ 그리고 다음 토큰을 보면 Text, 파서는 이동 여부를 알 수 없습니다. Text, 첫 번째 규칙과 일치하거나 이를 처리하기 위해 Text a의 시작으로서 sentenceList 두 번째 규칙을 일치시키는 방향으로 진행됩니다.

이제 2-토큰 예측을 사용하는 파서 생성기가 있는 경우 이는 문제가 되지 않지만 bison은 LALR(1)입니다(1은 하나의 토큰 예측임).

시도해 볼 수 있는 몇 가지 작업은 다음과 같습니다.

• Text-followed-]와 Text-not-followed-by-]를 두 개의 고유한 토큰으로 구별하기 위해 어휘분석기에서 추가 예측을 수행한 다음 이 두 토큰을 모두 사용하도록 규칙을 다시 작성합니다.

• GLR 파서를 사용하려면 bison의 %glr-parser 기능을 사용하세요.이렇게 하면 문장을 양방향으로 구문 분석하고 나중에 일치하지 않는 문장을 버립니다.

• 2-토큰 미리보기가 필요하지 않도록 문법을 리팩터링합니다.

귀하의 경우에 작동하는 리팩토링 중 하나는 sentence 왼쪽 재귀 대신 오른쪽 재귀로 만드는 규칙:

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

이것은 sentence (또는 다음으로 시작하는 다른 규칙 sentence ~와 같은 sentenceList)의 null 감소로 시작합니다. sentence: /*empty*/ 규칙.따라서 파서는 다음을 자유롭게 이동할 수 있습니다. Text 문제가 있는 경우에는 다음 토큰을 볼 때까지 축소를 연기합니다.그러나 이는 전체 입력을 파서 스택으로 이동한 다음 한 번에 한 문장씩 줄이는 파서가 되기 때문에 메모리 사용에 영향을 미칩니다.

당신이 할 수 있는 또 다른 리팩토링은 [Text] 그리고 [] 으로 구성 [sentenceList]:

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

sentenceList: sentence
            | sentenceList ',' sentence

그래서 지금은 sentenceList 두 개 이상의 문장이 아닌 쉼표로 구분된 하나 이상의 문장이며, sentence '[' sentenceList ']' 규칙에 따라 sentenceList 두 개 이상의 문장인지 확인하고 적절하게 행동하세요.