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:
“One must apply ones reason to everything here, learning to obey, to shut up, to help, to be good, to give in, and I dont know what else. Im afraid I shall use up all my brains too quickly, and I havent got so very many. Then I shall not have any left for when the war is over.”
—Anne Frank (19291945)