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:
“In his comprehensive delight in all experience Dickens resembles Walt Whitman, but he was innocent of that nebulous transcendentalism that blurred Whitmans universe into vast misty panoramas and left him, for all his huge democratic vistas, unable to tell a story or paint a single concrete human being.”
—Edgar Johnson (19121990)