I started to revisit syntactic mappings defined in EasyExtend 3 which are closely tied to the Python grammar being\u00a0 in use. Those are functions like `varargs2arglist`, `normalize`, `split_file_input` or `exprlist2testlist` defined in the `csttools.py` module. One of the major challenges of future releases of EasyExtend ( or a definite successor project – i don’t know ) is to abstract from Python as a target language. In EE3 only Python can be targeted by a langlet transformation whereas in EE 4 langlets are symmetric: each langlet can be a target langlet for any other langlet. All langlets exist on the same footing and also: each langlet can be used as a parent langlet of a newly defined langlet which means a proper inheritance relationship and maximum reuse.<\/p>\n
The relativity among langlets calls for raising the bar of abstraction. All Python specific dependencies, and there are a lot in EE3, have to be removed from the basic CST libraries. Indeed not even nodes of special importance like `expr`, `stmt` or `atom` shall be allowed in places other than modules which are specific to a particular langlet. The generalization of the mentioned functions leads to a study of abstract syntactic forms and some sort of “syntax algebra”. It isn’t studied rigorously in this article but shall be at least motivated. As a prerequisite I recommend to read my article about CST interpolation<\/a> which discusses concepts of major relevance.<\/p>\n The `exprlist2testlist` function turns a node of type `exprlist` defined as<\/p>\n into a node of type `testlist`defined as<\/p>\n This works without adding information because `{test, expr}` is a valid interpolation<\/em> i.e. there is a nested sequence<\/p>\n which is a representation of a valid CST. In terms of CST interpolations `test(expr)` yields a node of type `test` and induces a homomorphism `exprlist`->`testlist`. More generally an interpolation `{A, B}` induces an embedding `B (x B)*` -> `{A,B} (y {A,B})* = A (y A)*` if `x` and `y` are constant<\/em> terminal symbols i.e. terminal symbols where the corresponding token have a uniquely determined token string.<\/p>\n Another relevant example is the `normalize` function. The idea behind `normalize` is that statements like `if x: y` or `def foo(): pass` are semantically equivalent to block statements:<\/p>\n Those block statements can be used in a more general fashion because we can add other block statements in the thunked block. In Python blocks are expressed by the `suite` grammar rule:<\/p>\n Since `{stmt, simple_stmt}` is a valid interpolation, we can substitute all occurences of<\/p>\n with suites of the form<\/p>\n The general syntactic embedding is of the kind<\/p>\n `B` -> `a b… {A,B} c d…` with a, b, c, d … being constant terminal symbols.<\/p>\n Notice that `INDENT` is assumed to be a constant terminal despite the fact that the token string may vary. `INDENT` is treated special because in practical applications the number of used spaces for an indentation is fixed.\u00a0 EasyExtend always uses 4 spaces.<\/p>\n The function `split_file_input` is the prototype of a node splitting function which can be thought in analogy to string splits. In this particular case we have a node `file_input` of the form<\/p>\n and want to generate a sequence of nodes `file_input: stmt ENDMARKER`, `file_input: NEWLINE ENDMARKER` and `file_input: ENDMARKER` – one for each `NEWLINE`, `stmt` and `ENDMARKER` in the original `file_input` node. It doesn’t matter that `file_input: NEWLINE ENDMARKER` and `file_input: ENDMARKER` are likely be thrown away by an application because this can be decided by the nodes consuming function. The general split function is defined by<\/p>\n `R: x (A|B…)* y` -> `[(R: x A y), (R: x B y), …, (R: x y)]`<\/p>\n The mappings considered above were all rather straightforward. Now we want to discuss a rule transformation which is less obvious, namely that of a function signature into an argument tuple of a function call. In Python 2.6 the function signature is defined as<\/p>\n and an argument list of a function call by<\/p>\n Can we transform each `varargslist` into an `arglist`?<\/p>\n Let’s start our treatment of varargslist with `fpdef`. If we insert the RHS of `fplist` in `fpdef` we get<\/p>\n We show that this rule is a special form of\u00a0 the node `atom` and since `{test, atom}` is a valid interpolation it is also a `test` node. The `atom` node is defined by<\/p>\n which can be specialized to<\/p>\n Next we consider the `testlist_gexp` definition<\/p>\n which can be specialized to<\/p>\n We insert `testlist_gexp` in `atom` which yields<\/p>\n If we reduce `test` to `atom` we get a rule<\/p>\n which is isomorphic to `fpdef`. So we just need to substitute all occurrences of `fpdef` in `fpdef` with `atom`, then replace `atom` with `test(atom)` and finally replace the whole of `atom` again with `test(atom)`. This procedure substitutes `fpdef` with `test`.<\/p>\n When we substitute each occurrence of `NAME` with `test`in `varargslist` we get:<\/p>\n which can be reduced to<\/p>\n which is the same as<\/p>\n Voil\u00e0!<\/p>\n We have done some informal steps into syntax algebra with some real functions defined in EE 3 as a starting point. For the first three functions we have found general syntactical transformations which might be universally applicable. The last transformation is very specific though and it might be more interesting to determine an algorithm used to find<\/em> a rule transformation of a particular kind. Although the search algorithm might be NP complete I assume that the found transformation – if one exists – has linear time complexity which is what we want. Such an algorithm would be another great achievement of EasyExtend which does not cease to surprise me.<\/p>\n","protected":false},"excerpt":{"rendered":" Principle of relativity I started to revisit syntactic mappings defined in EasyExtend 3 which are closely tied to the Python grammar being\u00a0 in use. Those are functions like `varargs2arglist`, `normalize`, `split_file_input` or `exprlist2testlist` defined in the `csttools.py` module. One of … Continue reading Embeddings<\/h3>\n
exprlist: expr (',' expr)* [',']<\/pre>\ntestlist: test (',' test)* [',']<\/pre>\n[test<\/strong>, [or_test, [and_test, [not_test, [comparison , expr<\/strong>]]]]]<\/pre>\n
Blocks or no blocks<\/h3>\n
if x:\r\n y<\/pre>\n
def foo():\r\n pass<\/pre>\n
suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT<\/pre>\n
suite: simple_stmt<\/pre>\n
suite: NEWLINE INDENT stmt+ DEDENT<\/pre>\n
Splitting nodes<\/h3>\n
file_input: (NEWLINE | stmt)* ENDMARKER<\/pre>\n
Node rewritings<\/h3>\n
varargslist: ((fpdef ['=' test] ',')*\r\n('*' NAME [',' '**' NAME] | '**' NAME) |\r\nfpdef ['=' test] (',' fpdef ['=' test])* [','])\r\nfpdef: NAME | '(' fplist ')'\r\nfplist: fpdef (',' fpdef)* [',']<\/pre>\narglist: (argument ',')* (argument [',']| '*' test [',' '**' test] | '**' test)\r\nargument: test [gen_for] | test '=' test<\/pre>\n
fpdef: NAME | '(' fpdef (',' fpdef)* [','] ')'<\/pre>\natom: NAME | '(' [yield_expr|testlist_gexp] ')' |\u00a0 '[' [listmaker] ']' | ...<\/pre>\natom: NAME | '(' testlist_gexp ')'<\/pre>\ntestlist_gexp: test ( gen_for | (',' test)* [','] )<\/pre>\ntestlist_gexp: test (',' test)* [',']<\/pre>\natom: NAME | '(' test (',' test)* [','] ')'<\/pre>\natom: NAME | '(' atom (',' atom)* [','] ')'<\/pre>\n(test ['=' test] ',')* ('*' test [',' '**' test] | '**' test) |\r\n test ['=' test] (',' test ['=' test])* [',']<\/pre>\n(argument ',')* ('*' test [',' '**' test] | '**' test) |\r\n argument (',' argument)* [',']<\/pre>\n(argument ',')* (argument [','] | '*' test [',' '**' test] | '**' test)<\/pre>\n
Syntax algebra<\/h3>\n