Problème résolvant un conflit shift-reduce dans ma grammaire

J'essaye d'écrire un petit analyseur avec Irony. Malheureusement, je reçois un "décalage-réduire le conflit". Les grammaires ne sont pas mon point fort, et je n'ai besoin que de faire une petite chose. Voici la grammaire réduite qui produit l'erreur:Problème résolvant un conflit shift-reduce dans ma grammaire

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

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

Ajouté: Pour clarifier - "asd" est simplement une chaîne littérale "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: oublié de dire, la racine de la grammaire est LogicalExpression.

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

asd AND asd OR asd

pourrait être interprété de deux façons 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 un des ET ET OU être plus fort que l'autre (j'avais compris de toute façon). 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

à analyser à ceci:

(asd OR asd) OR asd

Quel est le non manière 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.

Source

2009-05-26 Vilx-

Heh, viennent à penser, je commence à le rappeler modèle de mes jours à l'Université. : D –

Votre grammaire est ambiguë si vous n'utilisez qu'une seule recherche. Pour illustrer, qu'est-ce que "asd"? Est-ce un ExpressionTerm ou un terme plus long. C'est le décalage-réduire le conflit. Je soupçonne un conflit réduire-réduire ici aussi.

La plupart 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 vont aussi par défaut à la séquence la plus longue en présence d'un conflit de décalage-réduction, de sorte que plus souvent que ceux-ci peuvent être ignorés (après un examen minutieux). (Dans ce cas, vous devrez peut-être déplacer le terme unique vers le bas pour qu'il se comporte correctement).

Source

2009-05-26 12:41:07 leppie

"asd" est simplement une chaîne littérale "asd". –

Je ne comprends toujours pas. ET et OU devraient dans ce cas avoir la même priorité. –

Avec 1 lookahead de caractère, vous pouvez oublier AND et OR. Le conflit est plus tôt :) – leppie

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

Source

2009-05-26 12:45:25 dwc

La réduction des conflits est l'une des choses les plus difficiles à comprendre pour les 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 de grammaires ambiguës, vous définissez généralement une valeur pour indiquer le nombre d'avertissements shift-reduce attendus dans votre grammaire.

Vous pouvez également utiliser un analyseur LL (k) ou LL (*). Ces types de parseurs n'ont pas le décalage/réduire l'ambiguïté. Selon votre application, ils peuvent être plus faciles ou plus difficiles que l'analyseur LALR (1).

Source

2009-06-04 01:16:17 brianegge

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

Source

2013-09-08 13:22:16

Problème résolvant un conflit shift-reduce dans ma grammaire

Répondre

Questions connexes