Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Parsing based on n-path tree - controlled grammars

Čermák M., Koutný J., Meduna A.

Theoretical and Applied Informatics

2011

Vol. 23, No. 3-4

213-228

This paper discusses recently introduced kind of linguistically motivated restriction placed on tree-controlled grammars-context-free grammars with some root-to-leaf paths in their derivation trees restricted by a control language. We deal with restrictions placed on n greater-than or equal to 1 paths controlled by a deterministic context-free language, and we recall several basic properties of such a rewriting system. Then, we study the possibilities of corresponding parsing methods working in polynomial time and demonstrate that some non-context-free languages can be generated by this regulated rewriting model. Furthermore, we illustrate the syntax analysis of LL grammars with controlled paths. Finally, we briefly discuss how to base parsing methods on bottom-up syntax-analysis.

Some power - decreasing derivation restrictions in grammar systems

Meduna A., Čermák M., Masopust T.

Schedae Informaticae

2010

Vol. 19

23-34

In this paper, we place some left restrictions on derivations in CD grammar systems with phrase-structure grammars, controlled by the regular languages. The first restriction requires that every production is always applied within the first k nonterminals in every sentential form, for some k greather than 1. The second restriction says how many blocks of non-terminals can be in each sentential form. The third restriction extends the second restriction and says how many blocks of non-terminals with limited length can be in each sentential form. We demonstrate that under these restrictions, the grammar systems generate different families of languages. Irideed, under the first restriction, these systems generate only context-free languages. Under the second restriction, even one-component systems characterize the entire family of recursively enu-merable languages. In the end, the family of languages generated by grammar systems under the third restriction is equal to the family of languages generated by programmed grammars with context-free rules without e-rules of finite index.