Parser fails on every 2nd rule - understanding problem

[DannyBoyKN]

This repo is quite a bit old, not sure is still actively maintained and supported.
Hope to get some feedback of my simple test setup trying to parse C-like basic string data.

This is my test setup, called it myparser.py:

from sly import Parser
from sly import Lexer

class myLexer(Lexer):

    tokens = { FILE, ID,
                INCLUDE,
                TYPE, IS, INTEGER }

    # String containing ignored characters
    ignore = ' \t'
    literals = ['<','>','[',']',';','.','/',',']

    FILE= r'[\w./]+[\w/]+[.]txt'

    ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
    # Special cases
    ID['include'] = INCLUDE
    ID['type'] = TYPE
    ID['is'] = IS

    @_(r'0[xX][0-9a-fA-F]+',    # LiteralIntHex
       r'0[0-7]+',              # LiteralIntOct
       r'[1-9][0-9]+')          # LiteralIntDec
    def INTEGER(self, t):
        if t.value.startswith('0x'):
            t.value = int(t.value[2:], 16)
        elif t.value.startswith('0'):
            t.value = int(t.value[1:], 8)
        else:
            t.value = int(t.value)
        return t
    
    # Ignored pattern
    @_(r'/\*(.|\n)*?\*/',   # Comment (C-Style)
       r'//.*\n')           # Comment (C++-Style)
    def ignore_comments(self, t):
        self.lineno += t.value.count('\n')

    # Line number tracking
    @_(r'\n+')
    def newline(self, t):
        self.lineno = t.lineno + t.value.count('\n')
    
    def error(self, t):
        self.index += 1
        print(f"{self.lineno}: Illegal character at index {self.index} '{t.value[0]}'! STOP")
    
class myParser(Parser):
    tokens = myLexer.tokens

    @_("includedef")
    def entry(self, p):
        return p.includedef
    @_("typedef")
    def entry(self, p):
        return p.typedef


    @_("INCLUDE '<' FILE '>'")
    def includedef(self, p):
        print(p.INCLUDE, p.FILE)

    @_('TYPE ID IS ID "[" INTEGER "]" ";"')
    def typedef(self, p):
        print(p.TYPE, p.ID0, p.ID1, f"[{p.INTEGER}]")

if __name__ == '__main__':
    text = \
'''
/*============================================================================*/
include <../myfile.txt>

type mytype_t is uint32[40];
'''
    lexer = myLexer()
    parser = myParser()

    tok = lexer.tokenize(text)
    parser.parse(tok)

When I run it parsing the input text I get a failure for the type entry:

$ python myparser.py 
include ../myfile.txt
sly: Syntax error at line 5, token=TYPE

If I invert the order of the include and type lines:

type mytype_t is uint32[40];
include <../myfile.txt>

I get again the error on the 2nd line:

$ python myparser.py 
type mytype_t uint32 [40]
sly: Syntax error at line 4, token=INCLUDE

Couldn't figure out where is my failure 😞

The debug output seems to be ok for me:

Grammar:

Rule 0     S' -> entry
Rule 1     entry -> typedef
Rule 2     entry -> includedef
Rule 3     includedef -> INCLUDE < FILE >
Rule 4     typedef -> TYPE ID IS ID [ INTEGER ] ;

Terminals, with rules where they appear:

;                    : 4
<                    : 3
>                    : 3
FILE                 : 3
ID                   : 4 4
INCLUDE              : 3
INTEGER              : 4
IS                   : 4
TYPE                 : 4
[                    : 4
]                    : 4
error                : 

Nonterminals, with rules where they appear:

entry                : 0
includedef           : 2
typedef              : 1


state 0

    (0) S' -> . entry
    (1) entry -> . typedef
    (2) entry -> . includedef
    (4) typedef -> . TYPE ID IS ID [ INTEGER ] ;
    (3) includedef -> . INCLUDE < FILE >
    TYPE            shift and go to state 4
    INCLUDE         shift and go to state 5

    entry                          shift and go to state 1
    typedef                        shift and go to state 2
    includedef                     shift and go to state 3

state 1

    (0) S' -> entry .


state 2

    (1) entry -> typedef .
    $end            reduce using rule 1 (entry -> typedef .)


state 3

    (2) entry -> includedef .
    $end            reduce using rule 2 (entry -> includedef .)


state 4

    (4) typedef -> TYPE . ID IS ID [ INTEGER ] ;
    ID              shift and go to state 6


state 5

    (3) includedef -> INCLUDE . < FILE >
    <               shift and go to state 7


state 6

    (4) typedef -> TYPE ID . IS ID [ INTEGER ] ;
    IS              shift and go to state 8


state 7

    (3) includedef -> INCLUDE < . FILE >
    FILE            shift and go to state 9


state 8

    (4) typedef -> TYPE ID IS . ID [ INTEGER ] ;
    ID              shift and go to state 10


state 9

    (3) includedef -> INCLUDE < FILE . >
    >               shift and go to state 11


state 10

    (4) typedef -> TYPE ID IS ID . [ INTEGER ] ;
    [               shift and go to state 12


state 11

    (3) includedef -> INCLUDE < FILE > .
    $end            reduce using rule 3 (includedef -> INCLUDE < FILE > .)


state 12

    (4) typedef -> TYPE ID IS ID [ . INTEGER ] ;
    INTEGER         shift and go to state 13


state 13

    (4) typedef -> TYPE ID IS ID [ INTEGER . ] ;
    ]               shift and go to state 14


state 14

    (4) typedef -> TYPE ID IS ID [ INTEGER ] . ;
    ;               shift and go to state 15


state 15

    (4) typedef -> TYPE ID IS ID [ INTEGER ] ; .
    $end            reduce using rule 4 (typedef -> TYPE ID IS ID [ INTEGER ] ; .)

I would appreciate if anyone could tell me where's my error.

[MicahGale]

This repo is quite a bit old, not sure is still actively maintained and supported.

No*, per the README

The SLY project is no longer making package-installable releases. It's fully functional, but if choose to use it, you should vendor the code into your application. SLY has zero-dependencies. Although I am semi-retiring the project, I will respond to bug reports and still may decide to make future changes to it depending on my mood. I'd like to thank everyone who has contributed to it over the years. --Dave

I think this issue might be because the starting symbol is not accurate for this grammar.
This is the symbol that once it is fully parsed the parsing should be complete. So for parsing you don't want includedef as the starting, because that completely makes it impossible to parse a typingdef.

Options:

1. Make a "file-level" symbol that treats a single file as a plurality of includedef and typingdef or something more complicated.
2. Make larger symbol that is includedef OR typingdef and then chunk your parsing line by line. I have some examples of how to "chunk" an input if you are interested.

[DannyBoyKN]

(1) something like that?

    ...
    @_('entries',
       '')
    def file(self, p):
        pass

    @_('entries entry')
    def entries(self, p):
        pass
    @_('entry')
    def entries(self, p):
        pass

    @_('includedef')
    def entry(self, p):
        return p.includedef
    @_('typedef')
    def entry(self, p):
        return p.typedef
    ....

I was trying similar setups and debugging now for days without success but that one actually works ! 😄

My starting BNF was this

entry = includedef
      | typedef

with the small adaption now

file = (entries)*
entries = entries entry
        | entry
entry = includedef
      | typedef

looks strange .... I'll need to think about that .... 🤔

(2) Chunks

Yes, please

[MicahGale]

Yes I think that grammar looks correct. If you wanted to you could skip the file rule as it looks (at least right now) like a wrapper for file. Also you can specify multiple rules for one function, so it might be clear to say:

    @_('entry', 'entries entry')
    def entries(self, p):
        pass
    @_('includedef', 'typedef')
    def entry(self, p):
        return p[0]

Note that by default in entries if you just return p you will end up with a massively recursive structure so you may want to create a list for entries and append entry to it every time (if you aren't doing so already).

I'm not an expert on Context-free grammars.
I found that the textbook Engineering a Compiler helped a lot with understanding these grammars.

"chunking"

So I am using sly in MontePy, which has to parse a domain-specific language for the Monte Carlo N-Particle (MCNP) code, which can was designed for punch cards.

Quick overview: a file is made of three blocks: cells, surfaces, and "data" each made of multiple "inputs" that define a single cell, surface, material, etc. These inputs are 1+ lines long. If multiple lines are given for an input you have to somehow designate a "continue" with either & or 5 spaces at the start.

So how I handle "chunking" is that prior to parsing the file is split into these inputs via read_data. This just does simple string operations to find these continue lines and creates an Input object to represent all of these lines (this parser technically is a very simple regular parser). The Input object also is used to decide which lexer to use based on which block it is in (yes, the keywords do change between blocks). Then the input is parsed with the proper parser based on which block it is in*.
Here is an example for parsing a cell input.
Note: I did some really jank things to allow subclassing of parsers, so not all rules are defined here, for completeness you also need to look at parser_base. I would not recommend doing what I did with subclassing.
Also some of the rules look overly complicated: I am generating a concrete syntax tree, and not an abstract one, so whitespace and comments can't be thrown away.

Shameless plug: if you want to know more I actually wrote a conference paper on this parsing paradigm.

*the data block is a complexity I'm ignoring here.