akiezun / hampi Goto Github PK
View Code? Open in Web Editor NEWAutomatically exported from code.google.com/p/hampi
License: Other
Automatically exported from code.google.com/p/hampi
License: Other
#******************************************************************** # Copyright 2008 Adam Kiezun, Vijay Ganesh #******************************************************************** # AUTHORS: Adam Kiezun, Vijay Ganesh # # BEGIN DATE: October/November 2008 # # This file belongs to the Hampi string solver project (solver for # equations over regular expressions) # # LICENSE: Please view LICENSE file in the home dir of this Program #******************************************************************** Lead Author: Adam Kiezun Other Contributors: Vijay Ganesh Hampi is a solver for string constraints. The supported constraint language contains regular expressions and (fixed-size) context-free grammars. For example, you can find an 18-character string of balanced parentheses that contains substring ")(())(", you can write a Hampi constraint: var v:18; cfg S := "(" ")" | S S | "(" S ")"; reg Sbound := fix(S, 18); assert v in Sbound; assert v contains ")(())("; The first line declares the variable var of size 18 (there can be only one variable in a Hampi constraint). The second line declares a context-free grammar of balanced parentheses. S is the start nonterminal of the grammar. The third line creates a regular language Sbound that is the language of all 18-character strings of well-balanced parentheses (the fix operator takes a context-free grammar symbol, and a integer, and returns a regular-language symbol). The fourth line asserts that the value of v is a 18-character string of well-balanced parentheses (i.e., v is in the language L(Sbound)). The fifth line asserts that v contains the specific substring. STANDALONE MODE --------------- To test Hampi, put the above constraint in a file, e.g., a.hmp, and run hampi a.hmp. (or you can use a test input in the test directory as a template hampi tests/hampi/tests/testSolveCFG2.hmp) OUTPUT -------- You should see something like this: {VAR(v)=(()(())()()())(())} which means that Hampi found the value of v that satisfies the constraints. SERVER MODE ----------- Hampi can also be run in a server mode - this improves solving time for small constraints because you do not pay the cost of JVM startup. Run the server, e.g., hampi_server.sh 4444 Run a query, e.g., hampi_client.sh 4444 a.hmp or hampi_client.sh 4444 tests/hampi/tests/testSolveCFG2.hmp To shut the server down, call hampi_client.sh 4444 SHUTDOWN HOW TO MEASURE IMPROVEMENT IN HAMPI PERFORMANCE ----------------------------------------------- 1. First, translate cfg examples into Hampi examples: make translate-perftests 2. Create golden logs, before coding the performance improvement in Hampi: make create-perftest-gold 3. To compare the performance improvement against the golden logs: make run-perftests
Run this:
var v : 1;
cfg R := ['a' - 'b'];
assert v in R;
assert v in R;
Should return 'a' or 'b'. Instead, throws exception:
distributions in bounding: 0ms (3 times)
grammar bounding for R: 27ms (1 times)
java.lang.IllegalArgumentException: Cannot find nonterminal rangea_b in
grammar: R = rangea_b ;
at
hampi.grammars.apps.UnreachableNonterminalRemover.getReachableNonterminals(Unrea
chableNonterminalRemover.java:62)
at
hampi.grammars.apps.UnreachableNonterminalRemover.removeUnreachableNonterminals(
UnreachableNonterminalRemover.java:76)
at
hampi.grammars.apps.EpsilonProductionRemover.removeEpsilonProductions(EpsilonPro
ductionRemover.java:52)
at
hampi.grammars.apps.GrammarStringBounder.getBoundedRegexp(GrammarStringBounder.j
ava:51)
at
hampi.parser.HConstraintPreparer.prepareSizeFixRegexp(HConstraintPreparer.java:2
16)
at hampi.parser.HConstraintPreparer.prepareIn(HConstraintPreparer.java:132)
at hampi.parser.HConstraintPreparer.prepare(HConstraintPreparer.java:47)
at hampi.parser.HConstraintPreparer.prepare(HConstraintPreparer.java:34)
at hampi.Hampi.run(Hampi.java:283)
at hampi.Hampi.run(Hampi.java:259)
at hampi.Hampi.main(Hampi.java:238)
Original issue reported on code.google.com by [email protected]
on 2 Feb 2010 at 1:50
linux systems often come with openjdk installed instead of sun-java. Thus
the correct java path could be any one of
/usr/lib/jvm/java-6-openjdk/include/ or /usr/lib/jvm/java-6-sun/include.
The current configure scripts and makefiles assume the later resulting in
errors during make if you don't have the sun-java6-jdk package installed.
Original issue reported on code.google.com by [email protected]
on 4 Mar 2010 at 7:02
This should go through really fast because all sizes are fixed. Instead, it
blows up.
var string:75;
cfg q2 := \104 \116 \116 \112 \058 \047 \047 \057 \056;
cfg q3 := \046;
cfg q4 := \049 \051 \048;
cfg q5 := \046;
cfg q6 := \050 \052 \057;
cfg q7 := \046;
cfg q8 := \053 \055 \047 \098 \050 \101 \118 \111 \108 \117 \116 \105
\111 \110 \047 \097 \100 \109 \105 \110;
cfg q9 := \046;
cfg q10 := \112 \104 \112;
cfg q11 := \063;
cfg q12 := \099 \116 \114 \108 \061 \105 \116 \101 \109 \115 \038
\102 \105 \108 \116 \101 \114 \061 \114 \101 \115 \116 \111 \114 \101
\038 \098 \108 \111 \103 \061 \049;
cfg q1 := q2 q3 q4 q5 q6 q7 q8 q9 q10 q11 q12;
cfg flax0 := q1;
assert string in flax0;
Original issue reported on code.google.com by [email protected]
on 3 Feb 2010 at 6:19
var hampiStringVar : 9 ;
cfg _q2 := \049 ;
assert hampiStringVar not in _q2 ;
This should return any string of length 9, but it seems to return UNSAT
Original issue reported on code.google.com by [email protected]
on 14 Oct 2010 at 6:40
What steps will reproduce the problem?
1. ./hampi.sh ${ATTACHEDFILE}.hmp
What is the expected output? What do you see instead?
SAT
I see UNSAT
Original issue reported on code.google.com by [email protected]
on 24 Jan 2010 at 2:11
Attachments:
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.