Preparing for new Python parsing

#33

Yes to the first three.

I don’t want to do anything about the tokenizer, since it works fine. It is full of arcana, and I worry that replacing it with a different mechanism would break corner cases.

In contrast, the grammar-to-CST mechanism we currently use is straightforward, and I don’t expect nasty corner cases there if we replace it with e.g. a PEG-based parser.

The current CST-to-AST translation code is too ad-hoc and complex, because has to make up for restrictions in pgen, and I want to replace it. If we couldn’t replace it I think the whole project would not be worth it.

Finally, the memory we might save by skipping the CST would give us some space back that we could use for the memoization cache. (The CST is quite large, due to the explicit presence of “trivial” nodes with a single child.)

In my toy project, I want to get to the point where in pure Python I can get from stream of tokens to AST (This is feasible because the ast module lets you create and combine AST nodes.)

We can then double-check that the AST created by the toy for a given program is identical to that created by the current parser, and iterate on areas where it isn’t.

I am looking for other parsing technology than pgen because I want to be able to write the grammar to match how I think about the program, e.g. (that same example again):

start: assignment | expression
assignment: NAME '=' expression
expression: NAME | <other categories>

PEG + packrat looks like a reasonable candidate so I am looking into that in detail.

#34

I too saw many (unwanted?) dependencies on the tokenizer. Not to worry about, as experts said that the tokenizer may stay over any language category or parsing strategy chosen.

I forgot to mention “maintainability” among the summary points, and that was among your original main concerns as I remember now (I think currently nobody dares come near pgen).

Yes.

I think that the “toy-project” will likely become the blueprint. You’re way past the warnings by Dennis Ritchie I quote here. You can do what you want. And it’s a fun project! I’m sorry (though I warned) that I didn’t have the time to do the feasibility testing you are doing during these past weeks.

Yes. Today there doesn’t have to be a performance penalty for a grammar that humans can understand.

In case you eventually decide in favor of PEG (knowing that LL(small-k) will also work), I’ll repeat the warning: It is non-obvious to explain why choices must be ordered in PEG grammars.

#35

And it is non-obvious to explain why an LL(k) parser generator will reject a grammar… So?

#36

So true! I’ve now gotten far enough with my toy project to have experienced this myself. Consider this grammar. (Sorry for using the pgen notation – please read ':' as '<-' and '|' as '/'.)

start: NAME '(' arguments ')'
arguments: kwargs | posargs [',' kwargs]
posargs: posarg (',' posarg)*
kwargs: kwarg (',' kwarg)*
posarg: expr
kwarg: NAME '=' expr
expr: NAME

The intention is that it accepts simple call expressions like these:

foo(a)
foo(a, b)
foo(x=y)
foo(a, x=y)

But not this (since positional arguments must not follow keyword arguments):

foo(x=y, a)

In fact, it accepts the first three but not the fourth one, foo(a, x=y). Why not? For a hint, see this fixed version:

start: NAME '(' arguments ')'
arguments: kwargs | posarg [',' arguments]
kwargs: kwarg (',' kwarg)*
posarg: expr
kwarg: NAME '=' expr
expr: NAME

SPOILER:

The first version of the grammar parses a,x=y as posargs (i.e., a,x) followed by =y. This is because PEG is always eager. How can I make this kind of situation easier to debug?

1 Like
#37

In my experience grammar design is like program design, or as language design. Part of it is logic, and another part intuition (or experience) and aesthetics.

As a rule of thumb, don’t use recursion in PEG rules unless the construct being described is recursive, because the extended EBNF of PEG is powerful enough to not require it.

Another hint is that lookeaheads and negative lookaheads are in PEG for a reason.

This grammar solves that language fragment, because the longest choices come first, and lookaheads avoid the wrong choices (the negative lookahead is not actually needed, but better safe than sorry):

start: NAME '(' arguments ')'
arguments: kwargs | posargs ',' kwargs | posargs | ()
posargs: posarg (',' posarg)* 
kwargs: kwarg (',' kwarg)*
posarg: expr !'='
kwarg: NAME '=' expr
expr: NAME

As to debugging, I chose cut expressions for TatSu. A cut parses nothing, but the parser commits to the current choice after it sees it. While debugging, using cut makes the parser fail early if the rules are not right. Using ~ for `cut, the above could be:

start: NAME '(' arguments ')'
arguments: kwargs | posargs ',' ~ kwargs | posargs | ()
posargs: posarg (',' ~ posarg)* 
kwargs: kwarg (',' ~ kwarg)*
posarg: expr !'='
kwarg: NAME '=' ~ expr
expr: NAME
#38

Ah, very cool. I need to add lookaheads and cut to the toy project!

#39

We’ll, there’s already some parsing of Python using PEG/Packrat with pglc and TatSu. It will likely take a couple more sessions to finish debugging the grammar.

This is output from parsing the Python in CPython (smallest files first):

pglc_cpython

(@guido There may be ideas there that can be used in your parser).

#40

I probably have to put the toy project on ice, too many other things are begging for my attention. :frowning:

#41

Aw! That’s a shame… :frowning:

I can work on my own toy project only during parts of some weekends. But that should be fine, as there’s no deadline in sight, and any progress should be good, even if the only usable product is information to feed into the decision-making for Python parsing :slight_smile:

#42

Question about this (it’s keeping me up :-). Does failure to match what follows ~ cause the entire parse to fail (a panic if you will), or does it just skip further alternatives of the current rule, while still allowing further alternatives of “callers” to be probed?

#43

A cut acts locally. After it is seen, independently of if what follows succeeds or fails, the parser will skip further alternatives of the current choice, which could be the choice for the whole rule, or a choice in a parenthesis group.

work = preamble (paragraph)* ('->' ~ epilogue | end) | paragraph

After the cut following -> is seen, epilogue must succeed for the choice to succeed, and end will never be tried, but the rule may succeed with the second main choice if paragraph succeeds.

#44

Results so far for most of cpython/**/*.py:

--------------------------------------------------------------------------------
         184   files input
         184   files parsed
     126,160   lines input
     126,160   lines parsed
          86   successes
          98   failures
       46.7%   success rate
     0:02:26   elapsed time
     0:29:29   runtime
          71   LOC/s

(runtime different from elapsed because of the 8 cores involved)

This is good progress for a weekend project.

My apologies, @guido, but it seems obvious that TYPE_COMMENT was hacked into the grammar:

typedargslist
    =
        '**' tfpdef [','] [TYPE_COMMENT]
    |
        '*' [tfpdef] {',' [TYPE_COMMENT] tfpdef ['=' test]}*
        (
                TYPE_COMMENT
            |
                [',' [TYPE_COMMENT] ['**' tfpdef [','] [TYPE_COMMENT]]]
        )
    |
        tfpdef ['=' test] {',' [TYPE_COMMENT] tfpdef ['=' test]}*
        (
                TYPE_COMMENT
            |
                [
                    ',' [TYPE_COMMENT]
                    [
                        |  '**' tfpdef [','] [TYPE_COMMENT]
                        |  '*' [tfpdef] {',' [TYPE_COMMENT] tfpdef ['=' test]}*
                            (
                                  TYPE_COMMENT
                                | [',' [TYPE_COMMENT] ['**' tfpdef [','] [TYPE_COMMENT]]]
                            )
                    ]
                ]
        )
    ;

I cannot simplify the grammar at this point, or I’d lose the connection to Grammar/Grammar. The only changes allowed are ordering of choices and lexical tweaks. There can be experiments with rewriting of some rules later.

The expectation over coverage of 46.7% is that progress will be exponential, as a single fix in the grammar makes N more files parseable. A 100% coverage is a matter of more hours of work on PEGifiying the LL(1) original.

I think that I’ll integrate the Python tokenizer before going for 100% coverage, as 71 lines/sec is too slow, and I’m certain that most of the time is being spent keeping track of Python’s lexical idiosyncrasies (newlines within expressions allowed in some and not others, multi-strings, newline escaping, INDENT/DEDENT, etc.). In fact, most of the time I’ve spent so far on the PEG parser has been figuring out the lexical.

After 100% coverage, and the tokenizer, the target will be AST!

AFTERTHOUGH: Mmm. Maybe not hacked, but trying everything to get past the limitations of LL(1)? (some grammar writers call that “hell”).

#45

On cut, the “Packrat Parsers Can Handle Practical Grammars in Mostly Constant Space” paper by Kota Mizushima et al.

I haven’t tried implementing it.

#46

The “calling” rule may also be affected by the cut if there are no choices in the callee:

work = preamble (paragraph)* (long_ending | end) | paragraph 
long_ending = '->' ~ epilogue
#47

I ended up rewriting the rule for typedarglist. I just couldn’t understand the original. There’s now 88% parse coverage of cpython/**/*.py.

typedargslist
    =
    (
    | [typedargs] (vararg|typedarg) [',' _ [typedargs] (kwvararg|typedarg)]
    | [typedargs] (kwvararg|typedarg)
    | (kwvararg | vararg) [[','] TYPE_COMMENT]
    | typedargs
    )
    ;


typedarg
    =
    tfpdef ['='  _ test] &[[','] TYPE_COMMENT]
    ;


typedargs
    =
    {typedarg ',' [TYPE_COMMENT] _ }+
    ;

vararg
    =
    '*' !'*' ~ [tfpdef ~ &[[','] TYPE_COMMENT] ]
    ;


kwvararg
    =
    '**' ~ tfpdef ~ &[[','] TYPE_COMMENT]
    ;
#48

It seems that this new rule does not include PEP 570. After the implementation I added some comments to explain where the full-expanded rule comes from:

#49

That is correct. It seems I didn’t bootstrap from the latest Grammar/Grammar.

There seem to be no instances of that syntax in the Python source code. I’ll create a unit test and fix the grammar.

#50

They are several cases in the latest master.

#51

I’ll check.

I also need to include the files under cpython/test/data which I excluded initially because some of them are intentional bad Python.

I added PEP570 to the grammar, and refactored varargslist (to the style of typedarglist). There’s now 100% parse coverage for the 184 chosen Python files (126 KLOC).

I’ll work on the tokenization before adding any more test cases because the current parsing speed is not good enough nor fun.

#52

Also, although you probably already know, take into account that the actual grammar is more restricted that the Grammar/Grammar file as there is a second pass that further restricts what is allowed on Grammar/Grammar. I think it should be great if we could collect all of these secondary restrictions and push them into the PEG specification.

This is specially tricky as there is no way of proving that the new parser parses exactly the same programs as the old one (is equivalent to the halting problem if I am not mistaken) so for doing that we need to rely on the test suite (as in we need to execute it).