# Lossless Syntax Trees

**URL:** <https://discuss.python.org/t/lossless-syntax-trees/520>\
**Category:** Ideas\
**Created:** [December 6, 2018, 6:01pm UTC](https://discuss.python.org/t/lossless-syntax-trees/520 "2018-12-06T18:01:23Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![nchammas](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/nchammas/32/233_2.png) [@nchammas](https://discuss.python.org/u/nchammas)\
**Post date:** [December 6, 2018, 6:01pm UTC](https://discuss.python.org/t/lossless-syntax-trees/520/1 "2018-12-06T18:01:23Z")

</div>

Continuing the discussion from [Switch Python's parsing tech to something more powerful than LL(1)](https://discuss.python.org/t/switch-pythons-parsing-tech-to-something-more-powerful-than-ll-1/379/3):

> [@Switch Python's parsing tech to something more powerful than LL(1)](https://discuss.python.org/t/switch-pythons-parsing-tech-to-something-more-powerful-than-ll-1/379/3):
>
> I don’t have an opinion on whether or not to change the parsing tech, but if we do then I hope high-quality error messages will be given serious weight when picking the replacement.

Just an aside that may be interesting to folks, I read about something called [“Lossless Syntax Trees”](http://www.oilshell.org/blog/2017/02/11.html) on the [Oil project](http://www.oilshell.org) blog last year:

> [A Lossless Syntax Tree is] a representation for source code that can be converted back to the **original text**. In Oil, I implement it with a combination of:
> 
> 1. An ordered [ASDL](http://www.oilshell.org/blog/2016/12/11.html) **tree** structure, and
> 2. An **array** of **line spans**. Concatenating these spans gives you back the original source file.
> 
> It’s not an AST because it **preserves details** of the syntax that are irrelevant to interpretation and compilation.

I don’t know much about parsing. Is this idea relevant to those who are looking to improve Python’s syntax error messages?

Here are some related issues on [bugs.python.org](http://bugs.python.org), by the way:

- [Provide more helpful error message when `await` is called inside non-`async` method](https://bugs.python.org/issue26188)
- [Show “expected” token on syntax error](https://bugs.python.org/issue1634034)
- [‘SyntaxError: invalid token’ is unfriendly](https://bugs.python.org/issue20608)
- [Provide a supported Concrete Syntax Tree implementation in the standard library](https://bugs.python.org/issue33337) (this perhaps encompasses the above idea already?)

---

<div class="post-metadata">

**Author:** ![apalala](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/apalala/32/683_2.png) [@apalala](https://discuss.python.org/u/apalala)\
**Post date:** [April 25, 2019, 1:24pm UTC](https://discuss.python.org/t/lossless-syntax-trees/520/2 "2019-04-25T13:24:46Z")

</div>

> [@nchammas](#):
>
> [A Lossless Syntax Tree is] a representation for source code that can be converted back to the **original text**. In Oil, I implement it with a combination of:
> 
> 1. An ordered [ASDL](http://www.oilshell.org/blog/2016/12/11.html) **tree** structure, and
> 2. An **array** of **line spans**. Concatenating these spans gives you back the original source file.
> 
> It’s not an AST because it **preserves details** of the syntax that are irrelevant to interpretation and compilation.

That is what TatSu does, and it works! It requires a record (`tuple`) per input source postion:

```python
    def line_info(self, pos=None):
        if pos is None:
            pos = self._pos
       
        # -2 to skip over sentinel
        pos = min(pos, len(self._line_cache) - 2)
        start, line, length = self._line_cache[pos]
        end = start + length
        col = pos - start

        text = self.text[start:end]
        n = min(len(self._line_index) - 1, line)
        # note: this can be omitted if there's no support for #include
        filename, line = self._line_index[n]

        return LineInfo(filename, line, col, start, end, text)

```

The AST needs only record the start and end positions in the source for the source it represents.