✦ LIBER ✦

Chart parsing of scattered context grammars

✍ Scribed by F. Popowich

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 544 KB
Volume: 7
Category: Article
ISSN: 0893-9659
DOI: 10.1016/0893-9659(94)90049-3

No coin nor oath required. For personal study only.

✦ Synopsis

scattered context grammars are a class of context-sensitive grammars. The rules of these grammars can be viewed ss sequences of traditional context-free grammar rules. We show how a chart-parsing algorithm for context-free grammars can be extended to scattered context grammars.

1. SCATTERED CONTEXT GRAMMARS

Although context-free grammars (CFGs) have frequently been used in natural language processing research, this family of grammars is not powerful enough to describe some linguistic phenomena [l]. Scattered Context Grammars (SCGs) are more powerful than CFGs, being a subset of context-sensitive grammars [2]. Chart parsing, which is based on Earley's algorithm [3], is often used for efficient processing of CFGs. Here, we will show how the techniques used in chart parsing CFGs can be applied to SCGs.

📜 SIMILAR VOLUMES

Scattered context grammars

✍ Sheila Greibach; John Hopcroft 📂 Article 📅 1969 🏛 Elsevier Science 🌐 English ⚖ 676 KB

Unilateral context sensitive grammars an

Unilateral context sensitive grammars and left-to-right parsing

✍ György Révész 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 682 KB

Classes of languages between context-free and context-sensitive ones may be of theoretical interest. From the practical point of view they might be useful also for the parsing of context-free languages. For example, a left-to-right parser for an LR(k) context-free grammar [1] has to look k symbols a

Scattered context grammars that erase no

Scattered context grammars that erase nonterminals in a generalizedk-limited way

✍ Alexander Meduna; Jiří Techet 📂 Article 📅 2008 🏛 Springer-Verlag 🌐 English ⚖ 192 KB

A simultaneous reduction of several meas

A simultaneous reduction of several measures of descriptional complexity in scattered context grammars

✍ H. Fernau; A. Meduna 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 92 KB

In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with a reduced number of both nonterminals and context-sensing productions.

Parsing as abstract interpretation of gr

Parsing as abstract interpretation of grammar semantics

✍ Patrick Cousot; Radhia Cousot 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 153 KB

Earley's parsing algorithm is shown to be an abstract interpretation of a reÿnement of the derivation semantics of context-free grammars.

Parsing of edNLC-graph grammars for scen

Parsing of edNLC-graph grammars for scene analysis

✍ Mariusz Flasiński 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 496 KB