"parser ricorsivo di discendenza" scritto a mano con regola "catch all"

Question

"parser ricorsivo di discendenza" scritto a mano con regola "catch all"

#1 da (3 voti)
#2 da (0 voti)

2

Sto provando a scrivere un parser di discesa ricorsiva (senza scanner) con una regola "catch all" per la seguente grammatica "Modello di baffi" (semplificata qui):

       content : (variable_tag | section_tag | static)*
  variable_tag : mustache_open id mustache_close
   section_tag : mustache_open '#' id mustache_close
                 content mustache_open '/' id mustache_close
 mustache_open : '{{'
mustache_close : '}}'
            id : [a–zA–Z$_][a–zA–Z0–9$_]*
        static : .+  // "catch all"

La produzione static dovrebbe fermarsi prima della prossima produzione abbinata. E non posso venire a una soluzione per questo che non rompere la struttura grammaticale.

Un input valido è:

You have just won {{value}} dollars!
{{#in_ca}}
Well, {{taxed_value}} dollars, after taxes.
{{/in_ca}}

L'output per questo sarebbe un albero sintattico astratto come:

                           +-------+
                           |Content|
                           +-------+
                               |
        +---------------+------+--------+--------------+
        |               |               |              | 
+--------------+  +-----------+  +-------------+  +----------+
|Static        |  |VariableTag|  |Static       |  |SectionTag|
|"\nYou...won "|  |value      |  |" dollars"\n"|  |in_ca     |
+--------------+  +-----------+  +-------------+  +----------+
                                                       | 
                                                   +-------+
                                                   |Content|
                                                   +-------+
                                                       |
                                    +-------------+----+--------------+
                                    |             |                   |
                              +----------+  +-----------+  +---------------------+
                              |Static    |  |VariableTag|  |Static               |
                              |"\nWell, "|  |taxed_value|  |" dollars...taxes.\n"|
                              +----------+  +-----------+  +---------------------+

Qualsiasi riferimento a un'implementazione di una regola "catch all" per un parser di discesa ricorsivo?

grammar algorithms parsing

posta ericbn 28.05.2015 - 00:07

fonte

2 risposte

0

Per questa particolare grammatica, penso che puoi abbinare fino a visualizzare {{ . Quindi premi {{ sui token da leggere.

Quindi penso che la chiave qui abbia solo la possibilità di tornare all'elenco dei token. Avere un buffer fisso di token è generalmente buono anche per la gestione degli errori, nei parser LR, ma non sarei sorpreso se fosse utile anche nei parser LL.

risposta data 28.05.2015 - 01:38

fonte

Leggi altre domande sui tag grammar algorithms parsing

Quali sono le complessità temporali e spaziali di questo metodo ricorsivo che inverte una lista concatenata? Condivisione di oggetti info tra oggetti?

score 3 · Accepted Answer

La tua grammatica sarà corretta se la regola catch-all consuma solo un singolo carattere e se utilizzi la scelta prioritaria nella grammatica in modo che static venga tentato solo come ultima risorsa. Naturalmente, questi token a carattere singolo sono terribilmente inefficienti. Ci sono due modi per risolvere questo problema:

lascia che la regola catch-all sia static : [^\{]+ | .
fai in modo che il parser memorizzi un puntatore al token precedente. Se stai leggendo un token statico e il token precedente era statico, aggiungi la stringa anziché creare un nuovo elemento nel tuo AST. Questo può essere un po 'complicato da eseguire, poiché in un parser RecDesc ogni regola di solito fallisce o restituisce una sottostruttura AST. Potrebbe avere senso introdurre uno pseudo-token che significhi "successo, ma nessuna necessità di azione" poiché il token risiede già nell'AST in caso di una correzione e non dovrebbe essere aggiunto due volte.

C'è un problema con questo: dato che in nessun momento ti impegni con un'alternativa, questo parser richiede molto backtracking. Mi aspetto che ciò causi complessità esponenziale, a meno che non si utilizzi una strategia Packrat (o si usi una tecnica di analisi che sia effettivamente adatta per grammatiche ambigue). Ecco un esempio di input per tale comportamento:

{{#foo}} {{#a}} {{#a}} {{#a}} {{/foo} sic!

Secondo la tua grammatica, questo input sarebbe completamente statico, ma il parser ricorrerebbe quattro volte nella regola della sezione.