Come faresti per implementare la regola off-side?

Question

Ho già scritto un generatore che fa il trucco, ma mi piacerebbe conoscere il modo migliore per implementare la regola off-side.

In breve: Regola off-side significa che in questo contesto il rientro viene riconosciuto come un elemento sintattico.

Ecco la regola del fuorigioco nello pseudocodice per creare tokenizzatori che catturano il rientro in forma utilizzabile, non voglio limitare le risposte per lingua:

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

Questo layouter non genera più di una NEWLINE alla volta e non genera NEWLINE in caso di rientro. Pertanto le regole di analisi rimangono piuttosto semplici. È abbastanza buono, penso, ma informo se esiste un modo migliore per realizzarlo.

Durante l'utilizzo di questo per un po ', ho notato che dopo DEDENT può essere comunque bello emettere newline, in questo modo è possibile separare le espressioni con NEWLINE mantenendo INDENT DEDENT come trailer per l'espressione.

Answer 1

Ho scritto tokenizer e parser per un paio di piccole lingue specifiche del dominio incentrate sulla rientranza negli ultimi due anni, e quello che hai lì sembra abbastanza ragionevole per me, per tutto ciò che vale. Se non sbaglio, il tuo metodo è abbastanza simile a quello che fa Python, ad esempio, il che sembra che dovrebbe avere un certo peso.

La conversione di NEWLINE NEWLINE INDENT in INDENT prima che colpisca il parser sembra sicuramente il modo giusto di fare le cose - è un dolore (IME) essere sempre alla ricerca di ciò nel parser! In realtà ho fatto quel passaggio come un livello separato in quello che alla fine è stato un processo in tre fasi: il primo ha combinato quello che fanno il tuo lexer e il tuo layouter meno tutte le cose lookline di NEWLINE (che lo hanno reso molto semplice), il secondo (anche molto semplice ) ha piegato NEWLINE consecutivi e convertito NEWLINE INDENT in appena INDENT (o, in realtà, COLON NEWLINE INDENT in INDENT, poiché in questo caso tutti i blocchi rientrati erano sempre preceduti da due punti), quindi il parser era il terzo stadio in cima a quello. Ma ha anche molto senso per me fare le cose nel modo in cui le hai descritte, specialmente se vuoi separare il lexer dal layouter, cosa che presumibilmente vorresti fare se stessi usando uno strumento di generazione del codice per rendere il tuo lexer, ad esempio, come è prassi comune.

Avevo un'applicazione che doveva essere un po 'più flessibile riguardo alle regole di rientro, essenzialmente lasciando che il parser le imponesse quando necessario - ad esempio, i seguenti devono essere validi in determinati contesti:

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

che non funziona molto bene con i token INDENT / DEDENT, poiché alla fine devi generare un INDENT per ogni colonna di rientro e un uguale numero di DEDENT sulla via del ritorno, a meno che non guardi avanti per capire dove i livelli di rientro finiranno per essere, cosa che non sembra che tu voglia fare un tokenizer. In quel caso ho provato alcune cose diverse e ho finito per memorizzare un contatore in ogni token NEWLINE che ha dato il cambio di rientro (positivo o negativo) per la seguente riga logica. (Ogni token memorizzava anche tutti gli spazi bianchi finali, nel caso fosse necessario preservarli; per NEWLINE, lo spazio bianco memorizzato includeva la stessa EOL, eventuali righe vuote intermedie e il rientro sulla seguente riga logica.) Nessun token INDENT o DEDENT separato. Far affrontare il parser con questo era un po 'più di lavoro che annidare INDENT e DEDENT, e avrebbe potuto essere un inferno con una grammatica complicata che aveva bisogno di un generatore di parser sofisticato, ma non era affatto male come temevo, o. Ancora una volta, non è necessario che il parser guardi avanti da NEWLINE per vedere se c'è un rientro in questo schema.

Tuttavia, penso che saresti d'accordo nel consentire e preservare ogni sorta di spazio bianco dall'aspetto folle nel tokenizer / layouter e lasciare che il parser decida che cosa è letterale e che codice è un po 'un requisito insolito! Non vorrai certo che il tuo parser venga sellato con quel contatore di rientri se volessi solo essere in grado di analizzare il codice Python, per esempio. Il modo in cui stai facendo le cose è quasi sicuramente l'approccio giusto per la tua applicazione e molti altri. Tuttavia, se qualcun altro ha pensieri sul modo migliore per fare questo genere di cose, ovviamente mi piacerebbe ascoltarli ....

Answer 2

Di recente ho sperimentato questo, e sono giunto alla conclusione che, almeno per le mie esigenze, volevo che le NEWLINES segnassero la fine di ciascuna "dichiarazione", sia che fosse l'ultima frase in un blocco rientrato o no, cioè ho bisogno dei newline anche prima di DEDENT.

La mia soluzione era di capovolgerla, e invece di NEWLINES che segna la fine delle linee, uso un token LINE per segnare l'inizio di una linea.

Ho un lexer che comprime le righe vuote (comprese le righe di solo commento) ed emette un singolo token LINE con informazioni sul rientro dell'ultima riga. Quindi la mia funzione di preelaborazione prende questo flusso di token e aggiunge INDENT o DEDENT "tra" qualsiasi riga in cui cambia il rientro. Quindi

line1
    line2
    line3
line4

darebbe il flusso di token

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

Questo mi permette di scrivere chiare produzioni grammaticali per le affermazioni senza preoccuparmi di rilevare la fine delle affermazioni anche quando terminano con blocchi secondari nidificati, rientrati, qualcosa che può essere difficile se si abbinano invece NEWLINES (e DEDENTS).

Ecco il nucleo del preprocessore, scritto in 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 ()

Non ho ancora aggiunto il supporto per le parentesi, ma dovrebbe essere una semplice estensione. Tuttavia, evita di emettere una LINEA vagante alla fine del file.

Answer 3

Tokenizer in ruby ??per divertimento:

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

Funziona solo con rientro a due spazi. Il risultato è qualcosa come [" Salve a partire dal livello 0 \ n " ;,: INDENT, " Questo \ nis livello \ ntwo \ n " ;,: DEDENT, " Questo è di nuovo livello0 \ n "] .