Creazione di un parser (parte I)

Question

Sto creando il mio linguaggio di programmazione basato su javascript (sì, è pazzesco, ma è solo per imparare ...). Beh, sto leggendo parser e il primo passaggio è quello di convertire il codice sorgente per i token, come:

if(x > 5) 
    return true; 

Tokenizer a:

T_IF   "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_NUMBER  "5" 
T_RPAREN  ")" 
T_IDENTIFIER "return" 
T_TRUE  "true" 
T_TERMINATOR ";" 

Non so se la mia logica è corretta per quello per un po '. Sul mio parser è ancora meglio (o no?) E tradurre ad esso (sì, array multidimensionale):

T_IF    "if" 
    T_EXPRESSION  ... 
    T_IDENTIFIER  "x" 
    T_GT    ">" 
    T_NUMBER   "5" 
    T_CLOSURE  ... 
    T_IDENTIFIER  "return" 
    T_TRUE   "true" 

ho qualche dubbio:

1. è il mio modo migliore o peggiore che il modo originale ? Nota che il mio codice sarà letto e compilato (tradotto in un'altra lingua, come PHP), invece di essere interpretato in ogni momento.
2. Dopo il tokenizer, cosa devo fare esattamente? Sono davvero perso su questo passaggio!
3. Ci sono alcuni buoni tutorial per imparare come posso farlo?

Bene, è quello. Ciao!

Answer 1

In generale, si desidera separare le funzioni del tokeniser (chiamato anche lexer) da altre fasi del compilatore o dell'interprete. La ragione di ciò è la modularità di base: ogni passaggio consuma un tipo di cosa (ad esempio, caratteri) e ne produce un altro (ad esempio, token).

Quindi hai convertito i tuoi personaggi in token. Ora si desidera convertire la propria lista di token in espressioni nidificate significative e questo è convenzionalmente chiamato analizzando. Per un linguaggio simile a JavaScript, dovresti esaminare recursive descent parsing. Per l'analisi di espressioni con operatori infissi con diversi livelli di precedenza, lo Pratt parsing è molto utile e puoi ricorrere all'ordinaria analisi della discesa ricorsiva per casi speciali.

Solo per darti un esempio più concreto basato sul tuo caso, presumo che tu possa scrivere due funzioni: accept(token) e expect(token), che testano il token successivo nello stream che hai creato. Farai una funzione per ogni tipo di istruzione o espressione nella grammatica della tua lingua. Ecco pseudocodice Pythonish per una funzione statement(), per esempio:

def statement(): 

    if accept("if"): 
    x = expression() 
    y = statement() 
    return IfStatement(x, y) 

    elif accept("return"): 
    x = expression() 
    return ReturnStatement(x) 

    elif accept("{") 
    xs = [] 
    while True: 
     xs.append(statement()) 
     if not accept(";"): 
     break 
    expect("}") 
    return Block(xs) 

    else: 
    error("Invalid statement!") 

Questo ti dà ciò che è chiamato un albero di sintassi astratta (AST) del programma, che è quindi possibile manipolare (ottimizzazione e analisi), uscita (compilation), o correre (interpretazione).

Answer 2

Il mio modo migliore o peggiore è che il modo originale ? Nota che il mio codice sarà letto e compilato (tradotto in un'altra lingua, come PHP), invece di essere interpretato in ogni momento.

Qual è il modo originale ? Esistono molti modi diversi per implementare le lingue. Penso che in questo momento sia tutto a posto, una volta ho provato a costruire un linguaggio da me tradotto in C#, lo hack programming language. Molti compilatori di lingue traducono in una lingua intermedia, è abbastanza comune.

Dopo il tokenizer, cosa devo fare esattamente? Sono davvero perso su questo passaggio!

Dopo creazione di token, è necessario analizzare esso. Utilizza un buon framework lexer/parser, come lo Boost.Spirit, o Coco, o qualsiasi altra cosa. Ce ne sono centinaia. Oppure puoi implementare il tuo lexer, ma ciò richiede tempo e risorse. Esistono molti modi per analizzare il codice, in genere faccio affidamento su recursive descent parsing.

Quindi è necessario generare codice. Questa è la parte più difficile secondo me. Ci sono anche strumenti per questo, ma puoi farlo manualmente se vuoi, ho provato a farlo nel mio progetto, ma era piuttosto semplice e buggato, c'è qualche codice utile here e here.

Ci sono alcuni buoni tutorial per imparare come posso farlo?

Come ho suggerito in precedenza, utilizzare strumenti per farlo. Esistono molti buoni framework di parser ben documentati.Per ulteriori informazioni, puoi provare a chiedere ad alcune persone che conoscono questa roba. @DeadMG, sopra allo Lounge C++ sta creando un linguaggio di programmazione chiamato "Wide". Potresti provare a consultarlo.

Answer 3

La maggior parte dei kit di strumenti dividere il processo completo in due separati parti

• lexer (aka. Tokenizer)
• parser (aka. Grammatica)

Il tokenizzatore dividerà i dati di input in token. Il parser opererà solo sul token "stream" e costruirà la struttura.

La tua domanda sembra essere focalizzata sul tokenizer. Ma la tua seconda soluzione mescola il parser di grammatica e il tokenizer in un unico passaggio. Teoricamente questo è anche possibile, ma per un principiante è molto più semplice da fare come la maggior parte degli altri strumenti/framework: tenere separati i passaggi.

Per la tua prima soluzione: Vorrei tokenize vostro esempio come questo:

T_KEYWORD_IF "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_LITARAL  "5" 
T_RPAREN  ")" 
T_KEYWORD_RET "return" 
T_KEYWORD_TRUE "true" 
T_TERMINATOR ";" 

Nella maggior parte delle lingue parole chiave non possono essere usati come i nomi dei metodi, i nomi delle variabili e così via. Ciò si riflette già a livello di tokenizer (T_KEYWORD_IF, T_KEYWORD_RET, T_KEYWORD_TRUE).

Il livello successivo sarebbe prendere questo flusso e - mediante l'applicazione di una grammatica formale - sarebbe costruire qualche datastructure (spesso chiamato AST - Abstract Syntax Tree), che potrebbe essere simile a questo:

IfStatement: 
    Expression: 
     BinaryOperator: 
      Operator:  T_GT 
      LeftOperand: 
       IdentifierExpression: 
        "x" 
      RightOperand: 
       LiteralExpression 
        5 
    IfBlock 
     ReturnStatement 
      ReturnExpression 
       LiteralExpression 
        "true" 
    ElseBlock (empty) 

Attuare il parser a mano di solito è fatto da alcuni framework.Implementare qualcosa del genere a mano e in genere viene fatto in un'università nella migliore parte del semestre. Quindi dovresti davvero usare un qualche tipo di framework.

L'input per un framework di parser di grammatica è in genere una grammatica formale in un tipo di BNF. La tua parte "se" sembra così:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ; 

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ; 

BinaryExpression: LeftOperand BinaryOperator RightOperand; 

.... 

Questo è solo per avere l'idea. L'analisi di un linguaggio realistico come Javascript correttamente non è un compito facile. Ma divertente.