An extension of context-free grammars with one-sided context specifications

DOI10.1016/j.ic.2014.03.003zbMath1360.68531OpenAlexW2161789621MaRDI QIDQ2252533

Mikhail Barash, Alexander Okhotin

Publication date: 18 July 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.03.003

zbMATH Keywords

context-free grammarscontext-sensitive grammarscontextsparsingconjunctive grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (13)

Input-driven languages are linear conjunctive ⋮ Generalized LR Parsing for Grammars with Contexts ⋮ Generalized LR parsing algorithm for grammars with one-sided contexts ⋮ The hardest language for grammars with context operators ⋮ The Hardest LL(k) Language ⋮ Linear-space recognition for grammars with contexts ⋮ Context-free grammars with lookahead ⋮ Hardest languages for conjunctive and Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ The Hardest Language for Conjunctive Grammars ⋮ Linear grammars with one-sided contexts and their automaton representation ⋮ Improved normal form for grammars with one-sided contexts ⋮ Two-sided context specifications in formal grammars

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parsing by matrix multiplication generalized to Boolean grammars
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• On the expressive power of univariate equations over sets of natural numbers
• Well-founded semantics for Boolean grammars
• Unambiguous Boolean grammars
• Conjunctive grammars with restricted disjunction
• On multiple context-free grammars
• General context-free recognition in less than cubic time
• LL-regular grammars
• Tree adjunct grammars
• Conjunctive grammars and systems of language equations
• Boolean grammars
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• LR-regular grammars - an extension of LR(k) grammars
• The dual of concatenation
• Recursive descent parsing for Boolean grammars
• LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata
• On certain formal properties of grammars
• BOOLEAN FUZZY SETS
• Parsing expression grammars
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Linear Grammars with One-Sided Contexts and Their Automaton Representation
• GENERALIZED LR PARSING ALGORITHM FOR BOOLEAN GRAMMARS
• A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars
• Two Families of Languages Related to ALGOL

This page was built for publication: An extension of context-free grammars with one-sided context specifications