Spécification de grammaire résolvant les conflits Shift/Reduce

Question

J'utilise Jison (Bison) pour créer un langage de balisage simple.Je suis clairement nouveau dans ce domaine, mais de légères variations fonctionnent très bien.Je ne comprends tout simplement pas la source du conflit S/R.

Il ne semble pas important que « Texte » soit renvoyé par deux actions lexer (avec des conditions de démarrage différentes) et j'aime cela car cela semble permettre à la grammaire d'avoir moins de règles et parce que les messages d'erreur adressés à l'utilisateur sont cohérents.J'ai essayé de rendre la règle « Texte » commune quel que soit le contexte et j'ai également essayé de donner à chaque jeton un nom différent, mais cela ne semble pas avoir d'effet sur les conflits S/R lorsque tout est ensemble.

L'analyseur est CENSÉ créer un objet json avec du texte brut, des sous-tableaux et divers nœuds spéciaux.

Spécification:

/* 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*/
    ;

Avertissements:

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 ]

Différents algorithmes de générateur ont plus ou moins de problèmes, mais ils semblent tous avoir des problèmes.

Merci!

Answer 1

Le conflit vient fondamentalement de ces deux règles :

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

La raison est qu'après avoir vu un sentence et un [ et en regardant le prochain jeton étant Text, l'analyseur ne sait pas s'il doit décaler le Text, correspondant à la première règle, ou pour traiter cela Text comme le début d'un sentenceList aller vers la correspondance avec la deuxième règle.

Maintenant, si vous aviez un générateur d'analyseur qui utilise une anticipation à 2 jetons, cela ne poserait pas de problème, mais bison est LALR (1) (le 1 étant une anticipation à un jeton).

Vous pouvez essayer plusieurs choses :

• effectuez une analyse anticipée supplémentaire dans le lexer pour différencier Text-follow-by-] de Text-not-follow-by-] comme deux jetons distincts, puis réécrivez les règles pour utiliser ces deux jetons.

• Utilisez la fonctionnalité %glr-parser de bison pour utiliser l'analyseur GLR.Cela analysera la phrase dans les deux sens et supprimera plus tard celle qui ne correspond pas

• refactorisez la grammaire pour ne pas avoir besoin d'une anticipation à 2 jetons.

Une refactorisation qui fonctionne dans votre cas serait de réécrire le sentence règles pour les rendre tous récursifs à droite au lieu de récursifs à gauche :

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

Cela évite d'avoir sentence (ou toute autre règle commençant par sentence tel que sentenceList) commencent par une réduction nulle du sentence: /*empty*/ règle.Ainsi, l'analyseur peut librement déplacer un Text dans le cas problématique, reporter la réduction jusqu'à ce qu'il voie le prochain jeton.Cela a cependant des implications en matière d'utilisation de la mémoire, car il en résulte un analyseur qui déplacera essentiellement l'intégralité de l'entrée vers la pile de l'analyseur, puis la réduira une phrase à la fois.

Un autre refactor que vous pourriez faire serait d'intégrer le [Text] et [] construit dans le [sentenceList]:

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

sentenceList: sentence
            | sentenceList ',' sentence

Alors maintenant un sentenceList est une ou plusieurs phrases séparées par des virgules (au lieu de deux ou plus), et dans l'action pour la sentence '[' sentenceList ']' règle, tu vérifierais le sentenceList pour voir s'il s'agissait de deux phrases ou plus et agir en conséquence.