Opened 2 years ago
Last modified 2 years ago
#30760 new enhancement
Implement parser for Sage
Reported by: | embray | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-wishlist |
Component: | user interface | Keywords: | parser, syntax |
Cc: | gh-mwageringel, slelievre | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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
orR
denoting that they should be interpreted as the Python built-in types instead of Sage types
- generator syntax:
g.0
is equivalent tog.gen(0)
(ifg
does not have.gen
method this results in aTypeError
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 toa * 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
Change History (6)
comment:1 Changed 2 years ago by
comment:2 Changed 2 years ago by
Cc: | gh-mwageringel added |
---|
comment:3 follow-up: 5 Changed 2 years ago by
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.
comment:4 Changed 2 years ago by
Description: | modified (diff) |
---|
comment:5 Changed 2 years ago by
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).
comment:6 Changed 2 years ago by
Cc: | slelievre added |
---|---|
Description: | modified (diff) |
Keywords: | parser syntax added |
Another useful resource is Guido's blog series on implementing a PEG parser for Python: https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60