From 14013d04f5023e68b5a804c3735e909241795878 Mon Sep 17 00:00:00 2001 From: Matthew Hall Date: Tue, 7 Mar 2023 01:30:02 +1300 Subject: Initial --- .editorconfig | 9 +++ .gitignore | 9 +++ LICENSE | 21 ++++++ README.md | 39 +++++++++++ shard.yml | 11 ++++ spec/parcom_spec.cr | 183 ++++++++++++++++++++++++++++++++++++++++++++++++++++ spec/spec_helper.cr | 2 + src/parcom.cr | 108 +++++++++++++++++++++++++++++++ 8 files changed, 382 insertions(+) create mode 100644 .editorconfig create mode 100644 .gitignore create mode 100644 LICENSE create mode 100644 README.md create mode 100644 shard.yml create mode 100644 spec/parcom_spec.cr create mode 100644 spec/spec_helper.cr create mode 100644 src/parcom.cr diff --git a/.editorconfig b/.editorconfig new file mode 100644 index 0000000..163eb75 --- /dev/null +++ b/.editorconfig @@ -0,0 +1,9 @@ +root = true + +[*.cr] +charset = utf-8 +end_of_line = lf +insert_final_newline = true +indent_style = space +indent_size = 2 +trim_trailing_whitespace = true diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..0bbd4a9 --- /dev/null +++ b/.gitignore @@ -0,0 +1,9 @@ +/docs/ +/lib/ +/bin/ +/.shards/ +*.dwarf + +# Libraries don't need dependency lock +# Dependencies will be locked in applications that use them +/shard.lock diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..a6ae1d7 --- /dev/null +++ b/LICENSE @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2023 Matthew Hall + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/README.md b/README.md new file mode 100644 index 0000000..9d7d2d3 --- /dev/null +++ b/README.md @@ -0,0 +1,39 @@ +# parcom + +TODO: Write a description here + +## Installation + +1. Add the dependency to your `shard.yml`: + + ```yaml + dependencies: + parcom: + github: your-github-user/parcom + ``` + +2. Run `shards install` + +## Usage + +```crystal +require "parcom" +``` + +TODO: Write usage instructions here + +## Development + +TODO: Write development instructions here + +## Contributing + +1. Fork it () +2. Create your feature branch (`git checkout -b my-new-feature`) +3. Commit your changes (`git commit -am 'Add some feature'`) +4. Push to the branch (`git push origin my-new-feature`) +5. Create a new Pull Request + +## Contributors + +- [Matthew Hall](https://github.com/your-github-user) - creator and maintainer diff --git a/shard.yml b/shard.yml new file mode 100644 index 0000000..e6fd943 --- /dev/null +++ b/shard.yml @@ -0,0 +1,11 @@ +name: parcom +version: 0.1.0 + +description: Simple parser combinator library + +authors: + - Matthew Hall + +crystal: 1.7.2 + +license: MIT diff --git a/spec/parcom_spec.cr b/spec/parcom_spec.cr new file mode 100644 index 0000000..a496a3f --- /dev/null +++ b/spec/parcom_spec.cr @@ -0,0 +1,183 @@ +require "./spec_helper" + +require "../src/parcom.cr" + +include Parcom + +describe Result do + describe "#initialize" do + it "sets values for #tokens and #value" do + tokens = "esting".chars + value = 't' + result = Result(Char, Char).new(tokens, value) + + result.tokens.should eq(tokens) + result.value.should eq(value) + end + end +end + +describe Parser do + describe "#|" do + it "creates an `Alt` instance from `self` and another `Parser(T, V)`" do + p = AnyToken(Char).new | AnyToken(Char).new + + p.should be_a(Alt(Char, Char)) + end + end + + describe "#assert" do + it "creates an `Assert` instance from self and a `Proc(T, Bool)`" do + f = ->(x : Char) { x == '#' } + p = AnyToken(Char).new.assert(f) + + p.should be_a(Assert(Char, Char)) + end + end +end + +describe Flunk do + describe "#parse" do + it "always fails" do + tokens = "testing".chars + expect_raises(ParserException) { Flunk(Char, Char).new.parse(tokens) } + end + end +end + +describe AnyToken do + describe "#parse" do + it "succeeds when input is non-empty" do + tokens = "testing".chars + result = AnyToken(Char).new.parse(tokens) + + result.tokens.should eq(tokens[1..]) + result.value.should eq('t') + end + + it "fails when input is empty" do + expect_raises(ParserException) { AnyToken(Char).new.parse([] of Char) } + end + end +end + +describe Eof do + describe "#parse" do + it "succeeds when input is empty" do + result = Eof(Char).new.parse([] of Char) + + result.tokens.empty?.should be_true + result.value.should be_nil + end + + it "fails when input is non-empty" do + tokens = "testing".chars + + expect_raises(ParserException) { Eof(Char).new.parse(tokens) } + end + end +end + +describe Peek do + describe "#parse" do + it "does not modify the result of the wrapped parser" do + tokens = "testing".chars + parser = AnyToken(Char).new + result_normal = parser.parse(tokens) + result_peek = Peek.new(parser).parse(tokens) + + result_peek.value.should eq(result_normal.value) + end + + it "does not consume any input" do + tokens = "testing".chars + parser = AnyToken(Char).new + result = Peek.new(parser).parse(tokens) + + result.tokens.should eq(tokens) + end + end +end + +describe Assert do + describe "#parse" do + it "fails if the wrapped parser fails" do + test = ->(x : Char) { true } # doesn't matter for this test + p = Assert.new(AnyToken(Char).new, test) + expect_raises(ParserException) { p.parse([] of Char) } + end + + it "fails if the result value fails the test" do + tokens = "testing".chars + test = ->(x : Char) { x == '$' } + p = Assert.new(AnyToken(Char).new, test) + expect_raises(ParserException) { p.parse(tokens) } + end + + it "succeeds if the wrapped parser succeeds and the test passes" do + tokens = "testing".chars + expected_char = tokens[0] + test = ->(x : Char) { x == expected_char } + p = Assert.new(AnyToken(Char).new, test) + result = p.parse(tokens) + + result.value.should eq(expected_char) + test.call(expected_char).should be_true + end + end +end + +describe Satisfy do + describe "#parse" do + it "fails if there are input is empty" do + test = ->(x : Char) { x == '#' } # doesn't matter for this case + p = Satisfy(Char).new(test) + + expect_raises(ParserException) { p.parse([] of Char) } + end + + it "fails if the token fails the test" do + tokens = "testing".chars + test = ->(x : Char) { x == '#' } + p = Satisfy(Char).new(test) + + expect_raises(ParserException) { p.parse(tokens) } + end + + it "succeeds if the token passes the test" do + tokens = "testing".chars + expected_char = tokens[0] + test = ->(x : Char) { x == expected_char } + p = Satisfy(Char).new(test) + result = p.parse(tokens) + + result.value.should eq(expected_char) + test.call(result.value).should be_true + end + end +end + +describe Token do + describe "#parse" do + it "fails if the input is empty" do + expect_raises(ParserException) { Token(Char).new('t').parse([] of Char) } + end + + it "fails if the token is not the expected token" do + tokens = "testing".chars + p = Token(Char).new('#') + + expect_raises(ParserException) { p.parse(tokens) } + end + + it "succeeds if the token is the expected token" do + tokens = "testing".chars + expected_char = tokens[0] + p = Token(Char).new(expected_char) + result = p.parse(tokens) + + result.value.should eq(expected_char) + end + end +end + diff --git a/spec/spec_helper.cr b/spec/spec_helper.cr new file mode 100644 index 0000000..3a4747e --- /dev/null +++ b/spec/spec_helper.cr @@ -0,0 +1,2 @@ +require "spec" +require "../src/parcom" diff --git a/src/parcom.cr b/src/parcom.cr new file mode 100644 index 0000000..0f907c4 --- /dev/null +++ b/src/parcom.cr @@ -0,0 +1,108 @@ +module Parcom + VERSION = "0.1.0" + + class ParserException < Exception + end + + class Result(T, V) + getter tokens, value + + def initialize(@tokens : Array(T), @value : V) + end + end + + abstract class Parser(T, V) + abstract def parse(tokens : Array(T)) : Result(T, V) + + def assert(f : V -> Bool) + Assert.new(self, f) + end + + def |(other : Parser(T, V)) : Parser(T, V) + Alt.new(self, other) + end + end + + class Flunk(T, V) < Parser(T, V) + def parse(tokens) : Result(T, V) + raise ParserException.new("Flunk: parsing failed") + end + end + + class AnyToken(T) < Parser(T, T) + def parse(tokens : Array(T)) : Result(T, T) + if tokens.empty? + raise ParserException.new("AnyToken: input was empty") + else + Result.new(tokens[1..], tokens[0]) + end + end + end + + class Eof(T) < Parser(T, Nil) + def parse(tokens : Array(T)) : Result(T, Nil) + if tokens.empty? + Result.new(tokens, nil) + else + raise ParserException.new("Eof: input was not empty") + end + end + end + + class Peek(T, V) < Parser(T, V) + def initialize(@p : Parser(T, V)) + end + + def parse(tokens : Array(T)) : Result(T, V) + result = @p.parse(tokens) + Result.new(tokens, result.value) + end + end + + class Assert(T, V) < Parser(T, V) + def initialize(@p : Parser(T, V), @f : V -> Bool) + end + + def parse(tokens : Array(T)) : Result(T, V) + result = @p.parse(tokens) + + unless @f.call(result.value) + raise ParserException.new("Assert: predicate failed") + end + + result + end + end + + class Satisfy(T) < Parser(T, T) + def initialize(@f : T -> Bool) + end + + def parse(tokens : Array(T)) : Result(T, T) + AnyToken(T).new.assert(@f).parse(tokens) + end + end + + class Token(T) < Parser(T, T) + def initialize(@expected : T) + end + + def parse(tokens : Array(T)) : Result(T, T) + Satisfy(T).new(->(x : T) { x == @expected }).parse(tokens) + end + end + + class Alt(T, V) < Parser(T, V) + def initialize(@p1 : Parser(T, V), @p2 : Parser(T, V)) + end + + def parse(tokens : Array(T)) : Result(T, V) + begin + @p1.parse(tokens) + rescue ParserException + @p2.parse(tokens) + end + end + end +end + -- cgit v1.2.1