context-sensitive grammars

Aug 7, 2015 at 8:18 PM
This is my first post, so please be gentle.

I have a DSL I'm trying to define within Irony. It includes an aspect that has me puzzled. Consider this example:
<table> <row> <cell> ...text... </cell> </row> </table> it is straightforward to set up non-terminals with rules preventing text or cell or row in the wrong context.

This DSL also has a looping structure called foreach. Normally, foreach can enclose anything in the DSL, except when used this way:
<table columns="2"> <foreach> <cell> ...text... </cell> </foreach> </table> When foreach is used within a tabular context, it is constrained to just enclose cells.

My first thought (that didn't work) was to create two non-terminals for foreach, one for each context.

This doesn't work. Grammar explorer declares a reduce-reduce error.

Now it seems as if I need a single non-terminal with rules that admit either one context or the other.

Is this doable in the grammar definition?

Or must I catch this in a token filter?
Aug 7, 2015 at 10:54 PM
Edited Aug 7, 2015 at 10:55 PM
At first glance this seems like a typical example of a (software) language that isn't parsable by context-free parsers like Irony. The canonical example is:
int function() {
    /** **/
    return var; // A CFG cannot enforce that var is an int
}
The classic solution is to implement a type system. That is, you define your grammar/parser too broadly so it accepts invalid syntax (like a foreach that contains non-cells in a table) and then have your type system check the types by walking through the tree.

Very simplified it could look something like this for you:
AnyTag.Rule = AnyTagOpen + TagContents + AnyTagClose
Foreach.Rule = ForeachTagOpen + AnyTag + ForeachTagClose
Table.Rule = TableRows | Foreach
TableRows.Rule = MakeStarRule(TableWithRows, Row,"")
And then somewhere in your type system:
public void TypeCheckNode(ParseTreeNode node) {
     /* ... */
     // Check if AnyTags opening and closing are the same tag
     if(node.Term.Name == "AnyTag" && TagName(node.ChildNodes[0]) != TagName(node.Childnodes[2])) {
              throw new TypesystemException("Unmatched tags");
     }
     // Check if a foreach in a table only contains cells
     if(node.Term.Name == "Table" && node.ChildNodes[0].Term.Name == "Foreach") {
          if(TagName(node.ChildNodes[0].ChildNodes[1]) != "cell") {
              throw new TypesystemException("Foreach in table can only contain a cell");
          }
     }
     /* ... */
}