Comment feriez-vous pour mettre en œuvre la règle de hors-jeu?

Question

J'ai déjà écrit un générateur qui fait l'affaire, mais j'aimerais connaître le meilleur moyen possible d'implémenter la règle de hors-jeu.

En bref: Règle hors-jeu signifie dans ce contexte que l'indentation est reconnue comme un élément syntaxique.

Voici la règle de hors-jeu dans le pseudocode pour la création de jetons qui capturent l'indentation 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

Cet afficheur ne génère pas plus d'une NEWLINE à la fois, et ne génère pas NEWLINE lorsqu'il y a une indentation à venir. Par conséquent, les règles d'analyse restent assez simples. C’est plutôt bon, mais informez-nous s’il existe un meilleur moyen de le réaliser.

En l'utilisant depuis un moment, j'ai remarqué qu'après les DEDENT, il peut être intéressant d'émettre newline de toute façon. Ainsi, vous pouvez séparer les expressions avec NEWLINE tout en conservant INDENT DEDENT en tant que suivi d'expression.

Answer 1

J'ai écrit des marqueurs et des analyseurs syntaxiques pour quelques langages spécifiques à un domaine centrés sur l'indentation au cours des dernières années, et ce que vous avez là me semble assez raisonnable, quelle que soit la valeur de celle-ci. Si je ne me trompe pas, votre méthode est assez similaire à ce que fait Python, par exemple, qui semble devoir peser un peu.

Convertir NEWLINE NEWLINE INDENT en juste INDENT avant qu’il ne soit affiché à l’analyseur semble bien être la bonne façon de faire les choses - c’est pénible (IME) de toujours regarder en avant dans l’analyseur! En fait, j’ai fait cette étape en tant que couche distincte dans ce qui s’est avéré être un processus en trois étapes: la première combinant ce que votre lexer et votre layout font moins tout le truc lookhead de NEWLINE (ce qui la rend très simple), la seconde (également très simple). ) couche superposée NEWLINE consécutive convertie et NEWLINE INDENT convertie en INDENT (ou, en fait, COLON NEWLINE INDENT en INDENT, car dans ce cas, tous les blocs en retrait étaient toujours précédés de deux points), l’analyseur était alors la troisième étape. Mais il est également très logique pour moi de faire les choses comme vous les avez décrites, en particulier si vous voulez séparer le lexer du layouter, ce que vous voudriez probablement faire si vous utilisiez un outil de génération de code. pour rendre votre lexer, par exemple, selon la pratique courante.

J'avais une application qui devait être un peu plus flexible en ce qui concerne les règles d'indentation, laissant essentiellement l'analyseur pour les appliquer au besoin - les éléments suivants devaient être valides 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 devez générer un INDENT pour chaque colonne d'indentation et un nombre égal de DEDENT au retour, à moins que vous ne cherchiez le chemin les niveaux de retrait vont finir par être, ce qui ne semble pas vouloir être fait par un tokenizer. Dans ce cas, j'ai essayé plusieurs choses différentes et fini par ne stocker qu'un compteur dans chaque jeton NEWLINE qui donnait le changement d'indentation (positif ou négatif) pour la ligne logique suivante. (Chaque jeton stockait également tous les espaces finaux au cas où il aurait besoin d'être préservé; pour NEWLINE, les espaces blancs stockés incluaient l'EOL même, les lignes vides intermédiaires et l'indentation sur la ligne logique suivante.) Aucun jeton INDENT ou DEDENT séparé. Demander à l'analyseur de gérer cela demandait un peu plus de travail que de simplement imbriquer INDENT et DEDENT, et aurait peut-être été un enfer avec une grammaire compliquée qui nécessitait un générateur d'analyseur syntaxique sophistiqué, mais ce n'était pas aussi grave que je l'avais craint, non plus. Encore une fois, l'analyseur n'a pas besoin de regarder de l'avant dans NEWLINE pour voir si un INDENT se prépare dans ce schéma.

Néanmoins, je pense que vous conviendrez avec moi qu’il est permis de conserver et de conserver toutes sortes d’espaces fous dans le tokenizer / layouter et de laisser l’analyseur décider ce qui est un littéral et que le code est une exigence inhabituelle! Vous ne voudriez certainement pas que votre analyseur soit confronté à ce compteur d'indentation si vous voulez simplement pouvoir analyser le code Python, par exemple. La façon dont vous faites les choses est presque certainement la bonne approche pour votre application et bien d’autres encore. Bien que, si quelqu'un d'autre a des idées sur la meilleure façon de faire ce genre de chose, j'aimerais évidemment l'entendre ....

Answer 2

J'ai expérimenté cela récemment et je suis parvenu à la conclusion que, pour mes besoins du moins, je voulais que NEWLINES marque la fin de chaque "déclaration", qu'il s'agisse de la dernière déclaration d'un bloc en retrait ou non, c’est-à-dire que j’ai besoin des nouvelles lignes avant même DEDENT.

Ma solution a été de l'arrêter, 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 de commentaire uniquement) et émet un seul jeton LINE contenant 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" et "entre". toutes les lignes où l'indentation change. Donc

line1
    line2
    line3
line4

donnerait le flux de jetons

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

Cela me permet d’écrire des productions grammaticales claires pour des énoncés sans me soucier de détecter la fin des énoncés, même s’ils se terminent par des sous-blocs imbriqués, en retrait, ce qui peut être difficile si vous faites correspondre NEWLINES (et DEDENTS).

Voici le coeur du préprocesseur, écrit en O'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 encore ajouté de support pour les parenthèses, mais cela devrait être une simple extension. Cela évite toutefois 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 fonctionne que pour l'indentation à deux espaces. Le résultat est quelque chose comme ["Bonjour à partir du niveau 0 \ n",: INDENT, "Ceci \ n est de niveau \ ndeux \ n",: DEDENT, "c’est le niveau0 à nouveau \ n"] .