<p>Programming languages can come quite far with an easy grammar like LL(1), and parsers both in the compiler and tooling can be constructed with hand-written Predictive Parsers (or be generated).</p>
<p>When designing a language, I often feel that it is doable to get an &quot;ergonomic&quot; language design, while keeping the language grammar within LL(1).</p>
<p>What are some good reasons to use a &quot;more advanced&quot; grammar, like LR? I can see why some choose it, if they plan to use a <em>parser generator</em> anyway, but are there other good reasons? e.g. what kind of ergonomic language constructs make a language must be LR instead of LL(1)?</p>

<language-design><parsing><grammar>
What are good reasons for using a more complex grammar than LL(1)?
CC BY-SA 4.0
2024-08-23T19:28:17.560Z
Are you considering LL(1) as a "pure" LL(1) the way it exists in theory, or the widely supported "LL(1) with resolvers that can do whatever" the way it is implemented by LL parser generators?
user555045
CC BY-SA 4.0
2024-08-23T23:26:54.637Z
Do consider C(++)'s pointer declaration syntax `TYPE *var;` to be "ergonomic"?  Because you can't do that with "pure" LL(1) (since it can't be distinguished from a multiplication).
dan04
CC BY-SA 4.0
2024-08-24T06:42:06.510Z
I could provide an answer if the LR reference were be removed from the question. Otherwise, it does not make sense as LL and LR grammars are essentially equivalent. The theoretical differences do not matter after rule transformations and adding attribute processing.
feldentm
CC BY-SA 4.0
2024-08-25T13:04:07.920Z
IIRC, Python's grammar used to be LL(1); the switch to a PEG grammar is what allowed the `match` statement to be added to the language without breaking (all) code that used `match` as an identifier.
chepner
CC BY-SA 4.0
2024-08-26T02:28:04.780Z
What makes you think LR(1) is not simpler than LL(1)?
Chris Dodd
CC BY-SA 4.0
2024-08-26T16:58:05.780Z
Not an answer, but it always confused me how languages (well, notably Python for a while) tout being LL(1) by throwing a metric ton of cleverness at the definition, when something "complex" like PEG would just get the job *done*.
MisterMiyagi
CC BY-SA 4.0
2024-08-27T15:29:13.100Z
@MisterMiyagi Well, from 1991-or-earlier until 2004, parsing expression grammars had not yet been invented/discovered.  Work on a PEG parser for Python probably began sometime between 2012 and 2019 (depending on when exactly ["some years ago"](https://medium.com/@gvanrossum_83706/peg-parsers-7ed72462f97c) refers to), and officially adopted for Python 3.9.
chepner
<p>In practice, it's usually <em>harder</em> to create a true LL(1) grammar than a more complex one, because the most common parsing techniques and parser generators handle LL(k) at least.* You'd have to manually check the grammar is still LL(1) after you've already written the parser.</p>
<p>If you don't particularly care about syntax, there's no reason to write a parser at all: just use <a href="https://en.wikipedia.org/wiki/S-expression" rel="nofollow noreferrer">S-expressions</a>, XML, JSON, or some other tree-structured data format (<a href="https://docs.ansible.com/ansible/latest/reference_appendices/YAMLSyntax.html" rel="nofollow noreferrer">but hopefully not YAML</a>). Alternatively, you can <a href="https://decomposition.al/blog/2015/06/02/embedding-deep-and-shallow/" rel="nofollow noreferrer"><strong>&quot;shallowly embed&quot;</strong></a> your language in another and reuse its syntax. If you do care about syntax and don't want to shallowly embed, the easiest way to create a parser is probably either recursive descent with a language-specific <strong>&quot;parser combinator&quot;</strong> library, or via a popular parser generator like <a href="https://www.antlr.org/" rel="nofollow noreferrer">ANTLR4</a> or <a href="https://tree-sitter.github.io/tree-sitter/" rel="nofollow noreferrer">tree-sitter</a> (both of which target most popular languages).</p>
<p>One notable exception is if you can fit your grammar into a <a href="https://en.wikipedia.org/wiki/Regular_expression" rel="nofollow noreferrer">regular expression</a>, it may be considerably easier to parse via a &quot;regex&quot; than to hand-write or generate a parser for. Since most languages have regex libraries, and a regex is a small string, it can often be done in one or two lines of code. However, AFAIK there's no &quot;regex&quot; equivalent for LL(1) grammars; that is, no technique to represent LL(1) grammars in a way that's more consise than LL(k) or other would be.</p>
<hr />
<p>* Most modern languages are parsed from <a href="https://en.wikipedia.org/wiki/Recursive_descent_parser" rel="nofollow noreferrer">hand-rolled recursive-descent parsers</a>. When writing a hand-rolled parser you have the power of a full programming language, so it's easy to write something that's not even context-free. From <a href="https://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages" rel="nofollow noreferrer">Wikipedia's list of parser generators</a>, almost all support at least LL(k).</p>

CC BY-SA 4.0
2024-08-24T14:20:58.720Z
2024-08-26T20:58:24.477Z
2024-08-26T20:58:24.477Z
tarzh
CC BY-SA 4.0
2024-08-24T19:31:08.543Z
Missed opportunity to cite that infamous parsing HTML with regex answer :P
Seggan
CC BY-SA 4.0
2024-08-25T14:16:17.347Z
"Most modern languages are parsed from hand-rolled recursive-descent parsers" - would appreciate a citation for this.
Karl Knechtel
CC BY-SA 4.0
2024-08-25T15:22:42.853Z
clang (C/C++/objC), Roslyn (C#/VB), openJDK (Java), v8 (JavaScript), R, Kotlin, Swift, Go, Rust, and Zig all have hand-written parsers. Sometimes the documentation is spotty but you can tell by looking at the source code on Github, all of their parser classes are not auto-generated. Interestingly, I found pythonc uses a PEG, and ocaml and Haskell both use their LR parser generator (menhir and Happy, respectively). So it's not every language, but most are hand-rolled. See also: https://softwareengineering.stackexchange.com/questions/250256/do-modern-languages-still-use-parser-generators
tarzh
CC BY-SA 4.0
2024-08-26T17:45:54.473Z
@tarzh could you elaborate a little more about why its _"harder"_ e.g. with some examples of language constructs?
Jonas
CC BY-SA 4.0
2024-08-26T21:07:42.057Z
For example, a language that permits both function calls of the form `foo(...)` and identifiers `foo` as expressions is not LL(1), because when the lexer sees an identifier, it doesn't know whether to parse a plain identifier or function call expression. Likewise, if it permits both assignments `a = foo(...);` and expression statements `foo(...);`, it isn't LL(1) because an identifier could be the start of an assignment or its own statement. Most popular languages permit both of these.
tarzh
CC BY-SA 4.0
2024-08-26T21:13:06.940Z
The main point though, is that if you add any of these syntax forms to a grammar and feed it to a parser generator, unless it's one of the few that are LL(1), it will almost certainly not complain and give you a working parser. Likewise, if you write a recursive-descent parser, even if the lexer only gives you one token of lookahead, you can write a function that will consume a token, store it in a local variable, then peek the next token to implement e.g. the identifier or function call. You have to go out of your way to *not* use the extra capability, because if you do, nothing stops you.
tarzh
CC BY-SA 4.0
2024-09-08T20:09:03.150Z
@tarzh that does not sound correct. It is common to have both `foo(...)` as call-expr and `foo` as identifier in LL(1) languages, by using `(` as a binary operator. In the second case, you can see that `a = foo(...);` is an assingment by using the lookahead token, so that case is also not difficult in an LL(1) language.
Jonas
CC BY-SA 4.0
2024-09-11T20:17:51.363Z
After more research, you're probably right and the above comment is wrong. In fact, an LL(1) language can be quite expressive: [this SO answer gives a "small" non-LL(1) language](https://stackoverflow.com/a/10657843), and it's fairly contrived (the third answer on that page is wrong too). But there's still an issue that makes creating an LL(1) *grammar* not so easy: to parse calls and assignments, you need to structure your AST in a non-straightforward way, with an "identifier OR call OR assignment" node ([example](https://github.com/simonpicard/ll1-compiler/blob/master/doc/grammar.md)).
tarzh
CC BY-SA 4.0
2024-09-24T08:43:08.743Z
I'd say deep embedding is also a viable way to avoid writing a parser, given that you essentially reuse parsing of data structures in the host language as the parser of your object language. In fact, if the embedding is too shallow, it can become hard to implement any sort of front end or optimisation, because you don't have a handle on the AST.
James Wood
# What are good reasons for using a more complex grammar than LL(1)?
Posted by: username_0 on 2024-08-23
Programming languages can come quite far with an easy grammar like LL(1), and parsers both in the compiler and tooling can be constructed with hand-written Predictive Parsers (or be generated).

When designing a language, I often feel that it is doable to get an "ergonomic" language design, while keeping the language grammar within LL(1).

What are some good reasons to use a "more advanced" grammar, like LR? I can see why some choose it, if they plan to use a *parser generator* anyway, but are there other good reasons? e.g. what kind of ergonomic language constructs make a language must be LR instead of LL(1)?
**Tags:** language-design parsing grammar
> **Comments:**
> **username_1**: Are you considering LL(1) as a "pure" LL(1) the way it exists in theory, or the widely supported "LL(1) with resolvers that can do whatever" the way it is implemented by LL parser generators?  
> **username_2**: Do consider C(++)'s pointer declaration syntax `TYPE *var;` to be "ergonomic"?  Because you can't do that with "pure" LL(1) (since it can't be distinguished from a multiplication).  
> **username_3**: I could provide an answer if the LR reference were be removed from the question. Otherwise, it does not make sense as LL and LR grammars are essentially equivalent. The theoretical differences do not matter after rule transformations and adding attribute processing.  
> **username_4**: IIRC, Python's grammar used to be LL(1); the switch to a PEG grammar is what allowed the `match` statement to be added to the language without breaking (all) code that used `match` as an identifier.  
> **username_5**: What makes you think LR(1) is not simpler than LL(1)?  
> **username_6**: Not an answer, but it always confused me how languages (well, notably Python for a while) tout being LL(1) by throwing a metric ton of cleverness at the definition, when something "complex" like PEG would just get the job *done*.  
> **username_4**: @MisterMiyagi Well, from 1991-or-earlier until 2004, parsing expression grammars had not yet been invented/discovered.  Work on a PEG parser for Python probably began sometime between 2012 and 2019 (depending on when exactly ["some years ago"](https://medium.com/@gvanrossum_83706/peg-parsers-7ed72462f97c) refers to), and officially adopted for Python 3.9.  
---
## 1 answers
### Answer by username_7 on 2024-08-24. Score: 6
In practice, it's usually *harder* to create a true LL(1) grammar than a more complex one, because the most common parsing techniques and parser generators handle LL(k) at least.\* You'd have to manually check the grammar is still LL(1) after you've already written the parser.

If you don't particularly care about syntax, there's no reason to write a parser at all: just use [S-expressions](https://en.wikipedia.org/wiki/S-expression), XML, JSON, or some other tree-structured data format ([but hopefully not YAML](https://docs.ansible.com/ansible/latest/reference_appendices/YAMLSyntax.html)). Alternatively, you can [**"shallowly embed"**](https://decomposition.al/blog/2015/06/02/embedding-deep-and-shallow/) your language in another and reuse its syntax. If you do care about syntax and don't want to shallowly embed, the easiest way to create a parser is probably either recursive descent with a language-specific **"parser combinator"** library, or via a popular parser generator like [ANTLR4](https://www.antlr.org/) or [tree-sitter](https://tree-sitter.github.io/tree-sitter/) (both of which target most popular languages).

One notable exception is if you can fit your grammar into a [regular expression](https://en.wikipedia.org/wiki/Regular_expression), it may be considerably easier to parse via a "regex" than to hand-write or generate a parser for. Since most languages have regex libraries, and a regex is a small string, it can often be done in one or two lines of code. However, AFAIK there's no "regex" equivalent for LL(1) grammars; that is, no technique to represent LL(1) grammars in a way that's more consise than LL(k) or other would be.

---

\* Most modern languages are parsed from [hand-rolled recursive-descent parsers](https://en.wikipedia.org/wiki/Recursive_descent_parser). When writing a hand-rolled parser you have the power of a full programming language, so it's easy to write something that's not even context-free. From [Wikipedia's list of parser generators](https://en.wikipedia.org/wiki/Comparison_of_parser_generators#Deterministic_context-free_languages), almost all support at least LL(k).
> **Comments:**
> **username_8** (2024-08-24): Missed opportunity to cite that infamous parsing HTML with regex answer :P  
> **username_9** (2024-08-25): "Most modern languages are parsed from hand-rolled recursive-descent parsers" - would appreciate a citation for this.  
> **username_7** (2024-08-25): clang (C/C++/objC), Roslyn (C#/VB), openJDK (Java), v8 (JavaScript), R, Kotlin, Swift, Go, Rust, and Zig all have hand-written parsers. Sometimes the documentation is spotty but you can tell by looking at the source code on Github, all of their parser classes are not auto-generated. Interestingly, I found pythonc uses a PEG, and ocaml and Haskell both use their LR parser generator (menhir and Happy, respectively). So it's not every language, but most are hand-rolled. See also: https://softwareengineering.stackexchange.com/questions/250256/do-modern-languages-still-use-parser-generators  
> **username_0** (2024-08-26): @tarzh could you elaborate a little more about why its _"harder"_ e.g. with some examples of language constructs?  
> **username_7** (2024-08-26): For example, a language that permits both function calls of the form `foo(...)` and identifiers `foo` as expressions is not LL(1), because when the lexer sees an identifier, it doesn't know whether to parse a plain identifier or function call expression. Likewise, if it permits both assignments `a = foo(...);` and expression statements `foo(...);`, it isn't LL(1) because an identifier could be the start of an assignment or its own statement. Most popular languages permit both of these.  
> **username_7** (2024-08-26): The main point though, is that if you add any of these syntax forms to a grammar and feed it to a parser generator, unless it's one of the few that are LL(1), it will almost certainly not complain and give you a working parser. Likewise, if you write a recursive-descent parser, even if the lexer only gives you one token of lookahead, you can write a function that will consume a token, store it in a local variable, then peek the next token to implement e.g. the identifier or function call. You have to go out of your way to *not* use the extra capability, because if you do, nothing stops you.  
> **username_0** (2024-09-08): @tarzh that does not sound correct. It is common to have both `foo(...)` as call-expr and `foo` as identifier in LL(1) languages, by using `(` as a binary operator. In the second case, you can see that `a = foo(...);` is an assingment by using the lookahead token, so that case is also not difficult in an LL(1) language.  
> **username_7** (2024-09-11): After more research, you're probably right and the above comment is wrong. In fact, an LL(1) language can be quite expressive: [this SO answer gives a "small" non-LL(1) language](https://stackoverflow.com/a/10657843), and it's fairly contrived (the third answer on that page is wrong too). But there's still an issue that makes creating an LL(1) *grammar* not so easy: to parse calls and assignments, you need to structure your AST in a non-straightforward way, with an "identifier OR call OR assignment" node ([example](https://github.com/simonpicard/ll1-compiler/blob/master/doc/grammar.md)).  
> **username_10** (2024-09-24): I'd say deep embedding is also a viable way to avoid writing a parser, given that you essentially reuse parsing of data structures in the host language as the parser of your object language. In fact, if the embedding is too shallow, it can become hard to implement any sort of front end or optimisation, because you don't have a handle on the AST.  
---
