Paper: An Extension Of Earley's Algorithm For S-Attributed Grammars

ACL ID E91-1052
Title An Extension Of Earley's Algorithm For S-Attributed Grammars
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1991
Authors

Attribute grammars are an elegant formalization of the augmented context-free grammars characteristic of most current natural language systems. This paper presents an extension of Earley's algorithm to Knuth's attribute grammars, considering the case of S-attributed grammars. For this case, we study the conditions on the underlying base grammar under which the extended algorithm may be guaranteed to terminate. Finite partitioning of attribute domains is proposed to guarantee the termination of the algorithm, without the need for any restrictions on the context-free base.