11
$\begingroup$

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)?

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – user555045
    Commented Aug 23 at 19:28
  • 1
    $\begingroup$ 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). $\endgroup$
    – dan04
    Commented Aug 23 at 23:26
  • $\begingroup$ 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. $\endgroup$
    – feldentm
    Commented Aug 24 at 6:42
  • 2
    $\begingroup$ 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. $\endgroup$
    – chepner
    Commented Aug 25 at 13:04
  • $\begingroup$ What makes you think LR(1) is not simpler than LL(1)? $\endgroup$
    – Chris Dodd
    Commented Aug 26 at 2:28

1 Answer 1

Reset to default
6
$\begingroup$

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, XML, JSON, or some other tree-structured data format (but hopefully not YAML). Alternatively, you can "shallowly embed" 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 or tree-sitter (both of which target most popular languages).

One notable exception is if you can fit your grammar into a 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. 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, almost all support at least LL(k).

$\endgroup$
9
  • 3
    $\begingroup$ Missed opportunity to cite that infamous parsing HTML with regex answer :P $\endgroup$
    – Seggan
    Commented Aug 24 at 19:31
  • $\begingroup$ "Most modern languages are parsed from hand-rolled recursive-descent parsers" - would appreciate a citation for this. $\endgroup$
    – Karl Knechtel
    Commented Aug 25 at 14:16
  • 4
    $\begingroup$ 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: softwareengineering.stackexchange.com/questions/250256/… $\endgroup$
    – tarzh
    Commented Aug 25 at 15:22
  • $\begingroup$ @tarzh could you elaborate a little more about why its "harder" e.g. with some examples of language constructs? $\endgroup$
    – Jonas
    Commented Aug 26 at 17:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – tarzh
    Commented Aug 26 at 21:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .