Welcome to The Sound of Grammars (Reprise), you can catch the first part of the series here. As a reminder, I’ve been reading Parsing Techniques: A Practical Guide by Ceriel J.H. Jacobs and Dick Grune which is available as a PDF on Grune’s site.

Type 2: Context-Free Grammars

Now that you’ve heard about context-sensitive grammars, let’s throw context out the window! Both left and right contexts are absent for a type 2 grammar, meaning there is only one symbol on the left hand side.

FavoriteThing -> Adjectives Noun | Noun PrepositionalPhrase

Adjectives -> Adjective Adjective

Adjective -> bright | copper | warm | woolen

PrepositionalPhrase -> on Noun

Noun -> raindrops | roses | whiskers | kittens | kettles | mittens

Because we are lacking context, it is even easier to write sentences that have correct structure but may be weird or not make sense, like kittens on raindrops or bright warm whiskers. However this makes our grammar more flexible and like we said before — grammar only determines if you are structurally correct, not logically (or lyrically) correct.

For sake of example, let’s say we want unlimited (at least one) adjective. We can alter our Adjectives rule to be Adjectives -> Adjective Adjectives | Adjective. As soon as you want to end your list of Adjectives you can choose the Adjective option from the right hand side and that cuts the recursion off. This is a very common rule structure for duplicates of the same thing, so there’s shorthand for it already!

There is an extended context-free grammar (called Extended Context-Free 😱 or Regular Right Part Grammars) that adds some symbols to Context-Free grammars that allows a bit more flexibility for these common patterns. Let’s say there will always be more than one adjective but maybe more. We could define them as Adjectives -> Adjective**+**. Maybe we will have no adjectives or only one adjective: MaybeAdjective -> Adjective**?**. And if you combine them and want zero or more adjectives: MaybeAdjectives -> Adjective**\***.

If you’re familiar with regular expressions, you may recognize these common modifiers: +, ?, and *. We’re just pattern matching! And speaking of…

Type 3: Regular Grammars

Let’s get regular. For a Type 3 grammar, a right hand side can only have one non-terminal symbol and it must be at the end. As far as Chomsky is concerned, a non-terminal must produce one terminal or one terminal followed by one non-terminal.The book differs from this definition and replaces the bolded ones with “zero or more”.

Terminal symbols are usually single characters only (think of regular expressions and how each letter/symbol is a match, not the group) and in addition to the symbols in the extended context-free grammar, [] is used to denote a possible set of characters (like how we were using | before). This grammar makes less sense for the grammar we were using and more sense for a pattern of characters you might want to produce. Instead of thinking about all of our favorite things, let’s focus on that kitten that has whiskers.

Our kitten may say meow or mew so we could make a grammar that is S -> meo?w which would produce an m, an e, maybe an o, and a w. But let’s make our cat a little more international. Let’s say our cat can speak the following languages (list from Care2):

1. Catalan: Meu

2. Chinese: Mao

3. Dutch: Miauw

4. Finnish: Miau

5. French: Miaou

6. Hebrew: Miau or Miya

7. Hungarian: Miaaau

8. Portuguese & Spanish: Miau

Cats can say other things too (like nyan) but I kept our list to languages that follow a pattern: these all start with one m, that m is followed by one or more vowels (counting y), and sometimes the meow ends in one w. Let’s make a regular grammar that can produce cat sounds for cats who are brief and for cats who are chatty:

S -> M, S | M

M -> m[aeiouy]+w?

When you have the letters to meow, you can meow most anything! If you remember, [] denote a set of characters to choose from, the + is “one or more” and the ? just means “maybe ¯\_(ツ)_/¯”. This grammar is also able to make up new words for the cat to say, like meyw and myyyyyyyyyyyy which can be fun but can also be not what you want. If you restrict the grammar to only produce cat sounds from _real_ languages, our grammar we just made wouldn’t work out.

If you’re interested in playing around with the regular expression I used to create this grammar, I have a regex101 tester set up that contains some other languages that don’t follow our pattern as well as made up words from the grammar we created.

So Long, Farewell

The book also identifies a type 4 grammar (finite-choice — no non-terminal symbols allowed) and Van Wijngaarden grammars. I wanted to stick to just the Chomsky hierarchy as these were the grammars (specifically context sensitive) that were talked about the most. It’s important to note that the hierarchy stacks — a grammar that is Type 3 (regular) still fits the Type 1 (context-sensitive) definition.

tl;dr — Type 0 is all formal grammars, Type 1 is context-sensitive (bright Adjective -> bright copper), Type 2 is context-free (Adjective -> bright | copper | warm | woolen), and Type 3 is regular (M -> m[aeiouy]+w?).

So long, farewell, au revoir, auf wiedersehen

I hope I’ve helped to lessen grammar pain

I am currently working my way through Parsing Techniques: A Practical Guide by Ceriel J.H. Jacobs and Dick Grune which is available as a PDF on Grune’s site. As I continued in the book I found myself having a hard time following classifications and grammar levels when they were used interchangeably. I am using this blog post to hash it all out for myself so I can practice keeping the order and meaning straight by explaining these concepts to my good friend, the internet.

Let’s start at the very beginning (a very good place to start): what is the Chomsky Hierarchy? Well it’s a hierarchy of formal grammars described by Noam Chomsky. Hm, that wasn’t exactly the very beginning, was it?

What most people think of as a “normal language” (something you use to communicate with other humans, like English) is called a natural language, whereas a programming language (something you use to communicate with computers) is a formal language.

A formal grammar describes a formal language. Just like in natural language, a grammar isn’t going to tell you what a sentence means but it will tell you how to form that sentence. In our formal world, a sentence is more like a formula or a statement. In a language where we can have any amount of a and any amount of b , but every a has to always be before every b, aaaabbb would be a valid sentence.

Now that we’re back at the very beginning: what is the Chomsky Hierarchy? This is a classification of how strict a grammar is, with 0 being the least strict (but hardest to parse) and 3 being the most strict (but easiest to parse!). Before diving in I want to get some definitions out of the way for the terms that we’ll be using.

• Rule: A rule takes the form of A -> a where A and a are both something (each step of the hierarchy has its own definition). But this is basically a production step — given this input, provide this output.

• Symbol: This can be anything! They are values used in some sort of sequence of values. We’ll get into two types of symbols soon but for now think of them as a placeholder value and a content value. In our rule, both A and a are symbols.

• Sentence: A sentence contains one or more symbol. A “valid” sentence is a sentence that can be produced by the given grammar and a fully produced/final sentence has used the rules provided to replace all placeholder values with real content.

• Left-hand side: The left-hand side (you’ll see LHS sometimes but I want to try to avoid acronyms) is the A in my above example — it is the left-hand side of the rule.

• Right-hand side: Bet you can guess what this one is. Yep, the right-hand side of the rule! You did great. That would be a in our example.

• Non-Terminal Symbol: A non-terminal, or non-terminal symbol, is a symbol that will not be allowed in a final sentence —this is our placeholder value from before! You can also think of it as a variable. Hopefully you will be able to turn it into a terminal eventually using the rules in the grammar, otherwise it is a sentence that doesn’t exist in the language. A is our non-terminal in our rule.

• Terminal Symbol: A terminal, or terminal symbol, is a legal symbol in the language — this is our content symbol. Like the non-terminal is our variable, the terminal symbol is the value. This symbol will no longer be processed further since it is in its final form. A terminal is usually lower case, so in our example it is a.

Type 0: Unrestricted Grammars

A grammar rule consists of a left hand side and a right hand side. Something like A -> a. An unrestricted grammar means anything can be on the left hand side and anything can be on the right hand side. Go nuts (well, as nuts as a Turing machine will let you go).

Type 1

Type 1 grammars are where things get more restrictive (and more fun!). These grammars may have rules that transform a non-zero number of symbols to possibly zero number of symbols. These come in two flavors: original and flavortown.

Monotonic

Monotonic grammars contain no rules where the left-hand side has more symbols than the right-hand side. For an example, I just try to think of nice things: FavoriteThing and FavoriteThing -> raindrops on roses and whiskers on kittens. Our left-hand side has 3 symbols and our right-hand side has 7 symbols. This grammar is Monotonic! A rule that has 16 symbols on the left hand side going on 17 symbols on the right hand side would also be monotonic.

Context-Sensitive

Context-sensitive seems like the prominent definition of Type 1 grammars. A context-sensitive grammar only consists of rules where only one symbol on the left-hand side is replaced by another symbol on the right-hand side. The note here is that the left-hand side can still be any number of symbols but the grammar must remain monotonic (i.e. number of symbols on the left-hand side is less than the number of symbols on the right-hand side.

Below we’ve added two possible outcomes for the rule FavoriteThing as well as how to parse after you have selected a FavoriteThing structure.

You’ll see | used in the upcoming grammar examples, it just means that for the given left hand side, you have options!

FavoriteThing -> Adjective Adjective Noun | Noun on Noun

Noun on -> raindrops on | whiskers on

Adjective -> bright | copper | warm | woolen

bright Adjective -> bright copper

warm Adjective -> warm woolen

raindrops on Noun -> raindrops on roses

whiskers on Noun -> whiskers on kittens

bright copper Noun -> bright copper kettles

warm woolen Noun -> warm woolen mittens

In this grammar we have defined, only one non-terminal (e.g. Noun) is replaced by a terminal (e.g. kittens) at a time and the left hand side is always equal to or less than the number of symbols on the right. Our example for monotonic grammars above isn’t context-sensitive because it is replacing multiple words at once. I like this example because the term “context sensitive” makes a lot of sense — in the context of raindrops on you can only finish that with roses and not kettles.

Intermission

Keep your eye out for Sound of Grammars (Reprise) where we’ll explore Type 2 and Type 3 grammars!

A class I took in college called Programming Language Fundamentals introduced me to Haskell and it didn’t take long until I was utterly charmed by this language. It was my first taste of the functional programming paradigm and everything I did felt like solving a riddle. Haskell made me feel clever and while programming shouldn’t be all solving riddles, it is sure fun to feel clever. Before class one day, a friend who shared my enthusiasm (and who knew I liked frontend development) told me I should check out Elm. I searched for “Elm” and once google figured out I wanted the language and not “West Elm”, I found my way to their website and to the web browser wysiwyg. For once I had a hard time paying attention to my Haskell class because I was so interested in figuring out (and comparing) Elm.

Eventually I graduated and started working at AppNexus and for my goals at work I focused on Elm for a quarter and read Learn You a Haskell for Great Good for a quarter — both to better learn functional programming. But let’s be honest it was to scratch this itch I had for these languages. Or at least that’s how it started. Unbeknownst to me I was learning Haskell and Elm for great JavaScript.

At my job we use React and Redux — when I first started learning Redux I had a really hard time primarily because of the language around it. What the hell were reducers and dispatchers and why were actions not taking action? The names didn’t make sense to me and didn’t hold meaning to me so I had a rough time trying to keep it all straight in my head. Learning Elm was really valuable to me for this reason because Redux’s architecture was inspired by Elm’s architecture. Redux has actions that get sent to reducers that change your app’s state; Elm has messages that get sent to updates that change your app’s model. Learning this pattern with the word choice that Elm used, as opposed to Redux, helped me immensely. I could understand what a message was and wasn’t confused why it wasn’t taking action. Update is a word I use in my personal lexicon far more than reduce. To be fair, state and model were pretty 50/50 for me.

Going through Learn you a Haskell actually helped me get to know lodash better. As I learned more about the core Haskell library functions I would check out lodash and try to figure out its equivalent. Sometimes I would even write the Haskell lesson in pseudo-javascript just to try on different hats while learning. Haskell helped lodash’s reduce really click. I had a hard time remembering that function and why to use it but then when I was doing a lesson involving folding, I realized “Hey, this is what reduce is!” This is another example where word choice affected my understanding — “folding” makes me think of when you lightly mix things in cooking so I had that visual cue to remember what it was called whereas reduce doesn’t really give me that memory cue.

At a broader scale, working through Elm and Haskell helped me be more conscious in JavaScript. Since both languages are pretty minimal on parentheses, I started focusing more on readability and noting what I liked, what I didn’t like, and what seemed the most clear. I was more conscious about side effects and how we could keep functions as pure as possible. Type systems became even more my jam than they were before. And finally I just learned how to think functionally and how to keep those functional tools within reach so they could be part of muscle memory.

Part way through this I did stop and start wondering what I’m even doing and why. It’s not like I’m writing Haskell day to day. I wrote a scrabblizer that takes a message and translates it to the scrabble emoji code for slack but that’s about it. But then I just reminded myself that 1) I’m doing it because I just genuinely think these languages are fun and 2) they are teaching me lessons I can take elsewhere.

Now I’m not saying YOU should go out and learn Haskell and Elm for great Javascript. Learn the languages you want to learn — pay attention to the lessons that are agnostic of language and be aware that certain word choices will click better for some people over others. If you’re studying some weird language, think about the patterns you are using and how their word choice could be better or how it aides your mental model. Languages have certain attributes baked in and that will change how you approach and understand problems.