ANTLR Qual è il modo più semplice per realizzare la grammatica basata su indent python?

Question

Sto provando a realizzare la grammatica come indent-python. esempio

Fonte:

ABC QWE 
    CDE EFG 
    EFG CDE 
    ABC 
    QWE ZXC 

come la vedo io, che cosa ho bisogno è di realizzare due token trattino e DEDENT, così ho potuto scrivere qualcosa di simile:

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

C'è un modo semplice per realizzare questo usando ANTLR?

(preferirei, se è possibile, utilizzare lexer ANTLR standard.)

Answer 1

Io non so quale sia il modo più semplice per gestire la cosa è, ma ciò che segue è un modo relativamente facile. Ogni volta che abbini un'interruzione di riga nel tuo lexer, opzionalmente abbina uno o più spazi. Se ci sono spazi dopo l'interruzione di riga, confronta la lunghezza di questi spazi con la dimensione corrente del rientro. Se si tratta di più rispetto alla dimensione di rientro corrente, emettere un Indent modo, se è inferiore al trattino-dimensioni attuali, emettono un token Dedent e se è lo stesso, non fare nulla.

È inoltre necessario emettere un numero di token Dedent alla fine del file per consentire ad ogni Indent di avere un token Dedent corrispondente.

Per farlo funzionare correttamente, è must aggiunge una pausa iniziali e finali riga al file sorgente d'ingresso!

ANTRL3

Un rapido demo:

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 : ; 

È possibile verificare il parser con la classe:

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); 
    } 
}  

Se ora mettete quanto segue in un file chiamato in.txt:

 

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

(nota le interruzioni di linea iniziali e finali!)

allora vedrete uscita che corrisponde al seguente AST:

Nota che il mio demo non sarebbe produrre abbastanza dedents in successione, come dedenting ccc-aaa (2 dedent sono necessari i token):

aaa 
    bbb 
    ccc 
aaa 

si avrebbe bisogno di modificare il codice all'interno else if(n < previousIndents) { ... } per emettere forse più di 1 gettone DEDENT bas sulla differenza tra n e previousIndents. Fuori della parte superiore della mia testa, che potrebbe assomigliare a questo:

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

Per ANTLR4, fare qualcosa di simile:

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 

Tratto da: https://github.com/antlr/grammars-v4/blob/master/python3/Python3.g4

Answer 2

Avete guardato il Python ANTLR grammar?

Edit: Aggiunto codice Python per la creazione di pseudo TRATTINO/DEDENT gettoni

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 3

C'è una libreria open source antlr-denter per ANTLR v4 che consente di analizzare i rientri e le deduzioni per te. Controlla il suo README per come usarlo.

Poiché si tratta di una libreria, piuttosto che di frammenti di codice da copiare e incollare nella grammatica, la gestione dell'indentazione può essere aggiornata separatamente dal resto della grammatica.

Answer 4

Esiste un modo relativamente semplice per eseguire questo ANTLR, che ho scritto come esperimento: Dent.g4. Questa soluzione è diversa dalle altre menzionate in questa pagina che sono state scritte da Kiers e Shavit. Si integra con il runtime esclusivamente tramite un override del metodo nextToken() della Lexer. Esegue il suo lavoro esaminando i token: (1) un token NEWLINE innesca l'inizio di una fase di "tenere traccia di indentazione"; (2) spazi bianchi e commenti, entrambi impostati sul canale HIDDEN, vengono conteggiati e ignorati, rispettivamente, durante tale fase; e, (3) qualsiasi token non HIDDEN termina la fase. Pertanto, il controllo della logica di indentazione è una semplice questione di impostare il canale di un token.

Entrambe le soluzioni citate in questa pagina richiedono un token NEWLINE per acquisire anche tutti gli spazi bianchi successivi, ma in tal modo non è possibile gestire i commenti su più righe che interrompono quello spazio vuoto. L'ammaccatura, invece, conserva i token di spazi bianchi separati da NEWLINE e può gestire i commenti su più righe.

La tua grammatica dovrebbe essere impostata come in basso. Si noti che le regole LEXER NEWLINE e WS hanno azioni che controllano lo stato pendingDent e tengono traccia del livello di indentazione con la variabile 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...