Quelle est la procédure à suivre pour écrire un lexer basé sur une grammaire?

En lisant une réponse à la question Clarification sur les grammaires, les lexers et les analyseurs , la réponse a déclaré que:

[...] une grammaire BNF contient toutes les règles dont vous avez besoin pour l'analyse et l'analyse syntaxique lexicale.

Cela m'a semblé quelque peu étrange parce que jusqu'à présent, j'avais toujours pensé qu'un lexer n'était pas du tout basé sur une grammaire, alors qu'un analyseur était fortement basé sur une grammaire. J'étais arrivé à cette conclusion après avoir lu de nombreux articles de blog sur l'écriture de lexers, et aucun n'utilisant jamais ¹ EBNF / BNF comme base pour la conception.

Si les lexers, ainsi que les analyseurs, sont basés sur une grammaire EBNF / BNF, alors comment procéder pour créer un lexer en utilisant cette méthode? Autrement dit, comment pourrais-je construire un lexer en utilisant une grammaire EBNF / BNF donnée?

Je l' ai vu beaucoup, beaucoup après qui traitent avec l' écriture d' un analyseur en utilisant EBNF / BNF comme un guide ou un plan, mais je l' ai rencontré aucun jusqu'à présent qui montrent l'équivalent avec la conception lexer.

Par exemple, prenez la grammaire suivante:

input = digit| string ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
string = '"', { all characters - '"' }, '"' ;
all characters = ? all visible characters ? ;

Comment créer un lexer basé sur la grammaire? Je pourrais imaginer comment un analyseur pourrait être écrit à partir d'une telle grammaire, mais je n'arrive pas à saisir le concept de faire la même chose avec un lexer.

Existe-t-il certaines règles ou logique utilisées pour accomplir une tâche comme celle-ci, comme pour écrire un analyseur? Franchement, je commence à me demander si les conceptions de lexers utilisent une grammaire EBNF / BNF, et encore moins sont basées sur une.

¹ _{forme Backus – Naur étendue et forme Backus – Naur}

Les Lexers ne sont que de simples analyseurs qui sont utilisés comme optimisation des performances pour l'analyseur principal. Si nous avons un lexer, le lexer et l'analyseur travaillent ensemble pour décrire le langage complet. Les analyseurs qui n'ont pas d'étape de lexing séparée sont parfois appelés «sans scanner».

Sans lexers, l'analyseur devrait opérer caractère par caractère. Étant donné que l'analyseur doit stocker des métadonnées sur chaque élément d'entrée et peut avoir à pré-calculer des tables pour chaque état d'élément d'entrée, cela entraînerait une consommation de mémoire inacceptable pour les grandes tailles d'entrée. En particulier, nous n'avons pas besoin d'un nœud séparé par caractère dans l'arbre de syntaxe abstraite.

Étant donné que le texte caractère par caractère est assez ambigu, cela entraînerait également une ambiguïté beaucoup plus gênante à gérer. Imaginez une règle R → identifier | "for " identifier. où l' identifiant est composé de lettres ASCII. Si je veux éviter toute ambiguïté, j'ai maintenant besoin d'une tête de lecture à 4 caractères pour déterminer quelle alternative doit être choisie. Avec un lexer, l'analyseur n'a qu'à vérifier s'il a un jeton IDENTIFIER ou FOR - une tête de lecture à 1 jeton.

Grammaires à deux niveaux.

Les Lexers fonctionnent en traduisant l'alphabet saisi en un alphabet plus pratique.

Un analyseur sans scanner décrit une grammaire (N, Σ, P, S) où les non terminaux N sont les côtés gauche des règles de la grammaire, l'alphabet Σ est par exemple des caractères ASCII, les productions P sont les règles de la grammaire et le symbole de début S est la règle de niveau supérieur de l'analyseur.

Le lexer définit désormais un alphabet de jetons a, b, c,…. Cela permet à l'analyseur principal d'utiliser ces jetons comme alphabet: Σ = {a, b, c,…}. Pour le lexer, ces jetons ne sont pas des terminaux, et la règle de début S _L est S _L → ε | un S | b S | c S | …, C'est-à-dire: toute séquence de jetons. Les règles de la grammaire de lexer sont toutes des règles nécessaires pour produire ces jetons.

L'avantage de la performance vient de l'expression des règles du lexeur en langage régulier . Ceux-ci peuvent être analysés beaucoup plus efficacement que les langages sans contexte. En particulier, les langages réguliers peuvent être reconnus dans l'espace O (n) et le temps O (n). En pratique, un générateur de code peut transformer un tel lexer en tables de sauts très efficaces.

Extraire des jetons de votre grammaire.

Pour toucher à votre exemple: les règles digitet stringsont exprimées au niveau caractère par caractère. Nous pourrions les utiliser comme jetons. Le reste de la grammaire reste intact. Voici la grammaire lexer, écrite comme une grammaire linéaire droite pour indiquer clairement qu'elle est régulière:

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
string = '"' , string-rest ;
string-rest = '"' | STRING-CHAR, string-rest ;
STRING-CHAR = ? all visible characters ? - '"' ;

Mais comme c'est régulier, nous utilisons généralement des expressions régulières pour exprimer la syntaxe du jeton. Voici les définitions de jetons ci-dessus en tant que regex, écrites à l'aide de la syntaxe d'exclusion de classe de caractères .NET et des charclasses POSIX:

digit ~ [0-9]
string ~ "[[:print:]-["]]*"

La grammaire de l'analyseur principal contient alors les règles restantes non gérées par le lexer. Dans votre cas, c'est juste:

input = digit | string ;

Lorsque les lexers ne peuvent pas être utilisés facilement.

Lors de la conception d'un langage, nous veillons généralement à ce que la grammaire puisse être séparée proprement en un niveau lexer et un niveau analyseur, et que le niveau lexer décrive un langage normal. Ce n'est pas toujours possible.

• Lors de l'intégration de langues. Certaines langues vous permettent d'interpoler code dans les chaînes: "name={expression}". La syntaxe d'expression fait partie de la grammaire sans contexte et ne peut donc pas être symbolisée par une expression régulière. Pour résoudre ce problème, nous recombinons l'analyseur avec le lexer, ou nous introduisons des jetons supplémentaires comme STRING-CONTENT, INTERPOLATE-START, INTERPOLATE-END. La règle de grammaire pour une chaîne pourrait alors ressembler à : String → STRING-START STRING-CONTENTS { INTERPOLATE-START Expression INTERPOLATE-END STRING-CONTENTS } STRING-END. Bien sûr, l'expression peut contenir d'autres chaînes, ce qui nous amène au problème suivant.

• Quand les jetons peuvent se contenir. Dans les langages de type C, les mots clés ne se distinguent pas des identifiants. Ceci est résolu dans le lexer en priorisant les mots clés sur les identifiants. Une telle stratégie n'est pas toujours possible. Imaginez un fichier de configuration où Line → IDENTIFIER " = " REST, où le reste est n'importe quel caractère jusqu'à la fin de la ligne, même si le reste ressemble à un identifiant. Un exemple de ligne serait a = b c. Le lexer est vraiment stupide et ne sait pas dans quel ordre les jetons peuvent apparaître. Donc, si nous priorisons IDENTIFICATEUR sur REST, le lexer nous le donnerait IDENT(a), " = ", IDENT(b), REST( c). Si nous priorisons REST sur IDENTIFIER, le lexer nous donnerait juste REST(a = b c).

  Pour résoudre ce problème, nous devons recombiner le lexer avec l'analyseur. La séparation peut être maintenue quelque peu en rendant le lexer paresseux: chaque fois que l'analyseur a besoin du prochain jeton, il le demande au lexer et lui dit l'ensemble des jetons acceptables. En fait, nous créons une nouvelle règle de niveau supérieur pour la grammaire lexère pour chaque position. Ici, cela entraînerait des appels nextToken(IDENT), nextToken(" = "), nextToken(REST), et tout fonctionne bien. Cela nécessite un analyseur qui connaît l'ensemble complet de jetons acceptables à chaque emplacement, ce qui implique un analyseur ascendant comme LR.

• Quand le lexer doit maintenir son état. Par exemple, le langage Python délimite les blocs de code non pas par des accolades, mais par indentation. Il existe des moyens de gérer la syntaxe sensible à la disposition dans une grammaire, mais ces techniques sont exagérées pour Python. Au lieu de cela, le lexer vérifie l'indentation de chaque ligne et émet des jetons INDENT si un nouveau bloc indenté est trouvé et des jetons DEDENT si le bloc est terminé. Cela simplifie la grammaire principale, car il peut désormais prétendre que ces jetons sont comme des accolades. Le lexer doit cependant maintenant conserver son état: l'indentation actuelle. Cela signifie que le lexer ne décrit plus techniquement un langage normal, mais en fait un langage contextuel. Heureusement, cette différence n'est pas pertinente dans la pratique, et le lexer de Python peut toujours fonctionner en temps O (n).