Analyse lexicale sans expressions régulières

J'ai regardé quelques lexers dans différentes langues de niveau supérieur ( Python , PHP , Javascript entre autres) et ils semblent tous utiliser des expressions régulières sous une forme ou une autre. Bien que je sois sûr que les regex sont probablement la meilleure façon de le faire, je me demandais s'il y avait un moyen d'obtenir une lexing de base sans expressions régulières, peut-être une sorte d'analyse de chaîne directe ou quelque chose.

Alors oui, est-il possible d'implémenter une sorte de lexing de base dans un langage de niveau supérieur * sans utiliser d'expressions régulières sous aucune forme?

_{* Les langages de niveau supérieur étant des choses comme Perl / PHP / Python / Javascript, etc. Je suis sûr qu'il existe un moyen de le faire en C}

Tout d'abord, il y avait des bibliothèques d'expressions régulières pour C depuis avant que vos langages de "niveau supérieur" ne soient inventés. Je dis simplement que les programmes C ne sont pas aussi podunk que certaines personnes semblent le penser.

Pour la plupart des grammaires, la lexie consiste à rechercher des espaces et quelques autres caractères comme () [] {}; pour diviser les mots, puis en les comparant à une liste de mots clés pour voir si une correspondance existe.

Vous pourriez être intéressé par les "analyseurs sans scanner", qui n'ont pas d'étape de tokenisation distincte. Une explication des avantages des analyseurs sans scanner est donnée au début de cet article: Filtres de désambiguïsation pour les analyseurs LR généralisés sans scanner . (Il y a aussi des inconvénients.)

(Les PEG, qui ont été mentionnés dans d'autres réponses, peuvent également être utilisés pour construire des analyseurs sans scanner.)

Il n'y a rien de spécifique dans les expressions régulières. Ils sont simplement un raccourci qui vous permet de générer le code beaucoup plus facilement, et les implémentations sont généralement livrées. Cependant, fondamentalement, les lexers sont des FSM et les expressions régulières ne sont qu'un moyen d'atteindre cet objectif.

Bien sûr, vous pouvez utiliser d'autres analyseurs, car chaque langue régulière est également sans contexte. La question se résume vraiment à pourquoi vous voudriez.

Il n'y a rien de plus simple que les expressions régulières (comment pouvez-vous améliorer O (N)?) Et essayer de simplifier n'aidera pas. Vous pouvez toujours utiliser un retour arrière simple comme l'a souligné Jetti, bien que je recommande de l'éviter si possible.

Si vous allez utiliser un analyseur plus avancé pour lexing, vous n'avez probablement pas du tout besoin d'une phase de lexing. En fait, les raisons pour lesquelles nous avons une phase de lexing est qu'il est plus rapide d'analyser les jetons lexés que d'analyser les caractères, ce qui simplifie considérablement notre étape d'analyse. Ainsi, en utilisant un analyseur plus avancé, vous perdez simplement tout avantage de lexing en premier lieu.

Il est judicieux soit de faire une analyse lexicale avec des expressions régulières, soit de sauter cette passe du tout et de faire une analyse lexerless beaucoup plus flexible et puissante avec PEG ou GLR.