Qual è un approccio più efficiente alla decodifica delle sequenze di escape nel testo?

Question

Qual è un approccio più efficiente alla decodifica delle sequenze di escape nel testo?

#1 da (5 voti)

3

Sto lavorando su parser che non elaborano solo contenuti delimitati, ma anche sequenze di escape all'interno di determinate parti di quel contenuto. Sto contemplando l'efficienza di diversi approcci alla tokenizzazione e apprezzerei i pensieri su quanto segue.

Per usare JSON come un solo esempio, ci sono alcuni modi per elaborare quanto segue:

["Foo\n"]

Considera che il flusso di input potrebbe essere multi-megabyte con molte sequenze di escape / evasioni varie

approcci:

Per carattere

La prima opzione è semplicemente quella di tokenize per carattere:

[array string #"F" #"o" #"o" #"^/" /string /array]

Pro: uniforme, veloce da implementare, funziona bene con i contenuti in streaming

Con: non è affatto efficiente poiché stai invocando il gestore di token per un numero di token simile al numero di caratteri nel flusso di input.

Con token di escape / non-escape

Un tokenizzatore un po 'più efficiente potrebbe comportare:

[array string "Foo" "^/" /string /array]

Pro: un po 'più efficiente, rapido da implementare

Contro: ci sono ancora molti token per contenuti ad alto rischio di escape, non può implicare che due token rappresentino uno o due elementi

Per Token interi

Un tokenizzatore minimo potrebbe produrre quanto segue:

[array "Foo^/" /array]

Pro: molti meno token da gestire

Con: questo solleva molte domande, tra le principali: come viene creata la stringa "Foo^/" ? Per rompere questo, prenderà in considerazione due sotto-approcci:

Abbina la sequenza, quindi risolvi gli escape:

Questo potrebbe essere gestito così:

[
      "[" (emit 'array)
    | "]" (emit /array)
    | {"} copy value string-sequence {"} (emit de-escape value)
]

Professionisti: identifica rapidamente le partite, usa e modifica una singola stringa

Contro: si tratta in effetti di un processo a due passaggi: potrebbero esserci due regole separate per abbinare le sequenze di escape: una in string-sequence e una in de-escape - ecco lo sforzo extra per garantire che siano coerenti

Abbina porzioni della stringa e aggiungi a un buffer:

Potrebbe essere:

[
      "[" (emit 'array)
    | "]" (emit /array)
    | {"} (buffer: make string! "") some [
          copy part unescaped-sequence (append buffer part)
        | "\n" (append buffer "^/")
    ] {"} (emit buffer)
]

Professionisti: un passaggio

Contro: Ora torniamo alla gestione di blocchi simili al metodo "Gestisci la sequenza di escape / non-escaping" e gestendo un valore aggiuntivo buffer .

strings parsing rebol escaping

posta rgchris 10.09.2017 - 20:44

fonte

1 risposta

Leggi altre domande sui tag strings parsing rebol escaping

Una tabella di database che contiene statistiche su altri dati di tabella deve essere a colonne o a righe? Assegnazione con parentesi

score 5 · Accepted Answer

La maggior parte dei parser decodifica gli escape di stringhe durante la tokenizzazione. Si noti che il tokenizer deve essere comunque consapevole degli escape per determinare la fine di una stringa, poiché il delimitatore di stringhe " stesso può essere sfuggito. Ciò significa che non è fondamentalmente più complicato anche decodificarlo in un solo passaggio.

Non è peggio riconoscere prima la stringa letterale e quindi elaborare gli escape. Nei linguaggi di basso livello (come C) un approccio a due fasi consente di conoscere le dimensioni esatte della stringa di decodifica prima di elaborare gli escape. Questo non è un buon argomento nel tuo caso. Potrebbe comunque essere una buona idea se questo approccio fosse più semplice, ma la tua funzione di de-escape ammonterà comunque a qualcosa come il tokenizer a passaggio singolo.

Un tokenizzatore dovrebbe produrre un token per letterale perché questo rende molto più facile da gestire per gli utenti del flusso di token. In particolare, una stringa letterale suddivisa in più token sarebbe concatenata in una singola stringa comunque ad un certo punto, quindi dovremmo farlo subito.

Uno scenario notevole in cui è non il caso è in linguaggi complicati con stringhe "letterali" che consentono l'interpolazione - il tokenizzazione di quelli eleganti è impegnativo e probabilmente porterà a qualcosa di simile al tuo "tokenize" sfuggito "suggerimento token / caratteri non evasi". Come altro esempio, il modello di documento XML può contenere più nodi di testo consecutivi. Le entità XML sono complicate perché un tokenizzatore dovrà analizzare la DTD prima che le entità possano essere espanse, e poiché le entità in espansione espandono il programma a un attacco denial-of-service.

TL; DR: preferisci il tuo approccio By Whole Tokens , idealmente implementato tramite la tua idea Corrispondenza delle porzioni della stringa e aggiunta a un buffer .