Local Variable Parsing

RubyconceptualintermediateParslet-compatible

Non-greedy parsing with local bindings

How the Code Works

This section explains how the parsing rules map to the format semantics.

The Problem with Greedy Parsing

a = str('a').repeat >> str('aa')
# Input: 'aaaa'
# Fails! repeat consumes all 'a's, leaving nothing for 'aa'

Traditional repetition is greedy and blind: Greedy repetition takes as much as possible without considering what follows.

Non-Blind Pattern

# E1% E2 transformation:
# S = E2 | E1 S

def this(name, &block)
  Parsanol::Atoms::Entity.new(name, &block)
end
def epsilon
  any.absent?
end

a = str('a').as(:e) >> this('a') { a }.as(:rec) | epsilon

Transform the grammar to look ahead: This recursively matches while checking alternatives.

Greedy Non-Blind Alternative

b = str('aa').as(:e2) >> epsilon |
    str('a').as(:e1) >> this('b') { b }.as(:rec)

Put the terminal first: Try to match the end (`aa`) first, then recurse if that fails.

Entity for Recursion

def this(name, &block)
  Parsanol::Atoms::Entity.new(name, &block)
end

The `this()` helper enables recursive rule definition: Entity delays evaluation until parse time, allowing forward references.

Entity for Recursion

def this(name, &block)
  Parsanol::Atoms::Entity.new(name, &block)
end

The `this()` helper enables recursive rule definition: Entity delays evaluation until parse time, allowing forward references.

Source Code

Ruby

# frozen_string_literal: true

# An exploration of two ideas:
#   a) Constructing a whole parser inline, without the artificial class around
#      it.
# and:
#   b) Constructing non-greedy or non-blind parsers by transforming the
#      grammar.

$LOAD_PATH.unshift "#{File.dirname(__FILE__)}/../lib"

require "parsanol/parslet"
include Parsanol::Parslet

a = str("a").repeat >> str("aa")

# E1% E2
#
# S = E2 | E1 S

def this(name, &)
  Parsanol::Atoms::Entity.new(name, &)
end

def epsilon
  any.absent?
end

# Traditional repetition will try as long as the pattern can be matched and
# then give up. This is greedy and blind.
a = (str("a").as(:e) >> this("a") { a }.as(:rec)) | epsilon

# Here's a pattern match that is greedy and non-blind. The first pattern
# 'a'* will be tried as many times as possible, while still matching the
# end pattern 'aa'.
b = (str("aa").as(:e2) >> epsilon) | (str("a").as(:e1) >> this("b") {
  b
}.as(:rec))

p a.parse("aaaa")
p b
p b.parse("aaaa")