GLR Parser - Advantages

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:

    “When the manipulations of childhood are a little larceny, they may grow and change with the child into qualities useful and admire in the grown-up world. When they are the futile struggle for love and concern and protection, they may become the warped and ruthless machinations of adults who seek in the advantages of power what they could never win as children.”
    —Leontine Young (20th century)

    “No advantages in this world are pure and unmixed.”
    —David Hume (1711–1776)

    “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)