MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If you start with the rules for building a context-free grammar and extend them by allowing left-hand nonterminals to be functions of one or more arguments, does that go beyond the definition of a context-free grammar? If so (I imagine it does), what class of grammars is it? Context-sensitive?

To clarify, suppose we have the following grammar:

$S \to F(a,b,c)$
$F(x,y,z) \to xyz$

The grammar above is equivalent to the following because x, y, and z are substituted:

$S \to abc$

Now suppose we leverage the function capability with the following grammar:

$S \to F(\epsilon)$
$F(x) \to x\ a\ |\ x\ a\ F(x\ b)$

($\epsilon$ means empty string)

That grammar produces:


A practical application of functions in a grammar is to express an indentation-formatted computer language. Trivial example:

    : indent basic_statement
    | indent header ':' newline statement_list(indent whitespace)
    : statement(indent)*

This means that a statement, given some indentation string, may either be a one-liner (e.g. print 'hello') or it may be a header (e.g. if (x == 5)) followed by ':', a newline, and one or more child statements of a greater indentation level.

Note that statement_list has to be out by itself here, as statement(indent whitespace)* could yield child lines of inconsistent indentation if the whitespace expands to something not constant. By calling statement_list once with the possibly variable whitespace, we coerce all the child statements to have the exact same indentation. Once again, functions come to the rescue.

To be more specific on the rules of the grammar system I'm talking about:

  • The left hand of each rule is either a terminal, a nonterminal, or a function declaration for zero or more arguments.
  • A function of zero arguments is equivalent to a nonterminal.
  • The arguments of a function declaration must be single variables (I used $x$, $y$, and $z$ in the examples above).
  • The arguments of a "function call" (used on the right-hand side of a rule) may contain terminals, nonterminals, and nested function calls.
  • The arguments of a function call are expanded before being passed. Thus, functions in this grammar system are no higher than first order (if I'm using the term correctly).

So, by adding "functions" to CFG, what do I get?

share|cite|improve this question

Since you can pass arbitrary nonterminals to functions, you can encode van Winjgaarden grammars (aka two-level grammars) with your formalism, which makes parsing an undecidable problem.

A caveat: I'm not sure what you mean by "arguments of a function call are expanded before being passed". If you pass a recursive nonterminal as an argument, it can be infinitely expanded.

share|cite|improve this answer

Your rules are not completely clear to me but the language that you use as an example (with ababbabbba) is not a context free language as it does not satisfy the pumping lemma, so you can go beyond the context free languages.

share|cite|improve this answer

Just as a bit of a "big picture" comment... most grammatical formalisms are chosen for parsing use because they admit efficient implementations as some sort of automaton. An automaton implementation is desirable because it gives you precise bounds on both the time and space complexity of the implementation as a function of the length of the input (n) and input expression nesting depth (d). For example, Tomita's GLR uses O(d) space whereas Packrat Parsing uses O(n) space. For human-generated inputs, O(d) is effectively O(1).

Tight, precise bounds are more important in parsing than in most other areas, because it is usually the case that the programmer who is using the generated parser (for example, the person who runs "yacc") does not understand the parsing algorithm, and will not be able to know which inputs will result in pathological behavior (in time or space) for his/her grammar. Furthermore, the person who uses the parser (the person who runs the program that includes yacc-generated code) is even less likely to understand this, so if pathological behavior arises, dealing with it will be especially difficult. Therefore it is important to have good worst-case bounds on time and space, since these are likely all that can be relied upon.

Additionally, since the parser is generally the first in a sequence of operations performed on the input, its time/space complexity establish a lower limit on the time/space complexity of the whole operation. You don't want to use an O($n^3$)-time parser as a front end to an O($n\log n$)-time computation! To maximize the applicability of their work, researchers in parsing and formal languages tend to impose pretty strict upper limits on themselves.

In this case it's pretty clear that any formalism that can handle your grammar is going to have extremely large worst-case time complexity, so it may be worth looking for a weaker formalism that is still able to do the job. I'd suggest looking at Boolean Grammars; they have the same time/space complexity as GLR even though they can handle non-context-free structures. Encoding indentation in a Boolean Grammar can be a bit tricky, but the result is quite efficient. Packrat Parsers might be another option, but the space complexity often becomes a problem once you try to scale up to large "real world" inputs; this can be insidious because you don't get hit with the nasty surprise until you've already invested a lot of work in developing the parser.

share|cite|improve this answer

Have a look at the following two papers of Engelfriet and Schmidt:

@article{engelfried:1977:IOandOI, author = {J. Engelfriet and E. M. Schmidt}, title = {{IO} and {OI}. {P}art {I} and {II}}, journal = JCSS, volume = {15 and 16}, pages = {328--353, 67--99}, year = 1977 }

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.