I'll first give you a basic overview of my task, I'm working with Deterministic Context Free Languages. It's not really important if you don't know what that is, I've got that covered. I just need help on developing an algorithm.

Basically I'm given an Axiom, which is my starting string, and I'm supposed to expand the Axiom generation by generation into one large character Array based on a set of production rules.

I pass the axiom, Production rules, and Number of generations that I want expanded into a method called Produce. Produce will then develop a character array that contains each generation. (and will convert it to a string to be returned)

here's a simple example

String[] rules = {"f=afg ", " g = b f h", "h= ab"};


String axiom= "f";


String[] rules = {"f=f-h","h=f+h"}

What the method "produce" should return:

String str = produce(axiom, rules, 3);

Each generation is separated by a #
As you can see, the first generation is an f. Based on production rules, f is expanded to f-h in the next generation. generations are added to the string until it reaches desire number of generations.

There are a ton more things to this program I have already done, (in the end it will print out things like the Koch Star, Peano curve etc, but all I really need help with is developing this algorithm, I've figured the rest out, fingers crossed)

I can't seem to find a way to do this without triple nested for loops and a huge amount of if statements (assuming that method would even work once I finished writing it).

What I've come up with so far is this:

int CGIndx=0;
    int NGIndx=axiom.length()+1;
    int RuleNum=0;

for ( RuleNum=0; RuleNum<rules.length; RuleNum++)
        if (TPath[CGIndx]==rules[RuleNum].charAt(0)) // if Current character = predecessor in rules[RuleNum]
          rules[RuleNum].getChars( 2, rules[RuleNum].length(), TPath, NGIndx );
          NGIndx+= rules[RuleNum].length()-2; 

it successfully expands the first character of the axiom and appends it to the string right after the axiom and a '#'. I feel like I can't really expand the algorithm with this method without creating a monster. Please, any ideas? and if any clarification is needed just ask, I have a feeling I did a sloppy job of trying to explain this.

A few more things:

-Each rule is formatted so that the first character is a variable and the second character is an '='. these are stored in an array of strings.
-neither rules nor axioms include whitespace thanks to a method I already wrote.
-variables can include "a-e,f,h,g" and terminals include "-,+,#"

Ok so I figured out how to write the algorithm, it's working so far. But I do have another simpler question that hopefully someone can answer.

I'm supposed to follow a format for returning error messages (there is a method called isDCFL that runs numerous checks on the rules and axiom)

basically I need to put this code in my main method:

      TPath = produce(axiom, rules, 6);
    catch (Exception e)
      System.out.println("ERROR: "+ e.getMessage());

At the beginning of my produce method I'm supposed to put

if (isDCFL(axiom, rules) == false)
      throw new IllegalArgumentException("not a DCFL");

previously I had setup my isDCFL method to do a simple system.out.println() that would display exactly what the error was (there are around 10 or 20 checks that are performed). using this rigid format, is there a way to throw an exeption that tells exactly what error was found in my isDCFL method?

I don't really understand how these catch/throw statements are used/how they work. Even a good explanation of these would be a great help!

This article has been dead for over six months. Start a new discussion instead.