ANTLR ¿Cuál es la forma más sencilla de realizar python como la gramática dependiente de sangría?

lexer indentation

Question

Estoy tratando de realizar python como la gramática dependiente de sangría.

Ejemplo de fuente:

ABC QWE
  CDE EFG
  EFG CDE
    ABC 
  QWE ZXC

Como veo, lo que necesito es realizar dos tokens INDENT y DEDENT, para poder escribir algo como:

grammar mygrammar;
text: (ID | block)+;
block: INDENT (ID|block)+ DEDENT;
INDENT: ????;
DEDENT: ????;

¿Hay alguna forma simple de darse cuenta de esto usando ANTLR?

(Preferiría, si es posible, usar el lexer ANTLR estándar).

Answer 1

¿Has mirado la gramática ANTLR de Python ?

Edición: Se agregó el código Python de psuedo para crear tokens INDENT / DEDENT

UNKNOWN_TOKEN = 0
INDENT_TOKEN = 1
DEDENT_TOKEN = 2

# filestream has already been processed so that each character is a newline and
# every tab outside of quotations is converted to 8 spaces.
def GetIndentationTokens(filestream):
    # Stores (indentation_token, line, character_index)
    indentation_record = list()
    line = 0
    character_index = 0
    column = 0
    counting_whitespace = true
    indentations = list()
    for c in filestream:
        if IsNewLine(c):
            character_index = 0
            column = 0
            line += 1
            counting_whitespace = true
        elif c != '' '' and counting_whitespace:
            counting_whitespace = false
            if(len(indentations) == 0):
                indentation_record.append((token, line, character_index))
            else:
                while(len(indentations) > 0 and indentations[-1] != column:
                    if(column < indentations[-1]):
                        indentations.pop()
                        indentation_record.append((
                            DEDENT, line, character_index))
                    elif(column > indentations[-1]):
                        indentations.append(column)
                        indentation_record.append((
                            INDENT, line, character_index))

        if not IsNewLine(c):
            column += 1

        character_index += 1
    while(len(indentations) > 0):
        indentations.pop()
        indentation_record.append((DEDENT_TOKEN, line, character_index))
    return indentation_record

Answer 2

Hay una biblioteca de código abierto antlr-denter para ANTLR v4 que ayuda a analizar sangrías y deducciones para usted. Echa un vistazo a su README para saber cómo usarlo.

Ya que es una biblioteca, en lugar de fragmentos de código para copiar y pegar en su gramática, su manejo de sangría se puede actualizar por separado del resto de su gramática.

Answer 3

Hay una forma relativamente simple de hacer este ANTLR, que escribí como un experimento: Dent.g4 . Esta solución es diferente de las otras mencionadas en esta página que fueron escritas por Kiers y Shavit. Se integra con el tiempo de ejecución únicamente a través de una anulación del método nextToken() de nextToken() . Hace su trabajo al examinar los tokens: (1) un token NEWLINE desencadena el inicio de una fase de "seguimiento de sangrado"; (2) los espacios en blanco y los comentarios, ambos establecidos en el canal HIDDEN , se cuentan y se ignoran, respectivamente, durante esa fase; y, (3) cualquier token no HIDDEN termina la fase. Por lo tanto, controlar la lógica de sangría es una simple cuestión de configurar el canal de un token.

Ambas soluciones mencionadas en esta página requieren un token NEWLINE para capturar también todos los espacios en blanco posteriores, pero al hacerlo no pueden manejar los comentarios de varias líneas que interrumpen ese espacio en blanco. Dent, en cambio, mantiene los tokens de espacios en blanco y NEWLINE separados y puede manejar comentarios de varias líneas.

Tu gramática se configuraría algo como abajo. Tenga en cuenta que las reglas NEWLINE y WS lexer tienen acciones que controlan el estado pendingDent de sangrado y pendingDent un seguimiento del nivel de sangría con la variable indentCount .

grammar MyGrammar;

tokens { INDENT, DEDENT }

@lexer::members {
    // override of nextToken(), see Dent.g4 grammar on github
    // https://github.com/wevrem/wry/blob/master/grammars/Dent.g4
}

script : ( NEWLINE | statement )* EOF ;

statement
    :   simpleStatement
    |   blockStatements
    ;

simpleStatement : LEGIT+ NEWLINE ;

blockStatements : LEGIT+ NEWLINE INDENT statement+ DEDENT ;

NEWLINE : ( ''/r''? ''/n'' | ''/r'' ) {
    if (pendingDent) { setChannel(HIDDEN); }
    pendingDent = true;
    indentCount = 0;
    initialIndentToken = null;
} ;

WS : [ /t]+ {
    setChannel(HIDDEN);
    if (pendingDent) { indentCount += getText().length(); }
} ;

BlockComment : ''/*'' ( BlockComment | . )*? ''*/'' -> channel(HIDDEN) ;   // allow nesting comments
LineComment : ''//'' ~[/r/n]* -> channel(HIDDEN) ;

LEGIT : ~[ /t/r/n]+ ~[/r/n]*;   // Replace with your language-specific rules...

Answer 4

No sé cuál es la forma más fácil de manejarlo, pero la siguiente es una forma relativamente fácil. Siempre que coincida con un salto de línea en su lexer, opcionalmente haga coincidir uno o más espacios. Si hay espacios después del salto de línea, compare la longitud de estos espacios con el tamaño de sangría actual. Si es más que el tamaño de sangría actual, emita un token de Indent , si es menor que el tamaño de sangría actual, emita un token de Dedent y si es el mismo, no haga nada.

También querrá emitir una cantidad de tokens de Dedent al final del archivo para permitir que cada Indent tenga un token de Dedent coincida.

Para que esto funcione correctamente, debe agregar un salto de línea anterior y posterior a su archivo de fuente de entrada.

ANTRL3

Una demostración rápida:

grammar PyEsque;

options {
  output=AST;
}

tokens {
  BLOCK;
}

@lexer::members {

  private int previousIndents = -1;
  private int indentLevel = 0;
  java.util.Queue<Token> tokens = new java.util.LinkedList<Token>();

  @Override
  public void emit(Token t) {
    state.token = t;
    tokens.offer(t);
  }

  @Override
  public Token nextToken() {
    super.nextToken();
    return tokens.isEmpty() ? Token.EOF_TOKEN : tokens.poll();
  }

  private void jump(int ttype) {
    indentLevel += (ttype == Dedent ? -1 : 1);
    emit(new CommonToken(ttype, "level=" + indentLevel));
  }
}

parse
 : block EOF -> block
 ;

block
 : Indent block_atoms Dedent -> ^(BLOCK block_atoms)
 ;

block_atoms
 :  (Id | block)+
 ;

NewLine
 : NL SP?
   {
     int n = $SP.text == null ? 0 : $SP.text.length();
     if(n > previousIndents) {
       jump(Indent);
       previousIndents = n;
     }
     else if(n < previousIndents) {
       jump(Dedent);
       previousIndents = n;
     }
     else if(input.LA(1) == EOF) {
       while(indentLevel > 0) {
         jump(Dedent);
       }
     }
     else {
       skip();
     }
   }
 ;

Id
 : (''a''..''z'' | ''A''..''Z'')+
 ;

SpaceChars
 : SP {skip();}
 ;

fragment NL     : ''/r''? ''/n'' | ''/r'';
fragment SP     : ('' '' | ''/t'')+;
fragment Indent : ;
fragment Dedent : ;

Puedes probar el analizador con la clase:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
  public static void main(String[] args) throws Exception {
    PyEsqueLexer lexer = new PyEsqueLexer(new ANTLRFileStream("in.txt"));
    PyEsqueParser parser = new PyEsqueParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.parse().getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}    

Si ahora pone lo siguiente en un archivo llamado in.txt :

AAA AAAAA BBB BB B BB BBBBB BB CCCCCC C CC BB BBBBBB C CCC DDD DD D DDD D DDD

(Tenga en cuenta los saltos de línea iniciales y finales!)

entonces verás una salida que corresponde al siguiente AST:

Tenga en cuenta que mi demostración no producirá suficientes deducciones sucesivas, como la deducción de ccc a aaa (se necesitan 2 tokens de dedent):

aaa
  bbb
    ccc
aaa

Necesitaría ajustar el código en else if(n < previousIndents) { ... } para emitir más de 1 token de dedent en función de la diferencia entre n y previousIndents . En la parte superior de mi cabeza, podría verse así:

 else if(n < previousIndents) {
   // Note: assuming indent-size is 2. Jumping from previousIndents=6 
   // to n=2 will result in emitting 2 `Dedent` tokens
   int numDedents = (previousIndents - n) / 2; 
   while(numDedents-- > 0) {
     jump(Dedent);
   }
   previousIndents = n;
 }

ANTLR4

Para ANTLR4, haga algo como esto:

grammar Python3;

tokens { INDENT, DEDENT }

@lexer::members {
  // A queue where extra tokens are pushed on (see the NEWLINE lexer rule).
  private java.util.LinkedList<Token> tokens = new java.util.LinkedList<>();
  // The stack that keeps track of the indentation level.
  private java.util.Stack<Integer> indents = new java.util.Stack<>();
  // The amount of opened braces, brackets and parenthesis.
  private int opened = 0;
  // The most recently produced token.
  private Token lastToken = null;
  @Override
  public void emit(Token t) {
    super.setToken(t);
    tokens.offer(t);
  }

  @Override
  public Token nextToken() {
    // Check if the end-of-file is ahead and there are still some DEDENTS expected.
    if (_input.LA(1) == EOF && !this.indents.isEmpty()) {
      // Remove any trailing EOF tokens from our buffer.
      for (int i = tokens.size() - 1; i >= 0; i--) {
        if (tokens.get(i).getType() == EOF) {
          tokens.remove(i);
        }
      }

      // First emit an extra line break that serves as the end of the statement.
      this.emit(commonToken(Python3Parser.NEWLINE, "/n"));

      // Now emit as much DEDENT tokens as needed.
      while (!indents.isEmpty()) {
        this.emit(createDedent());
        indents.pop();
      }

      // Put the EOF back on the token stream.
      this.emit(commonToken(Python3Parser.EOF, "<EOF>"));
    }

    Token next = super.nextToken();

    if (next.getChannel() == Token.DEFAULT_CHANNEL) {
      // Keep track of the last token on the default channel.
      this.lastToken = next;
    }

    return tokens.isEmpty() ? next : tokens.poll();
  }

  private Token createDedent() {
    CommonToken dedent = commonToken(Python3Parser.DEDENT, "");
    dedent.setLine(this.lastToken.getLine());
    return dedent;
  }

  private CommonToken commonToken(int type, String text) {
    int stop = this.getCharIndex() - 1;
    int start = text.isEmpty() ? stop : stop - text.length() + 1;
    return new CommonToken(this._tokenFactorySourcePair, type, DEFAULT_TOKEN_CHANNEL, start, stop);
  }

  // Calculates the indentation of the provided spaces, taking the
  // following rules into account:
  //
  // "Tabs are replaced (from left to right) by one to eight spaces
  //  such that the total number of characters up to and including
  //  the replacement is a multiple of eight [...]"
  //
  //  -- https://docs.python.org/3.1/reference/lexical_analysis.html#indentation
  static int getIndentationCount(String spaces) {
    int count = 0;
    for (char ch : spaces.toCharArray()) {
      switch (ch) {
        case ''/t'':
          count += 8 - (count % 8);
          break;
        default:
          // A normal space char.
          count++;
      }
    }

    return count;
  }

  boolean atStartOfInput() {
    return super.getCharPositionInLine() == 0 && super.getLine() == 1;
  }
}

single_input
 : NEWLINE
 | simple_stmt
 | compound_stmt NEWLINE
 ;

// more parser rules

NEWLINE
 : ( {atStartOfInput()}?   SPACES
   | ( ''/r''? ''/n'' | ''/r'' ) SPACES?
   )
   {
     String newLine = getText().replaceAll("[^/r/n]+", "");
     String spaces = getText().replaceAll("[/r/n]+", "");
     int next = _input.LA(1);
     if (opened > 0 || next == ''/r'' || next == ''/n'' || next == ''#'') {
       // If we''re inside a list or on a blank line, ignore all indents, 
       // dedents and line breaks.
       skip();
     }
     else {
       emit(commonToken(NEWLINE, newLine));
       int indent = getIndentationCount(spaces);
       int previous = indents.isEmpty() ? 0 : indents.peek();
       if (indent == previous) {
         // skip indents of the same size as the present indent-size
         skip();
       }
       else if (indent > previous) {
         indents.push(indent);
         emit(commonToken(Python3Parser.INDENT, spaces));
       }
       else {
         // Possibly emit more than 1 DEDENT token.
         while(!indents.isEmpty() && indents.peek() > indent) {
           this.emit(createDedent());
           indents.pop();
         }
       }
     }
   }
 ;

// more lexer rules

Tomado de: https://github.com/antlr/grammars-v4/blob/master/python3/Python3.g4