Grammar types constraint after adding a couple of types (and a statement involving them) to a “typeless” language

Question

Foreword : by "typeless programming language", I naively mean "language in which you don't write statements like type x (=) ... to declare(define) x". Maybe there is an internal typing deduced from what is in ... but I suppose that this is not the case, as it is not the case in the example interesting me. (If "typeless programming language" already means something, forbid me, but this is not the point.)

Consider the grammar of a "typeless" programming language, python (3.6.3) for instance :

https://docs.python.org/3/reference/grammar.html

I rather used its description here :

https://github.com/erezsh/plyplus/blob/master/plyplus/grammars/python.g

Then I lightened the grammar a lot and modified the resulting subgrammar by adding new features, but for the sake of simplicity, one can assume that I add features to the complete python grammar, not to a subgrammar of it.

Here are my modifications :

1) I added a date "type" (I put type in "" because there's no type in python)

date: US_DATE;

where :

US_DATE: '!(?:(?:(?:(?:(?:[13579][26]|[2468][048])00)|(?:[0-9]{2}(?:(?:[13579][26])|(?:[2468][048]|0[48]))))(?:(?:(?:09|04|06|11)(?:0[1-9]|1[0-9]|2[0-9]|30))|(?:(?:01|03|05|07|08|10|12)(?:0[1-9]|1[0-9]|2[0-9]|3[01]))|(?:02(?:0[1-9]|1[0-9]|2[0-9]))))|(?:[0-9]{4}(?:(?:(?:09|04|06|11)(?:0[1-9]|1[0-9]|2[0-9]|30))|(?:(?:01|03|05|07|08|10|12)(?:0[1-9]|1[0-9]|2[0-9]|3[01]))|(?:02(?:[01][0-9]|2[0-8])))))';

(thx to https://stackoverflow.com/a/16088645/1581875)

and I propagated date to atom.

Then d = !20171116 produce the following syntax tree :

2) I also added what I call an underlying, and this time it's a real type. Namely, I added a

UNDERLYING: 'underlying';

in the %unless part of NAME definition, and I introduced an underlying statement :

underlying_stmt : UNDERLYING name (COMMA name)*;

that I of course propagated to small_stmt.

Now one can write :

underlying z

which produces the following syntax tree :

3) Here comes the tricky (at least for me) part : after what preceeds, I introduced a new use of the @ symbol, namely a "stamp statement", stamp_stmt, as follows :

stamp_stmt: name AT (name | date);

(that I propagated of course to small_stmt)

Namely, I can write

z @ d #or
z @ !20171116

and this will produce the following syntax tree :

In fact, as I defined the stamp_stmt, I can write name @ date for any name (and date).

I cannot write 2 @ !20171116 for instance : this is already a constraint. I would like to be able, within the grammar, to also add the following constraint : name @ date could be written only for a name of an underlying.

How could I achieve this ? I mean, I could still introduce a kind of light "typing" in name by refining it by saying that date (resp. underlying) has datename (resp. underlyingname) and try to use it to achieve the wanted constraint, but I could also say that d = !20170823 is not an assignement statement (assign_stmt) and introduce a "date assignement statement", same for underlying.

Is it anyway a good idea to want to put such a type constraint already in the grammar or not ? (I am really not an expert in languages designing etc ... I am doing all of this because I need a small programming language with the aforementionned features and because around me, no one can help.)

Remark : I am doing all of this under windows with plyplus in python and producing syntax trees figures using graphwiz.

Answer 1

There is no way to express that constraint with a context-free grammar. (It is, almost by definition, context-sensitive since the validity of z @ … depends on the presence of underlying z.)

So you are left with two choices:

1. Perform the validity check as a semantic action.

2. Modify the lexical scanner's categorization of tokens on the fly, by recategorizing z after underlying z is seen.

Option 2 is usually called the "lexical feedback hack" and that is precisely what it is. Sometimes it cannot be conveniently avoided, but this is not one of them.