Electronic Resource
Oxford, UK
:
Blackwell Publishing Ltd
Computational intelligence
10 (1994), S. 0
ISSN:
1467-8640
Source:
Blackwell Publishing Journal Backfiles 1879-2005
Topics:
Computer Science
Notes:
Coupled-context-free grammars are a natural generalization of context-free grammars obtained by combining nonterminals to corresponding parentheses which can only be substituted simultaneously. Refering to the generative capacity of the grammars we obtain an infinite hierarchy of languages that comprises the context-free languages as the first and all the languages generated by TAGs as the second element. Here, we present a generalization of the context-free LL(k)-notion onto coupled-context-free grammars, which leads to a characterization of subclasses of coupled-context-free grammars–and in this way of TAGs as well–which can be parsed in linear time. The parsing procedure described works incrementally so that it can be used for on-line parsing of natural language. Examples show that important elements of the tree-adjoining languages can be generated by LL(k)-coupled-context-free grammars.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1111/j.1467-8640.1994.tb00017.x
Permalink
|
Location |
Call Number |
Expected |
Availability |