Formal Grammars and Tools for Java

A grammar is formally defined as the ordered quad-tuple (N,Σ,P,S),
where:

• a finite set N of nonterminal symbols;
• a finite set Σ of terminal symbols that is disjoint from N;
• a finite set P of production rules;
• a distinguished symbol S from set N that is the start symbol.

Chomsky hierarchy of classes of formal grammars:

• type 0 - unrestricted grammars - include all formal grammars;
• type 1 - context-sensitive grammars - generate the context-sensitive languages;
• type 2 - context-free grammars - generate the context-free languages. Context free languages are the theoretical basis for the syntax of most programming languages;
• type 3 - regular grammars - generate the regular languages. Regular languages are commonly used to define search patterns and the lexical structure of programming languages.

In computer science, Extended Backus–Naur Form (EBNF) is a metasyntax notation used to express context-free grammars: that is, a formal way to describe computer programming languages and other formal languages. It is an extension of the basic Backus–Naur Form (BNF) metasyntax notation.

Compiler of computer programming languages consists of:

• parsing:
  • lexical analysis - produces tokens / lexemes;
  • syntactic analysis - produces parse tree or abstract syntax tree (AST);
• optimizer (optional);
• code generator.

Types of parsers:

• Top-down parsing
• Bottom-up parsing

Sample:

• grammar:
  S ::= Ax
  A ::= a
  A ::= b
  
  
• input sequence:
  ax
  
  
• Top-down parsing:
  S → Ax → ax
  
  
• Bottom-up parsing:
  ax → Ax → S
  

Top-down parsers:

• LL parser (Left-to-right, Leftmost derivation)

Bottom-up parsers:

• LR parser (Left-to-right, Rightmost derivation)
• SLR parser (Simple LR parser)
• LALR parser (lookahead LR parser)

In good review of Lex and Yacc for Java next tools were selected:

• ANTLR
• JavaCC
• SableCC

I think that ANTLR is one of the best tools because:

• it has a lot of features
• it has nice GUI - ANTLRWorks
• there are a lot of sample grammars
• there is a book - The Definitive ANTLR Reference: Building Domain-Specific Languages (DSL)
  

Screens of ANTLR GUI:

Post Archives to Your Blog

If you need to post an archive (source codes, binaries, etc) to your blog then check next advices:

• usually you are not able to post an archive to your blog
• the only thing you can do is to have a link to external location
• so you need to have a public web site to store archives
  
  • check GeoCities
    
• or you could share archives with some collaboration tools
  
  • check box.net

And you can add links like next:

• Paging Demo Binary and Source Code
• Paging AJAX Binary and Source Code

Java String Internals

General info about Java Strings could be found in API Doc.
Strings are immutable. So they can't be changed.

Strings store value internally in char array and have offset of the first character and characters count.

/** The value is used for character storage. */
private final char value[];
  
/** The offset is the first index of the storage that is used. */
private final int offset;
  
/** The count is the number of characters in the String. */
private final int count;

Example of initialization of empty String:

public String() {
    this.offset = 0;
    this.count = 0;
    this.value = new char[0];
}

Strings could share the same character array. Check constructor and substring code:

// Package private constructor which shares value array for speed.
String(int offset, int count, char value[]) {
    this.value = value;
    this.offset = offset;
    this.count = count;
}
  
public String substring(int beginIndex, int endIndex) {
    ...
    return ((beginIndex == 0) && (endIndex == count)) ? this :
        new String(offset + beginIndex, endIndex - beginIndex, value);
}

Sample:

String str = "Hello World";
String substr = str.substring(6, 11);

Low level system implementation of String class follows Flyweight Design Pattern

/**
 * Returns a canonical representation for the string object.
 *
 * @return  a string that has the same contents as this string, but is
 *          guaranteed to be from a pool of unique strings.
 */
public native String intern();

Sample:

String world = "World";
String str = "Hello World";
  
String substr1 = str.substring(6, 11);
String substr2 = str.substring(6, 11).intern();

Bigtable: Distributed Storage System

Here I've tried to collect information about Bigtable:

• Google Research Publication: BigTable
• Bigtable: A Distributed Storage System for Structured Data
• BigTable - Wikipedia, the free encyclopedia
• Google's BigTable
• Back to the Future for Data Storage
• The Python Datastore API
• Videos
  

AJAX Paging Internals

PagingCalc java class described in Paging Internals could be used in usual and AJAX web applications.

This AJAX Paging Demo web project is based on MVC model 1.
Specifications: Servlet 2.5. Libraries: json-lib-2.2.3.
It could be tested with Tomcat 6.0.x and it could be built with Maven 2.

Check the code below:

@Override
protected void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
    HttpSession session = request.getSession(true);
  
    PagingBean bean = getPagingBean(request);
    JSONObject jsonObject = JSONObject.fromObject(bean);
  
    response.setHeader("Content-type", "text/json");
    response.getOutputStream().print(jsonObject.toString());
}
  
private PagingBean getPagingBean(HttpServletRequest request){
    int currPage = getCurrPage(request);
  
    PagingCalc calc = new PagingCalc(PagingCalc.DEFAULT_ITEMS_COUNT,
            PagingCalc.DEFAULT_INDEXES_COUNT, currPage, dataIF.getDataRowsCount());
  
    PagingBean bean = new PagingBean();
    bean.setData(dataIF.getDataRows(calc.getStartItem(), calc.getEndItem()));
    bean.setActionUrl("json");
    bean.setCurrPageParam(PagingBean.DEFAULT_CURR_PAGE_PARAM);
    bean.setCalc(calc);
  
    return bean;
}

Servlet returns JSON like next:

{"actionUrl":"json",
    "calc":{"currPage":2,
                    "endItem":6,
                    "endPage":5,
                    "firstLink":1,
                    "firstLinkVisible":true,
                    "lastLink":8,
                    "lastLinkVisible":true,
                    "nextLink":6,
                    "nextLinkVisible":true,
                    "pagesCount":8,
                    "prevLink":0,
                    "prevLinkVisible":false,
                    "startItem":4,
                    "startPage":1,
                    "totalItems":23},
    "currPageParam":"currPage",
    "data":[{"description":"description 4","id":"4","name":"name 4"},
                    {"description":"description 5","id":"5","name":"name 5"},
                    {"description":"description 6","id":"6","name":"name 6"}]}

Download project binary and sources.

Exec with stdout / output redirected

You could have exec feature in your code / application. But if you need to exec with output redirected to a log file it will not work without pipes operations. But there is one trick - exec bash and provide your command with output redirected to a log as parameter to bash.

Syntax:

bash -c "command"

Example:

bash -c "ls -la"

Example with stdout redirected to a log:

bash -c "ls -la > log.txt"

In programming languages usually we have exec with several parameters:

• path - string
• args - array

java: Runtime.exec
php: pcntl_exec

So we need to prepare something like next:

• path = /bin/bash
• args:
  • arg1 = -c
  • arg2 = "command > log"     or     "command > log 2>&1"

Refer the PHP code below:

<?php
    /**
     * Execute an external program
     * @param string $path path to external program
     * @param array $args program arguments
     */
    function execute($path, $args) {
        return pcntl_exec($path, $args);
    }
  
    /**
     * Execute an external program with output redirected to log
     * @param string $path path to external program
     * @param array $args program arguments
     * @param string $log log file name
     */
    function execute_redir($path, $args, $log) {
        $path .= ' '.implode(' ', $args);
  
        $args = array();
        $args[] = '-c';
        $args[] = $path.' > '.$log.' 2>&1';
  
        $path = '/bin/bash';
        execute($path, $args);
    }
      
    // execute without output redirected
    //execute('/bin/ls', array('-la'));
      
    // execute with output redirected
    execute_redir('/bin/ls', array('-la'), 'log.txt');
?>

Paging Internals

If you have a task to create custom paging by yourself then this post could be helpful for you.

This Paging Demo web project is based on MVC model 1.
Specifications: Servlet 2.5 / JSP 2.1 / JSTL 1.2.
It could be tested with Tomcat 6.0.x and it could be built with Maven 2.

Download project binary and sources.

Paging design:

Class diagram:

Screens: This paging is based on a java class PagingCalc (paging calculator). It could do most calculations required by paging. The class follows Immutable Design Pattern. Check the code below:

package com.blogspot.illyakeeplearning.paging;
  
/**
 * Paging Calculator
 */
public class PagingCalc {
    public static final int DEFAULT_ITEMS_COUNT = 3;
    public static final int DEFAULT_INDEXES_COUNT = 5;
  
    private int maxItemsCount;
    private int maxIndexesCount;
  
    private int currPage;
    private int totalItems;
  
    private int pagesCount;
    private int startPage;
    private int endPage;
  
    /**
     * Constructor
     *
     * @param maxItemsCount   max items count on page
     * @param maxIndexesCount max page indexes count in a page block
     * @param currPage        current page index
     * @param totalItems      total items count
     */
    public PagingCalc(int maxItemsCount, int maxIndexesCount, int currPage, int totalItems) {
        this.maxItemsCount = maxItemsCount;
        this.maxIndexesCount = maxIndexesCount;
        this.currPage = currPage;
        this.totalItems = totalItems;
  
        initInternalVariables();
    }
  
    /**
     * Inits internal variables
     */
    private void initInternalVariables() {
        initPagesCount();
        initStartPage();
        initEndPage();
    }
  
    /**
     * Inits pages count
     */
    private void initPagesCount() {
        pagesCount = totalItems / maxItemsCount;
        pagesCount += (totalItems % maxItemsCount == 0) ? 0 : 1;
    }
  
    /**
     * Inits start page
     */
    private void initStartPage() {
        startPage = (currPage + maxIndexesCount - 1) / maxIndexesCount;
        startPage = (startPage - 1) * maxIndexesCount + 1;
    }
  
    /**
     * Inits end page
     */
    public void initEndPage() {
        endPage = startPage + maxIndexesCount - 1;
        endPage = (endPage > pagesCount) ? pagesCount : endPage;
    }
  
    /**
     * Gets current page index. 1-based value
     *
     * @return current page index. 1-based value
     */
    public int getCurrPage() {
        return currPage;
    }
  
    /**
     * Returns total items count
     *
     * @return total items count
     */
    public int getTotalItems() {
        return totalItems;
    }
  
    /**
     * Gets start item index on page
     *
     * @return start item index on page
     */
    public int getStartItem() {
        int startItem = (currPage - 1) * maxItemsCount + 1;
        return startItem;
    }
  
    /**
     * Gets end item index on page
     *
     * @return end item index on page
     */
    public int getEndItem() {
        int endItem = currPage * maxItemsCount;
        endItem = (endItem > totalItems) ? totalItems : endItem;
        return endItem;
    }
  
    /**
     * Gets pages count
     *
     * @return pages count
     */
    public int getPagesCount() {
        return pagesCount;
    }
  
    /**
     * Gets start page
     *
     * @return start page
     */
    public int getStartPage() {
        return startPage;
    }
  
    /**
     * Gets end page
     *
     * @return end page
     */
    public int getEndPage() {
        return endPage;
    }
  
    /**
     * Is Prev Link Visible
     *
     * @return true, if Prev Link Visible
     */
    public boolean isPrevLinkVisible() {
        return (pagesCount > maxIndexesCount) && (startPage > 1);
    }
  
    /**
     * Gets Prev Link
     *
     * @return prev link
     */
    public int getPrevLink() {
        return startPage - 1;
    }
  
    /**
     * Is Next Link Visible
     *
     * @return true, if Next Link Visible
     */
    public boolean isNextLinkVisible() {
        return (pagesCount > maxIndexesCount) && (endPage < pagesCount);
    }
  
    /**
     * Gets Next Link
     *
     * @return next link
     */
    public int getNextLink() {
        return endPage + 1;
    }
  
    /**
     * Is First Link Visible
     *
     * @return true, if First Link Visible
     */
    public boolean isFirstLinkVisible() {
        return currPage != 1;
    }
  
    /**
     * Gets First Link
     *
     * @return first link
     */
    public int getFirstLink() {
        return 1;
    }
  
    /**
     * Is Last Link Visible
     *
     * @return true, if Last Link Visible
     */
    public boolean isLastLinkVisible() {
        return (currPage != pagesCount);
    }
  
    /**
     * Gets Last Link
     *
     * @return last link
     */
    public int getLastLink() {
        return pagesCount;
    }
}

PagingCalc could be initialized...

PagingCalc calc = new PagingCalc(maxItemsCount, maxIndexesCount, currPage, totalItems);

...and be used

calc.getStartPage();
calc.getEndPage();

Download project binary and sources.

Raise Exception / Error in MySQL 5.0

There is no standard way to raise exception or error in MySQL.
But there is a trick:

• call to a not existing Stored Procedure raises MySQL exception
  
• so call to not existing Stored Procedure using "error message" as "procedure name" forces MySQL to raise exception that looks like "error message"

So to have Raise Exception feature we need next stored procedures / functions:

• procedure to execute dynamic SQL statements
• function to format text
• and main procedure to raise error / exception

See the code below:

DELIMITER $$
  
  
-- PROCEDURE pExecuteImmediate
--   executes dynamic SQL statement
-- Params:
--   tSQLStmt - SQL statement to be executed
DROP PROCEDURE IF EXISTS `pExecuteImmediate` $$
CREATE PROCEDURE `pExecuteImmediate`(IN tSQLStmt TEXT)
BEGIN
  SET @executeImmediateSQL = tSQLStmt;
  PREPARE executeImmediateSTML FROM @executeImmediateSQL;
  EXECUTE executeImmediateSTML;
  DEALLOCATE PREPARE executeImmediateSTML;
END $$
  
  
-- FUNCTION fFormat
--   replaces '%s' in a string with some value
-- Params:
--   sFormat - string to be formatted
--   sPar1 - value used in replacement
-- Returns:
--   formatted string
DROP FUNCTION IF EXISTS `fFormat` $$
CREATE FUNCTION  fFormat(sFormat TEXT, sPar1 TEXT)
  RETURNS TEXT
BEGIN
  RETURN REPLACE(sFormat, '%s', sPar1);
END $$
  
  
-- PROCEDURE pRaiseError
--   raises error
-- Params:
--   sError - error message
DROP PROCEDURE IF EXISTS `pRaiseError` $$
CREATE PROCEDURE `pRaiseError`(sError VARCHAR(255))
BEGIN
  -- trick
  --   calling of not existing procedure with name that equals error message
  --   will force MySQL exception that looks like error message
  CALL pExecuteImmediate(fFormat('CALL `error: %s, solution`', sError));
END  $$
  
  
DELIMITER ;

After execution of SQL:

CALL pRaiseError("this is a sample error message")

MySQL will raise exception:

PROCEDURE error: this is a sample error message, solution does not exist

Additional information could be found here: Stored Procedures in MySQL 5.x

Disable Triggers in MySQL 5.0

Information about triggers in MySQL 5.0 you can find here:

• MySQL 5.0 New Features: Triggers
• MySQL 5.0 Reference Manual :: 18 Stored Programs and Views :: 18.3 Using Triggers
  

It is not possible to temporary disable triggers in MySQL 5.0.
But there are several tricks:

1. drop/create triggers
   • drop triggers
     
   • do anything you need (import, update, etc)
     
   • create triggers


2. Use global variable
   
   • each trigger should check this variable in its code beginning
   • set global variable to 1 (or other NOT NULL value) to disable triggers
     
   • do anything you need (import, update, etc)
   • set global variable to NULL to enable triggers
   • global variable IS NULL by default
     
   
   
   • see sample below:

schema:

script:

CREATE TABLE  `users` (
  `id` int(10) unsigned NOT NULL auto_increment,
  `name` varchar(45) NOT NULL,
  PRIMARY KEY  (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
  
CREATE TABLE  `properties` (
  `userid` int(10) unsigned NOT NULL,
  `updated` varchar(45) NOT NULL,
  PRIMARY KEY  (`userid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;


trigger:

DROP TRIGGER IF EXISTS tUsersInsert;
  
DELIMITER $$
CREATE TRIGGER tUsersInsert AFTER INSERT ON users
FOR EACH ROW BEGIN
  IF (@DISABLE_TRIGGERS IS NULL) then
    # main trigger part
    INSERT INTO properties VALUES(NEW.id, NEW.name);
  END IF;
END; $$
DELIMITER ;


trigger is enabled during insert:

INSERT INTO users(name) VALUES('aaa');


disable trigger during insert:

BEGIN;
SET @DISABLE_TRIGGERS=1;
INSERT INTO users(name) VALUES('bbb');
SET @DISABLE_TRIGGERS=NULL;
COMMIT;


result:

Ant tips

1. JWSDP integration
   

   <path id="jaxrpc.libs">
     <fileset dir="${lib.dir}/jwsdp-1.5/jaxrpc">
       <include name="*.jar" />
     </fileset>
   </path>
     
   <path id="saaj.libs">
     <fileset dir="${lib.dir}/jwsdp-1.5/saaj">
       <include name="*.jar" />
     </fileset>
   </path>
     
   <path id="jwsdp-shared.libs">
     <fileset dir="${lib.dir}/jwsdp-1.5/jwsdp-shared">
       <include name="*.jar" />
     </fileset>
   </path>
     
   <path id="tools.jar">
     <pathelement location="${env.JAVA_HOME}/lib/tools.jar" />
   </path>
     
   <taskdef name="wscompile" classname="com.sun.xml.rpc.tools.ant.Wscompile">
     <classpath>
       <path refid="jaxrpc.libs" />
     </classpath>
   </taskdef>
     
   <target name="generate-wsclient" depends="create-target-dirs">
     <wscompile keep="true" fork="true" client="true" features="noencodedtypes" base="${classes.dir}" sourceBase="${gensrc.dir}" mapping="${classes.dir}/ProvisionService-mapping.xml" nonClassDir="${config.dir}" xPrintStackTrace="true" verbose="true" config="${config.dir}/ProvisionService-client-config.xml">
       <classpath>
         <path refid="jaxrpc.libs" />
         <path refid="jwsdp-shared.libs" />
         <path refid="tools.jar" />
       </classpath>
     </wscompile>
   </target>
     
   <target name="generate-ws-test" depends="create-target-dirs">
     <wscompile keep="true" fork="true" server="true" features="noencodedtypes" base="${test-classes.dir}" sourceBase="${test-gensrc.dir}" mapping="${test-classes.dir}/ProvisionService-mapping.xml" nonClassDir="${config.dir}" xPrintStackTrace="true" verbose="true" config="${config.dir}/ProvisionService-config.xml">
       <classpath>
         <path refid="jaxrpc.libs" />
         <path refid="saaj.libs" />
         <path refid="jwsdp-shared.libs" />
         <path refid="tools.jar" />
       </classpath>
     </wscompile>
   </target>



2. JUnit integration
   

   <path id="junit.libs">
     <fileset dir="${lib.dir}/junit-3.8.1">
       <include name="**/*.jar" />
     </fileset>
   </path>
     
   <junit printsummary="yes" haltonfailure="no" fork="true">
     <classpath>
       <path refid="junit.libs" />
     
       <pathelement path="${classes.dir}" />
       <pathelement path="${test-classes.dir}" />
       <pathelement path="${test-resources.dir}" />
     </classpath>
     
     <formatter type="plain" />
     
     <batchtest todir="${test-results.dir}">
       <fileset dir="${test-classes.dir}">
         <include name="**/ws/client/test/unit/**" />
       </fileset>
     </batchtest>
   </junit>



3. JMeter integration
   

   <path id="jmeter-ant.libs">
     <fileset dir="${lib.dir}/jakarta-jmeter-2.2/extras">
       <include name="ant-jmeter.jar" />
     </fileset>
   </path>
     
   <taskdef name="jmeter" classname="org.programmerplanet.ant.taskdefs.jmeter.JMeterTask">
     <classpath>
       <path refid="jmeter-ant.libs" />
     </classpath>
   </taskdef>
     
   <jmeter jmeterhome="${lib.dir}/jakarta-jmeter-2.2" testplan="${test-results.dir}/WebService.jmx" resultlog="${test-results.dir}/WebService.jtl" />
   <xslt in="${test-results.dir}/WebService.jtl" out="${test-results.dir}/WebService.html" style="${lib.dir}/jakarta-jmeter-2.2/extras/jmeter-results-report_21.xsl" />



4. AntContrib integration
   

   <taskdef resource="net/sf/antcontrib/antlib.xml">
       <classpath>
       <pathelement location="${libs.dir}/ant/ant-contrib-1.0b3.jar"/>
       </classpath>
   </taskdef>
     
   <target name="dist-sql">
     <!-- iterate over each .sql file found within database folder
           and call concatSQLFile target for them: -->
     <foreach target="concatSQLFile" param="targetFile">
       <path>
         <fileset dir="database">
           <include name="*.sql"/>
         </fileset>
       </path>
     </foreach>
   </target>
     
   <!-- is called by target dist-sql
       param: targetFile - the sql file to append -->
   <target name="concatSQLFile">
     <basename property="targetFileShort" file="${targetFile}"/>
     <echo message="${targetFileShort}"/>
     
     <concat destfile="${dist.dir}/${sql.name}" append="true">
       <header>-- ${targetFileShort}${line.separator}</header>
       <fileset file="${targetFile}"/>
       <footer>-- ${line.separator}</footer>
     </concat>
   </target>



5. SSH integration
   

   <sshexec host="${host}" username="${user}" password="${password}" command="rm -rf ${path}/${subfolder}; mkdir -p ${path}/${subfolder}"/>
     
   <scp todir="${user}:${password}@${host}:${path}/${subfolder}">
     <fileset dir="${dist.dir}">
       <include name="${release.archive}"/>
       <include name="${docs.archive}"/>
     </fileset>
   </scp>