{"action":"closed","issue":{"url":"https://api.github.com/repos/bitwalker/combine/issues/5","repository_url":"https://api.github.com/repos/bitwalker/combine","labels_url":"https://api.github.com/repos/bitwalker/combine/issues/5/labels{/name}","comments_url":"https://api.github.com/repos/bitwalker/combine/issues/5/comments","events_url":"https://api.github.com/repos/bitwalker/combine/issues/5/events","html_url":"https://github.com/bitwalker/combine/issues/5","id":136820223,"number":5,"title":"question about parsing performance / time complexity","user":{"login":"sunaku","id":9863,"avatar_url":"https://avatars.githubusercontent.com/u/9863?v=3","gravatar_id":"","url":"https://api.github.com/users/sunaku","html_url":"https://github.com/sunaku","followers_url":"https://api.github.com/users/sunaku/followers","following_url":"https://api.github.com/users/sunaku/following{/other_user}","gists_url":"https://api.github.com/users/sunaku/gists{/gist_id}","starred_url":"https://api.github.com/users/sunaku/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sunaku/subscriptions","organizations_url":"https://api.github.com/users/sunaku/orgs","repos_url":"https://api.github.com/users/sunaku/repos","events_url":"https://api.github.com/users/sunaku/events{/privacy}","received_events_url":"https://api.github.com/users/sunaku/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-02-26T21:34:22Z","updated_at":"2016-02-26T22:34:52Z","closed_at":"2016-02-26T22:34:52Z","body":"Hello,\r\n\r\nI would like to migrate from leex and yecc (Erlang's versions of the famous lex and yacc LALR parsing toolset) to this library but I'm concerned about the time complexity of top-down recursive descent parsing because my Elixir program needs to parse input files that can be several gigabytes in size. :scream:\r\n\r\nI skimmed through this library's code and didn't find any use of backtracking, which is the main cause of exponential time complexity in recursive descent parsers, so it _appears_ that this library can determine whether a given input string (1) parses correctly or (2) has errors in linear time. :runner::dash:\r\n\r\nIs this correct? How would you characterize the time and space complexity of the parsers generated by this library? Could they benefit from any further optimization, such as packrat memoization? :rat: (Edit: Oops, of course memoization wouldn't help because there's no backtracking! :disappointed_relieved:)\r\n\r\nThanks for your consideration."}}