Lark: Parse tree for ambiguous grammar contains `drv` subtree?

Created on 5 Dec 2017 · 6Comments · Source: lark-parser/lark

Hi -- I recently updated the version of Lark I'm using and am trying to debug the following program (which contains a deliberately ambiguous grammar):

from lark import Lark

grammar = '''
stmt : ifthenelse
     | ifthen
     | assign

ifthen : "if" "cond" "then" stmt

ifthenelse : "if" "cond" "then" stmt "else" stmt

assign : "a:=1"

%import common.WS
%ignore WS
'''

foo = 'if cond then if cond then a:=1 else a:=1'

parser = Lark(grammar, start='stmt', ambiguity='explicit')
print(parser.parse(foo))

When I was using lark 0.2.7, I got the following output.

Once I upgraded to any version of lark 0.3.0 or above, I instead get the following output, which I've pretty-printed for readability:

Tree(_ambig, [
    Tree(stmt, [
        Tree(ifthenelse, [
            Tree(stmt, [
                Tree(ifthen, [
                    Tree(stmt, [Tree(drv, [Token(__ANONSTR_4, 'a:=1')])])])]), 
            Tree(stmt, [Tree(drv, [Token(__ANONSTR_4, 'a:=1')])])])]), 
    Tree(stmt, [
        Tree(ifthen, [
            Tree(stmt, [
                Tree(ifthenelse, [
                    Tree(stmt, [Tree(assign, [])]), 
                    Tree(stmt, [Tree(assign, [])])])])])])])

While I appreciate that the output is significantly shorter (it certainly does make debugging easier!), I'm also a little baffled as to why my parse tree contains the subtree Tree(drv, [Token(__ANONSTR_4, 'a:=1')]) instead of Tree(assign, []), which is what I was expecting.

Is this behavior intentional or a bug? (The documentation didn't seem to mention anything about drv subtrees). Either way, is there any way I can get lark to return Tree(assign, []) instead of the drv thing?

Thanks!

(For context, I'm updating some code that pretty-prints ambiguous trees for debugging purposes and ran into this case. I'm sure I could modify my code to work around this issue if necessary, but figured I might as well ask first.)

bug

Source

Michael0x2a

All 6 comments

(Ignore my comment if you saw it. I will address this bug soon)

erezsh on 10 Dec 2017

Hi Michael,
Sorry it took me a while to get to this issue, and thank you for pointing out a bug in Lark's core.
I just pushed a fix to master. Let me know if it solves this issue.

erezsh on 10 Dec 2017

@erezsh -- sorry for the delayed response. I can confirm that the code currently on master resolves my issue. Thanks for the fix!

Michael0x2a on 15 Dec 2017

👍1

Hi -- I still have this issue with the following grammar

from lark import Lark

grammar = '''
start :  "1"
      | "1" "+" start
      | start "-" start
      | "(" start ")"
      | "(" start ")" "-" start
'''

foo = '1+(1+1)-1'

parser = Lark(grammar, start='start', ambiguity='explicit')
print(parser.parse(foo))

Output -

Tree(_ambig, [
    Tree(start, [
        Tree(start, [
            Tree(start, [
                Tree(start, [
                    Tree(drv, [Token(__ANON_0, '1')])
                ])
            ])
        ]),
        Tree(start, [])
    ]),
    Tree(start, [
        Tree(start, [
            Tree(start, [
                Tree(start, [])
            ]),
            Tree(start, [])
        ])
    ]),
    Tree(start, [
        Tree(start, [
            Tree(start, [
                Tree(start, [
                    Tree(drv, [Token(__ANON_0, '1')])
                ])
            ]),
            Tree(start, [])
        ])
    ])
])

Lark Version - v0.7.0
Python - v3.7.3

Thanks!