Regex is for Regular Grammars as to ____ is for Context Free Grammars

Question

I have just learned that Regular Grammars have their corresponding Finite State Acceptors which will correspond to Regular Expressions.

Is there an equivalent conversion with Context Free Grammars? As far as I know Context Free Grammars can be represented by Push Down Automata which in turn would correspond to what?

Thanks to anyone who would clear my mind off of this.

Answer 1

From Wikipedia Context Free Grammar:

a popular notation for context-free grammars is Backus–Naur Form

…just as regexes are a notation for regular grammars.

Answer 2

Actually, the answer could still be "Regex".

Modern regex dialects, specifically those that support recursion (like PHP, Perl, .NET, JGSoft and others) can handle context-free languages perfectly.

Answer 3

Modern programming languages themselves are for the most part described by context free grammars. Although theoretically phrase structured grammars are the most powerful (English is an example), it has been found that for solving problems with computers context free grammars in combination with a powerful memory model (variables) are sufficient. The programs that accept these context free languages are the modern language parsers.

Some example language BNF

• BNF for Pascal
• BNF for Ruby
• BNF for Javascript
• BNF for Python
• BNF for Java
• BNF for C

Given the BNF is context free, a parser can be generated automatically, the original and most famous example is of course Yacc others have been created since with Bison being invented for the creation of gcc. There are now a host of parser generators whose output is a parser written in one of the popular languages.

Answer 4

There's a problem with the phrasing of the question, in that it refers to grammars instead of to languages.

A Regular Language is one that can be defined over sets with the operations of union, concatenation, and closure. Both Regular Expressions and Regular Grammars are convenient ways to represent Regular Languages.

The thing with Context Free Language is that it is defined as the language accepted by a Context Free Grammar, so the answer to the OP's question is within the language category definition itself.