Lexer / Parser per le lingue multidimensionali

4

In che modo Lexer / Parser funziona in un linguaggio di programmazione 2D come Funciton al fine di trasformare tali un codice sorgente insolito per l' AST ?

corretto     
posta 53777A 14.05.2014 - 09:33
fonte

2 risposte

5

I linguaggi sensibili al layout sono un evento insolito perché sono un po 'più difficili da analizzare. Un token prodotto da un lexer non solo contiene un tipo e un valore, ma anche una posizione e forse una dimensione. È possibile che il lexer non proceda linearmente riga per riga, ma prima legge l'intero file in memoria e poi lo attraversa come una mappa 2D.

L'analisi sensibile al layout o l'analisi sensibile all'indentazione è un campo di ricerca piccolo ma ancora attivo; indagando su questi termini ti forniremo un numero di documenti. In casi facili come Python, possiamo usare un lexer stateful che nasconde il rientro da un parser, e invece emette token fantasma come INDENT e DEDENT che sarebbe l'equivalente di parentesi graffe in C. In casi più complessi, noi bisogno di annotare la grammatica del parser con i requisiti sul rientro, ad es la grammatica avanzata senza contesto

DoExpression{n} ::= "do"{n} DoExpressionInner{m: m > n}
DoExpressionInner{n} ::= Expression{n}+

potrebbe consentire

do expr1
   expr2
   expr3

ma non

do expr1
     expr2
expr3

Nella grammatica di cui sopra, l'espressione nelle parentesi graffe pone una condizione sulla posizione del bordo sinistro della regola o del token. La maggior parte dei generatori di parser non supporta l'analisi del layout.

Nel caso più generale, un lexer dovrebbe riconoscere le forme nell'input testuale. Un parser quindi probabilmente userebbe tecniche bottom-up per raggruppare le forme primitive in una struttura dati utilizzabile, probabilmente un grafo non gerarchico. Ad esempio, l'immagine

  012345678901234567890123456789
0 +---+
1 | A |-----------.
2 +---+           |        +---+
3                 '------->| B |
4                          +---+

potrebbe essere lexato come:

BOX "A" at ( 0, 0) to ( 4, 2)
BOX "B" at (25, 2) to (29, 4)
ARROW   at ( 5, 1) to (24, 3)

Questi token potrebbero quindi essere memorizzati in modo da supportare la ricerca spaziale. A partire dalla casella A , possiamo guardare i campi circostanti e trovare l'inizio della freccia. Alla fine della freccia, troviamo la casella B e quindi possiamo aggiungere questa connessione tra A e B al grafico della sintassi astratta. Successivamente, la freccia può essere rimossa dal set di token inutilizzati. Poiché nessun altro token si trova nel vicinato immediato di A , anche questo può essere rimosso, idem per B . Poiché il set di token non verificati è vuoto, l'analisi è riuscita.

Parsing Funciton è più semplice dell'analisi di tale arte ASCII, poiché i simboli utilizzati mostrano direttamente le connessioni. Potrebbe quindi essere possibile analizzare la fonte in un unico passaggio: una volta trovato qualsiasi elemento, possiamo seguire le connessioni e aggiungere le connessioni appropriate al nostro Abstract Syntax Graph.

La maggior parte delle lingue che usano i grafici per rappresentare dati o un programma non usano una rappresentazione testuale 2D. Al contrario, forniranno gli IDE che rappresentano il rendering della struttura come un grafico, ma lo memorizzeranno come una forma più facilmente elaborabile. Probabilmente, le connessioni verrebbero archiviate dagli ID anziché da posizioni spaziali, sebbene il layout sarebbe parte delle informazioni memorizzate. LabView è probabilmente uno dei linguaggi di programmazione visiva più noti che utilizzano i grafici per rappresentare il flusso di controllo / dati, ma non offrono una rappresentazione testuale del programma.

    
risposta data 14.05.2014 - 14:14
fonte
3

È solo flusso di dati: solo la rappresentazione visiva visualizzata all'utente è 2D. Internamente, questa è una struttura grafica con un elenco di nodi e un elenco di vertici.

Guarda VHDL , Verilog o qualsiasi linguaggio di descrizione dell'hardware per i linguaggi del flusso di dati basati su testo.

Guarda Excel o qualsiasi foglio di lavoro per un'altra rappresentazione del linguaggio del flusso di dati.

La differenza principale non è l'analisi, è in runtime.

Modifica

Il linguaggio Funciton in realtà è molto specifico in quel codice sorgente è una sorta di arte ASCII di scatole e bordi. Il primo commit dell'interprete fornisce l'algoritmo generale utilizzato per analizzare l'arte ASCII:

  1. Trova caselle e i loro bordi in uscita
    • Inizia a cercare una casella qui se questo è un angolo in alto a sinistra di una casella
    • trova la larghezza della casella camminando lungo il margine superiore
    • Trova l'altezza del riquadro camminando lungo il bordo sinistro
    • Verifica il bordo inferiore
    • Verifica il margine destro
    • ...
  2. Analizza le connessioni tra i nodi e scopri tutti i lati liberi ...
risposta data 14.05.2014 - 09:41
fonte

Leggi altre domande sui tag