Les expressions régulières

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 ( 1 ) , etc. sans construire de tables d'analyse?$LR(1)$$LL(1)$$SLR(1)$

Toutes les langues régulières ont des grammaires LL (1). Pour obtenir une telle grammaire, prenez n'importe quel DFA pour le langage régulier (peut-être en faisant la construction du sous-ensemble sur le NFA obtenu à partir de l'expression régulière), puis convertissez-le en une grammaire régulière récursive à droite. Cette grammaire est alors LL (1), car toute paire de productions pour le même non-terminal commence soit par des symboles différents, soit on produit ε et a $ comme jeton d'anticipation. Par conséquent, toutes les langues régulières sont également LR (1), car toute grammaire LL (1) est LR (1). De plus, en utilisant un résultat important de cet article , vous pouvez montrer que toute langue LR (1) a une grammaire SLR (1), ce qui signifie que toute langue régulière a une grammaire SLR (1).

Cependant, les langues régulières ne sont pas toutes LR (0). Les langages LR (0) ont des propriétés très spécifiques - en particulier, ils doivent être exempts de préfixe. Ainsi le langage régulier {a, aa} n'est pas LR (0), bien qu'il soit clairement régulier (regex a | (aa)). Cependant, les langues LR (0) ne sont pas correctement contenues dans les langues régulières; cette grammaire pour {0 ⁿ 21 ⁿ | n ≥ 1} est LR (0), mais la langue n'est pas régulière:

S -> E
E -> 0E1 | 2

J'espère que cela t'aides!

La syntaxe d' expression régulière (ordinaire) (vous avez dit "représentation") est LR (0). Vous n'avez pas besoin d'anticipation pour analyser une chaîne représentant une expression régulière. Vous pouvez facilement décider cela en exécutant un générateur d'analyseur sur une grammaire pour les expressions régulières: -} Vous pouvez également facilement coder un analyseur de descente récursive simple (LL (0)) pour les expressions régulières; tout ce qui est LL (0) est LR (0).

Je ne sais pas si la syntaxe de soi-disant "regexps" plus compliquées comme Perl est comme ça; mais les regexps de Perl sont strictement plus puissants que les regexps, donc ce ne sont pas de vieilles regexps simples.

Pour déterminer si une grammaire possède une propriété, vous devez exécuter une sorte de prédicat. Pour déterminer s'il s'agit de (S) LR (k), vous devez exécuter un prédicat qui peut vérifier cette propriété. En effet, un tel prédicat doit en effet créer les tables d'analyse, en raison de la façon dont elles sont définies.