Integrazione delle funzioni in un'implementazione dell'algoritmo di Shunting-Yard

Question

Integrazione delle funzioni in un'implementazione dell'algoritmo di Shunting-Yard

#1 da (1 voti)
#2 da (1 voti)

2

tl; dr Quale sarebbe un modo semplice per incorporare le funzioni in un'implementazione dell'algoritmo di Shunting-Yard?

Se fossero consentite solo espressioni come function(arg1, arg2, arg3) (dove function è una funzione incorporata), sarebbe davvero facile, dato che potrei semplicemente trattare function come un operatore. Ma considera un caso in cui l'utente definisce la propria funzione come f = function , quindi chiama f(arg1, arg2, arg3) . In questo caso avrei bisogno di un AST strongmente tipizzato per rilevare al momento della compilazione quale tipo di f è per vedere che i token procedenti ( (arg1, arg2, arg3) ) sono in realtà una chiamata di funzione, e non solo una costruzione di un tuple.

Peggio ancora, considera (f)() dove f è una funzione nulla definita dall'utente. Quindi quando arrivo a f , anche se so che è una funzione, il token successivo sarà ) , che non è l'inizio di una chiamata di funzione valida. Che dire di (l[i])() , dove l è una lista di funzioni?

Al livello più generale, capisco grammaticalmente che quando abbiamo un'istruzione come [expression], "(", [expression], ")" , allora sappiamo che stiamo chiamando una funzione. Tuttavia, non sono abbastanza sicuro di come controllare questo senza l'implementazione di un AST (che, per semplicità, preferirei non farlo).

Potrei memorizzare un elenco di tutti i token operatore e "parentesi", e poi quando raggiungo il "(" in una supposta chiamata di funzione, controllo solo se l'ultimo token non-bracket fosse un operatore. quindi "(" rappresenta una sottoespressione, come in 5 * (3 - 8) . Se non era un operatore, quindi "(" rappresenta una chiamata di funzione, tuttavia questo metodo si sente facilmente infranto. Per esempio, cosa succede se là dove qualche operatore $ che era "unary left-associative", quindi (expression $)(args) era valido? Quindi l'algoritmo non avrebbe funzionato, a meno che non avessi un controllo speciale per $ . Cosa accadrebbe se ci fosse un commento tra la funzione e la chiamata di funzione, come function \* comment *\ (args) ? O ancora peggio, qualcosa come

function \ lol the last token in this comment is an operator +
    (args)

Ciò richiederebbe agli addetti all'implementazione molti casi speciali e mi chiedo se c'è un modo migliore per farlo.

programming-languages grammar algorithms parsing shunting-yard

posta user3002473 27.07.2015 - 07:06

fonte

2 risposte

Leggi altre domande sui tag programming-languages grammar algorithms parsing shunting-yard

Come gestisco le chiamate di terze parti a esecuzione prolungata dal backup della coda dei messaggi? Come approccio al codice legacy? Caso disperato [duplicato]

score 1 · Answer 1

È una parentesi aperta che segue direttamente dopo un identificatore. Quindi, quando incontri una parentesi aperta, controlli se l'ultimo token che hai analizzato fosse un identificatore o un operatore. Se si trattava di un operatore, allora è solo una sottoespressione, se non è parte di una chiamata di funzione.

I commenti dovrebbero essere trattati prima di analizzare il flusso di token.

Questo trasforma l'ultimo bit di codice in identifier comment openBracket identifier closeBracket dove puoi ignorare il token comment quando costruisci l'AST o esegui lo scalo di smistamento.

score 1 · Answer 2

Uso un modello a due stati, due stack simile all'algoritmo Shunting Yard. I due stati sono lo stato unario e lo stato binario. In ogni stato, si gestiscono token (o errori di rilascio) e quindi si continua lo stesso stato o si passa all'altro stato.

Nello stato unario, se trovi un paren aperto, ( , si tratta di un raggruppamento di operatori, e tu rimani nello stato unario. (Nello stato unario, un identificatore è un riferimento di variabile lo si preme sulla pila di operandi e passa allo stato binario, un meno, - , è una negazione unaria e si rimane nello stato unario.)

Nello stato binario, se si trova un paren aperto, si tratta di una funzione invocata (e si passa allo stato unario). La differenziazione tra i due stati ti aiuta anche a gestire gli operatori unari e pre / post-fix. (Qui un meno, - , è una sottrazione binaria e si passa allo stato unario.)

ok, per l'espressione (*p[i++])() , p è un puntatore al puntatore alla funzione, giusto? Così,

(Si noti che l'espressione elenco dei parametri vuoto deve essere consentita solo quando le chiamate alle funzioni sono effettivamente presenti, ci sono vari modi e luoghi per rilevare i vari possibili errori.)

I token effettivi gestiti allo stato unario e in stato binario sono determinati dalla lingua che stai cercando di analizzare. Consento sezioni di codice separate per lo stato unario e lo stato binario. Non sembra esserci alcun punto nel mixarli e quindi non è necessario neanche una variabile di stato (la sezione di codice sa solo quale sia).