/*
* This groovy script converts a JFLAP jff file representing a finite automaton
* to LaTeX file depicting the automaton graphically using TikZ.
*
* Copyright (c) 2009, 2014, 2015 Andrew Mertz and William Slough
*
* 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.
*/
// Define a few constants
scale = 1.0 // 1 pixel in JFLAP = scale points in LaTeX
gridsize = 20.0 // gridsize is measured in pixels
turingBlank = '$\\Box$' // the symbol to be used for a blank in a TM
blank = '$\\lambda$' // the symbol to be used for blank otherwise
arrowWidth = 6 // width of an arrow in points
arrowLength = 9 // length of an arrow in points
arrowType = 'Stealth' // arrow type from arrows.meta TikZ library
acceptingDistance = 2 // distance, in pt, between circles in accepting
// state
version = '1.2'
infilename = null
outputStream = null
// Define a function that cleans up text that could be "bad" for LaTeX to
// ingest
String fixText(String text)
{
if(text)
{
text = text.replace('\\', '$\\backslash$')
text = text.replace('~', '$\\sim$')
text = text.replaceAll('[$%^&_#{}]', {'\\'+ it[0]})
}
return text
}
// Setup the command line options
// TODO: maybe add a switch for arrow type
// TODO: maybe allow different scales and grid sizes for each axis
// TODO: maybe allow user to set preview boarder
cmdLine = new CliBuilder(usage: 'jflap2tikz [options]',
header: "Version ${version}",
width: 80)
cmdLine.d(longOpt:'accepting-distance',
args: 1,
argName: 'distance',
required: false,
"Distance, in pt, between the circles of an accepting state (default is ${acceptingDistance})")
cmdLine.i(longOpt: 'input-file',
args: 1,
argName: 'filename',
'Name of a JFLAP jff file representing a finite automaton, pushdown automaton, or Turing machine. If a ' +
'file is not given standard input will be used.')
cmdLine.g(longOpt:'grid',
args:1,
optionalArg: true,
argName: 'size',
required: false,
"Round positions so that they are on a grid. If a size is given it sets the spacing of the grid (default " +
"is ${gridsize})")
cmdLine.h(longOpt:'help',
required: false,
'Show usage information and quit')
cmdLine.l(longOpt:'arrow-length',
args:1,
argName: 'length',
required: false,
"Length of arrows in points (default is ${arrowLength})")
cmdLine.o(longOpt: 'output-file',
args: 1,
argName: 'filename',
'Name of a file for writing output. If this file already exists it will be overwritten.')
cmdLine.r(longOpt:'rotate',
required: false,
'Rotate labels along edges')
cmdLine.s(longOpt:'scale',
args:1,
argName:'x',
required: false,
"1 pixel in JFLAP = x points in LaTeX (default is ${scale})")
cmdLine.w(longOpt:'arrow-width',
args:1,
argName:'width',
required: false,
"Width of arrows in points (default is ${arrowWidth})")
cmdLine.k(longOpt:'keep-names',
required: false,
"Use the state names from the JFLAP file. The default is to replace the state names with names of the " +
"form '\$q_{id}\$', where id is the unique state number. Note state names will not be sanitized and thus " +
"may contain invalid TeX.")
// Parse the command line options
options = cmdLine.parse(args)
// If there is a parse error, quit. Note usage information will already have
// been displayed.
if(!options)
{
System.exit(1)
}
// If the user has asked for help print the usage information and quit
if(options.h)
{
cmdLine.usage()
System.exit(0)
}
keapNames = options.k
grid = false
if(options.g)
{
grid = true
// Verify that gridsize is valid (a positive double)
if(!(options.g instanceof Boolean))
{
try
{
gridsize = Double.valueOf(options.g)
if (gridsize <= 0) throw new NumberFormatException()
}
catch(NumberFormatException ex)
{
System.err.println "error: gridsize must be a positive number"
cmdLine.usage()
System.exit(2)
}
}
}
// Verify that the scale is valid (a positive double)
try
{
if(options.s)
{
scale = Double.valueOf(options.s)
if (scale <= 0)
{
throw new NumberFormatException()
}
}
}
catch(NumberFormatException ex)
{
System.err.println "error: scale must be a positive number"
cmdLine.usage()
System.exit(3)
}
// Verify that the accepting distance is valid (a positive double)
try
{
if(options.d)
{
acceptingDistance = Double.valueOf(options.d)
if (acceptingDistance <= 0)
{
throw new NumberFormatException()
}
}
}
catch(NumberFormatException ex)
{
System.err.println "error: accepting distance must be a positive number"
cmdLine.usage()
System.exit(4)
}
if(options.i)
{
infilename = options.i
}
if(options.o)
{
try
{
outputStream = new FileWriter(options.o)
}
catch(Exception e)
{
System.err.println "error: unable to write to output file ${options.o}"
System.exit(5)
}
}
else
{
outputStream = System.out
}
// Try to get the text from the file
if(infilename)
{
try
{
body = new File(infilename).text
}
catch(IOException ex)
{
System.err.println "error: unable to read ${infilename}"
System.exit(4)
}
}
else
{
body = System.in.text
}
// Parse the XML
try
{
structure = new XmlParser().parseText(body)
}
catch(Exception ex)
{
System.err.println "error: parsing XML"
System.exit(5)
}
// Check the type to be sure it is a machine that can be converted
type = structure.type.text()
if(type != "fa" && type != "pda" && type != "turing")
{
System.err.println "error: unsupported machine type --- only FAs, PDAs and Turing machines can be converted"
System.exit(6);
}
// If the automaton is a Turing machine, get the number of tapes
try
{
tapes = Integer.valueOf(structure.tapes.text())
}
catch (Exception ex)
{
tapes = 1
}
// Find the automaton in the XML tree
automaton = structure.automaton
if(!automaton)
{
automaton = structure
}
// For each state in the XML define a TikZ node and record their position
statePosition = [:]
automaton.state.each
{
// Get the x and y value of the position, correcting for the change in
// coordinate systems
x = Double.valueOf(it.x.text()) * scale
y = -Double.valueOf(it.y.text()) * scale
if(grid)
{
x = Math.round(x / gridsize) * gridsize
y = Math.round(y / gridsize) * gridsize
}
// record position
statePosition[it.@id] = [x,y]
// get state name
def stateName
if(keapNames)
{
stateName = it.@name
}
else
{
stateName = "\$q_{${fixText(it.@id)}}\$"
}
// Output the TikZ version of this state
outputStream.println " \\draw (${x}pt, ${y}pt)" +
"node[state${it.initial ? ", initial, initial text =" : ""}" +
"${it.get("final") ? ", accepting" : ""}]" +
"(${fixText(it.@id)}){$stateName};"
}
// Define a function that makes a key based on the end points of a transition
// without taking into account the order of the keys. In other words, edge
// (a,b) results in the same key as the edge (b,a).
String makeKey(String a, String b)
{
return a < b ? "${a},${b}" : "${b},${a}"
}
// Scan transitions and create their labels. Also, check to see if there are
// edges going in both directions.
doubleEdges = [:]
edgeLabels = [:]
automaton.transition.each
{
orderedKey = [it.from.text(), it.to.text()]
// Have we seen the reverse of this edge before?
if(edgeLabels.get([it.to.text(), it.from.text()]) &&
it.to.text() != it.from.text())
{
doubleEdges.put(makeKey(it.from.text(), it.to.text()), true)
}
// Get the read symbol. If it is blank use lambda for the symbol.
if(!(readSymbol = fixText(it.read.text())))
{
readSymbol = blank
}
// Get the pop and push symbols if the machine is a PDA
if(type == "pda")
{
if(!(popSymbol = fixText(it.pop.text())))
{
popSymbol = blank
}
if(!(pushSymbol = fixText(it.push.text())))
{
pushSymbol = blank
}
}
// If the machine is a Turing machine, get all of the read, write, and move
// information
if(type == "turing")
{
readSymbols = []
it.read.each{r->
readSymbols << (r.text() ? fixText(r.text()) : turingBlank)
}
// Make the label for this transition
if(type == "fa")
{
label = readSymbol;
}
else if(type == "pda")
{
label = "${readSymbol}, ${popSymbol}; ${pushSymbol}"
}
else if(type == "turing")
{
// Merge the read, write and move lists into one label
label = []
readSymbols.eachWithIndex{read, i->
label << "${read} : ${writeSymbols[i]}, ${moves[i]}"
}
label = label.join('$|$')
}
// Add this edge's label to the edge label list
if((oldLabel = edgeLabels.get(orderedKey)))
{
oldLabel << label
}
else
{
edgeLabels.put(orderedKey, [label])
}
}
// For each transition draw an edge
edgeLabels.each
{
// Turn the label into a string
if(type == "fa")
{
label = it.value.join(", ")
}
else
{
label = it.value.join("\\\\ ")
}
// Construct the options for the node that will hold the label
nodeOptions = []
if(type != "fa" && it.value.size() > 1) // Are line breaks needed?
{
nodeOptions << "align=center"
}
if(options.r && it.key[0] != it.key[1]) // Does the text need to be rotated?
{
nodeOptions << "sloped"
// In the case of rotations auto positioning is not used. Thus, an anchor
// point for the node must be given.
if(statePosition[it.key[0]][0] < statePosition[it.key[1]][0])
{
nodeOptions << "anchor=south"
}
else
{
nodeOptions << "anchor=north"
}
}
// Turn the node options into a string. If there are no options then use the
// empty string. Otherwise join the option with commas and surround them with
// square brackets.
if(nodeOptions.size() > 0)
{
nodeOptions = "[${nodeOptions.join(",")}]"
}
else
{
nodeOptions = ""
}
outputStream.println " \\path[->] (${it.key[0]}) edge" +
(it.key[0] == it.key[1] ? "[loop above]" : "") + // Do we have a self loop?
(doubleEdges.get(makeKey(it.key[0], it.key[1])) ? "[bend left]" : "") + // Do we have more than one edge? If so add a bend.
" node${nodeOptions}" +
"{${label}}(${it.key[1]});"
}
// Print the LaTeX footer
outputStream.println """\\end{tikzpicture}
\\end{document}"""
outputStream.close()
