IOA PRESENTATIONIOA2JAVA ToolInput/Output AutomataStructure of an IOAObjectivesAssumptionsSlide 7Java Compiler CompilerCompiler ProcedureIOA TokensIOA grammar to JavaCC grammarTranslation of Grammar Cont’dJava file which implements the ParserDifferences in GrammarsLeft Recursion RemovedThe FibonacciSkew IOASlide 17The FibonacciSkew IOAIOA States to Private DataInput Action to Public MethodSlide 21Internal and Ouput Actions to Public MethodsSlide 23IOA Input ParametersHelper MethodsIOA SchedulerRound Robin SchedulerFuture ResearchSlide 29ReferencesFlowCSE298 CSE300CSE.-IOA-1IOAIOAPRESENTATIONPRESENTATIONMay 01, 1999May 01, 1999CSE298 CSE300CSE.-IOA-2IOA2JAVA ToolIOA2JAVA ToolComputer Science & Engineering DepartmentThe University of Connecticut191 Auditorium Road, Box U-155Storrs, CT 06269-3155Joe BalthazarChristine KenneyJim ByrneAinsley NathanielCSE298 CSE300CSE.-IOA-3Input/Output AutomataInput/Output AutomataC(2,1)C(1,2)P2init(v2)decide(v2)P1init(v1)decide(v1)send(m(1,2))receive(m(1,2))send(m(2,1))receive(m(2,1))ChannelProcessCSE298 CSE300CSE.-IOA-4Structure of an IOAStructure of an IOAMain components of an I/O Automaton(A):Main components of an I/O Automaton(A):sig(A), a signaturestates(A), a set of statesstart statestrans(A), a state-transition relation that follows a precondition-effect styleinput actions - no preconditions and hence, are permanently enabledinternal and output actions - have preconditions and effectsoptional tasksCSE298 CSE300CSE.-IOA-5ObjectivesObjectivesCreate a tool to convert the general structure of an Create a tool to convert the general structure of an IOA to Java codeIOA to Java codeIOA can be used for algorithm correctness proofsRecognize only a subset of the languageAutomaton name, states and data typesInput, internal, and output actionsPreconditions and effectsParses majority of languageConvert a single IOA to a single Java classConvert a single IOA to a single Java classProduce necessary additional Java code to create a Produce necessary additional Java code to create a executable program with IOA functionalityexecutable program with IOA functionalityCode will run on one machineCSE298 CSE300CSE.-IOA-6AssumptionsAssumptionsAction names, parameters, and state variables are Action names, parameters, and state variables are uniqueuniqueDeal only basic data typesDeal only basic data typesbooleandoubleintPreconditions and effects written as Java CodePreconditions and effects written as Java CodeMay change state variables so long as same names are usedCode copied directly to Java classCSE298 CSE300CSE.-IOA-7AssumptionsAssumptionsInternal and output actions have no parametersInternal and output actions have no parametersParameters values selected by IOA code in preconditions based on stateA large enough subset of IOA is not yet implemented to do thisChanges to IOA code in parserChanges to IOA code in parserAll keywords have the first letter capitalized ie. Automaton, Transition, etc.Some symbols were changed to accommodate the keyboard ie. E - There exist.Java types were used instead of IOA types- this eliminated the need for a symbol table.Type checking done by the Java Compiler.CSE298 CSE300CSE.-IOA-8Java Compiler CompilerJava Compiler CompilerCompiler Tool for Java Language.The Java equivalent of Lex and YaccParses grammar to produce Java codeJavaCC uses an input file written in a standard BNF grammar. Example of simple BNF grammar<exp> :: = <simp exp> <rel op> <simp exp><rel op> :: = < | >= | <= | = | >CSE298 CSE300CSE.-IOA-9Compiler ProcedureCompiler ProcedureGet the tokens Get the tokens The first part of the JCC specification defines the tokens for the language.Parse the LanguageParse the LanguageThe second part defines the transitions that make up the language. Generate the code Generate the code The compiler output is generated by the insertion of Java code in the transitions.CSE298 CSE300CSE.-IOA-10IOA TokensIOA TokensIOA Token definitions.IOA Token definitions.< AUTOMATON: “Automaton” >< TRANSITION: “Transition” >< INPUT: “Input” >< OUTPUT: “Output” >Resulting Java code is too complicated to put here, Resulting Java code is too complicated to put here, looks like assembly language.looks like assembly language.CSE298 CSE300CSE.-IOA-11IOA grammar to JavaCC grammarIOA grammar to JavaCC grammarIOA grammar specification translates directly into IOA grammar specification translates directly into JCC grammar because of similarity in structures.JCC grammar because of similarity in structures.states ::= ‘states’ state,+ (‘so’ ‘that’ predicate)?void states() :{}{ <STATES> state()(“,” state())* (<SO> <THAT> predicate())?}CSE298 CSE300CSE.-IOA-12Translation of Grammar Cont’dTranslation of Grammar Cont’dJavaCC grammar with Java code inserted to create JavaCC grammar with Java code inserted to create the IOA compiler.the IOA compiler.states ::= ‘states’ state,+ (‘so’ ‘that’ predicate)?void states() :{}{ {String lTokStr;} <STATES> lTokStr = state() {pwOutput.println(lTokStr);}("," lTokStr = state() {pwOutput.println(lTokStr);})* ( <SO> <THAT> predicate())?}CSE298 CSE300CSE.-IOA-13Java file which implements the Parser Java file which implements the Parser The IOA compiler takes an automaton definition as input and produces an equivalent automaton, written in Java, as output.static final public void states() throws ParseException { String lTokStr; jj_consume_token(STATES); lTokStr = state(); System.out.println(lTokStr); label_12: while (true) { if (jj_2_38(2)) { ;CSE298 CSE300CSE.-IOA-14Differences in GrammarsDifferences in GrammarsJCC does not permit left recursion and hence two JCC does not permit left recursion and hence two transitions have to be modified.transitions have to be modified.For example, A C | AB is a transition with left-recursion. The equivalent transition A CB+ does not contain left recursion and can be used in a JavaCC grammar file.subterm ::= subterm (opSym subterm)+ | (quantifier | opSym)* opSym secondary | (quantifier | opSym)* quantifier primary | secondary opSym*CSE298 CSE300CSE.-IOA-15Left Recursion RemovedLeft Recursion
View Full Document
Unlocking...