Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: ε-production

Sortuj według:

Ogranicz wyniki do:

Nullifying rules influence on speed in context free grammar LL(1)

Pavlov V.

Journal of Theoretical and Applied Computer Science

2016

Vol. 10, nr 2

3--15

This research is an investigation of nullifying rules influence on speed of parsing grammar type LL(1). As a prototype, it’s considered a free context language based on LL(1) grammar, containing no nullifying rules (ε-rules). It is shown that recognizer which is based on deterministic push-down automaton (DPDA), in this case parses terms of the language in a minimum number of steps equal to length of the analyzed chain of tokens. It was demonstrated that for terms of another context-free language, which is also described by grammar LL(1) but containing nullifying rules, parsing by push-down automaton needs more cycles. It was shown, a cause of this is presence of nullifying (canceling) rules in LL(1) grammar. After transformations of the original grammar for exclusion these rules from the grammar, parsing speed increased almost to level of the prototype. This fact was confirmed by number of reviewed examples.