Accommodating Left Recursion in Top-down Parsing
A formal grammar that contains left recursion cannot be parsed by a LL(k)-parser or other naive recursive descent parser unless it is converted to a weakly equivalent right-recursive form. In contrast, left recursion is preferred for LALR parsers because it results in lower stack usage than right recursion. However, more sophisticated top-down parsers can implement general context-free grammars by use of curtailment. In 2006, Frost and Hafiz describe an algorithm which accommodates ambiguous grammars with direct left-recursive production rules. That algorithm was extended to a complete parsing algorithm to accommodate indirect as well as direct left-recursion in polynomial time, and to generate compact polynomial-size representations of the potentially exponential number of parse trees for highly ambiguous grammars by Frost, Hafiz and Callaghan in 2007. The authors then implemented the algorithm as a set of parser combinators written in the Haskell programming language.
Read more about this topic: Left Recursion
Famous quotes containing the word left:
“At the milliners, the ladies we met were so much dressed, that I should rather have imagined they were making visits than purchases. But what diverted me most was, that we were more frequently served by men than by women; and such men! so finical, so affected! they seemed to understand every part of a woman’s dress better than we do ourselves; and they recommended caps and ribbons with an air of so much importance, that I wished to ask them how long they had left off wearing them.”
—Frances Burney (1752–1840)