Skip to content
GitLab
Projects Groups Topics Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Register
  • Sign in
  • J json
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
  • Issues 4
    • Issues 4
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 1
    • Merge requests 1
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • curry-packages
  • json
  • Merge requests
  • !1

Draft: Use non-backtracking (<!>) over (<|>) where possible

  • Review changes

  • Download
  • Email patches
  • Plain diff
Open Fredrik Wieczerkowski requested to merge non-backtracking into master Mar 09, 2022
  • Overview 1
  • Commits 1
  • Pipelines 0
  • Changes 1

JSON has the advantage of being LL(1), therefore we can pretty much always decide which rule to apply based on the next symbol and thus parse in linear time. In consequence, we can almost everywhere rewrite the alternatives to use the non-backtracking (<!>) combinator, since we will never go deeper than one symbol into a branch that will be rejected. The rules where (<|>) couldn't be replaced with (<!>) could probably be rewritten to use (<!>).

This should improve parsing performance by quite a bit, invalid JSON in particular should be rejected much more quickly (a ~2000 line JSON file with a single misplaced \ was rejected almost instantaneously compared to the current implementation not terminating within > 5 min, with KiCS2).

Still, this branch probably needs some more testing to make sure that it doesn't miss some edge case that currently parses.

Edited Mar 09, 2022 by Fredrik Wieczerkowski
Assignee
Assign to
Reviewers
Request review from
Time tracking
Source branch: non-backtracking