1
Je suis tombé sur de nombreux algorithmes différents (CYK et Earley) pour vérifier si une chaîne fait partie de la LCF dont le CFG est fourni. Je cherche quelque chose de simple à comprendre et à mettre en œuvre. Ce que j'ai besoin de savoir, c'est si la chaîne est dans le CFG ou pas. Le CFG est donnée habituellement sous la forme desimple analyseur CFG avec transition epsilon
S->S1 S2
S1->S1 a | a
S2->S2 b | b
La solution est censé accepter les transitions epsilon, ainsi par exemple S1-> a | e
des idées?
Vous avez donc trouvé de nombreux algorithmes différents. Pourquoi n'essayez-vous pas d'en implanter un? –
Je crois qu'ils sont plus compliqués et nécessitent un certain type d'entrée, ils ne supportent pas non plus les transitions epsilon. – Iordanis
1) Ils ne sont pas si compliqués. 2) "exiger un certain type d'entrée"; quelle contribution spéciale ont-ils besoin (vous ne pouvez pas vous plaindre de telles choses sans fournir des preuves). 3) Je pensais que l'algorithme d'Earley ne dérange pas les règles d'epsilon. Wikipedia http://en.wikipedia.org/wiki/Earley_parser semble prétendre ("alpha beta gamma ... [peut être] la chaîne vide") que l'algorithme d'Earley permet des règles avec des transitions epsilon. Une personne moins généreuse pourrait penser que vous n'avez pas fait vos devoirs. –