Directives de conception pour l'analyseur et lexer?

Question

J'écris un lexer (avec re2c) et un parser (avec Lemon) pour un format de données légèrement compliqué: CSV, mais avec des types de chaînes spécifiques à des endroits spécifiques (caractères alphanumériques seulement, caractères alphanumériques et signes moins, tout char à l'exception des guillemets et des virgules, mais avec des accolades équilibrées, etc.), des chaînes à l'intérieur des accolades et des chaînes qui ressemblent à des appels de fonction avec des accolades ouvrantes et fermantes pouvant contenir des paramètres.

Mon premier tir était un lexer avec de nombreux états, chaque état répondant au format de chaîne spécifique. Mais après de nombreux messages "d'entrée inattendue" inutiles de la lexer (qui est devenu très gros), j'ai réalisé que peut-être il essayait de faire le travail de l'analyseur. J'ai abandonné mon premier essai et suis parti avec un lexer avec un seul état, plusieurs jetons de personnage et un analyseur qui combine les jetons dans les différents types de cordes. Cela fonctionne mieux, je reçois des erreurs de syntaxe plus utiles de l'analyseur quand quelque chose est éteint, mais il ne se sent toujours pas tout à fait raison. Je pense à ajouter un ou deux états à la lexer, mais en initiant les états à partir de l'analyseur, qui a une meilleure "vue d'ensemble" sur le type de chaîne requis dans une instance donnée. Dans l'ensemble, je me sens un peu stupide :(

Je n'ai pas d'antécédents formels de CS et je suis un peu à l'écart de la théorie mathématique, mais il y a peut-être un tutoriel ou un livre qui explique ce que devrait être un lexer. Comment construire de bons modèles de jetons, quand utiliser des états lexers, quand et comment utiliser des règles récursives (avec un analyseur LALR), comment éviter les règles ambigues. Le "Lex and YACC primer/HOWTO" était sympa, mais pas suffisant, puisque je veux juste analyser un format de données, les livres sur la construction de compilateurs (comme le livre de dragon rouge) me paraissent un peu surdimensionnés

Ou peut-être quelqu'un peut me donner quelques règles simples ici

Answer 1

Ce que vous devez faire est d'écrire une grammaire pour votre langue. Une fois que vous avez, la frontière est facile:

• Le lexer est responsable de prendre votre entrée et vous dire quel terminal que vous avez.
• L'analyseur est responsable de faire correspondre une série de terminaux et nonterminals à une règle de production, à plusieurs reprises, jusqu'à ce que vous avez un arbre d'analyse syntaxique ou un échec d'analyse syntaxique.

Le lexer n'est pas responsable de la validation d'entrée, sauf dans la mesure où de rejeter des caractères impossibles, et d'autres très basiques morceaux. L'analyseur fait tout cela.

Jetez un oeil à http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html. C'est une page de cours d'intro CS sur l'analyse syntaxique.

Answer 2

Un bon test décisif pour décider si quelque chose doit être fait par un analyseur ou lexer est de vous poser une question:

Est-ce que la syntaxe ont des récursives, imbriquées, des éléments autosimilaires?
(par exemple, parenthèses imbriquées, accolades, étiquettes, sous-expressions, sous -ences, etc.). Si ce n'est pas le cas, les expressions rationnelles simples suffisent et cela peut être fait par le lexeur.
Si oui, il devrait être analysé par un analyseur, parce que c'est au moins une grammaire sans contexte.

Lexer est généralement utilisé pour trouver des "mots" de votre langage et les classer (est-ce un nom?un verbe? un adjectif? etc.).
Parser est pour trouver des «phrases» appropriées, en les structurant une conclusion si elles sont des phrases appropriées dans une langue donnée.