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.

score 2 · Accepted Answer · answered Feb 02 '14 at 15:00

2

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.

answered Feb 02 '14 at 15:00

Bergi

630,263
148
957
1,375

Indeed, BNF is probably the equivalent. Can it also become a regex though? @Tim mentioned it can still be regex in a way. – Jer Yango Feb 02 '14 at 17:36
1

Well, some context-free grammars are also regular, so at least these would be representable as regexes :-) What Tim mentioned are not "theoretical" regular expressions from computer science, but the implementations of regex engines which often have features beyond regular languages - up to recursion which indeed makes them match any context-free language. However, as complexity increases, regexes become unusable, and depending on the information that is to be extracted a stack-based parser usually the better choice – Bergi Feb 02 '14 at 17:55

score 2 · Answer 2 · edited May 23 '17 at 12:03

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.

edited May 23 '17 at 12:03

Community

1
1

answered Feb 02 '14 at 15:07

Tim Pietzcker

328,213
58
503
561

Hahaha. I’d like to call them “real world regex”. – SnowOnion Dec 17 '18 at 03:50

score 0 · Answer 3 · edited Jun 20 '20 at 09:12

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

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.

score 0 · Answer 4 · answered Feb 03 '14 at 12:55

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.

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

4 Answers4

Some example language BNF