Giter VIP home page Giter VIP logo

pog's Introduction

Pog

Build Status Build Status Documentation Status codecov

Pog is C++17 library for generating LALR(1) parsers. It splits definitions of parser into:

  1. Declaration of tokens (regular expressions describing how the input should be tokenized)
  2. Grammar rules over tokens from tokenization phase

If you are familiar with tools like yacc + lex or bison + flex then this should be already known concept for you. This library is header-only itself but requires RE2 library which does not come with header-only version. The plan is to be completely header-only in the future.

See documentation for more information about the installation and usage of the library.

Why make another parser generator?

I had idea for project like this for a few years already, back when I used bison + flex for a school project. The advantage of bison + flex is that it generates LALR(1) parser. These parsers are very good for parsing usual programming languages constructs without any transformations of the grammar (such as removal of left-recursion, making sure that no 2 rules have same prefix). Their approach of splitting the process into tokenization and parsing makes it much easier to write the actual grammar without having it cluttered with things like whitespaces, comments and other things that can be ignored and don't have to be present in the grammar itself. The disadvantage of bison + flex is that you have to have these installed on your system because they are standalone tools which will generate you C/C++ code. Maintaining build system which uses them and works on Linux, Windows and macOS is not an easy task. For a long time, bison was also not able to work with modern C++ features such as move semantics. It should be supported as of now (3.4) but a lot of Linux distributions still don't have this version and some stable distros won't have for a very long time. There are also other options than bison + flex in C++ world such as Boost.Spirit or PEGTL which are all amazing but they all have some drawbacks (LL parsers, cluttered and hard to maintain grammars, inability to specify operator precedence, ...). This library aims to provide what was missing out there -- taking philosophy of bison + flex and putting it into pure C++ while still generating LALR(1) parser.

The implemented parser generator is based on algorithms from papers Efficient computation of LALR(1) look-ahead sets, Development of an LALR(1) Parser Generator, Simple computation of LALR(1) lookahead sets and book Compilers: Principles, Techniques, and Tools (2nd Edition).

Roadmap

Things to do before 1.0.0

  • Tokenizer action on end of input
  • Support for states in tokenizer (BEGIN, END like behavior in flex)
  • Generate debugging report (text file parsing table, states, lookahead sets, graphviz LALR automaton, ...)
  • Windows & macOS Build
  • Tests
  • Code Coverage
  • CI pipeline (Travis CI, AppVeyor)
  • Packaging (ZIP, RPM, DEB, ... + getting package into repositories)
  • Sphinx Docs (+ Read The Docs integration)

Things to do after 1.0.0

  • Error Recovery
  • Code Cleanup :)
  • Own implementation for tokenizer to be header-only (DFA)
  • Lightweight iterator ranges

Requirements

  • fmt (5.3.0 or newer)
  • re2 (2019-09-01 or newer)

pog's People

Contributors

metthal avatar tadeaskucera avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar

pog's Issues

Provide expected symbols in case of syntax error

As of right now, pog raises an exception in case of syntax error. It takes all symbols that are expected on the input in the particular parsing state it is in at the moment and serializes it into the string of parser error. So you'll get something like unexpected symbol <XYZ>, expected one of <A>, <B>, <C>, ....

It would be proficient for users of pog to have these expected symbols available for the purpose of building language servers. Instead of raising an exception, please return something like ParsingResult object which would contain all of these and would essentially bear the same information as the exception in case of syntax error.

Add command-line tool wich will generate C++ file with parser

Pog is able to generate parser during the runtime but it takes some time to actually create the parser itself. In the same way as bison and other parser generators, we should add CLI tool which generates C++ files with the parser itself. It would give an option to people which do not want to generate parser during the runtime.

Even though pog was created as a mean to replace bison because of problems of integrating it into CMake build system, we can still use the generated C++ file without actually running the pog each build.

when using "parser.enter_tokenizer_state" at midrule will cause a Syntax error.

The reason :
the parser first tokenize a token by the _tokens at @default_state , then find a action for reduce. but when using "parser.enter_tokenizer_state" at midrule , we hope to tokenize a token by the _tokens at @state_after_enter. So we need first execute midrule then to tokenize a token.
(actually, not only using midrule wil cause this error, but also using "parser.enter_tokenizer_state" at production is so. However, we can limit it to only midrule for simpleness)
Fix thinking
Adding a special empty symbol use for lookahead. when current rule is a midrule , the key of _action_table use the empty symbol instead of real next_symbol for searching action. then we can try search a maybe_action first by using empty symbol, if not finding an action, then get next token for searching action.

hoping fix it , thanks.
๐Ÿ™๐Ÿ™๐Ÿ™

Assertion failed: false && "Reduction happened but corresponding GOTO table record is empty"

Help , please .

#include <iostream>
#include <any>

#define POG_DEBUG_TOKENIZER
#define POG_DEBUG_PARSER
#include "pog/pog.h"

using namespace pog;
using Value = std::any;

int main(int argc, char const *argv[])
{
    Parser<Value> parser;

    parser.token("\\s+");
    parser.token("test").symbol("test").action(
        [](auto&& sv) {
            return sv;
        });

    parser.rule("TEST_LIST")
        .production("TEST_LIST", "TEST",
            [](auto&& p){ return std::move(p); })
        .production(
            [](auto&& p){ return std::move(p); })
        ;

    parser.rule("TEST")
        .production("test", 
            [](auto&& p){ return std::move(p); })
        ;

    parser.set_start_symbol("TEST_LIST");
    std::cout << parser.prepare().to_string() << std::endl;

    try{
        auto v = parser.parse(std::cin);
    }
    catch (const SyntaxError& err) {
        //HtmlReport html(parser);
        //html.save("parser.html");
        std::cerr << err.what()  << std::endl;
    }

    return 0;
}

DEBUG LOG:

test                                                                                                                                                                                                                                                                                        
^Z                                                                                                                                                                                                                                                                                          
[tokenizer] Matched 'test' with token 'test' (index 2)                                                                                                                                                                                                                                      
[parser] Tokenizer returned new token with symbol 'test'                                                                                                                                                                                                                                    
[parser] Top of the stack is state 0                                                                                                                                                                                                                                                        
[parser] Reducing by rule 'TEST_LIST -> <eps>'                                                                                                                                                                                                                                              
[parser] Pushing state 1                                                                                                                                                                                                                                                                    
[parser] Reusing old token with symbol 'test'                                                                                                                                                                                                                                               
[parser] Top of the stack is state 1                                                                                                                                                                                                                                                        
[parser] Shifting state 2                                                                                                                                                                                                                                                                   
[tokenizer] Matched '                                                                                                                                                                                                                                                                       
' with token '\s+' (index 1)                                                                                                                                                                                                                                                                
[tokenizer] Reached end of input                                                                                                                                                                                                                                                            
[tokenizer] Matched '' with token '$' (index 0)                                                                                                                                                                                                                                             
[tokenizer] At the end of input                                                                                                                                                                                                                                                             
[parser] Tokenizer returned new token with symbol '@end'                                                                                                                                                                                                                                    
[parser] Top of the stack is state 2                                                                                                                                                                                                                                                        
[parser] Reducing by rule 'TEST -> test'                                                                                                                                                                                                                                                    
[parser] Pushing state 3                                                                                                                                                                                                                                                                    
[parser] Reusing old token with symbol '@end'                                                                                                                                                                                                                                               
[parser] Top of the stack is state 3                                                                                                                                                                                                                                                        
[parser] Reducing by rule 'TEST_LIST -> TEST_LIST TEST'                                                                                                                                                                                                                                     
Assertion failed: false && "Reduction happened but corresponding GOTO table record is empty", file external\pog\include\pog/parser.h, line 206  

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.