I think that rici's answer is a good summary of the situation. As he
remarks, there is probably not too much to expect from from parallel
computing in the case of grammars that lend themselves reasonnably
well to deterministic parsing.
I am not sure whether the answer is the same when deterministic
parsing requires heavy changes in the grammar structure, even assuming
these changes are reversible, so that whatever parse tree is produced
with the transformed grammar can be transformed back into a parse tree
for the original grammar.
The Johnson paper, which I skimmed, seems to contain interesting
considerations and experimental results. However, you should keep in mind that parsing is not a
single problem. It does have many variants, depending on whether your
language is deterministic, or just unambiguous, or possibly ambiguous
but you want only some parses based on diverse criteria, or whether you want
all parses, possibly to select from them on the basis of further
processing. Non deterministic or ambiguous parsing is usually based on dynamc
programming techniques, the best known of which are CYK and Earley's
algorithm. But there are other views of it (see below).
Apparently, the Johnson's paper focusses on one of these categories:
very ambiguous probabilistic grammars with Viterbi selection of the
best parse, integrated in the algorithm.
If you were interested in getting the whole parse forest, representing
all possible parses, there is a possibility that the results might be
On the other hand, both problems rely on a vision of the parsing
process as computing an answer in a semiring algebra, so that the
difference is not so much in the logic of the computation as it is in
the data structures computed with. But parse forest are heavier
structures to manipulate than are single trees with probabilities.
I have no idea how much this would impact a complexity analysis.
Another point is that the semiring structure is an abstraction, but
the same parse forest (seen semantically as a set of parse trees) may
have many syntactic representations, some more condensed, or better
organized, than others. Parallelization on multiple processors is very
likely to have an impact on the syntactic representation of the
sharing structures of the parse forest, which could impact further
processing, unless it is also integrated adequately in the
It might be worth analyzing the problem abstractedly as a semiring
evaluation procedure. There is some literature on that, and one place
to start from might be Joshua Goodman's "Parsing inside out", though
he does not address parallelization (afaik).
Another way to look at your question is parsing as intersection,
i.e. to see parsing as the construction of the CF grammar $L_A$ for
the intersection of the languages of another CF grammar $L$ and a NFA
$A$. The main difference is that parsing corresponds to the case where
the graph of the DFA is mostly acyclic (some cycles may be considered
for special purposes such as handling of errors or ill-formedness).
Possibly that view of the problem could lead to some insight.
Coming back to your question of whether alternative rules for a
terminal could lead to parallelization. I would try tp look
at it from the point of view of intersection with NFA.