Lark: Reconstructor enters infinite loop on some example grammars

[julienmalard]

Hello,

I notice that code reconstruction with both the lark and python (2&3) example grammars enters infinite loops (sometimes it exists with an infinite recursion error message; other times it just eats up half of the CPU usage and nearly all of my RAM). JSON works quite well though.

I know that this functionality is still experimental, but since it would be very important for a new project of mine I was wondering if I could contribute to help solve this issue.

Many thanks!
-Julien

[erezsh]

Hi,

Yes, I'm aware that the reconstructor doesn't work well for Python grammars just yet. I'm not sure exactly why and how to fix it. There are two ways that I can think of trying:
1) Reducing the search-space, by transforming the rules in a smarter way (whatever that means)
2) Using LALR to reconstruct, instead of Earley. Of course, right now that won't work, because the Python grammar's reverse is too ambiguous. But I think it should be possible to write in a way that is.

If I sound uncertain and ambiguous, it's because I am. I believe it's possible, but there is still a lot of research needed for this sort of thing!

Please do contribute, either with insights or with code. I'll do my best to provide advice along the way.

Regards,
Erez

[julienmalard]

Hello,

Thanks for the insights. I tried understanding what is going on inside the reconstructor, with modest success, so instead I started making a list of things that work and things that don't. My hope would be to understand which are due to errors in the grammar (i.e., a badly written grammar for code reconstruction purposes) and which are due to errors in Lark (that could be fixed).

Most of these are minimalist examples from errors I encountered while trying to reconstruct with the .lark grammar.
All use LALR. and the following terminals:

_NL: /(\\r?\\n)+\s*/
%import common (WS_INLINE, NUMBER, WORD)
%ignore WS_INLINE

Example 1: Starred object

Grammar

start: (rule | _NL)*
rule: WORD ":" WORD

Code to be parsed and reconstructed

SALUT: BONJOUR

Error
lark.exceptions.ParseError: Infinite recursion detected! (rule <NonTerminal('__anon_star_0') : NonTerminal(Token(RULE, '__anon_star_0'))>)

Comments
Same thing happens with a plus instead of a star. Does not seem to cause a problem when included deeper inside a rule, as in the json parser. This seems like an error in Lark?

Example 2: Starred rule (works!)

Grammar

start: item*
item: NL
    | rule
rule: WORD ":" NUMBER

Code to be parsed and reconstructed

ABC: 1
DEF: 2

Comments
Example 1 works when rephrased as in this example so that no parenthesised object is starred.
However, if NL is written as an ignored terminal _NL, then the parsed tree looks like this:
Tree(start, [Tree(item, []), Tree(item, [Tree(rule, [Token(WORD, 'ABC'), Token(NUMBER, '1')])]), ...
...and the reconstructor fails with
AttributeError: 'WriteTokensTransformer' object has no attribute 'item'
...because the first new line in the code cannot be reconstructed. This seems like a grammar specification error to me?

Example 3: Extra output in reconstructed code

Grammar

start: line*
?line: NL
    | rule
    | "hello"

Code to be parsed and reconstructed

ABC: 1
DEF: 2

Error
Printing the reconstructed text gives, oddly enough, an extra "hello" at the beginning!

ABC:1
DEF:2

Comments
Works fine if line is not preceded by ?.

Example 4: Alias

Grammar

start: line*
line: NL
    | rule
    | "hello" -> hi

Code to be parsed and reconstructed

ABC: 1
hello

Error
AttributeError: 'Tree' object has no attribute 'pos_in_stream'

Comments
Works fine with no alias. If, however, hello is placed before | rule, then we get AttributeError: 'WriteTokensTransformer' object has no attribute 'line' followed by KeyError: 'HELLO'

Sorry for the very long post! Hope this can help improve the reconstructor and also help me find my way around the code. By the way, running the json parser example, I now get lark.exceptions.GrammarError: Using an undefined rule: NonTerminal(Token(RULE, '__anon_star_0')). Any idea why that happened?

Regards,
Julien

[julienmalard]

By the way, the following respecification of the majority of the LARK grammar seems to work and can parse and reconstruct itself!

start: line*

line: NL
    | rule
    | token
    | statement

rule: RULE priority? ":" expansions NL
token: TOKEN priority? ":" expansions NL
priority: "." NUMBER

statement: ignore
    | import

ignore: "%ignore " expansions NL
import: "%import " import_args ["->" TOKEN] NL

import_args: name ("." name)*

expansions: exp_or_alias (VBAR exp_or_alias)*
exp_or_alias: alias | expansion
alias: expansion "->" RULE
expansion: expr*
expr: atom [OP | "~" NUMBER [".." NUMBER]]
atom: group
    | maybe
    | literal_range
    | name
    | (REGEXP | STRING)


name: RULE
    | TOKEN

maybe: "[" expansions "]"
group: "(" expansions ")"
literal_range: STRING ".." STRING

RULE: /!?[_?]?[a-z][_a-z0-9]*/
VBAR: NL? "|"
OP: /[+*][?]?|[?](?![a-z])/
TOKEN: /_?[A-Z][_A-Z0-9]*/
STRING: ESCAPED_STRING "i"?
REGEXP: /\/(?!\/)(\\\/|\\\\|[^\/\n])*?\/[imslux]*/
NL: /(\r?\n)+\s*/
COMMENT: "//" /[^\n]/*

%import common.ESCAPED_STRING
%import common.INT -> NUMBER
%import common.WS_INLINE

%ignore WS_INLINE
%ignore COMMENT

[erezsh]

Thanks, it seems that many of these issues are simply due to the 0.6 upgrade.

Any chance you can pull request these as unit tests? (For example, in a test_reconstructor.py)

[julienmalard]

Sure! Will do.

[erezsh]

Fixed the reconstructor for the given examples (all tests passing!)

I'm sure you can find plenty of new edge-cases. Feel free to add tests for them, and I'll address them when I have the time.

[julienmalard]

Great, thanks so much! I am very eager to try it out. I will try to understand how you fixed these and will add tests (and fixes if I can figure them out) for other edge cases that I come across.

[erezsh]

Not sure why this is still open. Anyway, closing due to inactivity.

[GelaniNijraj]

Has there been any progress on this? I still can't seem to be able to re-construct from python 3 grammar. Just curious.

[erezsh]

There are some conceptual obstacles for making this work.

It's mainly caused by the conditional-collapse operator (?rule).

I will try to explain briefly the main obstacle I'm facing so far, using this toy grammar:

start: z
?z: a ("-" a)*
?a: b "+"
?b: a | "+"

When parsing the text ++, the result is the empty tree of b:

Tree(b, [])

When trying to reconstruct the text from this empty tree, the reconstructor notices that an empty b can be the result of a collapsed and empty a, and an empty a can be the result of a collapsed an empty b, and so on, throwing into an infinite loop.

In other words, any amount of pluses will result in the same tree. Both ++++ and ++++++++ produce:

Tree(b, [])

There may be a simple and obvious solution to this, while still maintaining generality, but for now it eludes me.

My current efforts are in the branch recons_2020 if anyone is brave enough to give it a go :)

[erezsh]

Having said that, if you remove all the question marks that prefix the rules, you will probably get a reconstructable grammar (if that's still useful or not, is another matter)

[julienmalard]

Hello,

I have succeeded in getting reconstruction to work with this modified Python 3 Grammar (through trial and error; not too sure why it works). Hope this helps!

ਪੈਧਾਨ ੩.lark.txt

-Julien

[GelaniNijraj]

Thanks, @julienmalard. Is that only suitable for reconstruction? Because I couldn't parse a simple python 3 program with it.

[julienmalard]

P.S. Regarding the infinite loop, I think I got around the problem by adding a ! to potentially ambiguous rules, forcing the parser to explicitly add the symbols to the tree.

[julienmalard]

Hello,

@GelaniNijraj, I managed to get both to work, parsing and reconstruction. What error are you getting?

-Julien

[GelaniNijraj]

The code I'm trying to parse:

for i in range(1, 100):
    print("Hello, World!")

Here's my program:

class PythonIndenter(Indenter):
    NL_type = "_NEWLINE"
    OPEN_PAREN_types = ["LPAR", "LSQB", "LBRACE"]
    CLOSE_PAREN_types = ["RPAR", "RSQB", "RBRACE"]
    INDENT_type = "_INDENT"
    DEDENT_type = "_DEDENT"
    tab_len = 8

py3 = Lark.open(
    "reconstructable.lark",
    parser="lalr",
    start="file_input",
    postlex=PythonIndenter(),
    propagate_positions=True,
)

with open("program.py") as program_file:
    program = program_file.read()
    original = program
    replacements = []
    tree = py3.parse(program)
    print(tree)
    reconstructed = Reconstructor(py3).reconstruct(tree)
    print(reconstructed)

Here's the error:

lark.exceptions.UnexpectedCharacters: No terminal defined for 'p' at line 2 col 2

        print("Hello, World!")
 ^

Expecting: {'__IGNORE_0', '__IGNORE_1', 'COMMENT'}

[julienmalard]

Hello,

Just tried and works for me. My ਲੱਸੀ package (an experimental programme I am developing to translate programming languages) manages to parse the code (and even translate it to other human languages by switching out grammar rules between the parse and the reconstruction phase). (Test script here; grammar code here).

However, one difference I see is that I am using the recons_work2 branch of Lark. Perhaps that will make the difference?

-Julien

[julienmalard]

@GelaniNijraj
If it is still useful, I made a working example (online) of Python reconstruction here: https://lassi-pakkam.herokuapp.com/
(You can click on the globe to change languages).