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

Sto cercando di realizzare la grammatica come indent-dependent di Python.

Esempio di fonte:

ABC QWE CDE EFG EFG CDE ABC QWE ZXC 

Come vedo, ciò di cui ho bisogno è realizzare due token INDENT e DEDENT, quindi potrei scrivere qualcosa come:

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

C’è un modo semplice per realizzare questo utilizzando ANTLR?

(Preferirei, se ansible, usare il lexer ANTLR standard).

Non so quale sia il modo più semplice per gestirlo, ma quanto segue è relativamente semplice. 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 è superiore alla dimensione corrente del rientro, emette un token di Indent , se è inferiore alla dimensione di rientro corrente, emette un token Dedent e se è lo stesso, non fare nulla.

Dovrai anche emettere un numero di token Dedent alla fine del file per consentire a ogni Indent avere un token Dedent corrispondente.

Affinché funzioni correttamente, è necessario aggiungere un’interruzione di riga iniziale e finale al file sorgente di input!

ANTRL3

Una demo veloce:

 grammar PyEsque; options { output=AST; } tokens { BLOCK; } @lexer::members { private int previousIndents = -1; private int indentLevel = 0; java.util.Queue tokens = new java.util.LinkedList(); @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 : ; 

Puoi testare il parser con la class:

 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 inserisci 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 riga iniziali e finali!)

quindi vedrai un output che corrisponde al seguente AST:

inserisci la descrizione dell'immagine qui

Nota che la mia demo non produrrebbe abbastanza deduzioni in successione, come la deduzione da ccc a aaa (sono necessari 2 token dediti):

 aaa bbb ccc aaa 

Dovresti modificare il codice all’interno else if(n < previousIndents) { ... } per emettere probabilmente più di un token dedunto in base alla differenza tra n e previousIndents . In cima alla mia testa, questo potrebbe apparire come 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, fai qualcosa di simile a questo:

 grammar Python3; tokens { INDENT, DEDENT } @lexer::members { // A queue where extra tokens are pushed on (see the NEWLINE lexer rule). private java.util.LinkedList tokens = new java.util.LinkedList<>(); // The stack that keeps track of the indentation level. private java.util.Stack 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, "")); } 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

C’è una libreria open-source antlr-denter per ANTLR v4 che aiuta ad analizzare i rientri e le deduzioni per te. Controlla il suo README su come usarlo.

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

Hai esaminato la grammatica ANTLR Python ?

Modifica: aggiunto il codice Python di psuedo per la creazione di token 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 

C’è un modo relativamente semplice per fare 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() di nextToken() . Esegue il suo lavoro esaminando i token: (1) un token NEWLINE fa scattare l’inizio di una fase di “tenere traccia della rientranza”; (2) spazi bianchi e commenti, entrambi impostati su channel HIDDEN , vengono conteggiati e ignorati, rispettivamente, durante quella fase; e, (3) qualsiasi gettone 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 menzionate in questa pagina richiedono un token NEWLINE per catturare anche tutti gli spazi bianchi successivi, ma in tal modo non possono gestire i commenti su più righe che interrompono quello spazio vuoto. L’ammaccatura, invece, mantiene separati i token NEWLINE e gli spazi bianchi e può gestire i commenti su più righe.

La tua grammatica dovrebbe essere impostata come in basso. Si noti che le regole pendingDent 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...