Aide avec la touche Shift / Réduire les conflits - Essayer de modéliser (X A) * (X B) *

Question

Im essayant de modéliser l'expression EBNF

("declare" "namespace" ";")* ("declare" "variable" ";")*

J'ai construit le yacc (Im en utilisant MPPG) la grammaire, qui semble représenter, mais il ne correspond pas à mon expression de test.

Le cas de test je suis en train de faire correspondre est

declare variable;

Le flux Token du lexer est

KW_Declare
KW_Variable
Separator

Le Parse de grammaire dit qu'il ya un « changement / Réduire les conflits, l'état 6 sur KW_Declare ». J'ai essayé de résoudre avec « % gauche PrologHeaderList PrologBodyList », mais aucune solution ne fonctionne.

Program                     : Prolog;
Prolog                      : PrologHeaderList PrologBodyList;

PrologHeaderList            : /*EMPTY*/
                            | PrologHeaderList PrologHeader;
PrologHeader                : KW_Declare KW_Namespace Separator;

PrologBodyList              : /*EMPTY*/
                            | PrologBodyList PrologBody;
PrologBody                  : KW_Declare KW_Variable Separator;

KW_Declare KW_Namespace KW_Variable séparateur sont tous les jetons avec des valeurs "déclarer", "naemsapce", "variable", ";"

.

Answer 1

Il a été longtemps que je l'ai utilisé quoi que ce soit yacc comme, mais voici quelques suggestions qui peuvent ou peuvent ne pas aider.

Il semble que vous avez besoin d'un 2-token préanalyse dans cette situation. L'analyseur arrive à la dernière PrologHeader , et il doit décider si la prochaine construction est un PrologHeader ou PrologBody , et il ne peut pas dire que du KW_Declare. S'il y a une directive visant à renforcer dans cette situation préanalyse, il résoudra probablement le problème.

Vous pouvez également introduire le contexte dans vos actions: plutôt que de définir PrologHeaderList et PrologBodyList , définir PrologRuleList et que vous avez les actions jeter une erreur si un en-tête apparaît après un corps. Laid, mais parfois, vous devez le faire. Ce qui semble simple dans une grammaire ne peut pas être simple dans l'analyseur généré

Une approche hackish pourrait être de combiner les jetons: plutôt que KW_Declare et KW_Variable , demandez à votre lexer reconnaître l'espace et utiliser KW_Declare_Variable . Puisque les deux sont des mots clés, vous ne vont pas rencontrer des problèmes de collision d'espace de noms.

Answer 2

La grammaire en haut est régulière si IIRC vous pouvez le tracer comme un DFA (ou un NDA et le convertir en un DFA), puis convertir le DFA à une grammaire. Il est un haricot alors que je vais donc laisser le travail comme un exercice pour le lecteur.