Dipendenze circolari: parser grammaticale ricorsivo (ad es. json)

4. Non creare 4 parser; fai 1 parser. Non stai analizzando 4 lingue diverse; stai analizzando 1 lingua con 4 principali componenti grammaticali. Il "problema della dipendenza circolare" può essere gestito abbastanza facilmente con un parser ricorsivo-discendente standard di bog i cui metodi ParseObject e ParseValue possono chiamarsi l'un l'altro.

Primo, non c'è modo di esprimere un parser JSON in un modo che non sia in definitiva "circolare". Possiamo tuttavia, allontanare la circolarità. Per esprimere questo in un modo più semplice, usiamo un linguaggio formale semplice definito come

array = squareArray | angleArray
squareArray = "[" array* "]"
angleArray = "<" array* ">"

e un tipo corrispondente (in pseudo-codice)

type Array = SquareArray List[Array] | AngleArray List[Array]

Quindi definiamo un parser semplice di questo tipo (usando una libreria di parser monadico fittizia).

arrayParser : Parser[Array]
arrayParser = try squareArray 'or' angleArray

squareArrayParser : Parser[Array]
squareArrayParser = 
      from start  in parseText "["
      from arrays in many arrayParser
      from end    in parseText "]"
      select SquareArray arrays

angleArrayParser : Parser[Array] 
angleArrayParser = 
      from start  in parseText "<"
      from arrays in many arrayParser
      from end    in parseText ">"
      select AngleArray arrays

A mio parere, non c'è assolutamente nulla di sbagliato nella definizione di cui sopra. Se siamo morti sulla rimozione della circolarità, possiamo notare che arrayParser , squareArrayParser e angleArrayParser sono tutti definiti in modo ricorsivo. Possiamo calcolare questa natura ricorsiva prima facendo in modo che ognuno prenda l'altro come parametro.

arrayParserF : forall t. Parser[t] -> Parser[t] -> Parser[t]
arrayParserF pSquareArray pAngleArray = try pSquareArray 'or' pAngleArray

squareArrayParserF : forall s, t. (s -> t) -> Parser[s]  -> Parser[t]
squareArrayParserF pSquareArray pArrayParser = 
      from start  in parseText "["
      from arrays in many pArrayParser
      from end    in parseText "]"
      select pSquareArray arrays

angleArrayParserF : forall s, t. (s -> t) -> Parser[s] -> Parser[t]
angleArrayParserF pAngleArray pArrayParser = 
      from start  in parseText "<"
      from arrays in many pArrayParser
      from end    in parseText ">"
      select pAngleArray arrays

Vediamo che possiamo immediatamente recuperare ciò che abbiamo iniziato dicendo

arrayParser' : Parser[Array]
arrayParser' = arrayParserF squareArrayParser' angleArrayParser'
  where
    squareArrayParser' : Parser[Array]
    squareArrayParser' = squareArrayParserF SquareArray arrayParser' 

    angleArrayParser' : Parser[Array]
    angleArrayParser' = angleArrayParserF AngleArray arrayParser'

O in modo equivalente

arrayParser' : Parser[Array]
arrayParser' = (\ pArrayParser -> 
                  arrayParserF 
                    (squareArrayParserF pArrayParser)
                    (angleArrayParserF pArrayParser)) arrayParser'

O in modo equivalente (per divertimento)

arrayParser' : Parser[Array]
arrayParser' = fix makeArrayParser SquareArray AngleArray

makeArrayParser : ([t] -> t) -> ([t] -> t) -> Parser[T] -> Parser[T]
makeArrayParser pSquareArray pAngleArray pArrayParser = 
    arrayParserF 
        (squareArrayParserF pSquareArray pArrayParser)
        (angleArrayParserF  pAngleArray  pArrayParser)

Anche se questo è per lo più accademico, non è del tutto inutile, poiché ora possiamo facilmente definire un parser che analizza un certo nidificazione di parentesi fisse.

fixedArrayParser : Parser [Array]
fixedArrayParser 1 = makeArrayParser SquareArray AngleArray blankParser
fixedArrayParser (n + 1) = makeArrayParser SquareArray AngleArray (fixedArrayParser n)

Possiamo persino diventare più creativi con i nostri combinatori e interpretare il nostro linguaggio come espressioni di somme e prodotti

sumsAndProductParser : Parser [int]
sumsAndProductsParser = fix (makeArrayParser product sum)

Pertanto, il fatto che il nostro parser venga suddiviso in subparatori può aiutarci a raggiungere la flessibilità e l'usabilità, rendendo molto più semplice l'analisi delle restrizioni e delle estensioni della grammatica originale, ma lo fa a un costo di complessità. Se tutto ciò che vuoi fare è analizzare JSON, potrebbe essere troppo.

Molte grammatiche hanno regole di produzione reciprocamente ricorsive, JSON è un ottimo esempio. Non è un marchio di un cattivo design.

Per quanto riguarda l'uso dei framework del parser combinator, se la lingua host consente definizioni reciprocamente ricorsive (ad esempio Haskell), non c'è alcun problema. Nelle lingue che non lo fanno (ad es. Java), un trucco è quello di consentire parser pigramente inizializzati - l'ho usato nel mio framework. Un esempio del suo utilizzo, per una grammatica JSON, è qui .

Il parser inizializzato pigramente è jvalue:

private static final Parser.Ref<Character, Node> jvalue = Parser.ref();

che viene dichiarato all'inizio della grammatica e inizializzato alla fine:

static {
    jvalue.set(
        choice(
            jnull,
            jbool,
            jnumber,
            jtext,
            jarray,
            jobject
        ).label("JSON value")
    );
}

Il tipo Parser.Ref è esso stesso un parser (vale a dire implementa l'interfaccia Parser).

Uno dei principali vantaggi dell'approccio del parser combinator è che fornisce un DSL per la definizione di grammatiche, che è ospitato nel linguaggio di programmazione che stai già utilizzando. Questo ha di per sé dei vantaggi, come rendere le azioni semantiche associate alle regole di produzione della grammatica soggette al controllo del tipo fornito dalla lingua ospite, vale a dire che le tue regole devono essere ben scritte. Un altro vantaggio è la possibilità di estendere il DSL con i propri combinatori.

Le strutture dati ricorsive sono sempre un po 'complicate e avrete bisogno di una sorta di pigrizia o di mutare la struttura dei dati dopo la costruzione iniziale. Di questi due, la mutazione è più semplice e può essere facilmente utilizzata per implementare la pigrizia. Tuttavia, set() esterni portano a una progettazione abbastanza fragile in cui sei costretto a eseguire passaggi manuali facilmente dimenticabili per assicurarti che il tuo oggetto parser sia stato inizializzato correttamente.

Per questo motivo, prenderemo in considerazione un contenitore delle dipendenze che viene interrogato pigramente per essere la soluzione più pulita:

class ObjectParser(parsers) {
    parse(input) { ... parsers.getArrayParser().parse(input) ... }
}

class ArrayParser(parsers) {
    parse(input) { ... parsers.getObjectParser().parse(input) ... }
}

class Parsers {
   // Instead of creating a new object each time,
   // you could use the getter to lazily initialize some field.
   getArrayParser()  { return new ObjectParser(this) }
   getObjectParser() { return new ArrayParser(this) }
}

new Parsers().getObjectParser().parse(input)

Notare che il parser "objects" ObjectParser e ArrayParser hanno un solo metodo pubblico parse() nella progettazione, quindi in realtà sarebbero equivalenti a funzioni o chiusure. Possiamo allineare parsres.getArrayParser().parse(input) a parsers.parseArray(input) :

class Parsers {
  parseArray(input) { ... this.parseObject(input) ... }
  parseObject(input) { ... this.parseArray(input) ... }
}

new Parsers().parseObject(input);

Quindi magicamente, quest'ultimo codice è esattamente equivalente ed ugualmente estensibile, ma usa molto meno codice. Perché? Poiché il sistema di oggetti linguaggio host già introduce l'indiretta richiesta per farlo funzionare: il parametro implicito this (in precedenza l'esplicito parsers ) è già puntatore e la ricerca del metodo deve essere eseguita abbastanza lentamente se si dispone di sottoclassi ( "Legatura tardiva"). Ma non abbiamo nemmeno bisogno di questo per un parser di discesa ricorsivo, se il nostro linguaggio ci permette di pre-dichiarare le funzioni, o non ha nemmeno bisogno di dichiarazioni preliminari. In C, questo funzionerebbe pure:

// predeclarations
ResultT parseArray(InputT input);
ResultT parseObject(InputT input);

// implementation
ResultT parseArray(InputT input) { ... parseObject(input) ... }
ResultT parseObject(InputT input)  { ... parseArray(input) ... }

Da dove viene l'indirezione? Dal compilatore: a causa delle predeclarazioni, è possibile compilare una chiamata a una funzione prima che l'obiettivo della chiamata sia noto. Questo è abbastanza semplice se entrambe le funzioni si trovano nella stessa unità di compilazione, altrimenti è richiesto un linker per "legare il nodo".

Se stai solo scrivendo un parser di discesa ricorsivo (che funziona per JSON ma non funziona bene per linguaggi più complicati che non sono LL (1)), allora usare la cosa più semplice che potrebbe funzionare è la soluzione che dovresti scegliere: nessuna mutabilità, nessun oggetto proxy, non dispacciamento virtuale, solo procedure reciprocamente ricorsive.

Se si desidera utilizzare un generatore di parser che simuli un parser di discesa ricorsivo per te, avrai bisogno di alcuni valori o oggetti da aggirare. Se la tua lingua dovesse supportare la programmazione funzionale o almeno le funzioni di ordine superiore, non cambierà nulla perché puoi semplicemente passare gli handle a quelle funzioni del parser in giro (ad esempio i puntatori di funzione in C, gli oggetti metodo in Java8, ...). Se la tua lingua è OOP più purista (ad es. Java < 8, C ++ < 11), avrai bisogno degli oggetti espliciti ObjectParser , ArrayParser ecc. Come nel primo esempio. Solo allora considererei questo enorme spreco di codice una soluzione fattibile.