13
$\begingroup$

I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python grammar in ANTLR-like format:

// on top-level the statements have empty indent
program  
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent) 
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

My question: Does this kind of grammars (CFG with parameters) have a name?

It looks that it wouldn't be hard to write a recursive descent parser for this grammar (parameters should be basically parsers). What could be the difficulties with this approach?

Does addition of parameters raise the supported language class above context-free?

$\endgroup$
  • 1
    $\begingroup$ If the set of values the parameters can take is finite then it's trivially context free still (you can then iterate over all values and write it all out). $\endgroup$ – ratchet freak Jun 1 '17 at 14:25
  • 1
    $\begingroup$ Worth noting that your proposal is for indentation-sensitive languages with fixed indentation. Python (and other such languages) are not restricted in this way; they accept whatever indentation the user wants. That doesn't affect parseability (except for handling tab characters) but it would be hard to express with your proposal, at least as I understand it. $\endgroup$ – rici Jun 1 '17 at 14:32
  • $\begingroup$ attribute grammars $\endgroup$ – Hendrik Jan Jun 1 '17 at 14:33
  • $\begingroup$ @HendrikJan, attribute grammars is a way of annotating grammar with semantic action, they don't control the parsing. $\endgroup$ – AProgrammer Jun 1 '17 at 14:37
  • 1
    $\begingroup$ If the goal is to handle indentation, that is more suitable for the tokenizer rather than the parser. Have the tokenizer emit virtual INDENT and UNINDENT tokens when the indentation level changes. Then there's no need to augment the language grammar with information about indentation. $\endgroup$ – John Kugelman supports Monica Jun 1 '17 at 17:14
14
$\begingroup$

Affix grammars (parameterised context-free grammars) were studied extensively by the eminent Dutch computer scientist Cornelis HA Koster, starting with his 1962 paper "Basic English, a generative grammar for a part of English", co-written with LGLT Meertens. In 1970, he produced a formalism of the concept; a useful overview is available in his 1971 paper "Affix Grammars for Programming Languages", a version of which I found on Citeseer.

In that paper, Koster compares his formalism (and another similar one) with Van Wijngaarden two-level grammars, and finds them to be very similar.

Dick Grune's invaluable annotated bibliography of parsing techniques includes a large number of other useful references for affix grammars and other non-Chomskyian formalisms. (See section 18.2.6 of the bibliography, although there are useful papers in other sections.) Grune covers affix grammars briefly in §15.3.2 of the second edition of Parsing Techniques: A Practical Guide (and even more briefly in the first edition, available online) mentioning the fact that it is easy to adapt top-down (and other) parsing techniques.

Unless the domain of parameters is finite, in which case they can be removed by statically generating all possible productions resulting in a CFG, the class of affix grammars is certainly a strict superset of the set of context-free grammars. (An affix grammar for $a^n b^n c^n$ can be found in Dick Grune's Parsing Techniques reference above.)

Koster, who was also an editor of the Algol 68 report, was the original developer of the Compiler Description Language (CDL), based on his ideas about affix grammars. This toolkit and its later derivatives were used in production for many years. This page, which I found with a Google search and whose permanence I cannot guarantee, has links to the manual and download site for CDL3.

$\endgroup$
  • $\begingroup$ I feel the CDL languages are more like attribute grammars: the values of the attributes can be computed by externally defined functions. I'd reserve the name affix grammar for cases where the relationships between the values of the affixes (attributes) are defined within the formalism, as in Extended Affix Grammars. $\endgroup$ – reinierpost Jun 1 '17 at 22:09
  • $\begingroup$ @reinierpost: You are, of course, entitled to your own terminology; the privilege is not restricted to anthropomorphic eggs. However, the CDL manual itself claims that "CDL3 is an implementation language based on affix grammars," which I think should be taken into account. (Manual available at ftp.cs.kun.nl/pub/cdl3/cdl3-manual-1.2.7.pdf). That's what I claimed in my answer: that CDL was based on Koster's work on affix grammars. As Grune points out, the difference between affix and attribute grammars is slight; his distinction is whether the affixes are used to decide syntactic validity. $\endgroup$ – rici Jun 1 '17 at 22:22
  • $\begingroup$ (The quote is from the first page of the manual.) $\endgroup$ – rici Jun 1 '17 at 22:27
  • $\begingroup$ I know ... and you're right. My comment wasn't meant to contradict you. $\endgroup$ – reinierpost Jun 1 '17 at 22:32
6
$\begingroup$

Take the pumping lemma for CFGs:

Take the grammar

S -> A("")
A(p) -> p 
      | p '\n' A(p"*") '\n' p 

This describes a star triangle:

*
**
***
**
*

There is no way to split a star triangle up in 5 parts $uvwxy$ such that $\{uv^nwx^ny|n>0\} $ is also a star triangle (with $vx$ non empty).

This means that the star triangle is not a context free language.

Or a simpler example:

S-> B("")
B(p)-> p 'a' p 'a' p
     | B(p 'b')

This describes the language $\{b^nab^nab^n | n\ge0 \}$ which is not context free.

$\endgroup$
3
$\begingroup$

I've never seen this formalism presented (even in something like Grune's Parsing Techniques), depending on the details on how you define exactly "parameters should be basically parsers" it looks mappable to van Wijngaarden two level grammars, which have the same power as unrestricted phase structure grammar (i.e. more powerful than context sensitive, you could write a VW grammar which gives all halting programs).

$\endgroup$
  • 2
    $\begingroup$ Dick Grune, Parsing Techniques 2nd edition, page 488 $\endgroup$ – rici Jun 1 '17 at 15:30
  • $\begingroup$ Koster and his group studied two types of affix grammars, as far as I'm aware: 1) restricted forms of Van Wijngaarden grammars, meant to allow easier recognition; 2) the CDL languages, practical compiler description languages without any explicit affix value manipulation but with the option to define rules in the target language (e.g. assembler), making them Turing complete. $\endgroup$ – reinierpost Jun 1 '17 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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