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 :


I rather used its description here :


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 :

enter image description here

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 :

enter image description here

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 :

enter image description here

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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – chi
    Commented Nov 16, 2017 at 13:00

1 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.


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.