Comprensione dello schema degli interpreti

3

Sto cercando di capire in che modo è possibile implementare il modello dell'interprete.

Comedadiagramma;un'espressioneha2nodi:terminaleeamp;nonterminale.Puòaverepiùtipidinodi?Perchécredochesiadisegnatoconsiderandol'espressionematematicatrasformatainalberobinarioDSincuiinodifogliasononumerieinodinonfogliasonooperazioni:+,-,/etc.

Daqualcheparteholettoche java.util.Pattern è un esempio di modello interprete.

Pattern pattern = Pattern.compile("^[abc](ab|c?d)?ef$");
Matcher matcher = pattern.matcher("some RE");
if(matcher.matches()){ .. }

Quindi stavo cercando di mettere in relazione se la mia implementazione del motore RE: BooleanSequence è anche un esempio di pattern dell'interprete.

BooleanSequence seq = new BooleanSequence("[abc](ab|c?d)?ef");
seq.compile();seq.minimize();
Matcher matcher = seq.getCoreMatcher();
matcher.match("some RE");

Nota di implementazione:

La classe principale BooleanSequence (BS) accetta RE (può essere considerato come contesto ) e crea una sorta di DS in memoria, in cui ogni char di RE è un nodo. Esistono molti tipi di nodi, come: normale, intervallo, pigro, ecc. Credo che possa essere considerato come espressione come indicato nel diagramma.

La classe Node ha anche match (). BS dà un matcher o può essere creato separatamente. È completamente isolato dalla classe BS. E ci sono molti tipi di giocatori (attualmente 3). Le chiamate matcher corrispondono a () di tutti i nodi fino a quando viene valutata l'intera espressione.

    
posta Amit Kumar Gupta 13.10.2016 - 21:05
fonte

2 risposte

2

Questo diagramma di classe indica che un AbstractExpression è o un TerminalExpression o un %codice%. Se è un NonTerminalExpression , è esso stesso un'aggregazione di uno o più NonTerminalExpression .

In realtà questa struttura è un albero. Tipicamente i terminali sarebbero ulteriormente derivati in vialebles e litterals, ei terminali non sarebbero ulteriormente derivati per gli operatori unari e binari, ma potrebbero essere ancora di più.

Un esempio di istanziazione potrebbe essere:

Nell'esempio AbstractExpression :

  • il codice chiamante è il client, che per prima cosa costruisce l'albero della sintassi astratta durante la compilazione di un modello regex (cioè costruendo una rappresentazione interna del modello regex).
  • il java.util.Pattern è l'interprete. In linea di principio corrisponderebbe al livello superiore Pattern . L'unica particolarità è che la struttura dell'espressione è incapsulata nell'interprete e non accessibile.
  • il AbstractExpression è l'equivalente di una chiamata a Pattern.matcher() , la stringa da analizzare è il contesto.
  • l'oggetto interpret() è il risultato dell'interpretazione con una particolare stringa.
risposta data 13.10.2016 - 22:37
fonte
2

Can it have multiple type of nodes as well?

Questo diagramma che stai mostrando è un diagramma di classe, quindi per definizione, più o meno, puoi continuare a sottoclasse. Ad esempio potresti sottoclasse NonTerminalExpression con BinaryExpression .

Se prendiamo il diagramma in modo suggestivo invece che letteralmente, potresti avere BinaryExpression direttamente sottoclasse da AbstractExpression , poiché sai che avrai esattamente un left e un right invece di una raccolta di dimensioni arbitrarie di bambini. Lo puoi vedere nell'articolo Modello di interpreti di Wikipedia , hanno fatto questo per la versione di Java.

Non vedo java.util.Pattern che mostri quel modello specifico di interprete, esternamente, almeno , perché coinvolge sempre un solo oggetto, un matcher , piuttosto che il numero arbitrario di oggetti che Mi aspetterei di essere coinvolto nel modello dell'interprete per ogni dato testo di lunghezza arbitraria. Al contrario, il pattern dell'interprete produrrebbe un albero di oggetti per una determinata espressione e non c'è nulla nell'API che suggerisca necessariamente che un albero di questo tipo sia presente.

java.util.Pattern può benissimo fare qualcosa del genere internamente, tuttavia, non è visibile (per me senza ulteriori indagini) perché sta fornendo un comportamento incapsulato. Quindi, l'API non sta dimostrando il modello dell'interprete. Tuttavia, un meccanismo di corrispondenza delle espressioni regolari che segue quell'API potrebbe essere implementato in diversi modi utilizzando o meno un modello di interprete.

Direi che sia java.util.Pattern che BooleanSequence seguono un modello linguistico in cui il primo passo crea un parser per una lingua, che viene definita specificando una grammatica in un'altra lingua, ed entrambi hanno un passo aggiuntivo di applicare un parser a un testo specifico.

Vedi anche Abstract Syntax Tree . Se dovessimo applicare i comportamenti (metodi) alla gerarchia di classi dell'albero della sintassi astratta potremmo arrivare al modello dell'interprete e potremmo anche arrivare a un compilatore (modello).

    
risposta data 13.10.2016 - 22:06
fonte

Leggi altre domande sui tag