Implement parser for Sage

[embray]

The Sage interpreter has its own language that is close to, but a slight extension of Python, including various transformations to how literals--particularly numeric literals--are to be interpreted (there is also the issue of automatic variables which traditionally was only implemented by the Sage Notebook REPL itself, rather than in Sage itself; see e.g. #21959).

The Sage preparser which converts Sage code to valid Python code is an unwieldy series of regular expressions and other ad-hoc string parsing and transformation code. While it has been fairly stable over the years, it is difficult to maintain, especially when new syntax is added to Python (see #28974 and the difficulty of adding support for f-strings).

It would make the code much simpler and easier to understand, make it easier to respond to syntax changes in Python, and make it easier to evolve the Sage language (as a real language that is a superset of Python) by defining a formal grammar for it (again, as an extension of Python's grammar) and using a real lexer/parser in the Sage interpreter to convert code to ASTs, that can then be transformed into ASTs acceptable by Python's bytecode compiler.

This might be made easier by using Python's new PEG parser introduced in Python 3.9: ​https://www.python.org/dev/peps/pep-0617/ Though this does not necessarily mean making Sage dependent on Python 3.9, as we can generate our own parser using an existing third-party parser generator, or using the one that was written for Python and generates a C parser: ​https://github.com/python/cpython/tree/master/Tools/peg_generator

(If using this, one would also want to want to add a simple extension module providing an interface to the new parser, so it can be easily used by the Sage interpreter; there is example code for such an extension in the peg_generator package as well).

If it turns out extending the parser generator used by Python is infeasible, I believe Guido was also inspired by the ​TatSu parser generator; the current version of which requires Python 3.8, though earlier versions are Python 3.6+.

This would be a major task for anyone who want to take it on, though it would be an interesting project and I think highly valuable.

---

Summary of new syntax that would have to be supported by a Sage parser (distilled from ​https://doc.sagemath.org/html/en/reference/repl/sage/repl/preparse.html):

• "raw" literals: numeric literals followed by r or R denoting that they should be interpreted as the Python built-in types instead of Sage types

• generator syntax:

• g.0 is equivalent to g.gen(0) (if g does not have .gen method this results in a TypeError at runtime, or something)
• g.<g1, g2, g3> = G() is equivalent to "g = G(names=['g1', 'g2', 'g3]); g1, g2, g3 = g.gens()` (again this should also include some runtime type check that G is a Parent with generators)

• implicit multiplication: a b c in an expression is equivalent to a * b * c (a feature that can be enabled or disabled, so this needs to be a flag in the parser whether or not to accept this)

• this also needs to support NUMBER '' term meaning <number> * <term>; e.g. 3exp(x) -> 3 * exp(x); this modifies somewhat the rules for terms in an expression since a term beginning with a number has different rules for a term not beginning with numbers

• method calls are allowed directly on numeric literals (just method calls or attribute lookups as well?)

• symbolic function definitions like f(x, y) = x + y^2

• ellipsis notation like (need to expand on what these mean and their exact syntax):
  • [1, 2, .., n]
  • for y in (f(x) .. L[10])
  • [1..5]

• Backslash operator \\ (it is treated equivalent to multiplication in the order of operations, but has different semantics)

Anything I'm missing?

Already valid syntax in Python but with different semantics in Sage:

• ^ means exponentiation by default
• numerical literals are Sage types (Integer, RealNumber, ComplexNumber, etc.)

Related:

• #30501: Define a Sage syntax highlighting

[embray]

Another useful resource is Guido's blog series on implementing a PEG parser for Python: ​https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60

[embray]

Python's built-in tokenizer (whether the C version or the plain Python version) is not so easy to extend as I'd hoped either. Would be nice to have an explicit listing somewhere of exactly what would be needed to support Sage.

[gh-mwageringel]

Replying to embray:

Python's built-in tokenizer (whether the C version or the plain Python version) is not so easy to extend as I'd hoped either.

For tokenization, it might also be worth taking a look at ​parso. Its tokenizer is adapted from the Python version, but has some improvements. In particular, it supports tokenizing f-strings (which Python handles in an ad-hoc manner in a later phase).