5
$\begingroup$

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
aba
ababba
ababbabbba
...

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

statement(indent)
    : indent basic_statement
    | indent header ':' newline statement_list(indent whitespace)
statement_list(indent)
    : 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?

$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure why I said the left-hand of a rule may be a terminal, since context-free grammars do not allow a terminal on the left-hand side. $\endgroup$
    – Joey Adams
    Nov 13, 2018 at 16:49

5 Answers 5

4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ My question is 8 years old, but I think I meant that passing functions as arguments is not allowed, e.g. G(F, d). But calling a function and then passing the result to another function is allowed, e.g. G(F(a,b,c), d). $\endgroup$
    – Joey Adams
    Nov 13, 2018 at 17:03
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 }

$\endgroup$
0
$\begingroup$

The fact that you say "A function of zero arguments is equivalent to a nonterminal" makes me believe that you mean the same function can be on the left-hand side of multiple rules, that is, you can have both $F(x,y,z) \to x$ and $F(x,y,z) \to zy$. In that case it seems to me that your formalism is exactly the same as Fischer's macro grammars. Sadly the paper is behind a paywall but here's a relevant screenshot:

screenshot from the introduction to Fischer 1968

"The arguments of a function call are expanded before being passed" seems to indicate that you want an inside-out (IO) expansion strategy. I don't know if that's been studied a lot, but the opposite one (OI) corresponds to indexed languages.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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