Comment allez-vous mettre en œuvre la règle hors-jeu?

Question

J'ai déjà écrit un générateur qui fait l'affaire, mais j'aimerais connaître la meilleure façon d'implémenter la règle du hors-jeu.

En résumé: Off-side rule signifie dans ce contexte que l'indentation est reconnue comme un élément syntaxique.

est ici la règle hors-jeu dans pseudocode pour faire tokenizers que indentation de capture sous une forme utilisable, je ne veux pas limiter les réponses par langue:

token NEWLINE 
    matches r"\n\ *" 
    increase line count 
    pick up and store the indentation level 
    remember to also record the current level of parenthesis 

procedure layout tokens 
    level = stack of indentation levels 
    push 0 to level 
    last_newline = none 
    per each token 
     if it is NEWLINE put it to last_newline and get next token 
     if last_newline contains something 
      extract new_level and parenthesis_count from last_newline 
      - if newline was inside parentheses, do nothing 
      - if new_level > level.top 
       push new_level to level 
       emit last_newline as INDENT token and clear last_newline 
      - if new_level == level.top 
       emit last_newline and clear last_newline 
      - otherwise 
       while new_level < level.top 
        pop from level 
        if new_level > level.top 
         freak out, indentation is broken. 
        emit last_newline as DEDENT token 
       clear last_newline 
     emit token 
    while level.top != 0 
     emit token as DEDENT token 
     pop from level 

comments are ignored before they are getting into the layouter 
layouter lies between a lexer and a parser 

Ce maquettiste ne génère pas plus d'un saut de ligne à temps, et ne génère pas NEWLINE quand il y a indentation à venir. Par conséquent, les règles d'analyse restent assez simples. C'est plutôt bien, je pense, mais informez s'il y a une meilleure façon de l'accomplir. En utilisant ceci depuis un moment, j'ai remarqué qu'après DEDENTs, il peut être sympa d'émettre une nouvelle ligne de toute façon, de cette façon vous pouvez séparer les expressions avec NEWLINE tout en gardant INDENT DEDENT comme bande-annonce pour l'expression.

Answer 1

J'ai écrit des tokenizers et des parseurs pour quelques petites langues spécifiques au domaine indentation-centric au cours des deux dernières années, et ce que vous avez là me semble assez raisonnable, pour tout ce que ça vaut. Si je ne me trompe pas, votre méthode est assez similaire à ce que Python fait, par exemple, qui semble devoir porter un certain poids.

Convertir NEWLINE NEWENT INDENT en seulement INDENT avant qu'il n'atteigne l'analyseur semble définitivement être la bonne façon de faire les choses - c'est une peine (IME) d'être toujours furieux pour cela dans l'analyseur! J'ai fait cette étape en tant que couche distincte dans ce qui a fini par être un processus en trois étapes: le premier combiné ce que votre lexer et layouter font moins tous les trucs de NEWLINE lookahead (qui le rend très simple), le second) couche plié NEWLINEs consécutifs et NEWLINE INDENT converti juste INDENT (ou, en fait, COLON NEWLINE INDENT à INDENT, puisque dans ce cas tous les blocs indentés étaient toujours précédés de deux-points), puis l'analyseur était la troisième étape en plus de cela. Mais il me semble aussi logique de faire les choses comme vous les avez décrites, surtout si vous voulez séparer le lexeur du layouter, ce que vous feriez probablement si vous utilisiez un outil de génération de code. pour faire votre lexer, par exemple, comme c'est la pratique courante.

J'ai eu une application qui a besoin d'être un peu plus flexible sur les règles d'indentation, laissant essentiellement l'analyseur pour les appliquer en cas de besoin - ce qui suit nécessaire pour être valable dans certains contextes, par exemple:

this line introduces an indented block of literal text: 
    this line of the block is indented four spaces 
    but this line is only indented two spaces 

qui ne fonctionne pas très bien avec les jetons INDENT/DEDENT, car vous finissez par avoir besoin de générer un INDENT pour chaque colonne d'indentation et un nombre égal de DEDENTS sur le chemin du retour, sauf si vous cherchez à savoir où Les niveaux d'indentation vont finir par être, ce qui ne semble pas être le cas pour un tokenizer. Dans ce cas, j'ai essayé quelques choses différentes et j'ai fini par stocker un marqueur dans chaque jeton NEWLINE qui donnait le changement d'indentation (positif ou négatif) pour la ligne logique suivante. (Chaque jeton stockait également tout l'espace de fin, au cas où il aurait besoin d'être préservé, pour NEWLINE, l'espace blanc stocké incluait l'EOL elle-même, toutes les lignes vides intervenant et l'indentation sur la ligne logique suivante.) Pas de jeton INDENT ou DEDENT séparé. Obtenir à l'analyseur de gérer cela était un peu plus de travail que d'imbriquer INDENT et DEDENT, et pourrait bien avoir été une enfer avec une grammaire compliquée qui avait besoin d'un générateur d'analyseur de fantaisie, mais ce n'était pas aussi grave que je le craignais. non plus. Encore une fois, pas besoin de l'analyseur de regarder à l'avance de NEWLINE pour voir s'il y a un INDENT à venir dans ce régime.Pourtant, je pense que vous seriez d'accord qu'autoriser et préserver toutes sortes d'espaces fous dans le tokenizer/layouter et laisser l'analyseur décider ce qu'est un littéral et quel est le code est une exigence inhabituelle! Vous ne voudriez certainement pas que votre parser soit harcelé avec ce compteur d'indentation si vous vouliez juste pouvoir analyser le code de Python, par exemple. La façon dont vous faites les choses est presque certainement la bonne approche pour votre application et bien d'autres. Bien que si quelqu'un d'autre a des pensées sur la meilleure façon de faire ce genre de chose, j'aimerais évidemment les entendre ....

Answer 2

J'ai récemment expérimenté avec ceci, et j'en suis venu à la conclusion que, pour mes besoins au moins, je voulais que les NEWLINES marquent la fin de chaque «déclaration», que ce soit la dernière déclaration dans un bloc en retrait ou non, c'est-à-dire que j'ai besoin des nouvelles lignes avant même que DEDENT.

Ma solution était de le tourner sur sa tête, et au lieu de NEWLINES marquant la fin des lignes, j'utilise un jeton LINE pour marquer le début d'une ligne.

J'ai un lexer qui réduit les lignes vides (y compris les lignes réservées aux commentaires) et émet un seul jeton LINE avec des informations sur l'indentation de la dernière ligne. Ensuite, ma fonction de prétraitement prend ce flux de jetons et ajoute INDENT ou DEDENT "entre" toutes les lignes où l'indentation change. Alors

line1 
    line2 
    line3 
line4 

donnerait le flux jeton

LINE "line1" INDENT LINE "line2" LINE "line3" DEDENT LINE "line4" EOF 

Cela me permet d'écrire des productions grammaticales claires pour les déclarations sans se soucier de détecter la fin des déclarations, même quand ils se terminent par imbriquée, dentelée, sous-blocs, quelque chose Cela peut être difficile si vous faites correspondre NEWLINES (et DEDENTS) à la place.

Voici le cœur du préprocesseur, écrit en Objective Caml:

match next_token() with 
     LINE indentation -> 
     if indentation > !current_indentation then 
      (
      Stack.push !current_indentation indentation_stack; 
      current_indentation := indentation; 
      INDENT 
     ) 
     else if indentation < !current_indentation then 
      (
      let prev = Stack.pop indentation_stack in 
       if indentation > prev then 
       (
        current_indentation := indentation; 
        BAD_DEDENT 
       ) 
       else 
       (
        current_indentation := prev; 
        DEDENT 
       ) 
     ) 
     else (* indentation = !current_indentation *) 
      let token = remove_next_token() in 
      if next_token() = EOF then 
       remove_next_token() 
      else 
       token 
    | _ -> 
     remove_next_token() 

Je n'ai pas ajouté le support pour parenthèses encore, mais cela devrait être une simple extension. Cela évite cependant d'émettre une ligne parasite à la fin du fichier.

Answer 3

Tokenizer en rubis pour le plaisir:

def tokenize(input) 
    result, prev_indent, curr_indent, line = [""], 0, 0, "" 
    line_started = false 

    input.each_char do |char| 

    case char 
    when ' ' 
     if line_started 
     # Content already started, add it. 
     line << char 
     else 
     # No content yet, just count. 
     curr_indent += 1 
     end 
    when "\n" 
     result.last << line + "\n" 
     curr_indent, line = 0, "" 
     line_started = false 
    else 
     # Check if we are at the first non-space character. 
     unless line_started 
     # Insert indent and dedent tokens if indentation changed. 
     if prev_indent > curr_indent 
      # 2 spaces dedentation 
      ((prev_indent - curr_indent)/2).times do 
      result << :DEDENT 
      end 
      result << "" 
     elsif prev_indent < curr_indent 
      result << :INDENT 
      result << "" 
     end 

     prev_indent = curr_indent 
     end 

     # Mark line as started and add char to line. 
     line_started = true; line << char 
    end 

    end 

    result 
end 

ne fait que le travail pour deux-espace-indentation. Le résultat est quelque chose comme ["Hello there from level 0\n", :INDENT, "This\nis level\ntwo\n", :DEDENT, "This is level0 again\n"].