/* * 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 } // Print the LaTeX header outputStream.println """\\documentclass{article} \\usepackage{tikz} \\usetikzlibrary{automata,positioning,arrows.meta}${type == "turing" ? "\n\\usepackage{amssymb}\n" : ""} \\usepackage[graphics,tightpage,active,pdftex]{preview} \\setlength{\\PreviewBorder}{5pt} \\PreviewEnvironment{tikzpicture} \\begin{document} \\begin{tikzpicture}[>={Stealth[width=${arrowWidth}pt,length=${arrowLength}pt]}, accepting/.style={double distance = ${acceptingDistance}pt, outer sep = ${acceptingDistance/2.0}pt + \\pgflinewidth}, shorten >=1pt${options.r ? "" : ", auto"}]""" // 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) } writeSymbols = [] it.write.each{w-> writeSymbols << (w.text() ? fixText(w.text()) : turingBlank) } moves = [] it.move.each{m-> moves << fixText(m.text()) } } // 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()