SLY(PLY) vs lark

[wqh17101]

There are some questions for me.

1. Can lark support some features like SLY(PLY) such as using decorator to register rule or expression. It will make programmer easy to read and write, I think it is very elegant.
2. I build a system with lexer and parser(transformer) to parse some nested expressions. Using SLY as the backend,and send 1000 expressions to parse cost 1s. But using lack as the backend cost 98s for 1000 expressions. I don`t know why it is so slow for lark.

[erezsh]

1. Lark dispatches to the method matching the rule name (or terminal), for visitors and transformers. I think it's pretty elegant. If you want to use decorators instead, just make sure that the function you return is named after the rule or terminal.
2. I don't know why it's slow for you. But try to check if the time comes from parsing (calling the .parse() function), or from generating the parser (i.e. creating the Lark instance).

[wqh17101]

lark cost 1.0949981212615967s
sly cost 0.1569974422454834s

faster than before but also more slower than SLY

[erezsh]

Don't be silly.

You're not parsing with sly, only lexing, which is of course faster.

list(lexer.tokenize("hello('a') and hello('b')"))

[wqh17101]

Don't be silly.

You're not parsing with sly, only lexing, which is of course faster.

list(lexer.tokenize("hello('a') and hello('b')"))

right,then i replace p.parse with p.lex for lark.
got

lark cost 0.2506539821624756s
sly cost 0.12274885177612305s

[erezsh]

So, we went from 100x slower to 2x slower.

Does sly do automatic line counting?

[ThatXliner]

Does sly do automatic line counting?

Reading an example from their docs, I'm guessing no

[wqh17101]

Here is a pipeline test contain lex and parse(transform)

import ast
import time

from lark import Lark, Transformer, v_args, Token
from sly import Lexer, Parser


def lark_test():
    p = Lark("""
    LPAREN:/\s*\(\s*/
    RPAREN:/\s*\)\s*/
    ?start: and_expr
    and_expr: func_call "and" func_call -> logic
    func_call: "hello" LPAREN value RPAREN -> hello
    
    
    name: NAME
    value: STRING ->string
    %import python (NAME, STRING)
    %import common (WS)
    %ignore WS
    """, parser="lalr")

    @v_args(inline=True)
    class BaseParser(Transformer):

        def expr(self, *prod):
            v = prod[0]
            try:
                if isinstance(v, Token):
                    v = v.value
                if isinstance(v, str):
                    v = ast.literal_eval(v)
                return v
            except:
                return v

        def string(self, s):
            return ast.literal_eval(s)

        def logic(self, *prod):
            return prod[0] + prod[1]

        def hello(self, *prod):
            return prod[1]

        pair = tuple
        object = dict

        null = lambda self, _: None
        true = lambda self, _: True
        false = lambda self, _: False

    start = time.time()
    for i in range(10000):
        tree = p.parse("hello('a') and hello('b')")
        res = BaseParser().transform(tree)
    print(res)
    print(f"lark cost {time.time() - start}s")


def sly_test():
    class BaseLexer(Lexer):
        """
        基础lexer
        """
        tokens = ['LPAREN', 'RPAREN', 'STRING', "LSQB", "RSQB", "COMMA", 'RESERVED_KEYWORDS', "number"]
        reserved_keys = ["hello", "and"]
        reserved = dict(zip(reserved_keys, [x.upper() for x in reserved_keys]))
        tokens = set(tokens) | set(reserved.values())
        COMMA = r'\,'
        LPAREN = r'\('
        LSQB = r'\['
        RPAREN = r'\)'
        RSQB = r']'
        STRING = r'\".*?\"|\'.*?\''
        ignore = " \t"

        @_(r'[0-9]+(\.[0-9]+)?')
        def number(self, tok):
            """
            number
            :param tok:
            :return:
            """
            try:
                tok.value = float(tok.value)
            except Exception:
                raise ValueError(f"Integer value too large, '{tok.value}' , lineno: {tok.lineno} , colno: {tok.index}")
            if int(tok.value) == tok.value:
                tok.value = int(tok.value)
            return tok

        @_(r'[a-zA-Z_][a-zA-Z_0-9]*')
        def reserved_keywords(self, tok):
            """
            关键字
            :param tok:
            :return:
            """
            # Check for reserved words
            tok.type = self.reserved.get(tok.value, 'RESERVED_KEYWORDS')
            return tok

        def error(self, tok):
            """
            lexer error
            :param tok:
            :return:
            """
            err_msg = "Illegal character '{}' , lineno: {} , colno: {}".format(
                self.text[self.index], tok.lineno, tok.index)
            self.index += 1
            raise ValueError(err_msg)

    class BaseParser(Parser):
        """
        Base Parser
        """
        tokens = BaseLexer.tokens
        precedence = (
            ('left', 'COMMA'),
        )

        def __init__(self):
            super().__init__()

        def error(self, token):
            """
            parser error
            :param token:
            :return:
            """
            err_msg = ""
            try:
                if token.value is not None:
                    err_msg = f"Syntax error at '{token.value}' , lineno: {token.lineno} , colno: {token.index}"
            except AttributeError:
                err_msg = "Syntax error: Expression is incomplete. "
            raise ValueError(err_msg)

        @_("HELLO LPAREN STRING RPAREN")
        def expression(self, production):
            """

            :param production:
            :return:
            """
            return ast.literal_eval(production[2])

        @_("expression AND expression")
        def expression(self, production):
            """

            :param production:
            :return:
            """
            return production[0] + production[2]

    lexer = BaseLexer()
    parser = BaseParser()
    start = time.time()
    for i in range(10000):
        s = "hello('a') and hello('b')"
        res = parser.parse(x for x in lexer.tokenize(s))
    print(res)
    print(f"sly cost {time.time() - start}s")


if __name__ == '__main__':
    lark_test()
    sly_test()

res:

lark cost 1.126863718032837s
sly cost 0.4023284912109375s

[erezsh]

Pass the transformer to the Lark instance using transformer=BaseParser() instead of doing the transform yourself.

[wqh17101]

i try something more complex like wrap every result of node with a class CateRes to check. And use maybe_placeholders = False and lexer = "basic"

import ast
import time

from lark import Lark, Transformer, v_args, Token
from sly import Lexer, Parser


class CateRes:
    def __init__(self, value):
        self.val = value

    def __repr__(self):
        return self.val


def lark_test():
    @v_args(inline=True)
    class BaseParser(Transformer):

        def expr(self, *prod):
            v = prod[0]
            try:
                if isinstance(v, Token):
                    v = v.value
                if isinstance(v, str):
                    v = ast.literal_eval(v)
                return v
            except:
                return v

        def string(self, s):
            return ast.literal_eval(s)

        def logic(self, *prod):
            v = prod[0].val + prod[1].val
            return CateRes(v)

        def hello(self, *prod):
            return CateRes(prod[1])

        def get(self, *prod):
            return CateRes(prod[1].val[0])

        pair = tuple
        object = dict

        null = lambda self, _: None
        true = lambda self, _: True
        false = lambda self, _: False

    p = Lark("""
    LPAREN:/\s*\(\s*/
    RPAREN:/\s*\)\s*/
    my_string: STRING ->string
    ?start: cate_res
    cate_res: log_res -> expr
             | hello_res -> expr
             | get_res -> expr
    log_res: cate_res "and" cate_res -> logic
    hello_res: "hello" LPAREN my_string RPAREN -> hello
    get_res: "get" LPAREN cate_res RPAREN -> get


    name: NAME
    %import python (NAME, STRING)
    %import common (WS)
    %ignore WS
    """, parser="lalr", transformer=BaseParser(), lexer="basic", maybe_placeholders=False)

    start = time.time()
    for i in range(10000):
        # s = "get(hello('a'))"
        s = "get(hello('a') and hello('b'))"
        res = p.parse(s)
        # res = BaseParser().transform(tree)
    print(res)
    print(f"lark cost {time.time() - start}s")


def sly_test():
    class BaseLexer(Lexer):
        """
        基础lexer
        """
        tokens = ['LPAREN', 'RPAREN', 'STRING', "LSQB", "RSQB", "COMMA", 'RESERVED_KEYWORDS', "number"]
        reserved_keys = ["hello", "and", "get"]
        reserved = dict(zip(reserved_keys, [x.upper() for x in reserved_keys]))
        tokens = set(tokens) | set(reserved.values())
        COMMA = r'\,'
        LPAREN = r'\('
        LSQB = r'\['
        RPAREN = r'\)'
        RSQB = r']'
        STRING = r'\".*?\"|\'.*?\''
        ignore = " \t"

        @_(r'[0-9]+(\.[0-9]+)?')
        def number(self, tok):
            """
            number
            :param tok:
            :return:
            """
            try:
                tok.value = float(tok.value)
            except Exception:
                raise ValueError(f"Integer value too large, '{tok.value}' , lineno: {tok.lineno} , colno: {tok.index}")
            if int(tok.value) == tok.value:
                tok.value = int(tok.value)
            return tok

        @_(r'[a-zA-Z_][a-zA-Z_0-9]*')
        def reserved_keywords(self, tok):
            """
            :param tok:
            :return:
            """
            # Check for reserved words
            tok.type = self.reserved.get(tok.value, 'RESERVED_KEYWORDS')
            return tok

        def error(self, tok):
            """
            lexer error
            :param tok:
            :return:
            """
            err_msg = "Illegal character '{}' , lineno: {} , colno: {}".format(
                self.text[self.index], tok.lineno, tok.index)
            self.index += 1
            raise ValueError(err_msg)

    class BaseParser(Parser):
        """
        Base Parser
        """
        tokens = BaseLexer.tokens
        precedence = (
            ('left', 'COMMA'),
        )

        def __init__(self):
            super().__init__()

        def error(self, token):
            """
            parser error
            :param token:
            :return:
            """
            err_msg = ""
            try:
                if token.value is not None:
                    err_msg = f"Syntax error at '{token.value}' , lineno: {token.lineno} , colno: {token.index}"
            except AttributeError:
                err_msg = "Syntax error: Expression is incomplete. "
            raise ValueError(err_msg)

        @_("HELLO LPAREN STRING RPAREN")
        def expression(self, production):
            """

            :param production:
            :return:
            """
            return CateRes(ast.literal_eval(production[2]))

        @_("GET LPAREN expression RPAREN")
        def expression(self, production):
            """

            :param production:
            :return:
            """
            return CateRes((production[2].val[0]))

        @_("expression AND expression")
        def expression(self, production):
            """

            :param production:
            :return:
            """
            return CateRes(production[0].val + production[2].val)

    lexer = BaseLexer()
    parser = BaseParser()
    start = time.time()
    for i in range(10000):
        # s = "hello('a') and hello('b')"
        s = "get(hello('a') and hello('b'))"
        res = parser.parse(x for x in lexer.tokenize(s))
    print(res)
    print(f"sly cost {time.time() - start}s")


if __name__ == '__main__':
    lark_test()
    sly_test()

got

a
lark cost 1.0387217998504639s
a
sly cost 0.4671924114227295s

so, it seems like sly`s performance is twice than lark

[erezsh]

Sure seems that way, though I didn't look deeply into it.

Performance against Lark-cython is much closer tho

lark cost 0.7475757598876953s
sly cost 0.6477043628692627s

Code:

    @v_args(inline=True)
    class BaseParser(Transformer):

        def expr(self, v, w):
            try:
                return ast.literal_eval(v.value)
            except:
                return v

        def string(self, s):
            return ast.literal_eval(s.value)

        def logic(self, a, b):
            v = a.val + b.val
            return CateRes(v)

        def hello(self, a):
            return CateRes(a)

        def get(self, a):
            return CateRes(a)

        pair = tuple
        object = dict

        null = lambda self, _: None
        true = lambda self, _: True
        false = lambda self, _: False

    import lark_cython
    p = Lark("""
    string: STRING
    ?start: expr
    ?expr: expr "and" expr
        | hello_res
        | get_res
    
    hello_res: "hello" "(" string ")" -> hello
    get_res: "get" "(" expr ")" -> get


    name: NAME
    %import python (NAME, STRING)
    %import common (WS)
    %ignore WS
    """, parser="lalr", transformer=BaseParser(), lexer="basic", maybe_placeholders=False, _plugins=lark_cython.plugins)

[erezsh]

However, in more objective comparisons, the gap between SLY and Lark (pure python) is very small.

https://github.com/goodmami/python-parsing-benchmarks

So it's possible that something small but significant about your benchmark is off.

[wqh17101]

I will try lark_cython.plugins .
But so far as I know，sly is pure python lib not a cython one. So i dont sure that the data of cython-sly in https://github.com/goodmami/python-parsing-benchmarks` is the real cython-sly or according to python-sly.
Also i think cython-sly will lead if it really exist.
So, maybe you can learn something from SLY to accelerate lark.

[erezsh]

I think for a real use-case, the difference won't be so drastic. But I agree, it's worth checking why there's such a difference in performance.