Existe-t-il une résolution différente du problème «balançant le reste» autre que «correspondre le plus près»?

9

La grammaire non contextuelle suivante présente une ambiguïté de type "balançant le reste" (imaginez que représente et représente et représente un autre type d'instruction ou de bloc): $a$ if expr then $b$ else $c$ Par exemple,peut être analysé commeou comme(c'est le mot ambigu le plus simple / le plus court pour cette grammaire).

\begin{aligned} S & \to a S b S | a S | c \end{aligned}

$\begin{aligned} S &\rightarrow aSbS \;|\; aS \;|\; c\\ \end{aligned}$

a a c b c

$aacbc$

(a (a c b c))

$(a(acbc))$

(a (a c) b c)

$(a(ac)bc)$

La manière "standard" de résoudre cette ambiguïté "pendant pendant" oblige l' instruction "else" ( ) à s'apparier avec le "if-then" ( ) le plus proche / le plus proche . Cela peut être accompli comme suit: $b$ $a$ Cette grammaire est sans ambiguïté. Dans l'exemple ci-dessus, il force l'analyse.

\begin{aligned} S & \to a T b S | a S | c \\ T & \to a T b T | c \end{aligned}

$\begin{aligned} S &\rightarrow aTbS \;|\; aS \;|\; c\\ T &\rightarrow aTbT \;|\; c\\ \end{aligned}$

(a (a c b c))

$(a(acbc))$

Question: Existe - t-il un autre moyen naturel de résoudre l'ambiguïté qui forcerait l' analyse de ? En d'autres termes, je recherche une grammaire qui génère le même langage que les deux ci-dessus, qui est sans ambiguïté, et qui analyse comme . $(a(ac)bc)$ $aacbc$ $aacbc$ $(a(ac)bc)$

Remarque: Ma première tentative a été la suivante: qui résout l'ambiguïté deselon les besoins - mais cette grammaire est toujours ambiguë:peut être analysée commeou comme.

\begin{aligned} S & \to a S b S | a U | c \\ U & \to a U | c \end{aligned}

$\begin{aligned} S &\rightarrow aSbS \;|\; aU \;|\; c\\ U &\rightarrow aU \;|\; c\\ \end{aligned}$

a a c b c

$aacbc$

a a c b a c b c

$aacbacbc$

(a (a c) b (a c b c))

$(a(ac)b(acbc))$

(a (a c b (a c)) b c)

$(a(acb(ac))bc)$

context-free formal-grammars parsers ambiguity Gro-Tsen
la source

1

Et dans votre dernier exemple, laquelle des deux analyses possibles considérez-vous comme "naturelle" ou correcte, et pourquoi?

rici

@rici Oui, c'est une question délicate !, et je ne sais pas. Je serai satisfait d'une grammaire sans ambiguïté qui produit soit l'analyse de

. Ce qui m'importe le plus, c'est que

(avec plus de

que de

) correspond au

-ième dernier

avec le

-ième

(et laisse le plus à l' intérieur d'

« s inégalée).

a a c b a c b c

$aacbacbc$

a a a \dots a a a c b c b c \dots b c

$aaa\ldots aaacbcbc\ldots bc$

a

$a$

b

$b$

k

$k$

b

$b$

k

$k$

a

$a$

a

$a$

Gro-Tsen

7

Ce problème est un analogue exact du problème de correspondance des parenthèses dans une expression dans laquelle certaines des parenthèses fermées ont été omises. Ici, un "si" (ou dans la grammaire représentative) est une parenthèse ouverte et un "autre" ( ) est une parenthèse étroite. (À partir de la séquence de s et s, vous pouvez insérer mécaniquement s en plaçant un avant chaque et un à la fin.) Parce que cela correspond mieux à mon cerveau entre parenthèses, j'écris comme si c'était le problème. $a$ $b$ $a$ $b$ $c$ $b$

La résolution traditionnelle "Correspondance la plus proche", sinon correspond à chaque fermeture avec l'ouverture la plus récente encore inégalée. Cela signifie qu'il n'y a jamais d'ouverture ouverte (ou de fermeture, d'ailleurs) entre une ouverture correspondante et sa fermeture correspondante.

Une alternative possible serait de faire correspondre chaque fermeture avec l'ouverture la plus rapprochée possible et inégalée. "Faisable" signifie ici que l'ouverture peut être mise en correspondance sans violer l'imbrication entre parenthèses (par exemple, la première dans ne peut pas correspondre à la dernière ). $($ $()()$ $)$

Cette correspondance doit être effectuée de l'extérieur vers l'intérieur, de sorte qu'aucune correspondance pour une fermeture ne soit tentée tant que toutes les paires englobantes n'ont pas été mises en correspondance. Ce fait rend impossible la production d'une analyse avec un algorithme d'anticipation bornée, car l'analyse doit fonctionner vers l'intérieur à partir des deux extrémités, après avoir divisé la chaîne en segments complètement correspondants (car ceux-ci limitent efficacement la plage de correspondances potentielles).

Cependant, le fait qu'il n'existe pas d'analyseur de gauche à droite en ligne n'implique pas qu'il n'y a pas de CFG sans ambiguïté. (Évidemment: une langue palindromique doit être analysée des deux extrémités vers le milieu, mais il est facile d'écrire une grammaire non ambiguë).

Pour produire une grammaire pour le problème de parenthèse "le plus éloigné", je me suis appuyé sur le fait qu'une ouverture sans correspondance ne peut pas être suivie d'une ouverture avec correspondance. Si tel était le cas, la propriété de correspondance la plus éloignée ne s'appliquerait pas car l'ouverture sans correspondance aurait pu correspondre à la fermeture de l'ouverture correspondante, donc le fait qu'elle ne soit pas correspondante viole la propriété de correspondance la plus éloignée.

Voici donc la grammaire légèrement maladroite:

\begin{aligned} S & \to U | M \\ U & \to T | a U b T | a U b c | a M b U \\ M & \to a M b M | c \\ T & \to a T | a c \end{aligned}

$\begin{aligned} S&\to U \;|\; M \\ U&\to T \;|\; a U b T \;|\; a U b c \;|\; a M b U \\ M&\to a M b M \;|\; c \\ T&\to a T \;|\; a c \\ \end{aligned}$

$S$ $M$ $U$ $a$ $T$ $a$ $T$ $T$ $U$ $U$ $T$

$U$ $U$ $S$ $M^* U$ $S$ $M$ $U$ $M$ $U$

Il existe probablement une meilleure solution de contournement que celle que j'ai choisie. Mais celui-ci semble fonctionner, et il fonctionne bien avec l'analyseur GLR de Bison que j'ai utilisé pour le tester; cet analyseur se plaint des analyses ambiguës sauf si vous écrivez du code supplémentaire pour gérer l'ambiguïté, et j'étais trop paresseux pour le faire. Je l'ai testé avec des chaînes allant jusqu'à 20 ouvert + ferme, et il semble avoir produit une analyse sans ambiguïté pour chaque séquence correctement imbriquée, sans produire d'analyses pour les séquences incorrectement imbriquées.

rici
la source

Félicitations pour avoir réalisé ce que j'avais conclu était probablement impossible! J'ai vérifié expérimentalement que pour les mots de longueur ≤16, cette grammaire est en effet sans ambiguïté et génère les mêmes mots que ceux de ma question. Maintenant, je dois comprendre en détail comment cela fonctionne!

Gro-Tsen

S \to a S b T | a M b S

$S \to aSbT \;|\; aMbS$

M

$M$

T \to a T | c

$T\to aT\;|\;c$

U

$U$

0

Prenez a + b + c + d + e et abcde. Il existe deux façons évidentes comment une grammaire pourrait les analyser, mais il y a une façon que nous utilisons.

Dans le cas du "balançoire d'autre", ce n'est pas vraiment la façon dont les gens le voient. Au lieu de cela, la syntaxe est interprétée comme "si", suivi de zéro, d'un ou plusieurs "else si", suivi d'un "else" facultatif.

gnasher729
la source

a c b a c b a c b c

$acbacbacbc$

Existe-t-il une résolution différente du problème «balançant le reste» autre que «correspondre le plus près»?

Réponses: