Linear-space recognition for grammars with contexts

Autor: Mikhail Barash, Alexander Okhotin
Rok vydání: 2018
Předmět:
General Computer Science
Computer science
media_common.quotation_subject
Context-sensitive grammar
0102 computer and information sciences
02 engineering and technology
computer.software_genre
01 natural sciences
Theoretical Computer Science
Indexed language
Rule-based machine translation
0202 electrical engineering
electronic engineering
information engineering
Indexed grammar
Immediate constituent analysis
Phrase structure grammar
c-command
media_common
Parsing
Grammar
business.industry
Programming language
Deterministic context-free grammar
Parsing expression grammar
Context-free grammar
Embedded pushdown automaton
Syntax
Substring
Tree-adjoining grammar
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Ambiguous grammar
Extended Affix Grammar
010201 computation theory & mathematics
Stochastic context-free grammar
020201 artificial intelligence & image processing
S-attributed grammar
Artificial intelligence
Definite clause grammar
L-attributed grammar
business
computer
Natural language processing
Zdroj: Theoretical Computer Science. 719:73-85
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2017.11.006
Popis: Grammars with contexts are an extension of context-free grammars equipped with operators for referring to the left and the right contexts of a substring being defined. These grammars are notable for still having a cubic-time parsing algorithm, as well as for being able to describe some useful syntactic constructs, such as declaration before use. It is proved in this paper that every language described by a grammar with contexts can be recognized in deterministic linear space.
Databáze: OpenAIRE
Externí odkaz: