The shunting yard algorithm is for a very specific parsing problem: parsing expressions with operator precedence. It can be used when all the productions in the grammar have the recursive form Expr → Expr op Expr, and the productions are ranked by priority. (Plus of course base cases of the form Expr → terminal, and productions for unary operators)
Most programming languages do not fit this simply structure. Even assignment = is not an ordinary operator because the left hand side may not be an arbitrary expression: 42 * 3 = a + 7 is invalid in most programming languages. As such, the assignment operator cannot be parsed by the shunting yard algorithm.
This restriction has nothing to do with RPN versus abstract syntax trees. RPN is exactly equivalent to a tree, the tree is just flattened out.
While the shunting yard algorithm is not powerful enough to parse “real” programming languages, it is a good stepping stone in order to understand more complex bottom-up parsing algorithms like LR. So because we will have to use a more powerful algorithm anyway, the shunting yard algorithm is not used in practice.
Many real programming language implementations use a parser generator (sometimes also called compiler-compiler). With a parser generator you write down the rules of your grammar in some kind of EBNF notation, and the tool generates a program that will parse this grammar. This is fairly maintainable and can use good parsing algorithms.
Alternatively, you can write a compiler by hand. This is actually quite common because this can potentially produce much better error messages or deal with ambiguities that a parser generator can't address. It is also much more difficult to get right.
Most hand-written parsers use a recursive descent strategy, which is basically your idea of sub-parsers: We implement each rule in our grammar as a function. The function takes parser state as input and returns a syntax tree fragment. For example a rule Assignment → Variable "=" Expr ";" might be implemented like this:
class Parser {
... // keep parser state as instance fields
Assignment parseAssignment() {
Variable variable = parseVariable();
consumeLiteral("=");
Expression expr = parseExpr();
consumeLiteral(";");
return new Assignment(variable, expr);
}
}
The problem with recursive-descent parsers is that they have difficulty dealing with left-recursive productions (i.e. the left hand symbol of a production is the first symbol on the right hand side, like X → X ...). But these rules are common in mathematical expressions!
One legitimate possibility is using the shunting-yard algorithm for that, because it deals well specifically with those cases. Alternatively, this can be also solved by explicitly eliminating recursion. E.g. the rules Term -> Term "*" Factor; Term -> Factor might naively be implemented as
Expression parseTerm() {
Expression left = parseTerm(); // FIXME infinite recursion
if (!peekLiteral("*")) return left;
consumeLiteral("*");
Expression right = parseFactor();
return new Multiplication(left, right);
}
Instead, the rule can be properly implemented without recursion but with a loop:
Expression parseTerm() {
Expression expr = parseFactor();
while (peekLiteral("*")) {
consumeLiteral("*");
Expression right = parseFactor();
expr = new Multiplication(expr, right);
}
return expr;
}
