Formal Grammars & Language Hierarchies

← Back to Domain-Specific Families

Abstractions about formal grammars, language classes, normal forms, reachability, ordering, and syntax-oriented computational representations.

16 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Abstract semantic graph — A graph representation of a formal expression or program whose nodes denote terms or semantic entities and whose shared nodes can represent common subexpressions beyond an abstract syntax tree.
• Chomsky hierarchy — A containment hierarchy of unrestricted, context-sensitive, context-free and regular grammars and their language classes, paired with progressively restricted computational recognizers.
• Context-free language reachability — The graph problem of deciding whether a path’s concatenated edge labels belongs to a given context-free language.
• Context-sensitive grammar — A formal grammar whose productions rewrite a nonterminal only within declared surrounding context without decreasing string length.
• Deterministic context-free grammar — A context-free grammar generating a language recognizable by a deterministic pushdown automaton.
• DRAKON — A flowchart-like visual algorithm notation designed around standardized control-flow icons, structured silhouettes, and readability rules.
• ECLR-attributed grammar — An LR-attributed grammar class that groups inherited attributes into equivalence classes so a one-pass compiler generator can reuse evaluation structure and reduce attribute-handling overhead.
• Generalized context-free grammar — A grammar formalism extending context-free rewriting with composition functions capable of combining discontinuous or otherwise non-context-free structures.
• Kuroda normal form — A restricted production-rule form for noncontracting grammars that characterizes context-sensitive languages apart from the empty-string convention.
• L-system — A parallel formal rewriting system that repeatedly replaces every symbol according to production rules, often interpreting resulting strings as branching geometry.
• Matrix grammar — A controlled formal grammar whose productions must be applied in prescribed finite sequences called matrices rather than as independent rules.
• S-attributed grammar — An attribute grammar using only synthesized attributes, so each parse-tree node's attributes depend solely on its children and can be evaluated naturally during bottom-up parsing.
• Separating words problem — The automata problem of finding the smallest deterministic finite automaton that accepts one of two given words and rejects the other.
• Shortlex order — A total order on finite sequences that compares length first and lexicographic position second.
• Star height problem — The formal-language problem of determining the minimum nesting depth of Kleene stars needed to express a regular language and how that depth can be decided.
• Stropping (syntax) — A programming-language notation technique marking character sequences so keywords or special identifiers occupy a namespace distinct from ordinary names.