Conference paper

 
Meduna, A., Vrábel, L., Zemek, P.: LL Leftmost k-Linear Scattered Context Grammars, In: AIP Conference Proceedings, Kassandra, Halkidiki, GR, AIP, 2011, p. 833-836, ISBN 978-0-7354-0956-9, ISSN 1551-7616
Publication language:english
Original title:LL Leftmost k-Linear Scattered Context Grammars
Title (cs):LL nejlevější k-lineární gramatiky s rozptýleným kontextem
Pages:833-836
Proceedings:AIP Conference Proceedings
Conference:9th International Conference of Numerical Analysis and Applied Mathematics
Place:Kassandra, Halkidiki, GR
Year:2011
URL:http://proceedings.aip.org/resource/2/apcpcs/1389/1/833_1?isAuthorized=no
ISBN:978-0-7354-0956-9
Journal:AIP Conference Proceedings, Vol. 1389, No. 1, US
ISSN:1551-7616
Publisher:American Institute of Physics
Keywords
Formal languages, scattered context grammars, generative power, parsing, deep pushdown automata
Annotation
The present paper introduces a new variant of a scattered context grammar, called an LL leftmost k-linear scattered context grammar. It is an ordinary scattered context grammar without erasing rules, where (1) every scattered context rule is composed of k-linear rules, (2) if we take the first components of every rule, the resulting context-free grammar is an LL grammar, and (3) every rule is applied in a leftmost way. We study the generative power of this variant and its parsing properties, including time and space complexity. In the conclusion, several remarks regarding the achieved results are made.
BibTeX:
@INPROCEEDINGS{
   author = {Alexander Meduna and Lukáš Vrábel and Petr Zemek},
   title = {LL Leftmost k-Linear Scattered Context Grammars},
   pages = {833--836},
   booktitle = {AIP Conference Proceedings},
   journal = {AIP Conference Proceedings},
   volume = {1389},
   number = {1},
   year = {2011},
   location = {Kassandra, Halkidiki, GR},
   publisher = {American Institute of Physics},
   ISBN = {978-0-7354-0956-9},
   ISSN = {1551-7616},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9586}
}