Problème résolution d'un conflit de décalage réduire dans ma grammaire

Question

Je suis en train d'écrire un petit analyseur avec Irony. Malheureusement, je reçois un « shift-réduire les conflits ». Grammars ne sont pas mon point fort, et je ne doivent se faire cette petite fait thingy. Voici la grammaire réduite qui produit l'erreur:

ExpressionTerm := "asd"
LogicalExpression :=
    ExpressionTerm |
    LogicalExpression "AND" LogicalExpression |
    LogicalExpression "OR" LogicalExpression

Qu'est-ce que le « shift-réduire les conflits » et comment puis-je résoudre? Je suppose que cela signifie que ma grammaire est ambiguë, mais je ne peux pas tourner suffisamment ma logique pour voir comment.

Ajouté: Pour clarifier - "asd" est simplement une chaîne littérale de "asd". Donc, j'attendre à ce que les expressions suivantes sont analysées par cette grammaire:

asd
asd AND asd
asd AND asd OR asd
asd OR asd AND asd OR asd

Ajouté 2:. Mot-à-dire la racine de la grammaire est LogicalExpression

Ajouté 3: Ahh, je l'ai! L'ambiguïté est parce qu'une expression comme

asd AND asd OR asd

pourrait être interprété de deux manières différentes:

(asd AND asd) OR asd
asd AND (asd OR asd)

Mais comment puis-je résoudre ce problème? OK, je peux mettre l'un des AND ou OR pour être plus forte que l'autre (j'avais de toute façon BUT). Mais maintenant, je vois que l'erreur apparaît même s'il n'y a qu'un seul opérateur. En d'autres termes, il se produit également la même erreur:

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

Dans ce cas, je veux ceci:

asd OR asd OR asd

à parser à ceci:

(asd OR asd) OR asd

Quelle est la façon non ambiguë de le faire?

Ajouté 4: Got it

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

Cette analyse toutes les expressions booléennes, avec priorité de l'opérateur NOT-> ET-> OR. « Asd » peut être remplacé par l'expression destinée à vos termes.

Answer 1

Votre grammaire est ambiguë, si vous utilisez un seul préanalyse. Pour illustrer, ce qui est « asd »? Est-ce un ExpressionTerm ou long terme. C'est la touche Maj enfoncée réduire les conflits. Je soupçonne une réduction-de réduire les conflits ici.

La plupart des LL (1) / LALR (1) générateurs fournira un moyen de régler les conflits de décalage réduire par les opérateurs de priorité. La plupart par défaut également la plus longue séquence en présence d'un conflit de décalage de réduire, de façon plus souvent ceux-ci peuvent être ignorés (après un examen). (Dans ce cas, vous devez peut-être déplacer le seul terme au fond pour se comporter correctement).

Answer 2

Shift-Réduire signifie conflit que votre grammaire est ambiguë. Avec votre règle récursive un jeton « asd » pourrait être interprétée comme faisant partie de l'une ou ExpressionTerm LogicalExpression et l'analyseur ne peut pas décider. Besoin d'une règle supplémentaire pour briser l'égalité.

Answer 3

Décalage de réduire les conflits sont l'une des choses les plus difficiles à obtenir votre cerveau autour quand il s'agit de parseurs. La meilleure façon d'illustrer le conflit est dans ce pseudo-code:

if (a) then
   if (b) then
     printf('a + b');
   else
     print('this could be a + !b or !a');

L'instruction else pourrait se lier à la première ou deuxième si. Dans le cas des grammaires ambiguës, vous définissez généralement une valeur pour indiquer le nombre de décalage prévu de réduire les avertissements dans votre grammaire.

Vous pouvez utiliser une LL (k) ou analyseur LL (*). Ces types de parseurs n'ont pas le changement / réduire l'ambiguïté. En fonction de votre application, ils peuvent être plus facile ou plus difficile que l'analyseur LALR (1).

Answer 4

grammaire est ambiguë LL(1) ou LALR(1) depuis jeton asd peut être substitué dans ExpressionTerm et aussi LogicalExpression aplatir les règles de grammaire pour résoudre changement / réduire les conflits