ANTLR Jaki jest najprostszy sposób realizacji języka Pythona?

Question

Próbuję zrealizować Pythona podobnie jak gramatyki zależne od wcięcia. Przykładem

Źródło:

ABC QWE 
    CDE EFG 
    EFG CDE 
    ABC 
    QWE ZXC 

jak widzę, co jest mi potrzebne do zrealizowania dwa żetony tiret i DEDENT, więc mogę napisać coś takiego:

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

Czy jest jakiś prosty sposób uświadomić to za pomocą ANTLR?

(wolałbym, jeśli to możliwe, używać standardowego antlr lexer.)

Answer 1

Nie wiem, co to najprostszy sposób, aby ją obsłużyć to, ale po to stosunkowo łatwy sposób. Za każdym razem, gdy dopasujesz podział linii do swojego lexera, opcjonalnie dopasuj jedną lub więcej spacji. Jeśli po łamaniu linii istnieją spacje, porównaj długość tych spacji z bieżącym rozmiarem wcięcia. Jeśli jest większy niż bieżący rozmiar wcięcia, emituj token Indent, jeśli jest on mniejszy niż bieżący rozmiar wcięcia, emituj token Dedent, a jeśli jest taki sam, nie rób nic.

Będziesz także chciał wysłać liczbę tokenów Dedent na końcu pliku, aby każdy Indent miał pasujący znacznik Dedent.

Aby to właściwie działa, koniecznością dodać początkowe i końcowe podział wiersza do pliku źródłowego wejściowego!

ANTRL3

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

można przetestować parser z klasą:

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

Jeśli teraz umieścić następujące informacje w pliku o nazwie in.txt:

 

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

(Zwróć uwagę na początkową i końcową kreskę!)

wtedy zobaczysz wyjście, które odpowiada następującym AST:

Uwaga że moje demo nie wytwarza wystarczającej dedents z rzędu, jak dedenting od ccc do aaa (2 dedent potrzebne są tokeny):

aaa 
    bbb 
    ccc 
aaa 

trzeba by dostosować kod do wewnątrz else if(n < previousIndents) { ... } ewentualnie emitują więcej niż 1 dedent tokenów BAS ed na różnicę między n i previousIndents. Od szczytu głowy, że może wyglądać następująco:

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

Dla ANTLR4, zrób coś takiego:

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 

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

Answer 2

Pan spojrzał na Python ANTLR grammar?

Edycja: Dodano kod Python psuedo tworzenia tiret/DEDENT tokeny

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

Jest biblioteka open-source antlr-denter dla ANTLR v4, która pomaga analizować wcięcia i dedycje dla ciebie. Sprawdź jego numer README, aby dowiedzieć się, jak z niego korzystać.

Ponieważ jest to biblioteka, a nie fragmenty kodu do skopiowania i wklejenia do gramatyki, jej obsługa wcięć może być aktualizowana niezależnie od pozostałej części gramatyki.

Answer 4

Istnieje stosunkowo prosty sposób na wykonanie tego ANTLR, który napisałem jako eksperyment: Dent.g4. To rozwiązanie różni się od innych wspomnianych na tej stronie, które zostały napisane przez Kiersa i Shavita. Integruje się z środowiskiem wykonawczym wyłącznie poprzez zastąpienie metody Lexer'a metodą nextToken(). Wykonuje swoją pracę poprzez sprawdzenie tokenów: (1) token NEWLINE uruchamia fazę "śledzenia wcięć"; (2) białe spacje i komentarze, oba ustawione na kanał HIDDEN, są odpowiednio zliczane i ignorowane podczas tej fazy; oraz (3) dowolny żeton nie-HIDDEN kończy fazę. Zatem sterowanie logiką wcięcia jest prostą kwestią ustawienia kanału tokena.

Oba rozwiązania wymienione na tej stronie wymagają tokena NEWLINE do przechwytywania wszystkich kolejnych białych znaków, ale w tym przypadku nie mogą obsłużyć wielowierszowych komentarzy przerywających ten spację. Dent zamiast tego zachowuje NEWLINE i oddzielne tokeny spacji i może obsługiwać komentarze wielowierszowe.

Twoja gramatyka zostanie skonfigurowana jak poniżej. Zwróć uwagę, że reguły NEWLINE i WS lexer mają akcje, które kontrolują stan pendingDent i śledzą poziom wcięcia ze zmienną 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...