J'ai découvert un exercice qui nécessite une astuce pour comprendre si une grammaire est LR (1) sans opérations de table d'analyse.Comprendre si une grammaire est LR (1) sans table d'analyse
La grammaire est le suivi:
S -> Aa | Bb
A -> aAb | ab
B -> aBbb | abb
Savez-vous quel est le truc derrière?
Merci :),
Imaginez que vous êtes un analyseur LR (1) et que vous venez de lire aab avec un b de préanalyse. (Je sais, vous pensez probablement "l'homme, cela m'arrive tout le temps!") Que devriez-vous faire exactement ici?
En regardant la grammaire, vous ne pouvez pas dire si la production initiale était Aa ou Bb, donc vous allez devoir considérer simultanément les règles de production pour A et B. Si vous regardez les options A, vous verrez qu'une option ici serait de réduire A → ab, ce qui est plausible ici parce que le lookahead est un b et c'est exactement ce que vous attendez à trouver après avoir vu un ab sur un A (notez qu'il y a la règle A → aRb, donc tout A récursivement étendu serait suivi d'un b). Cela vous dit de réduire. D'un autre côté, regardez les options B. Si vous voyez aab suivi d'un b, vous penseriez "oh, ce deuxième b va faire aabb, et puis j'irais et réduirais B → abb, parce que c'est tout à fait une chose que j'aime faire parce que je ' m un analyseur LR (1). " Alors ça vous dit de changer. À ce stade, bam! Vous avez un changement/réduire les conflits, donc vous n'allez certainement pas avoir une grammaire LR (1).
Est-ce que cela se produit réellement? Eh bien, allons construire le LR (1) ensembles que nous configurant verrions si nous avons effectivement lu aab et voir b comme préanalyse:
Initial State
S' -> .S [$]
S -> .Aa [$]
S -> .Bb [$]
A -> .aAb [a]
A -> .ab [a]
B -> .aBbb [b]
B -> .abb [b]
State after reading a
A -> a.Ab [a]
A -> a.b [a]
A -> .aAb [b]
A -> .ab [b]
B -> a.Bbb [b]
B -> a.bb [b]
B -> .aBbb [b]
B -> .abb [b]
State after reading aa
A -> a.Ab [b]
A -> a.b [b]
A -> .aAb [b]
A -> .ab [b]
B -> a.Bbb [b]
B -> a.bb [b]
B -> .aBbb [b]
B -> .abb [b]
State after reading aab
A -> ab. [b]
B -> ab.b [b]
Et hey! Il y a ce changement/réduction des conflits dont nous parlions. Ce premier item diminue sur b, mais le second sur b. Alors voilà! Notre intuition nous a amenés à penser que cela ne va pas être une grammaire LR (1), et si nous regardons les tableaux, les preuves sont supportées par les données.
Alors, comment savez-vous essayer cela? Eh bien, en général, c'est assez difficile à faire. Le principal indice, pour moi, au moins, est que l'analyseur doit deviner s'il veut A ou B à un certain point, mais la façon dont il se lie est le nombre de b s. L'analyseur allait devoir à un certain point déterminer s'il aime ab et aller avec A ou s'il aime abb et aller avec B, mais il ne peut pas voir les deux b s avant de prendre la décision. Cela m'a amené à penser que nous aimerions trouver une sorte de conflit où nous avons vu assez de savoir qu'une certaine récursion se produisait (de sorte que le b qui suivrait poserait problème) et de trouver un endroit où la récursivité serait différente entre les deux règles de production.