L'algoritmo dello shunting yard è per un problema di parsing molto specifico: analizzare le espressioni con la precedenza degli operatori. Può essere utilizzato quando tutte le produzioni nella grammatica hanno la forma ricorsiva Expr → Expr op Expr e le produzioni sono classificate in base alla priorità. (Più ovviamente casi di base della forma Expr → terminal e produzioni per operatori unari)
La maggior parte dei linguaggi di programmazione non si adatta a questa semplice struttura. Anche l'assegnazione = non è un operatore ordinario perché la parte sinistra potrebbe non essere un'espressione arbitraria: 42 * 3 = a + 7 è non valido nella maggior parte dei linguaggi di programmazione. In quanto tale, l'operatore di assegnazione non può essere analizzato dall'algoritmo dello shunting yard.
Questa restrizione non ha nulla a che fare con RPN contro alberi di sintassi astratti. L'RPN è esattamente equivalente a un albero, l'albero è solo appiattito.
Sebbene l'algoritmo dello shunting yard non sia abbastanza potente per analizzare i linguaggi di programmazione "reali", è un buon trampolino di lancio per comprendere algoritmi di analisi bottom-up più complessi come LR. Quindi, poiché dovremo utilizzare comunque un algoritmo più potente, l'algoritmo dello shunting yard non viene utilizzato nella pratica.
Molte implementazioni del linguaggio di programmazione reale utilizzano un generatore di parser (talvolta chiamato anche compiler-compilatore). Con un generatore di parser annoti le regole della tua grammatica in una sorta di notazione EBNF e lo strumento genera un programma che analizzerà questa grammatica. Questo è abbastanza gestibile e può utilizzare buoni algoritmi di parsing.
In alternativa, puoi scrivere un compilatore a mano. Questo è in realtà abbastanza comune perché questo può potenzialmente produrre messaggi di errore molto migliori o gestire le ambiguità che un generatore di parser non può indirizzare. È anche molto più difficile avere ragione.
La maggior parte dei parser scritti a mano usano una strategia di discesa ricorsiva , che è fondamentalmente la tua idea di sub-parser: implementiamo ogni regola nella nostra grammatica come una funzione. La funzione accetta lo stato del parser come input e restituisce un frammento di albero della sintassi. Ad esempio una regola Assignment → Variable "=" Expr ";" potrebbe essere implementata in questo modo:
class Parser {
... // keep parser state as instance fields
Assignment parseAssignment() {
Variable variable = parseVariable();
consumeLiteral("=");
Expression expr = parseExpr();
consumeLiteral(";");
return new Assignment(variable, expr);
}
}
Il problema con i parser ricorsivi-discendenti è che hanno difficoltà a gestire produzioni left-ricorsive (cioè il simbolo della mano sinistra di una produzione è il primo simbolo sul lato destro, come X → X ... ). Ma queste regole sono comuni nelle espressioni matematiche!
Una possibilità legittima è quella di utilizzare l'algoritmo dello shunting-yard per questo, perché si occupa in modo specifico di questi casi. In alternativa, questo può anche essere risolto eliminando esplicitamente la ricorsione. Per esempio. le regole Term -> Term "*" Factor; Term -> Factor potrebbero essere ingenuamente implementate come
Expression parseTerm() {
Expression left = parseTerm(); // FIXME infinite recursion
if (!peekLiteral("*")) return left;
consumeLiteral("*");
Expression right = parseFactor();
return new Multiplication(left, right);
}
Al contrario, la regola può essere implementata correttamente senza ricorsione ma con un ciclo:
Expression parseTerm() {
Expression expr = parseFactor();
while (peekLiteral("*")) {
consumeLiteral("*");
Expression right = parseFactor();
expr = new Multiplication(expr, right);
}
return expr;
}