4 ms·

Many parsing algorithms were designed with the idea that the input cannot stored in memory as a whole and that you need the parse the file from start to end. Ho

Many parsing algorithms were designed with the idea that the input cannot stored in memory as a whole and that you need the parse the file from start to end. However, nowadays, memory is usually not a problem, especially not for parsing files that are editted by humans. Who is going to use a gigebyte sized source file? When you store the source in memory this allows for parsing algorithms that can go backwards. I implemented a recursive decent algorithm with back-tracking which stores all parsed non-terminals at the location where they were first parsed. This results in a simple and relatively fast parser. I used it to implement an interpretting parser, which takes a grammar and input file and parses the input file according to the grammar, returning an abstract parse tree. Actually the parse takes an abstract parse tree of the grammar to parse the input. The grammar is parsed by the interpretting parser itself using a hard coded abstract parse tree of the grammar of the grammar. See https://github.com/FransFaase/IParse https://github.com/FransFaase/IParse

tom_mellior 9y ago
> Who is going to use a gigebyte sized source file? I used to mess around with the ROSE C++ source-to-source transformation framework (http://rosecompiler.org/ http://rosecompiler.org/). One of the files in there (defining the AST structure for representing C++ programs) was about 100,000 lines of autogenerated code. It wasn't heavily templated, I think, but it did pull in a bunch of standard C++ headers. I could imagine the whole preprocessed thing approaching a gigabyte.
- fjfaase 9y ago
  Yes, parsing generated source code might be a problem, and yes, C++ preprocessing adds a lot as well. But even 100,000 lines of 80 characters whould still be (a little less than) 8 Mbyte. I did not design my interpretting parser with maximum performance as a goal, but just to have a parser that is easy to use and allows for much flexibility with respect to the grammar specification. I feel that it is a good parser for domain specific languages.
  - tom_mellior 9y ago
    > even 100,000 lines of 80 characters whould still be (a little less than) 8 Mbyte Um, you're right of course. I did do the same math in my head but somehow got confused by two orders of magnitude.

tom_mellior 9y ago

> Who is going to use a gigebyte sized source file? I used to mess around with the ROSE C++ source-to-source transformation framework (http://rosecompiler.org/ http://rosecompiler.org/). One of the files in there (defining the AST structure for representing C++ programs) was about 100,000 lines of autogenerated code. It wasn't heavily templated, I think, but it did pull in a bunch of standard C++ headers. I could imagine the whole preprocessed thing approaching a gigabyte.

fjfaase 9y ago
Yes, parsing generated source code might be a problem, and yes, C++ preprocessing adds a lot as well. But even 100,000 lines of 80 characters whould still be (a little less than) 8 Mbyte. I did not design my interpretting parser with maximum performance as a goal, but just to have a parser that is easy to use and allows for much flexibility with respect to the grammar specification. I feel that it is a good parser for domain specific languages.
- tom_mellior 9y ago
  > even 100,000 lines of 80 characters whould still be (a little less than) 8 Mbyte Um, you're right of course. I did do the same math in my head but somehow got confused by two orders of magnitude.