Deterministic Parsing

The deterministic behavior is desired and expected in Compiling Programming Language s. In natural language processing, it was thought for a long time that deterministic parsing is impossible due to ambiguity inherent in natural languages (many sentences have more than one plausible parse). Thus, non-deterministic approaches such as the Chart Parser had to be applied. However, Masaru Tomita proposed in 1984 the MLR Parser that was able to deal with ambiguities while still keeping the deterministic behavior.

REFERENCES

Alfred V. Aho , Stephen C. Johnson , Jeffrey D. Ullman ( 1975 ): ''Deterministic parsing of ambiguous grammars.'' Comm. ACM 18:8:441-452.

Masaru Tomita ( 1984 ): LR Parsers for Natural Languages. In: ''Proceedings of the COLING-84'', pp. 354–357, Stanford University, Stanford, California.

Information About

Deterministic Parsing