Estimating the execution complexity of logical specifications based on context-free grammars

Autor: V. N. Glushkova
Rok vydání: 1996
Předmět:
Zdroj: Cybernetics and Systems Analysis. 32:505-510
ISSN: 1573-8337
1060-0396
DOI: 10.1007/bf02366772
Popis: Further research should strive to strengthen the expressiveness of the class of Δ0T-formulas, because they express only the relation of hierarchical subordination and do not reflect the relation of “being to the left” for tree nodes. The introduction of the corresponding relation in formula prefixes should not involve considerable difficulties for estimation of execution time, but will make it possible to express arbitrary context restrictions for programming languages. Δ0T-formulas with an extended prefix generalize the rules of attribute CF-grammars, because they trivially pass into the corresponding formulas. It is well know that attribute grammars are not an adequate apparatus for the description of context interrelationships of language constructs, because the graph structure of context dependencies is “poorly” representable in syntactic linear form [14]. The search for alternative approaches to the specification of complex dependencies of language constructs remains a topical problem, which is relevant not only for context analysis of programming languages, but also for many other problems, in particular, program optimization, database processing, etc. The absence of a rigid linkage to concrete grammatical rules is an advantage of the proposed logical specification, because in this case we avoid excessive transfer of information due to the possibility of specifying significant “tree” relationship. However, this expressive freedom leads to difficulties with the selection of the class of computable formulas, definition of its model-theoretical semantics, error diagnostics, and other tasks.
Databáze: OpenAIRE
Externí odkaz: