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...
Soit GGG une grammaire sans contexte. Une chaîne de terminaux et de nonterminals est dit être une forme propositionnelle de si vous pouvez l' obtenir en appliquant des productions de zéro fois ou plus au symbole de début de . Let l'ensemble des formes phrastiques de
J'étudie les langages formels et les systèmes de bases de production (systèmes de bases de règles) et je suis un peu confus quant à la raison pour laquelle ces deux mots "production" et "règle" signifient la même chose dans tant de contexte en informatique. En langue anglaise, ils ne semblent pas...
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...
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...
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...
Je suis nouveau dans les automates et je n'ai reçu une brève introduction aux expressions régulières qu'hier. J'ai lu les différentes règles qui définissent une expression régulière. Mais je suis incapable de faire la différence entre les expressions régulières et la grammaire d'une langue (on ne...
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 parcourais la définition de Wikipedia du langage contextuel et j'ai trouvé ceci: Chaque catégorie de langues est un sous-ensemble approprié de la catégorie directement au-dessus. Tout automate et toute grammaire dans chaque catégorie a un automate ou une grammaire équivalent dans la catégorie...
Je comprends que les grammaires sans contexte peuvent être utilisées pour représenter des langues sans contexte, ce qui peut avoir des ambiguïtés. Nous avons également des formes normales comme la forme normale de Chomsky et Greibach . Je ne pouvais pas comprendre le besoin de cela. Pourquoi...
J'essaie de comprendre les grammaires contextuelles. Je comprends pourquoi des langues comme { w w ∣ w ∈ A∗}{ww∣w∈A∗}\{ww \mid w \in A^*\} { anbncn∣ n ∈ N }{anbncn∣n∈N}\{a^n b^n c^n \mid n\in\mathbb{N}\} ne sont pas sans contexte, mais ce que j'aimerais savoir si un langage similaire au calcul...
Ceci est une question du livre Dragon (je m'excuse pour les erreurs de traduction, je n'ai pas la version anglaise sous la main): Quelle langue est générée par cette grammaire? S→aSbS∣bSaS∣ϵS→aSbS∣bSaS∣ϵS \rightarrow a S b S \mid b S a S \mid \epsilon Je ne sais pas ce que je suis censé faire ici....
J'ai la langue suivante { 0je1j2k∣ 0 ≤ i ≤ j ≤ k }{0i1j2k∣0≤i≤j≤k}\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\} J'essaie de déterminer dans quelle classe de langue Chomsky il s'intègre. Je peux voir comment cela pourrait être fait en utilisant une grammaire contextuelle, donc je sais qu'elle...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...
Les machines de Turing et les grammaires illimitées sont deux formalismes différents qui définissent les langages RE. Certaines langues RE sont décidables, mais pas toutes. Nous pouvons définir les langues décidables avec les machines de Turing en disant qu'une langue est décidable si il y a une MT...
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...
Que l'ensemble des terminaux et N l'ensemble des symboles non-terminaux de la grammaire hors-contexte G .ΣΣ\SigmaNNNggG Disons que j'ai une chaîne telle que où et sont les formes phrastiques de .a ∈ ( Σ ∪ N)+une∈(Σ∪N)+a \in (\Sigma \cup N)^+x , y ∈ ( Σ ∪ N ) ∗ S ( G ) Gx a y∈ S( G )Xuney∈S(g)x a y...
J'ai récemment rencontré un article décrivant la technique d'analyse mentionnée dans le titre. Malheureusement, la terminologie utilisée dans cet article est quelque peu au-delà de ma compréhension, j'ai donc essayé de saisir l'algorithme de construction de manière plus intuitive. Je crois que j'ai...
D'après ma lecture, il semble que la plupart des grammaires se préoccupent de générer un nombre infini de chaînes. Et si vous travailliez dans l'autre sens? Si on donne n chaînes de m longueur, il devrait être possible de faire une grammaire qui générera ces chaînes, et juste ces chaînes....