Hello, I don't know any Perl but I do know Java. I am studying about Push down automatas at the moment and wanted to make a simulator for myself. I have found some code in Perl that does it but I do not know how I can go about using the concepts it has to implement in Java. The following is the Perl code:
#!usr/bin/perl
use Text::ParseWords;
use strict;
use warnings;
my (@string, @branches, @stack, %accepts, %alphabet, @rules);
# Grabs the filenames for the machine and the word to be run on it.
my $pdaFile = $ARGV[0];
my $input = $ARGV[1];
# We use subroutines to parse and verify the data in the input files.
# The machine data is stored in the $machine structure as the keys rules, accepts, alphabet, and startState.
my $machine = readPDA($pdaFile);
# Rules and accepts are extracted from the $machine structure for ease of access.
@rules = @{$machine->{rules}};
%accepts = %{$machine->{accepts}};
# This reads the input file and parses it into an array of strings, with each element being one input symbol.
# It checks to make sure the elements are all in the machine's alphabet.
@string = readInput($input, $machine->{alphabet});
# The newstate is a temporary storage point for when a new state is calculated.
my $newstate;
# The usedRule is a temporary storage point for when a new state is calculated.
my $usedRule;
# The changed variable represents whether or the current branch is unfinished.
my $changed = 1;
------ I UNDERSTAND HOW TO DO THE ABOVE------
push(@stack, "");
# The top level of the branches array corresponds to each branch of possibilities created by the non-determinism of the PDA.
# Each element contains the conditions of the machine for that branched possibility.
# The first element of each collection is the state of the branch.
$branches[0][0] = $machine->{startState};
# The second element is how much of the input string the branch has read.
$branches[0][1] = 0;
# The third element is an array containing the stack for that branch.
$branches[0][2][0] = "";
# Now that the first branch is initialized, the processing can begin
for (my $i = 0; $i < @branches; $i++)
{
# When we start a branch, print the branch number
print "\nBeginning branch ".$i.".\n";
# As long as things keep changing, keep cycling through the rules.
while($changed)
{
# Unless it changes while going through the rules, this branch will quit.
$changed = 0;
# The input word is printed, with the next symbol highlighted.
print "Input: @string[0..$branches[$i][1]-1] <".$string[$branches[$i][1]]."> @string[$branches[$i][1]+1..@string-1]\n";
# The current state of the stack is printed.
print "Stack: @{$branches[$i][2]}\n";
# A new state is calculated by checking conditions against the list of rules
for my $rNum (0..@rules-1)
{
# print "::$rules[$rNum][0]??$branches[$i][0]";
# print "::$rules[$rNum][1]??$string[$branches[$i][1]]";
# print "::$rules[$rNum][2]??".${$branches[$i][2]}[@{$branches[$i][2]}-1]."::\n";
# Checks the current state, input, and top stack item against the rule
if (($rules[$rNum][0] eq $branches[$i][0]) and
(($rules[$rNum][1] eq "e") or ($rules[$rNum][1] eq $string[$branches[$i][1]])) and
(($rules[$rNum][2] eq "e") or ($rules[$rNum][2] eq ${$branches[$i][2]}[@{$branches[$i][2]}-1])))
{
if ($changed == 0)
{
# Set the new state.
$newstate = $rules[$rNum][3];
# The state transition is printed.
print "State: ".$branches[$i][0]." -> ".$newstate."\n\n";
$changed = 1;
# Because possible branched depend on this state, we can't update it yet.
# When we can update this state, $usedRule will help us remember which rule to base those updates on.
$usedRule = $rNum;
}
else
{
# Set the new state.
my $branchState = $rules[$rNum][3];
# The state transition is printed.
print "(branching) State: ".$branches[$i][0]." -> ".$branchState."\n\n";
my $newBranch = @branches;
# The state in the new branch is set.
$branches[$newBranch][0] = $branchState;
# The new branch starts with the same string position as the old branch,
$branches[$newBranch][1] = $branches[$i][1];
# and the same stack, so the stack has to be replicated.
@{$branches[$newBranch][2]} = @{$branches[$i][2]};
# If we read a symbol from the input to make the transition,
unless ($rules[$rNum][1] eq "e")
{
# then we should move to the next symbol.
$branches[$newBranch][1]++;
}
# If we used an element from the stack to make the transition,
unless ($rules[$rNum][2] eq "e")
{
# then it's used up and should be removed.
pop(@{$branches[$newBranch][2]});
}
# If the rule adds something to the stack,
unless ($rules[$rNum][4] eq "e")
{
# then it gets added.
push(@{$branches[$newBranch][2]}, $rules[$rNum][4]);
}
}
}
}
# Now that any branching has been finished, we can update the original branch.
if ($changed)
{
# If we read a symbol from the input to make the transition,
unless ($rules[$usedRule][1] eq "e")
{
# then we should move to the next symbol.
$branches[$i][1]++;
}
# If we used an element from the stack to make the transition,
unless ($rules[$usedRule][2] eq "e")
{
# then it's used up and should be removed.
pop(@{$branches[$i][2]});
}
# If the rule adds something to the stack,
unless ($rules[$usedRule][4] eq "e")
{
# then it gets added.
push(@{$branches[$i][2]}, $rules[$usedRule][4]);
}
# The state changes to the new state.
$branches[$i][0] = $newstate;
}
}
# When the input is exhausted, the branch is in its final state.
print "Final state of branch ".$i." is ".$branches[$i][0]."\n";
# If that state is in the accept states list, the machine accepts the input and halts.
if ((defined($accepts{$branches[$i][0]})) and ($branches[$i][1] == @string-1))
{
print "The machine accepts the string.\n";
exit;
}
# If that state doesn't, point it out.
else { print "The branch does not accept the string.\n"; }
# And move on.
$changed = 1;
}
print "The machine does not accept the string.\n";
###################################################The two methods this references ReadPDA and ReadInput can be found here:
http://en.wikibooks.org/wiki/Computability_and_Complexity/Formal_Languages/Chomsky_Hierarchy/Context_Free_Languages
I don't need help with that as I know how to do that in Java already. For the function above I know the beginning bit but after that I am lost on what to do in Java. I need explaination of what kind of data structures to use for "branch" (what is it? Is it a global variable? Is it a method that takes attributes??) and if someone can explain in Java terms what to do with the lines or help me get started it would be great.
