Class of linearly parsable languages?

142 Views Asked by At

Is there name for class of languages exactly such that their words can be parsed in $O(n)$ by program in conventional Turing-complete language (SML)? (i.e. without backtracking)

Any references?

2

There are 2 best solutions below

10
On

I do not know of a specific name for this class of languages.

However, there are many results on grammar types. For example, LR(1) and LL(1) grammars can be parsed in linear time, but using different parsing strategies.

1
On

Did you mean linear bounded automata?