Comment est-ce de la grammaire LR(1), mais pas SLR(1)?

J'ai la grammaire suivants, qui je dit, c'est LR(1), mais pas SLR(1):

S ::= un Un | b Un c | d c | d a

Un ::= d

Je ne comprends pas pourquoi c'est. Comment voulez-vous prouver?

  • Si vous allez faire une carrière dans l'informatique d'entreprise, vous avez besoin d'apprendre à lire quand vous ne savez pas quelque chose. Lire Wikipédia sur LR langues soigneusement, et de faire ce travail. Si il faut un certain temps à regarder et à comprendre, ainsi soit-il; c'est typique. en.wikipedia.org/wiki/LR_parser
  • Merci, vous avez été très utile!
  • Sur un ton sens, oui :- }
InformationsquelleAutor Konstantinos Georgiadis | 2012-05-08
  1. 12

    Je n'ai pas assez de karma pour commenter la réponse ci-dessus, et je suis un peu en retard à cette question, mais...

    J'ai vu cette grammaire comme un exemple d'ailleurs, et l'OP fait une faute de frappe. Il doit être:

    S ::= Un a | b Un c | d c | d a

    Un ::= d

    c'est à dire, la première clause de S est "Un une", pas " un Un'.

    Dans ce cas, le SUIT pour Un set est { $, a, c} et il est un REFLEX conflit dans l'état 8.

    • $ n'est pas dans fo(A) pour que la grammaire, mais le S/R conflit est toujours là sans elle.
    InformationsquelleAutor Toby Hutton
  2. 10

    Une façon de le savoir serait d'essayer de construire LR(1) et SLR(1) les analyseurs syntaxiques de la grammaire. Si nous constatons un changement de la/les réduire ou de les réduire/réduire les conflits dans le cadre de la sorte, nous pouvons montrer que la grammaire ne doit pas appartenir à un de ces cours de langues.

    Commençons avec le SLR(1) de l'analyseur. Tout d'abord, nous avons besoin de calculer la LR(0) configurant ensembles pour la grammaire. Ceux-ci sont considérés ici:

    (1)
S -> .aA
S -> .bAc
S -> .dc
S -> .bda

(2)
S -> a.A
A -> .d

(3)
S -> aA.

(4)
A -> d.

(5)
S -> b.Ac
S -> b.da
A -> .d

(6)
S -> bA.c

(7)
S -> bAc.

(8)
S -> bd.a
A -> d.

(9)
S -> bda.

(10)
S -> d.c

(11)
S -> dc.

    Ensuite, nous devons obtenir les ensembles pour tous les nonterminals. Ce qui est montré ici:

    FOLLOW(S) = { $ }
FOLLOW(A) = { $, c }

    Compte tenu de cela, nous pouvons revenir en arrière et de mise à niveau de la LR(0) configurant jeux de SLR(1) configurant ensembles:

    (1)
S -> .aA    [ $ ]
S -> .bAc   [ $ ]
S -> .dc    [ $ ]
S -> .bda   [ $ ]

(2)
S -> a.A    [ $ ]
A -> .d     [ $, c ]

(3)
S -> aA.    [ $ ]

(4)
A -> d.     [ $, c ]

(5)
S -> b.Ac   [ $ ]
S -> b.da   [ $ ]
A -> .d     [ $, c ]

(6)
S -> bA.c   [ $ ]

(7)
S -> bAc.   [ $ ]

(8)
S -> bd.a   [ $ ]
A -> d.     [ $, c ]

(9)
S -> bda.   [ $ ]

(10)
S -> d.c    [ $ ]

(11)
S -> dc.    [ $ ]

    Assez intéressant, il n'y a pas de conflits ici! Le seul changement possible/réduire le nombre de conflits est dans l'état (8), mais il n'y a pas de conflit ici parce que l'action de transfert est sur a et le réduire est sur $. Par conséquent, cette grammaire en fait est SLR(1). Depuis tout SLR(1) grammaire est LR(1), cela signifie que la grammaire est à la fois SLR(1) et LR(1).

    Espérons que cette aide!

    • Il suffit de noter que chaque grammaire SLR (1) est LR (1) de la grammaire, mais pas tous les LR (1) est SLR (1)
    • Si vous êtes à la recherche pour un exemple, vous pouvez utiliser cette grammaire: 1) S –> XX 2) X –> aX 3) X –> b
    • Que faire si il aurait été bda. [ $ ] dans l'état 8. Y aurait-il un à réduire à réduire les conflits ? Car nous n'avons qu'à suivre le symbole de ce qui est commun.
    • Yep, vous auriez un à réduire/réduire les conflits sur le symbole$. Rappelez-vous qu'un groupe de lookaheads fonctions comme "réduire sur aucun de ces symboles," de sorte que tout conflit entre les deux ensembles d'anticipation est un problème.
    • Monsieur, ce serait génial si vous pouviez répondre à cette question, cs.stackexchange.com/questions/80601/slr-vs-clr-parser
    InformationsquelleAutor templatetypedef
  3. 1

    J'ai pensé à écrire une application web afin de déterminer d'abord - et suivez-ensembles pour les CFGs et également LR(0), SLR(1) et LR(1) les tableaux. Cela aurait permis de vous pour essayer de sortir facilement.

    Mais heureusement, j'ai googlé première et a constaté qu'un tel outil existe déjà (je n'ai pas nécessairement que cela soit le cas). Vous pouvez trouver l'outil ici:

    http://smlweb.cpsc.ucalgary.ca/

    Il s'attend que l'entrée dans le format suivant:

    S -> a A | b A c | d c | b d a.
A -> d.

    À l'aide de cet outil, j'ai vérifié ce que les autres ont déjà dit: la grammaire en question est SLR(1). (Je donne -1 à la question).

    Après la modification suggérée par Toby Hutton, il n'est pas SLR(1), mais encore LR(1).

    InformationsquelleAutor Algoman
  4. 0

    1)La grammaire est LL(1) en haut en bas de l'analyse, et LALR(1) en bas de l'analyse.

    2)lors de la création de la table d'analyse, et l'analyse de la table n'a Pas d'inscriptions multiples, puis la grammaire tend à assister à LALR(1).

    3)Si votre table d'analyse entrées multiples(je veux dire le conflit occurrence), alors la grammaire est dit être SLR(1).

    4)Une grammaire est dite LR(1), puisque c'est la table d'analyse ou d'ACTION/GOTO table n'a pas de conflit, et nous savons tous que lors d'un conflit occurrence dans LR(1) nous fusionner les données et nous obtenons le LALR.

    LR(0) OU SLR OU SLR(1) sont les mêmes

    LR(1) OU CLR sont même

    LALR OU LALR(1) sont les mêmes

    du (1) paramètre définit à l'intérieur d'accroître l'efficacité du type de la syntaxe de l'analyseur.

    merci.

    InformationsquelleAutor selvabharathi s