μ-compiler

Coding Critique is the place to post source code for peer review by other members of DevNetwork. Any kind of code can be posted. Code posted does not have to be limited to PHP. All members are invited to contribute constructive criticism with the goal of improving the code. Posted code should include some background information about it and what areas you specifically would like help with.

Popular code excerpts may be moved to "Code Snippets" by the moderators.

Moderator: General Moderators

Post Reply
User avatar
nor0101
Forum Commoner
Posts: 53
Joined: Thu Jan 15, 2009 12:06 pm
Location: Wisconsin

μ-compiler

Post by nor0101 »

Last fall I got an assignment for class and decided to solve it using PHP. It translates from a simple made-up rectangle decomposition language to SVG. I'm sure many on these forums have experience with recursive descent parsing but for those who don't it might be instructive.

The problem description:
Write a program that reads a text file as input and creates an SVG file as output. The input file contains a decomposition of a rectangular area where the grammar is given as:

G = ({|,-,(,),:,0,1,2,3,4,5,6,7,8,9}, {<R>, <R1>, <R2>, <I>, <D>}, {see below}, <R>)

<R> ::= <R1> '|' <R> | <R1>
<R1> ::= <R2> '-' <R1> | <R2>
<R2> ::= <I> ':' <I>
<I> ::= <D><I> | <D>
<D> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

The vertical bar is a binary infix operator that represents the joining of two rectangles to form another. The right-most edge of the left operand is joined to the left-most edge of the right operand where those edges are required to be of the same length if the phrase is "valid". The dash symbol is a binary infix operator that denotes the joining of two rectangles such that the bottom edge of the left operand is joined to the top edge of the right operand. Of course, these edges must be identical in length for "validity". The colon is a binary infix operator that represents a rectangle such that the width is given on the left and the height on the right.

The program must read an element of the language given by the BNF grammar above and translate the expression to SVG. The program should accept both "valid" and "invalid" language elements. The color scheme of "valid" and "invalid" phrases must be different and automatically determined.

My Solution

svgTranslator_classes.php
Note to admins: BBCode for PHP syntax highlighting chokes on this.

Code: Select all

 
 
<?php
 
    /**
    *   Class to perform initial processing of the input file.
    */
    class RawInput {
 
        private $raw_expression;
 
        /**
        *   Given a path to the input file, extracts the raw expression
        *   from the filesystem resource and stores it in a private member
        *   variable of this class ($raw_expression).
        */
        public function __construct($input_file_path) {
            $input_handle = fopen($input_file_path, "r") or die("Error: Unable to open expression file '".$input_file_path."'.\n");
            if (filesize($input_file_path) > 0) { // checking for empty file
                if (!$this->raw_expression = trim(fread($input_handle, filesize($input_file_path)))) {
                    die("Error: Unable to read expression file.\n");
                }
                fclose($input_handle);
            }
            else {
                die ("Error: 0 byte expression file provided.\n");
            }
        }
 
        public function getExp() {
            return $this->raw_expression;
        }
    }
 
 
    /**
    *   Encapsulates routines to tokenize
    *   an input stream.
    */
    class Lexer {
        private $input_stream;
 
        public function __construct($i) {
            $this->input_stream = str_split($i);
        }
 
        public function nextToken() {
            return array_shift($this->input_stream);
        }
    }
 
 
    /**
    *   Encapsulates routines to build a parse
    *   tree, given an initialized Lexer.
    *
    *   @uses Rectangle
    *   @uses R1
    *   @uses R2
    *   @uses Integer
    *   @uses Digit
    *   @uses DimensionalOperator
    *   @uses VerticalAdjacencyOperator
    *   @uses HorizontalAdjacencyOperator
    */
    class Parser {
 
        private $lexer, $token;
    
        public function __construct($l) {
            $this->lexer = $l;
        }
 
        public function getNext() {
            return $this->token = $this->lexer->nextToken();
        }
 
        public function parse() {
            $this->getNext();
            $tree = $this->rectangle();
            if (is_string($this->token)) {
                die("Uexpected token error: '$this->token'\n");
            }
            return $tree;
        }
 
        private function rectangle() {
            $r1 = $this->r1();
            if ($this->token == "|") {
                $haO = $this->horizontalAdjacencyOperator();
                $this->getNext();
                $r = $this->rectangle();
                $rec_obj = new Rectangle(Array($r1, $haO, $r));
            }
            else {
                $rec_obj = new Rectangle(Array($r1));
            }
            return $rec_obj;
        }
 
        private function r1() {
            $r2 = $this->r2();
            if ($this->token == "-") {
                $vaO = $this->verticalAdjacencyOperator();
                $this->getNext();
                $r1 = $this->r1();
                $r1_obj = new R1(Array($r2, $vaO, $r1));
            }
            else {
                $r1_obj = new R1(Array($r2));
            }
            return $r1_obj;
        }
 
        private function r2() {
            $i1 = $this->integer();
            $dO = $this->dimensionalOperator();
            $this->getNext();
            $i2 = $this->integer();
 
            return new R2($i1, $dO, $i2);
        }
 
        private function integer() {
            $i = new Integer($this->digit());
            while ($this->isDigit($this->getNext())) {
                $i->appendDigit($this->digit());
            }
            return $i;
        }
 
        private function digit() {
            ($this->isDigit($this->token)) or die ("Parse Error:  Expecting <Digit>, found '$this->token'\n");
            return new Digit($this->token);
        }
 
        private function isDigit($c) {
            $isD;
            if (preg_match('{\d}', $c) && strlen($c) == 1) {
                $isD = true;
            }
            else {
                $isD = false;
            }
            return $isD;        
        }
 
        private function dimensionalOperator() {
            ($this->token == ":") or die ("Parse Error: Expecting <DimensionalOperator>, found '$this->token'\n");
            return new DimensionalOperator($this->token);
        }
 
        private function verticalAdjacencyOperator() {
            ($this->token == "-") or die("Parse Error: Expecting <VerticalAdjacencyOperator>, found '$this->token'\n");
            return new verticalAdjacencyOperator($this->token);
        }
 
        private function horizontalAdjacencyOperator() {
            ($this->token == "|") or die("Parse Error: Expecting <HorizontalAdjacencyOperator>, found '$this->token'\n");
            return new horizontalAdjacencyOperator($this->token);
        }
    }
 
 
    /**
    *   Is a  DimensionalOperator.
    */
    class DimensionalOperator {
 
        private $opSymbol;
 
        public function __construct($tok) {
            $this->opSymbol = $tok;
        }
    }
 
 
    /**
    *   Is a  HorizontalAdjacencyOperator.
    */
    class HorizontalAdjacencyOperator {
 
        private $opSymbol;
 
        public function __construct($tok) {
            $this->opSymbol = $tok;
        }
    }
 
 
    /**
    *   Is a  VerticalAdjacencyOperator.
    */
    class VerticalAdjacencyOperator {
 
        private $opSymbol;
 
        public function __construct($tok) {
            $this->opSymbol = $tok;
        }
    }
 
 
    /**
    *   Is a Rectangle, possibly including horizontal decomposition.
    */
    class Rectangle {
 
        public $r1_left, $op, $r_right;
 
        public $variant;
        const SIMPLE = 1;
        const COMPLEX = 2;
 
        public function __construct($list) {
            $member_count = count($list);
            if ($member_count == 3) {
                $this->variant = COMPLEX;
                $this->r1_left = $list[0];
                $this->op = $list[1];
                $this->r_right = $list[2];
            }
            else {
                $this->variant = SIMPLE;
                $this->r1_left = $list[0];
            }
        }
 
        public function isComplex() {
            if ($this->variant == COMPLEX)
                return true;
            else
                return false;
        }
 
        public function width() {
            if ($this->variant == SIMPLE) {
                $w_value = $this->r1_left->width();
            }
            else if ($this->variant == COMPLEX) {
                $r1_width = $this->r1_left->width();
                $r_width = $this->r_right->width();
                $w_value = $r1_width + $r_width;
            }
            return $w_value;
        }
 
        public function height() {
            if ($this->variant == SIMPLE) {
                $h_value = $this->r1_left->height();
            }
            else if ($this->variant == COMPLEX) {
                $r1_height = $this->r1_left->height();
                $r_height = $this->r_right->height();
                $h_value = ($r1_height > $r_height) ? $r1_height : $r_height;
            }
            return $h_value;
        }
    }
 
 
    /**
    *   Is a rectangle, possibly including vertical decomposition.
    */
    class R1 {
 
        public $r2_left, $op, $r1_right;
 
        private $variant;
        const SIMPLE = 1;
        const COMPLEX = 2;
 
        public function __construct($list) {
            $member_count = count($list);
            if ($member_count == 3) {
                $this->variant = COMPLEX;
                $this->r2_left = $list[0];
                $this->op = $list[1];
                $this->r1_right = $list[2];
            }
            else {
                $this->variant = SIMPLE;
                $this->r2_left = $list[0];
            }
        }
 
        public function isComplex() {
            if ($this->variant == COMPLEX)
                return true;
            else
                return false;
        }
 
        public function width() {
            if ($this->variant == SIMPLE) {
                $w_value = $this->r2_left->width();
            }
            else {
                $r2_width = $this->r2_left->width();
                $r1_width = $this->r1_right->width();
                $w_value = ($r2_width > $r1_width) ? $r2_width : $r1_width;
            }
            return $w_value;
        }
 
        public function height() {
            if ($this->variant == SIMPLE) {
                $h_value = $this->r2_left->height();
            }
            else {
                $r2_height = $this->r2_left->height();
                $r1_height = $this->r1_right->height();
                $h_value = $r2_height + $r1_height;
            }
            return $h_value;
        }
    }
 
 
    /**
    *   Is a basic Rectangle.
    */
    class R2 {
 
        private $width, $height, $dimensionalOperator;
 
        public function __construct($i1, $dO, $i2) {
            $this->width = $i1;
            $this->dimensionalOperator = $dO;
            $this->height = $i2;
        }
 
        public function width() {
            return $this->width->value();
        }
 
        public function height() {
            return $this->height->value();
        }
    }
 
 
    /**
    *   Is an Integer.
    */
    class Integer {
 
        private $digits;
 
        public function __construct($digit) {
            $this->digits[] = $digit;
        }
 
        public function appendDigit($digit) {
            $this->digits[] = $digit;
        }
 
        public function value() {
            $sum;
            foreach($this->digits as $digit) {
                $sum .= $digit->value();
            }
            return $sum;
        }
    }
 
 
    /**
    *   Is a Digit.
    */
    class Digit {
 
        private $d;
 
        public function __construct($tok) {
            $this->d = $tok;
        }
 
        public function value() {
            return $this->d;
        }
    }
 
 
    /**
    *   Evaluates an abstract syntax tree of the grammar,
    *   returning true or false for valid and invalid, respectively.
    */
    class Evaluator {
 
        private $tree;
 
        public function __construct($t) {
            $this->tree = $t;
        }
 
        public function evaluate() {
            return $this->validRectangle();
        }
 
        private function validRectangle() {
            // valid if and only if:
            //  every row (rectangle) in each column is the same width
            //  every total column height matches the total height
            $total_width = $this->tree->width();
            $total_height = $this->tree->height();
            return $this->validColHeights($this->tree, $total_height)
                        && $this->validRowWidths($this->tree);
        }
 
        private function validColHeights($rect, $total_height) {
            $OK = ($rect->r1_left->height() == $total_height);
            if ($rect->isComplex()) {
                $OK = ($OK && $this->validColHeights($rect->r_right, $total_height));
            }
            return $OK;
        }
 
        private function validRowWidths($rect) {
            $OK = $this->validRow($rect->r1_left, $rect->r1_left->width());
            if ($rect->isComplex()) {
                $OK = ($OK && $this->validRowWidths($rect->r_right));
            }
            return $OK;
        }
 
        private function validRow($r1, $width_to_match) {
            $OK = true;
            if ($r1->isComplex()) {
                $OK = $width_to_match == $r1->r2_left->width() 
                    && $this->validRow($r1->r1_right, $r1->r2_left->width());
            }
            return $OK;
        }
    }
 
 
    /**
    *   Translates an abstract syntax tree generated by a
    *   Parser into XML format.
    */
    class Translator {
 
        private $tree, $validity, $rec_vec, $xml_output;
 
        public function __construct($t, $v) {
            $this->tree = $t;
            $this->validity = $v;
        }
 
        public function translate() {
            $total_width = $this->tree->width();
            $total_height = $this->tree->height();
            $this->generate_recs($this->tree, 0, 0);
 
            $svg_output = "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?>";
            $svg_output .= "<svg\n";
            $svg_output .= "\txmlns:svg=\"http://www.w3.org/2000/svg\"\n";
            $svg_output .= "\txmlns=\"http://www.w3.org/2000/svg\"\n";
            $svg_output .= "\tversion=\"1.0\"\n";
            $svg_output .= "\twidth=\"".$total_width."\"\n";
            $svg_output .= "\theight=\"".$total_height."\">\n";
            $svg_output .= "\t<g>\n";
 
            foreach($this->rec_vec as $rec) {
                $svg_output .= $rec->toXML();
            }
            
            $svg_output .= "\t</g>\n";
            $svg_output .= "</svg>";
 
            return $svg_output;
        }
 
        private function generate_recs($source_obj, $x_pos, $y_pos) {
            if (is_a($source_obj, "R2")) {
                $this->make_rec($source_obj->width(), $source_obj->height(), $x_pos, $y_pos);
            }
            else if (is_a($source_obj, "R1")) {
                $this->generate_recs($source_obj->r2_left, $x_pos, $y_pos);
                if ($source_obj->isComplex()) {
                    $this->generate_recs($source_obj->r1_right, $x_pos, $y_pos+$source_obj->r2_left->height());
                }
            }
            else if (is_a($source_obj, "Rectangle")) {
                $this->generate_recs($source_obj->r1_left, $x_pos, $y_pos);
                if ($source_obj->isComplex()) {
                    $this->generate_recs($source_obj->r_right, $x_pos+$source_obj->r1_left->width(), $y_pos);
                }
            }
        }
 
        private function make_rec($w, $h, $x, $y) {
            $new_rec = new SVGRectangle($w, $h, $x, $y);
            if ($this->validity) {
                $new_rec->valid();
            }
            else {
                $new_rec->invalid();
            }
            $this->rec_vec[] = $new_rec;
        }
    }
 
 
    /**
    *   Represents an SVG Rectangle.
    */
    class SVGRectangle {
 
        private $attributes;
 
        // salmon fill with green border <!-- s:) --><img src=\"{SMILIES_PATH}/icon_smile.gif\" alt=\":)\" title=\"Smile\" /><!-- s:) -->
        private $valid_style = "fill:#FA8072; stroke:#00FF00; stroke-width:1;";
 
        // olive drab fill with deep pink border <!-- s:) --><img src=\"{SMILIES_PATH}/icon_smile.gif\" alt=\":)\" title=\"Smile\" /><!-- s:) -->
        private $invalid_style = "fill:#6B8E23; stroke:#FF1493; stroke-width:1;";
 
        private $width, $height, $x_pos, $y_pos, $isValid;
 
        public function __construct($w, $h, $x, $y) {
            $this->width = $w;
            $this->height = $h;
            $this->x_pos = $x;
            $this->y_pos = $y;
        }
 
        public function valid() {
            $this->isValid = true;
        }
 
        public function invalid() {
            $this->isValid = false;
        }
 
        public function toXML() {
            $rect_elem = "\t\t<rect\twidth=\"".$this->width."\"\n";
            $rect_elem .= "\t\t\theight=\"".$this->height."\"\n";
            $rect_elem .= "\t\t\tx=\"".$this->x_pos."\"\n";
            $rect_elem .= "\t\t\ty=\"".$this->y_pos."\"\n";
            $rect_elem .= ($this->isValid) ?
                                "\t\t\tstyle=\"".$this->valid_style."\"\n"
                            :   "\t\t\tstyle=\"".$this->invalid_style."\"\n";
            $rect_elem .= "\t\t/>\n";
            
            return $rect_elem;
        }
    }
    
    
    /**
    *   Encapsulates routine to output data to a file.
    *
    *   The file is opened for writing so if there is a file
    *   of the same name as $write_path, it is overwritten without warning.
    */
    class SVGWriter {
        
        public function __construct() {
        }
 
        public function writeSVG($content, $write_path) {
            $output_file_handle = fopen($write_path, "w")
                or die("Output Error: Unable to allocate output file.");
            if (!fwrite($output_file_handle, $content)) {
                die("Output Error: Unable to write to the output file.");
            }
            fclose($output_file_handle);
            return true;
        }
    }
?>
 
svgTranslator.php

Code: Select all

 
#! /usr/bin/php
<?php
 
    /**
    *   SVG Translator
    *
    *   Usage:
    *   
    *   ./svgTranslator <input_file> <target_file>
    *   
    *   @package svgTranslator
    *   @author Connor Doyle <connor@oneorangesoftware.com>
    *   @copyright Copyright (c) 2008, Connor Doyle
    *   @version 1.0
    */
 
    require_once("./svgTranslator_classes");
 
    array_shift($argv);
    if (count($argv) < 2) {
        exit();
    }
 
    main($argv[0], $argv[1]);
 
    /**
    *   Dictates abstract program behavior.
    */
    function main($_input, $_target) {
        echo("\nLexer: ");
        $raw_input = new RawInput($_input);
        $lexer = new Lexer($raw_input->getExp());
        echo("OK\n");
        echo("Parser: ");
        $parser = new Parser($lexer);
        $abstract_syntax_tree = $parser->parse();
        echo("OK\n");
        echo("Evaluator Result: ");
        $evaluator = new Evaluator($abstract_syntax_tree);
        if ($validity = $evaluator->evaluate()) {
            echo("Valid\n");
        }
        else {
            echo("Invalid\n");
        }
        echo("Translator: ");
        $translator = new Translator($abstract_syntax_tree, $validity);
        $svg_translation = $translator->translate();
        echo("Success\n");
        echo("Output: ");
        $svg_writer = new SVGWriter();
        $svg_writer->writeSVG($svg_translation, $_target);
        echo("Finished Writing\n\n");
    }
 
?>
 
That's all folks!
Thanks for looking; any comments are appreciated.
--
Connor Doyle
Last edited by nor0101 on Thu Jan 15, 2009 11:24 pm, edited 1 time in total.
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Re: μ-compiler

Post by Chris Corbyn »

I'm at work at the moment but I'm going to look at your code more closely later... I'm very interested in lexing and parsing. I've written a lexical analyzer (based on lex) in JavaScript. JavaScript lends itself to parsing and lexing routines which invoke user specified actions since the language makes callbacks and closures very streamlined.

I'm in the process of writing a LALR(1) (and supporting GLR routines) parser in JavaScript, using that lexical analyzer too. It's a learning experience that I plan to put to practical use when it's finished.

I'm very interested in reading through your code for a little inspiration. Have you played around with bison/yacc before?
User avatar
nor0101
Forum Commoner
Posts: 53
Joined: Thu Jan 15, 2009 12:06 pm
Location: Wisconsin

Re: μ-compiler

Post by nor0101 »

Right on, is that a project that you're doing just for fun?
I've read about things like YACC and Bison, but haven't actually used them.

If you're looking to actually run the code here is some sample input and output - for viewing the SVG output files I used Inkscape which is freely available.

Sample 1:

Code: Select all

10:10-10:30|30:40|30:35-30:5
Output (reduced screenshot from Inkscape):
Image

Sample 2:

Code: Select all

20:10-30:40|15:12|13:20-18:19
Output (reduced screenshot from Inkscape):
Image

Sample 3:

Code: Select all

20:10-22:5|25:15
Output (reduced screenshot from Inkscape):
Image
User avatar
Chris Corbyn
Breakbeat Nuttzer
Posts: 13098
Joined: Wed Mar 24, 2004 7:57 am
Location: Melbourne, Australia

Re: μ-compiler

Post by Chris Corbyn »

That's freakin' cool! :)

I will (try to) run the code yeah.

EDIT | And yes, I'm writing a parser just for the fun of it :) I'll do something cool with it when it written and perhaps will patch it into cappuccino since they have some bugs with their parsing that would be solved by a decent parser (and lexer).
Post Reply