Analyse d'une grammaire "simple"

Question

Désolé d'avance; Je suis sûr que cette question semblera presque idiote à ceux qui ont l'habitude de jouer avec les parsers et les grammaires, mais ce sont des sujets étrangers pour moi, et c'est ma tentative d'entrer doucement dans un cas pratique qui les nécessite.

Je voudrais écrire un analyseur syntaxique pour ce qui suit « langage », qui contient une seule « structure spéciale » qui ressemble à ceci:

\command[ options ]{ contents } 

Le contenu peut être quelque chose, y compris les commandes imbriquées, et peuvent contenir parenthèses échappées ou backslashes \{ \} \\. Je me rends compte que «n'importe quoi» n'est pas spécifique, mais idéalement, ils devraient être déterminés en faisant correspondre les parenthèses (excluant les échappées), si possible.

Les options doivent être une liste d'expressions d'affectation séparées par des virgules telles que name = value, mais la valeur peut être une chaîne entre guillemets contenant = ou , caractères. Enfin, les précédents name et command doivent valider l'expression régulière \w[\w\d\._-+*]* - c'est-à-dire que le premier caractère doit être une lettre et les caractères restants doivent être une lettre, un chiffre ou l'un des . _ - + *.

L'écriture avec des expressions régulières semble trop compliquée (par exemple, parce que les valeurs peuvent contenir des guillemets , =, qui séparent sinon les affectations ou les paires nom/valeur). Donc je pense que l'outil le plus approprié ici est une grammaire, mais malgré les lectures superficielles, je ne suis pas sûr de savoir comment l'écrire (BNF, PEG, etc?), Quel type d'analyseurs utiliser (LR, récursif, etc?) , et comment je pourrais utiliser la sortie d'analyse dans un programme pratique.

Je préférerais des réponses avec Python, ce qui explique l'étiquette, mais bien sûr, je serais parfaitement heureux avec une combinaison d'outils si nécessaire/mieux adapté.

---

REMARQUE: cela ne concerne pas LATEX. Je réalise la similitude bien sûr, mais LaTeX est extrêmement plus complexe que la langue précédente, par exemple avec des codes de caractères variant selon le contexte. Je demande simplement un exemple pratique qui (je pense) est assez simple pour SO, et pourtant serait déjà utile pour moi dans mon travail quotidien.

Answer 1

Commencez par exprimer votre grammaire plus formellement, quelle que soit la notation que vous préférez. par exemple, à partir de votre description, un EBNF serait comme ceci:

program := element+ 
element := command | literal 
literal := (not '\')+ 

command := '\'identifier options? '{' program '}' 
options := option | options ',' option 
option := identifier '=' value 
value := number | string 

string := '"' (escape | not '\' or '"')* '"' 
escape : = '\' char 

Ensuite, soit nourrir à un générateur d'analyseur (pyparsing, pyYACC, ANTLR) ou écrire un analyseur à la main. Dans ce dernier cas, l'option descendante est la plus simple: commencez par le début de la grammaire et convertissez chaque règle en une fonction qui retournera un noeud AST analysé et consommera l'entrée ou ne retournera rien ou lancera. Exemple:

def program(): 
    elements = [] 
    while next_sym(): 
     elements.append(element()) 
    return {'type': 'program', 'children': elements} 

def element(): 
    return command() or literal() 

def command(): 
    if next_sym() == '\\': 
     get_sym() 
     ...parse command here 
     return {'type': 'command', 'children': ...} 
    return None 

où next_sym retourne le symbole suivant à partir de l'entrée (ou None sur EOF) et get_sym consomme le symbole et avance le tampon d'entrée.