3

I'm currently building a crochet pattern parser in Java, and I've hit upon some trouble. I'll call the language used for input Crochet Pattern Code (CPC).

I have a rather large writeup on the context, it's appended at the end. You probably won't need all of it, so I'll start with:

The Problem

The problem that I'm facing is that I want to add functions, such as expandRepetitions, to change the following:

1 x repeat(3) - RepeatSymbol(3)
1 x chain - StitchSymbol(Stitch.Type.ch)

Into:

3 x chain - StitchSymbol(Stitch.Type.ch)

This is a representation of the ArrayList first containing a RepeatSymbol(3) and a Chain, and thereafter containing three times StitchSymbol(Stitch.Type.ch).

I also want to be able to turn 2{2{ch}} into:

1 x repeat(2) - RepeatSymbol(2)
1 x SymbolGroup {2{ch}}

And into:

4 x chain - StitchSymbol(Stitch.Type.ch)

However, the only way of applying this action not only to the current ArrayList<Symbol>, but also to the ArrayList<Symbol> inside any GroupSymbol. So far, the only thing I've come up with is this:

public class Parser {

    ...

    public static expandRepetitions(ArrayList<Symbol> input) {
        int pos = 0; 

        while (pos < input.size()) {
             /* on encounter with RepeatSimbol, simplify */
             ...
             /* on encounter with GroupSymbol, do this: */
             input.get(pos).expandRepetitions();
        }
    }

    ...
}

public class GroupSymbol {

    ...

    public void expandRepetitions() {
        Parser.expandRepetitions(this.symbolList);
    }

    ...

}

However, this seems like a terrible solutions. I think it's very ugly to have to integrate the GroupSymbol so tightly with the Parser, and feel like there should be a better way possible, but can't think of one.

The Question

How can I improve the structure of GroupSymbol (an ArrayList<Symbol> container) and Parser? Parser needs to apply actions upon an ArrayList<Symbol>, which may contain GroupSymbols, which may contain GroupSymbols, and so on, and these actions need to be applied to the whole contents of these GroupSymbols.

For instance, these actions will include the expanding of repetitions and the simplifying of a list of Symbols to not include groups and repetitions.

Background & details of the parser

I'm building a formalized language for crochet, a parser for this language and a visualizer. I'm currently stuck at the parser, specifically the part that simplifies constructions with grouping and repetitions to a flat list.

Disclaimer: I haven't built a parser, compiler, interpreter or language before and have been winging this up till this point. If you see (other) fatal flaws in my parser and/or language, please do point these out and/or point me at resources for learning about this sort of thing.

The parser is structured as follows:

  • A Parser object with static functions.

  • A Symbol interface, and a bunch of differt types of Symbol implementations, such as:

    • StitchSymbol, which has the property that it represents a certain Stitch.Type

    • GroupSymbol, which stores an ArrayList<Symbol>, and can contain other instances of GroupSymbol.

    • RepeatSymbol, which stores an int representing a number of repeats of the next item (a stitch, operation such as skip or a group).

  • A function preprocess to turn a String into an ArrayList of (basic) Symbols. This is done using a simple finite state machine parser.

  • A few functions to make these lists of Symbols more useable: one to change a BeginGroupSymbol, a bunch of Symbols and an EndGroupSymbol into a single GroupSymbol which contains the bunch, one to expand repetitions, one to simplify the list to simple instructions.

For instance, in preprocess:

  • ch is turned into a StitchSymbol with Stitch.Type set to 'ch' (a chain, for those familiar with crochet).

  • { is turned into a BeginGroupSymbol.

An example input and output:

10ch<{3sc2{chskdcchsk}}fo

Gives:

1 x repeat(10) - RepeatSymbol(10)
1 x chain - StitchSymbol(Stitch.Type.ch)
1 x reverse - ReverseSymbol()
1 x begin group - BeginGroupSymbol()
1 x repeat(3) - RepeatSymbol(3)
1 x single crochet - StitchSymbol(Stitch.Type.sc)
1 x repeat(2) - RepeatSymbol(3)
1 x begin group - BeginGroupSymbol()
1 x chain - StitchSymbol(Stitch.Type.ch)
1 x skip - SkipSymbol()
1 x double crochet - StitchSymbol(Stitch.Type.dc)
1 x chain - StitchSymbol(Stitch.Type.ch)
1 x skip - SkipSymbol()
2 x end group - EndGroupSymbol()
1 x fasten off - StitchSymbol(Stitch.Type.fo)

Then after that, collapseGroups turns it into the following:

1 x repeat(10) - RepeatSymbol(10)
1 x chain - StitchSymbol(Stitch.Type.ch)
1 x reverse - ReverseSymbol()
1 x GroupSymbol {3sc2{chskdcchsk}}
1 x fasten off - StitchSymbol(Stitch.Type.fo)

The string of CPC after the GroupSymbol is constructed from the items in the ArrayList inside the GroupSymbol. It could be expanded to:

1 x repeat(3) - RepeatSymbol(3)
1 x single crochet - StitchSymbol(Stitch.Type.sc)
1 x repeat(2) - RepeatSymbol(2)
1 x GroupSymbol {chskdcchsk}

This inner GroupSymbol could be further expanded, but I think the picture is clear.

For those who crochet, here's a visual explanation as well:

crochet instruction

And what it looks like in wool:

the result of the example pattern

  • 2
    It's hard to understand exactly what you want to do - what the rules are for your input language? My gut says that you have ambiguity in how you're trying to store things. Your repeat handles the "next" bundle, but it is unclear in your storage where "next" ends. I would expect your repeat token to have some other (possibly composite) token as an argument. Or more succinctly, it seems as though you are tokenizing/lexing but not building an actual parse tree. – Telastyn Apr 8 '15 at 22:16
  • 5
    At the risk of sounding too academical, I think you should go and try to learn the basics of parsers and compilers (namely, regular expressions and context free grammars) so at least you can define your language as a Regex/CFG. Once that is done, 90% of the work is finished, since there are lots of tools and techniques to create parsers from Regex/CFG. – SJuan76 Apr 8 '15 at 22:19
  • Something like CrochetCode -> repeat {CrochetCode} | reverse {CrochetCode} | StitchSymbol | [empty set] – SJuan76 Apr 8 '15 at 22:21
  • @SJuan76: Do you think that'd be necessary at this stage? The implementation of the language is done once I have a way of getting rid of the groups and repetitions, and this is only meant to be a proof of concept (for now). I was mainly looking for a solution to the wrinkle in the code, but I will keep your suggestions in mind when rebuilding it for the real release. – Willem Apr 8 '15 at 22:24
  • 6
    One question is why are you writing this yourself rather than using antlr or javacc to assist with generating the code once you have the language definition? – user40980 Apr 8 '15 at 22:48
4

What you have written is really a lexer. Parsers give you the nested structure from your input, whereas lexers just give a sequence of symbols. You've probably spent a lot of time reinventing the wheel, when you could use a parser generator like antlr to do most of the work. For example, it only took me around 5 minutes to come up with the following basic grammar for your example case. It works with the pegjs javascript parser generator:

start
  = pattern

pattern
  = symbol*

symbol
  = integer symbol / stitch / "{" pattern "}"

stitch
  = "ch" / "<" / "sc" / "sk" / "dc" / "fo"

integer
  = digits:[0-9]+ { return parseInt(digits.join(""), 10); }

It generates the following structured output:

[
   [
      10,
      "ch"
   ],
   "<",
   [
      "{",
      [
         [
            3,
            "sc"
         ],
         [
            2,
            [
               "{",
               [
                  "ch",
                  "sk",
                  "dc",
                  "ch",
                  "sk"
               ],
               "}"
            ]
         ]
      ],
      "}"
   ],
   "fo"
]

This sort of form is much easier to perform any sort of transformation you need. The groups are already properly nested. The repeat count is already properly associated with what it should repeat by being grouped inside the same array. Again, this is 5 minutes of work, and I didn't even try to add semantics. You can make it much cleaner and more useful with not much effort.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.