Introduction to Parsers

Theory of Formal Grammars

Type 3 — Regular languages

A deterministic finite automata representing the following regular expression: /-?[0–9]+\.?[0–9]*/

Type 2 — Context-Free languages

{ 0^n 1^n | n >= 0 }
  1. If you see a 0, push it onto the stack and go back to (1).
  2. If you see a 1, pop an item from the stack and go back to (2).
  3. If the stack is empty, we’ve verified that the input string is “in the language”.
***bold**italic*    =>  <em><strong>bold</strong>italic</em>***italic*bold**    =>  <strong><em>italic</em>bold<strong>*italic**not bold*  =>  <em>italic**not bold</em>

Type 1 — Context-Sensitive languages

{ a^n b^n c^n | n >= 0 }
  1. Read the first a and overwrite it with an x.
  2. Move to the first b and overwrite it with an x.
  3. Move to the first c and overwrite it with an x.
  4. Then move back to the beginning and go back to (1).
  5. If you make it to the end of the string looking for the first a and they’re all x’s, then we’ve verified the string.

Type 0 — Recursively Enumerable languages

An Unsolved Conjecture

Parser Combinators

A Naive Approach

Click “Edit on CodePen” in the top right to modify the code.

Round 2

Click “Edit on CodePen” in the top right to modify the code.

Other Libraries

Conclusion

  • The Chomsky Hierarchy defines four classes of formal languages that can be distinguished by the complexity of the program required to parse and validate a string.
  • Most programming languages are context-free and probably has a BNF grammar defined somewhere. A good place to start looking is ANTLR’s extensive list of examples.
  • Some languages, like Markdown, have lots of ambiguities. Even if they are context-free, it’s exceedingly difficult to define a parsing expression using BNF.
  • Parser combinators are an elegant general-purpose solution for all of your parsing needs.

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Controllable Text Generation in Deep Learning with Transformers (GPT3) using Tensorflow & Keras

I’m not a genius

Amazon Redshift Federated Queries: Rise Of Query Engines

Accessing Docker from a Kubernetes Pod

Mouse Tweaks Mod 1.16.4-1.16.3-1.15.2 — Minecraft players build tools faster

Using fdisk utility for partitioning on Linux

BENEFITS OF USING PUBLIC CLOUD WITH MULTI CLOUD TECHNOLOGY.

Micro:bit & vital signs

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Chet Corcos

Chet Corcos

More from Medium

Indenting JSON.stringify’s Output

Using Coroutines in Unity

Constructing a Navigation Mesh in Node.js

Haskell Journey: Creating Type