Category:Jq/peg.jq

module {
  "name": "peg",
  "description": "Parsing Expression Grammar foundations",
  "version": "0.0.2",
  "homepage": "https://rosettacode.org/w/index.php?title=Category:Jq/peg.jq",
  "license": "MIT",
  "author": "pkoppstein at gmail dot com",
  "repository": {
    "type": "",
    "url": ""
  }
};
# PEG-to-jq transcription is based on these equivalences:
# Sequence: e1 e2             e1 | e2
# Ordered choice: e1 / e2     e1 // e2
# Zero-or-more: e*            star(E)
# One-or-more: e+             plus(E)
# Optional: e?                optional(E)
# And-predicate: &e           amp(E)      # no input is consumed
# Not-predicate: !e           neg(E)      # no input is consumed

# The idea is to pass a JSON object {remainder:_, result:_ } through a
# pipeline, consuming the text in .remainder and building up .result.

def star(E): ((E | star(E)) // .) ;
def plus(E): E | (plus(E) // . );
def optional(E): (E // .);
def amp(E): . as $in | E | $in;
def neg(E): select( [E] == [] );

### Helper functions:

# Consume a regular expression rooted at the start of .remainder, or emit empty;
# on success, update .remainder and set .match but do NOT update .result
def consume($re):
  # on failure, match yields empty
  (.remainder | match("^" + $re)) as $match
  | .remainder |= .[$match.length :]
  | .match = $match.string;

def parse($re):
  consume($re)
  | .result = .result + [.match] ;

def parseNumber($re):
  consume($re)
  | .result = .result + [.match|tonumber] ;

# consume the literal string $s
def q($s):
  select(.remainder | startswith($s))
  | .remainder |= .[$s | length :] ;

def literal($s):
  q($s)
  | .result += [$s];

def nonempty: select( (.remainder | length) > 0 );

def eos: select(.remainder | length == 0);

# required white space
def _: consume("[ \n\r\t]+");

# optional white space
def ws: consume("[ \n\r\t]*");

# It is assumed that $n > 0
def nfold($n; E): reduce range(0;$n - 1) as $e (E; E);

# Tagging
def box(E):
  ((.result = null) | E) as $e
  | .remainder = $e.remainder
  | .result += [$e.result]  # the magic sauce
  ;

def box(name; E):
  ((.result = null) | E) as $e
  | .remainder = $e.remainder
  | .result += [{(name): (try ($e.result|join("")) catch $e.result) }]  # the magic sauce
  ;

def ast(tag; E):
  ((.result = null) | E) as $e
  | .remainder = $e.remainder
  | .result += [ {(tag): $e.result} ]  # the magic sauce
  ;

# A string that does NOT contain $regex
def string_except($regex):
  box(star(neg( parse($regex) ) | parse("."))) | .result[-1] |= add;

def objectify(E):
  box(E)
  | .result[-1] |= {(.[0]): .[1:]} ;

def keyvalue(E):
  box(E)
  | .result[-1] |= {(.[0]): .[1]} ;