search

munificent / craftinginterpreters

Repository for the book "Crafting Interpreters"
http://www.craftinginterpreters.com/
Other
9.02k stars 1.06k forks source link

Section 5.1.1: Confusing phrasing #869

Closed JohnnyWalkerDigital closed 3 years ago

JohnnyWalkerDigital commented 3 years ago

If it's at all possible (and it may not be possible) it would be great if the same terminology could be used consistently. I'm often very confused as to what's being referred to.

Consider the following in Section 5.1.1: Representing Code - Rules for Grammars (https://craftinginterpreters.com/representing-code.html#rules-for-grammars)

Recursion like this usually indicates that the language is context-free instead of regular. In particular, this kind of nested recursion where the recursive nonterminal has productions on both sides of it means that it’s not regular.

And then in the sidenote:

Keeping track of that number of trailing parts is beyond the capabilities of a simple regular grammar. A regular grammar can repeat, but it can’t count.

So... is the language regular or isn't it?

On the one hand this language is "context-free" (not "not regular") because it has "nested recursion where the recursive nonterminal has productions on both sides". On the other hand, it has the traits of a "simple regular grammar" because it can repeat, but can't count.

I'm sure I'm missing something, but I found it very confusing. I'd like to have faith in the terminology used through the book.

munificent commented 3 years ago

On the other hand, it has the traits of a "simple regular grammar" because it can repeat, but can't count.

When it says "a regular grammar can repeat, but it can't count" it's not referring to the Lox language (which is indeed not regular). It's making a statement about regular languages in general. Reworded stuff to hopefully be clearer.