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

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])))))';


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.

• So, summing up, you want to allow name @ date only when before that we can find underlying name. This looks to be the same problem of checking whether a variable was declared before it is used (in languages requiring that). If so, this is usually checked after parsing, since it seems impossible to encode this in the grammar. I'd say you can either 1) do a pass after parsing, or 2) use grammars with attributes, and keep track of the "declared" variables during parsing. – chi Nov 16 '17 at 13:00

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.)
2. Modify the lexical scanner's categorization of tokens on the fly, by recategorizing z after underlying z is seen.