Skip to content

Dyck Language

Authors
Joe Starr, Ph.D. image

Joe Starr, Ph.D.

I specialize in computational knot theory. I’m also a professional embedded software engineer.

What?

The Dyck language1 is a grammar that generates strings of paired (sometimes called balanced) parentheses. Further details can be found in the User Guide.

Special Care?

There's nothing special you need to do when deriving from the Dyck language specification.

What Happens When the Stack Is Full?

When the stack is full an empty string is produced.

File

[[production]]
name = "entry"
type = "pure"
replacements = ["(%{paren set})"]
terminals = [""]

[[production]]
name = "paren set"
type = "pure"
replacements = ["(%{paren set})", "%{paren set}%{paren set}", ""]
terminals = [""]

  1. Noam Chomsky and Marcel Paul Schützenbérger. The Algebraic Theory of Context-Free Languages. In Studies in Logic and the Foundations of Mathematics, volume 26, pages 118–161. Elsevier, 1959. doi:10.1016/S0049-237X(09)70104-1. ↩