Questions sur les algorithmes qui décident si une chaîne donnée appartient à un langage formel fixe.
Les gens disent souvent que les analyseurs syntaxiques LR (k) sont plus puissants que les analyseurs syntaxiques LL (k) . Ces déclarations sont vagues la plupart du temps; en particulier, devrions-nous comparer les classes pour un fixe ou l'union sur tous les k ? Alors, comment est la situation...
EPAL, la langue des palindromes pairs, est définie comme la langue générée par la grammaire sans contexte suivante sans ambiguïté: S→ a aS→aaS \rightarrow a a S→ b bS→bbS \rightarrow b b S→ un SuneS→aSaS \rightarrow a S a S→ b SbS→bSbS \rightarrow b S b EPAL est le «fléau» de nombreux algorithmes...
Je souhaite analyser les langues spécifiques au domaine défini par l'utilisateur. Ces langages sont généralement proches des notations mathématiques (je n'analyse pas un langage naturel). Les utilisateurs définissent leur DSL dans une notation BNF, comme ceci: expr ::= LiteralInteger | ( expr ) |...
Apparemment, les attaques ReDos exploitent les caractéristiques de certaines expressions régulières (autrement utiles) ... provoquant essentiellement une explosion de chemins possibles à travers le graphique défini par le NFA. Est-il possible d'éviter de tels problèmes en écrivant une expression...
Si j'ai une grammaire de type 3, elle peut être représentée sur un automate déroulant (sans faire aucune opération sur la pile) afin que je puisse représenter des expressions régulières en utilisant des langages sans contexte. Mais puis-je savoir si une grammaire de type 3 est , L L ( 1 ) , S L R (...
Il est possible d'analyser un document en un seul passage depuis une machine d'état. Quel est l'avantage d'avoir deux passes, à savoir. avoir un lexer pour convertir du texte en jetons, et avoir un analyseur pour tester les règles de production sur ces jetons? Pourquoi ne pas avoir un seul passage...
Selon l'article de Wikipedia , le L dans signifie "balayage de gauche à droite" et le "R" signifie "dérivation la plus à droite". Cependant, dans l'article original de Knuth sur les grammaires L R ( k ) , il définit L R ( k ) (à la page 610) comme un langage "traduisible de gauche à droite avec k...
J'essaie de m'enseigner l'usage du bison. Le bison de la page de manuel (1) dit à propos du bison: Générez un analyseur syntaxique déterministe LR ou LR généralisé (GLR) en utilisant les tables d'analyseur LALR (1), IELR (1) ou canonique LR (1). Qu'est-ce qu'un analyseur IELR? Tous les articles...
Je pensais aux grammaires pour les langues sensibles à l'indentation et il semble que les grammaires CF feraient l'affaire si elles étaient combinées avec des paramètres. À titre d'exemple, considérons ce fragment pour la grammaire Python simplifiée au format de type ANTLR: // on top-level the...
Je travaille souvent avec lexer / parsers , par opposition à un combinateur d'analyseurs et je vois des gens qui n'ont jamais suivi de cours d'analyse, poser des questions sur l'analyse des données binaires. En règle générale, les données sont non seulement binaires, mais également contextuelles....
J'ai un problème avec cet exercice: Soit G la grammaire ambiguë suivante pour le λ-calcul: E → v | λv.E | EE | (E) où E est le symbole non terminal unique, λv.E représente l'abstraction par rapport à la variable v dans E et EE représente l'application. Définissez une grammaire LL (1) G ′ telle que...
J'essaie de comprendre ce que l'on entend par «déterministe» dans des expressions telles que «grammaire déterministe sans contexte». (Il y a des "choses" plus déterministes dans ce domaine). J'apprécierais un exemple plus que l'explication la plus élaborée! Si possible. Ma principale source de...
Ceci est une question du Dragon Book. Voici la grammaire: S→AaAb∣BbBaS→AaAb∣BbBaS \to AaAb \mid BbBa A→εA→εA \to \varepsilon B→εB→εB \to \varepsilon La question demande comment montrer qu'il s'agit de LL (1) mais pas de SLR (1). Pour prouver qu'il s'agit de LL (1), j'ai essayé de construire sa...
J'étudie récemment la conception de compilateurs. J'ai appris l'existence de deux types de grammaire: la grammaire LL et la grammaire LR. Nous savons également que chaque grammaire LL est LR, c'est-à-dire que la grammaire LL est un sous-ensemble approprié de la grammaire LR. Le premier est utilisé...
Je souhaite convertir une expression régulière entrée par l'utilisateur en NFA afin de pouvoir ensuite exécuter le NFA sur une chaîne à des fins de correspondance. Quelle est la machine minimale qui peut être utilisée pour analyser des expressions régulières? Je suppose que ce doit être un automate...
Quelqu'un peut-il m'éclairer pourquoi un analyseur de descente récursive avec retour arrière qui essaie les productions et (dans cet ordre) ne reconnaît pas le langage formé par la grammaire .S→ un SuneS→uneSuneS \rightarrow aSaS→ a aS→uneuneS \rightarrow aaS→ un Sa | a a S→uneSune | uneuneS...
Dans un analyseur LR (0), chaque état consiste en une collection d'éléments LR (0), qui sont des productions annotées avec une position. Dans un analyseur LR (1), chaque état consiste en une collection d'éléments LR (1), qui sont des productions annotées avec une position et un caractère...
Il existe un moyen d'effectuer une analyse floue (accepte les chaînes même avec des fautes de frappe à une certaine distance d'édition), avec un DFA et un automate Levenshtein construit au moment de l'exécution du mot d'entrée. Peut-on faire quelque chose de similaire avec un analyseur Earley? J'ai...
L'utilisation du vecteur Earley comme identificateur est assez simple: lorsque la fin de la chaîne est atteinte, il vous suffit de vérifier si la production axiomatique terminée a commencé à la position 0. Si vous en avez au moins une, la chaîne est acceptée. L'utilisation du vecteur Earley pour...
Au collège, nous avons appris la théorie du calcul en général et les machines de Turing plus spécifiquement. L'un des grands résultats théoriques est qu'au prix d'un alphabet potentiellement grand (symboles), vous pouvez réduire le nombre d'états à seulement 2. Je cherchais des exemples de...