Questions marquées «formal-grammars»

J'ai récemment discuté avec un ami d'un site Web qui proposait des défis d'expression régulière, correspondant principalement à un groupe de mots avec une propriété spéciale. Il cherchait une expression régulière qui correspond à des chaînes comme ||||||||où le nombre de |est premier. Je lui ai...

Je me demandais récemment ce qui se passerait si nous permettions aux grammaires sans contexte d'avoir un nombre infini de règles. De toute évidence, si nous permettions arbitrairement de tels ensembles infinis de règles, chaque langue sur un alphabet pourrait être décrite par un CFG avec . Mais...

Dans l'article Parsing Expressions by Recursive Descent de Theodore Norvell (1999), l'auteur commence par la grammaire suivante pour les expressions arithmétiques: E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v ce qui est assez mauvais, car il est ambigu et...

La grammaire non contextuelle suivante présente une ambiguïté de type "balançant le reste" (imaginez que représente et b représente et c représente un autre type d'instruction ou de bloc): Saaaif expr thenbbbelseccc Par exemple,aacbcpeut être analysé comme(a(acbc))ou comme(a(ac)bc)(c'est le mot...

Je recherche une grammaire contextuelle qui décrit le langage suivant: .L={ww∣w∈{a,b}∗,|w|≥1}L={ww∣w∈{a,b}∗,|w|≥1}L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\} J'ai des problèmes avec le fait qu'aucune règle comme n'est autorisée et donc je ne peux placer aucun terminal indiquant le "milieu" du mot....

Existe-t-il un ensemble de règles ou de méthodes pour convertir une grammaire sans contexte en automates push down? J'ai déjà trouvé des diapositives en ligne mais je n'ai pas pu les comprendre. Dans la diapositive 10, il parle de certaines règles. Quelqu'un pourrait-il expliquer...

L:={w∈{0,1}∗|L:={w∈{0,1}∗|L := \{w \in \{0,1\}^* | la longueur de est impaire 1 est au milieu dewww∧∧ \wedge w}w}w\} Donc l'alphabet est . Mon problème est que je ne peux pas suivre l'égalité des caractères avant et après . Un DFA limité pour une longueur inférieure à 6:{0,1}∗{0,1}∗\{0,1\}^*111...

L' autre jour, je lisais le document intitulé Fundamental Concepts in Programming Languages ​​de C. Strachey , dans lequel j'ai lu quelque chose qui m'était assez étrange. Citant directement (avec la partie étrange surlignée par moi): Face à la situation telle qu'elle existe aujourd'hui, où il...

Question: Existe-t-il des textes d'introduction en langage formel ou en théorie du langage de programmation qui discutent de la façon de l'appliquer à l'étude de la notation optimale? En particulier, je suis intéressé à savoir quels sont les langages de pile, les arbres d'analyse et les indices, et...

Cette grammaire est récursive: Expression ::= AdditionExpression AdditionExpression ::= MultiplicationExpression | AdditionExpression '+' MultiplicationExpression | AdditionExpression '-' MultiplicationExpression MultiplicationExpression ::= Term | MultiplicationExpression '*' Term |...