lark-parser

Node depth encoded as number of stars


Documents in this language look like

* A top-level Headline 

  Some text about that headline.

** Sub-Topic 1

Text about the sub-topic 1.

*** Sub-sub-topic

 More text here about the sub-sub-topic

** Sub-Topic 2

   Extra text here about sub-topic 2

*** Other Sub-sub-topic

 More text here about the other sub-sub-topic

The number of depth levels is unlimited. I'm wondering how to get a parser that'll build the nested trees appropriately. I've been looking at the indenter example for inspiration, but I haven't figured it out.


Solution

  • The problem would require a context-sensitive grammar, so we use the work-around from the indenter example you linked:

    We write a custom postlex processor that keeps a stack of the observed indent levels. When a star token (*, **, ***, ...) is read, the stack is popped until the indent level on the stack is smaller, then the new level is pushed on the stack. For each push/pop, corresponding INDENT/DEDENT helper tokens are injected into the token stream. These helper tokens can then be used in the grammar to obtain a parse tree that reflects the nesting level.

    from lark import Lark, Token
    
    tree_grammar = r"""
        start: NEWLINE* item*
        item: STARS nest
        nest: _INDENT (nest | LINE+ item*) _DEDENT
        STARS.2: /\*+/
        LINE.1: /.*/ NEWLINE
        %declare _INDENT _DEDENT
        %import common.NEWLINE
    """
    
    class StarIndenter():
      STARS_type = 'STARS'
      INDENT_type = '_INDENT'
      DEDENT_type = '_DEDENT'
    
      def dedent(self, level, token):
        """ When the given level leaves the current nesting of the stack,
            inject corresponding number of DEDENT tokens into the stream.
        """
        while level <= self.indent[-1]:
          pop_level = self.indent.pop()
          pop_diff = pop_level - self.indent[-1]
          for _ in range(pop_diff):
            yield token
    
      def handle_stars(self, token):
        """ Handle tokens of the form '*', '**', '***', ...
        """
    
        level = len(token.value)
    
        dedent_token = Token.new_borrow_pos(self.DEDENT_type, '', token)
        yield from self.dedent(level, dedent_token)
    
        diff = level-self.indent[-1]
        self.indent.append(level)
    
        # Put star token into stream
        yield token
    
        indent_token = Token.new_borrow_pos(self.INDENT_type, '', token)
        for _ in range(diff):
          yield indent_token
    
      def process(self, stream):
        self.indent = [0]
    
        # Process token stream
        for token in stream:
          if token.type == self.STARS_type:
            yield from self.handle_stars(token)
          else:
            yield token
    
        # Inject closing dedent tokens
        yield from self.dedent(1, Token(self.DEDENT_type, ''))
    
      # No idea why this is needed
      @property
      def always_accept(self):
        return ()
    
    parser = Lark(tree_grammar, parser='lalr', postlex=StarIndenter())
    

    Note the STARS terminal has been assigned higher priority than LINES (via .2 vs. .1), to prevent LINES+ from eating up lines starting with a star.

    Using a stripped down version of your example:

    test_tree = """
    * A
    ** AA
    *** AAA
    ** AB
    *** ABA
    """
    
    print(parser.parse(test_tree).pretty())
    

    Results in:

    start
      
    
      item
        *
        nest
           A
    
          item
            **
            nest
               AA
    
              item
                ***
                nest     AAA
    
          item
            **
            nest
               AB
    
              item
                ***
                nest     ABA