Advantages
Recognition using the GLR algorithm has the same worst-case time complexity as the CYK algorithm and Earley algorithm: O(n3). However, GLR carries two additional advantages:
- The time required to run the algorithm is proportional to the degree of nondeterminism in the grammar: on deterministic grammars the GLR algorithm runs in O(n) time (this is not true of the Earley and CYK algorithms, but the original Earley algorithms can be modified to ensure it)
- The GLR algorithm is "on-line" – that is, it consumes the input tokens in a specific order and performs as much work as possible after consuming each token.
In practice, the grammars of most programming languages are deterministic or "nearly deterministic", meaning that any nondeterminism is usually resolved within a small (though possibly unbounded) number of tokens. Compared to other algorithms capable of handling the full class of context-free grammars (such as Earley or CYK), the GLR algorithm gives better performance on these "nearly deterministic" grammars, because only a single stack will be active during the majority of the parsing process.
GLR can be combined with the LALR(1) algorithm, in a hybrid parser, allowing still higher performance.
Read more about this topic: GLR Parser
Famous quotes containing the word advantages:
“In 1845 he built himself a small framed house on the shores of Walden Pond, and lived there two years alone, a life of labor and study. This action was quite native and fit for him. No one who knew him would tax him with affectation. He was more unlike his neighbors in his thought than in his action. As soon as he had exhausted himself that advantages of his solitude, he abandoned it.”
—Ralph Waldo Emerson (1803–1882)
“To say that a man is your Friend, means commonly no more than this, that he is not your enemy. Most contemplate only what would be the accidental and trifling advantages of Friendship, as that the Friend can assist in time of need by his substance, or his influence, or his counsel.... Even the utmost goodwill and harmony and practical kindness are not sufficient for Friendship, for Friends do not live in harmony merely, as some say, but in melody.”
—Henry David Thoreau (1817–1862)
“For, the advantages which fashion values, are plants which thrive in very confined localities, in a few streets, namely. Out of this precinct, they go for nothing; are of no use in the farm, in the forest, in the market, in war, in the nuptial society, in the literary or scientific circle, at sea, in friendship, in the heaven of thought or virtue.”
—Ralph Waldo Emerson (1803–1882)