<p>The <a href="https://en.wikipedia.org/wiki/Earley_parser" rel="nofollow noreferrer">Earley Parser</a> is able to parse all context-free languages. Are there parsers that can parse say languages in context-sensitive grammars? I realize ambiguous grammars are non-deterministic and might make this question not well formed and would be ready accept an answer that explains why it is not well formed if so.</p>

CC BY-SA 4.0
2022-09-03T19:34:17.807Z
https://en.wikipedia.org/wiki/Context-sensitive_grammar#Equivalence_to_linear_bounded_automaton
D.W.
CC BY-SA 4.0
2022-09-04T06:38:40.247Z
@D.W. I've already read that part of the page. So It's still an open problem to create parsers for more expressive grammars? AFAIK a LBA is not a parsing algorithm, it's a hypothetical machine that can accept or reject a set of strings.
Vivek Joshy
CC BY-SA 4.0
2022-09-04T16:04:06.083Z
You can write an LBA interpreter in any sufficiently expressive programming language, so the LBA construction does give an algorithm.
Max New
<computability><parsing>
Are there parsers that can parse languages in more expressive grammars than context-free grammars?
Vivek Joshy
# Are there parsers that can parse languages in more expressive grammars than context-free grammars?

(Asked by: username_0 on 2022-09-03)

The [Earley Parser](https://en.wikipedia.org/wiki/Earley_parser) is able to parse all context-free languages. Are there parsers that can parse say languages in context-sensitive grammars? I realize ambiguous grammars are non-deterministic and might make this question not well formed and would be ready accept an answer that explains why it is not well formed if so.

**Tags:** computability, parsing

> **Comments:**
> **username_1**: https://en.wikipedia.org/wiki/Context-sensitive_grammar#Equivalence_to_linear_bounded_automaton  
> **username_0**: @username_1 I've already read that part of the page. So It's still an open problem to create parsers for more expressive grammars? AFAIK a LBA is not a parsing algorithm, it's a hypothetical machine that can accept or reject a set of strings.  
> **username_2**: You can write an LBA interpreter in any sufficiently expressive programming language, so the LBA construction does give an algorithm.  

---

## 0 answers

