Balanced Parentheses

This article is not detailed enough and needs to be expanded. Please help us by adding some more information.

Balanced Parentheses, also called BP, is the language whose alphabet consists of two characters and whose strings consist of pairs of those characters with optional substrings between each pair. It is named for the presentation where those characters are opening and closing parentheses. It is the paradigmatic example of a Dyck language.

Grammar

The grammar of BP can be given by the following BNF:

BP = ( '(' BP ')' )*

It can also be represented by the following Zephyr ASDL:

bp = BP(bp*)

Properties

BP is closed under concatenation; any sequence of BP strings is also a BP string.

Like all Dyck languages, BP can be efficiently parsed from any starting point within a string, not only the beginning.